Perfect-path density conjecture in the hypercube
Perfect-path density conjecture in the hypercube
Let be the -dimensional hypercube, and let denote the vertex set of a path in with vertices whose endpoints are at Hamming distance . Such a configuration is called a perfect path. Let denote the maximum asymptotic density of vertex-induced copies of in subgraphs of large hypercubes.
Perfect-path density conjecture. For all ,
The case is proved in the paper, yielding . The source also notes that Baber's flag-algebra upper bound for is consistent with the conjectured value .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.