Meta-Heuristic Search and Square Erickson MatricesReportar como inadecuado

Meta-Heuristic Search and Square Erickson Matrices - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

* Corresponding author 1 LIL - Laboratoire Informatique du Littoral

Abstract : A Ramsey theory problem, that can be seen as a 2 dimensional extension of the Van der Waerden theorem, was posed by Martin J. Erickson in his book 1: -find the minimum n such that if the lattice points of n×n are two-colored, there exist four points of one color lying on the vertices of a square with sides parallel to the axes-. This was solved recently by Bacher and Eliahou in 2009 2, who showed that n = 15. In this paper we tackle a derived version of this problem, searching for the minimum n that forces the existence of a monochromatic 3 × 3 subgrid of n × n of the form {i, i + t, i + 2t} × {j, j +t, j +2t}. We use meta-heuristics on this open problem to find instances of 2-colorations without monochromatic 3 × 3 subgrid of the above form, setting a lower bound on n. In particular we found such a binary square grid of size 662, implying that n > 662.

Autor: Denis Robilliard - Amine Boumaza - Virginie Marion-Poty -



Documentos relacionados