Threshold-range conjecture for graph sequences

About 22 years old · traced to

Let t1t_1 and t2t_2 be functions such that t1∈Ω(n1/2)t_1\in\Omega(n^{1/2}), t2∈O(n)t_2\in O(n), and t1≪t2t_1\ll t_2. Threshold-range conjecture. There is a graph sequence G={G1,…,Gn,…}{\cal G}=\{G_1,\ldots,G_n,\ldots\} such that

th(G)∈Ω(t1)∩O(t2).th({\cal G})\in\Omega(t_1)\cap O(t_2).

Moreover, there is such a sequence in which each GnG_n is a tree. This conjecture asks whether threshold functions for graph sequences can realize a broad range between the known lower and upper scales; the supplied status evidence says the implication is false.

References

Primary source

Glenn Hurlbert, “A Survey of Graph Pebbling”, arXiv:math/0406024 (2004).

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.