Maximal Monochromatic Geodesics in an Antipodal Coloring of Hypercube
Kavish Gandhi · 2015
A geodesic in the hypercube is the shortest possible path between two vertices. Leader and Long (2013) conjectured that, in every antipodal 2-coloring of the edges of the hypercube, there exists a monochromatic geodesic between antipodal vertices. For this and an equivalent conjecture, we prove the cases n = 2; 3; 4; 5. We also examine the maximum number of monochromatic geodesics of length k in an antipodal 2-coloring and nd it to be 2 n 1 (n k + 1) n 1 k 1 (k 1)!. In this case, we classify all colorings in which this maximum occurs. Furthermore, we explore the maximum number of antipodal geodesics in a subgraph of the hypercube with a xed proportion of edges, providing a conjectured optimal conguration as a lower bound, which, interestingly, contains a constant proportion of geodesics with respect to n. Finally, we present a series of smaller results that could be of use in nding an upper bound on the maximum number of antipodal geodesics in such a subgraph of the hypercube.