Long geodesics in subgraphs of the cube

2013/01/10 by Leader, Imre, Long, Eoin · 1 citation
#05C35 #05C38 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1301.2195

Abstract

A path in the hypercube Q_n is said to be a geodesic if no two of its edges are in the same direction. Let G be a subgraph of Q_n with average degree d. How long a geodesic must G contain? We show that G must contain a geodesic of length d. This result, which is best possible, strengthens a theorem of Feder and Subi. It is also related to the `antipodal colourings' conjecture of Norine.

Cited by

• From the Finite to the Infinite: Sharper Asymptotic Bounds on Norin's Conjecture via SAT

Related

• Long paths and cycles in subgraphs of the cube
• Geodesic trajectories on regular polyhedra
• The geodesic-transversal problem
• Enumerating all geodesics
• Geodesic paths in the finite dimensional unit sphere under sup norm