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

Let E⊆FqdE \subseteq \mathbb{F}_q^d and let R⊆Fq∖{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.

References

Primary source

Ben Lund and Chuandong Xu, “Embedding edge-colored graphs in expanders with roll-back”, arXiv:2501.14286 (2025).

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.