Conjecture on the sharp threshold for embedding subdivisions in finite-field distance graphs
Conjecture on the sharp threshold for embedding subdivisions in finite-field distance graphs
Let and let . Let be the constant appearing in Theorem, whose conclusion guarantees the existence of the specified -distance subdivision of a complete graph in when the relevant size condition holds. Sharp-threshold conjecture. The conclusion of Theorem holds for
The preceding discussion says that the exponent is the natural threshold for finding a single distance edge, and that the dependence on the number of distances is understood, while the dependence on is believed removable. The conjecture asserts that the theorem's additive size threshold can be reduced to order , independently of the current larger bound.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Ben Lund and Chuandong Xu, “Embedding edge-colored graphs in expanders with roll-back”, arXiv:2501.14286 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.