Bounded gap between lower and upper threshold functions

About 2 years old · traced to

Let Gn,p,dG_{n,p,d} denote the class of dd-dependent random graph distributions on graphs with nn vertices and marginal edge probability pp. Let P\mathcal{P} be a monotone graph property, and let L(n,d)L(n,d) and U(n,d)U(n,d) be the lower and upper threshold functions from the existence-of-threshold-functions conjecture. Bounded threshold-gap conjecture. For every monotone graph property P\mathcal{P}, there exists a function f(d)f(d) depending only on dd such that

U(n,d)L(n,d)=O(f(d)).\frac{U(n,d)}{L(n,d)}=O(f(d)).

If true, the range between the two threshold functions would be controlled solely by the dependence parameter dd, rather than by nn. The source states this as an expected open phenomenon; the supplied parser status is unknown.

References

Primary source

Joshua Brody, Pat Devlin, Aditi Dudeja and Emmi Rivkin, “Evolution of locally dependent random graphs”, arXiv:2405.09489 (2024).

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.