Large Monochromatic Components in Two-colored Grids

Let denote the d-dimensional grid with diagonals, that is, the graph with vertex set d{1,2,…,n} and with edges connecting every two vertices that differ by at most 1 in every coordinate. We prove that for an arbitrary 2-coloring of the vertices of there exists a monochromatic connected subgraph with at least nd−1−d2nd−2 vertices. We also consider a d-dimensional triangulated grid; this is the graph of a triangulation of the solid cube d[1,n] that refines the subdivision of d[1,n] into the grid of unit cubes. Here every 2-coloring has a monochromatic connected subgraph with vertices.