Bounded gap between lower and upper threshold functions
Let denote the class of -dependent random graph distributions on graphs with vertices and marginal edge probability . Let be a monotone graph property, and let and be the lower and upper threshold functions from the existence-of-threshold-functions conjecture. Bounded threshold-gap conjecture. For every monotone graph property , there exists a function depending only on such that
If true, the range between the two threshold functions would be controlled solely by the dependence parameter , rather than by . 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
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.