Perfect-cycle density conjecture in the hypercube

Let QdQ_d be the dd-dimensional hypercube, and let C2dC_{2d} denote the vertex set of a 2d2d-cycle in QdQ_d whose dd opposite pairs of vertices are at Hamming distance dd. Such a configuration is called a perfect 2d2d-cycle. Let π(H,d)\pi(H,d) denote the maximum asymptotic density of vertex-induced copies of HH in subgraphs of large hypercubes.

Perfect-cycle density conjecture. For all d4d\geq 4,

π(C2d,d)=d!dd.\pi(C_{2d},d)=\frac{d!}{d^d}.

The cases d=3d=3 and d=4d=4 are addressed by the paper's results, with the displayed theorem giving π(C8,4)=3/32\pi(C_8,4)=3/32; the conjecture concerns the general range d4d\geq4.

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.