Large Monochromatic Components in Two-colored Grids

Let D n d denote the d-dimensional grid with diagonals, that is, the graph with vertex set { 1 , 2 , … , n } d 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 D n d there exists a monochromatic connected subgraph with at least n d − 1 − d 2 n d − 2 vertices. We also consider a d-dimensional triangulated grid; this is the graph of a triangulation of the solid cube [ 1 , n ] d that refines the subdivision of [ 1 , n ] d into the grid of unit cubes. Here every 2-coloring has a monochromatic connected subgraph with Ω ( n d − 1 / d ) vertices.