Bounded gap between lower and upper threshold functions
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.
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
Sign in to submit a solution.
No solutions have been posted yet.