Conjecture on the sharp threshold for embedding subdivisions in finite-field distance graphs

From papers

Let EFqdE \subseteq \mathbb{F}_q^d and let RFq{0}R \subseteq \mathbb{F}_q \setminus \{0\}. Let CC be the constant appearing in Theorem, whose conclusion guarantees the existence of the specified RR-distance subdivision of a complete graph in EE when the relevant size condition holds. Sharp-threshold conjecture. The conclusion of Theorem holds for

C=O(q(d+1)/2).C = O(q^{(d+1)/2}).

The preceding discussion says that the exponent (d+1)/2(d+1)/2 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 R|R| is believed removable. The conjecture asserts that the theorem's additive size threshold can be reduced to order q(d+1)/2q^{(d+1)/2}, 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

No solutions have been posted yet.