Meta-heuristic search and square Erickson matrices
Lists
Only you see this
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} for any 2-coloring of [n] × [n]. 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.
BibTeX
@inproceedings{robilliard2010meta,
author = {Denis Robilliard and Amine M. Boumaza and Virginie Marion-Poty},
title = {{Meta-heuristic search and square Erickson matrices}},
booktitle = {IEEE CEC},
year = {2010},
url = {https://openreview.net/forum?id=1W0Br6gigO},
}Loading related content...