Coloring grids

Ramiro de la Vega

Fundamenta Mathematicae, Tome 228 (2015), p. 283-289 / Harvested from The Polish Digital Mathematics Library

Résumé

A structure $ = (A;E_{i})_{i∈n}$ 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 χ: A → n is an acceptable coloring if for all i ∈ n, the $χ^{-1}(i)$ intersects each $E_{i}$-equivalence class in a finite set. If B is a set, then the n-cube Bⁿ 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 does not admit an acceptable coloring, then every finite n-cube is embeddable in .

Détail

Publié le : 2015-01-01

Zbl 1319.03052

EUDML-ID : urn:eudml:doc:286401