Coloring grids
Volume 228 / 2015
Abstract
A structure where each E_i is an equivalence relation on A is called an n-grid if any two equivalence classes coming from distinct E_i's intersect in a finite set. A function \chi : A \to n is an acceptable coloring if for all i \in n, the \chi ^{-1}(i) intersects each E_i-equivalence class in a finite set. If B is a set, then the n-cube B^n may be seen as an n-grid, where the equivalence classes of E_i are the lines parallel to the ith coordinate axis. We use elementary submodels of the universe to characterize those n-grids which admit an acceptable coloring. As an application we show that if an n-grid \mathcal {A} does not admit an acceptable coloring, then every finite n-cube is embeddable in \mathcal {A}.