2015/04/22 by Soltész, Daniel
#05C55 #05C78 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1504.05987
Feder and Subi conjectured that for any 2-coloring of the edges of the n-dimensional cube, we can find an antipodal pair of vertices connected by a path that changes color at most once. We discuss the case of random colorings, and we prove the conjecture for a wide class of colorings. Our method can be applied to a more general problem, where Qn can be replaced by any graph G, the notion of antipodality by a fixed automorphism ϕ∈ Aut(G). Thus for any 2-coloring of E(G) we are looking for a pair of vertices u,v such that u= ϕ(v) and there is a path between them with as few color changes as possible. We solve this problem for the toroidal grid G=C2a \square c2b with the automorphism that takes every vertex to its unique farthest pair. Our results point towards a more general conjecture which turns out to be supported by a previous theorem of Feder and Subi.