Bounded gap between lower and upper threshold functions

From papers

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.

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

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

Solutions 0

No solutions have been posted yet.