Perfect-path density conjecture in the hypercube

Let QdQ_d be the dd-dimensional hypercube, and let Pd+1P_{d+1} denote the vertex set of a path in QdQ_d with d+1d+1 vertices whose endpoints are at Hamming distance dd. Such a configuration is called a perfect path. Let π(H,d)\pi(H,d) denote the maximum asymptotic density of vertex-induced copies of HH in subgraphs of large hypercubes.

Perfect-path density conjecture. For all d3d\geq 3,

π(Pd+1,d)=d!(d+1)d1.\pi(P_{d+1},d)=\frac{d!}{(d+1)^{d-1}}.

The case d=3d=3 is proved in the paper, yielding π(P4,3)=3/8\pi(P_4,3)=3/8. The source also notes that Baber's flag-algebra upper bound for π(P5,4)\pi(P_5,4) is consistent with the conjectured value 24/12524/125.

Sources & referencesView supporting material

Primary source

John Goldwasser and Ryan Hansen, “Maximum density of vertex-induced perfect cycles and paths in the hypercube”, arXiv:2009.09037 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.