Thresholds for families of multisets, with an application to graph pebbling (Q1402065)

Let \(G_n\) be a graph with vertex set \([n]=\{1, 2,\dots, n\}\). A function \(D_n:[n]\to{\mathbb N}\) (where \({\mathbb N}\) contain 0) is a distribution of ``pebbles'' on the vertices. A pebbling step \([v,v^\prime]\) consists of replacing 2 pebbles from vertex \(v\) by 1 at an adjacent vertex \(v^\prime\); \(D_n\) is \(z\)-solvable if repeated pebbling steps result in a distribution where \(z\) has at least 1 pebble; \(D_n\) is \(G_n\)-solvable if it is \(z\)-solvable for all vertices \(z\). \({\mathcal D}_{n,t}\) is the probability space of all distributions \(D_n\) with \(t=\sum_{i\in[n]}D_n(i)\) pebbles, taken to be equally likely. For a graph sequence \({\mathcal G}=(G_1,\dots,G_n,\dots)\), \(P_{\mathcal G}(n,t)\) is the probability that an element of \({\mathcal D}_{n,t}\) chosen uniformly at random is \(G_n\)-solvable. A function \(t=t(n)\) is a threshold for \(\mathcal G\), written \(t\in \text{th}({\mathcal G})\), if, for every sequence \(\omega=\omega(n)\) tending to infinity (written \(\omega\gg 1\)), \(\lim_{n\to\infty}P_{\mathcal G}(n,t\omega)=1\) and \(\lim_{n\to\infty}P_{\mathcal G}(n,t/\omega)=0\). \({\mathcal M}_n\) is the poset of all multisets on \([n]\), ordered by inclusion; for \({\mathcal F}_n\subseteq{\mathcal M}_n\), \({\mathcal F}_n(t)\) is the family of all \(t\)-element multisets in \({\mathcal F}_n\); \({\mathcal F}_n\) is increasing if \(E\supseteq F\in{\mathcal F}_n\Rightarrow E\in{\mathcal F}_n\). For a sequence \({\mathcal F}=({\mathcal F}_1,\dots,{\mathcal F}_n,\dots)\) of increasing families \({\mathcal F}_n\in{\mathcal M}_n\), \(\text{th}({\mathcal F}_n)\) is the set of threshold functions \(t=t(n)\) -- functions such that, for any function \(\omega=\omega(n)\gg 1\), \(\lim_{n\to\infty}P_{t\omega}({\mathcal F}_n(t\omega))=1\) and \(\lim_{n\to\infty}P_{t/\omega}({\mathcal F}_n(t/\omega))=0\). The authors prove an analog of a result of \textit{B. Bollobás} and \textit{A. Thomason} [Combinatorica 7, 35-38 (1987; Zbl 0648.05048)]: Theorem 1.5: Let \(t(n)=\min\{r\mid P_r({\mathcal F}_n(r))\geq\frac 12\}\). Then \(t\in \text{th}({\mathcal F})\), which implies Theorem 1.3: For any graph sequence \({\mathcal G}\), let \(t(n)=\min\{r\mid P_{\mathcal G}(n,r)\geq\frac 12\}\). Then \(t\in \text{th}({\mathcal G})\). They also improve on bounds in [\textit{A. Czygrinow}, \textit{N. Eaton}, \textit{G. Hurlbert} and \textit{P. M. Kayll}, Discrete Math. 247, 93-105 (2002; Zbl 1002.05037)] in Theorem 1.4: For the sequence of paths \({\mathcal P}=(P_1,P_2,\dots,P_n,\dots)\) and any constant \(c<2^{-\frac 12}\), \(\text{th}({\mathcal P})\subseteq\Omega(n2^{c\sqrt{\log_2n}})\) and \(\text{th}({\mathcal P})\subseteq O(n2^{2\sqrt{\log_2n}})\). From the authors' abstract: In our proof of Theorem 1.5 the crucial tool will be \dots{} a result of \textit{G. F. Clements} and \textit{B. Lindström} [A generalization of a combinatorial theorem of Macaulay, J. Comb. Theory 7, 230-238 (1969; Zbl 0186.01704)] extending an earlier result of \textit{F. S. Macaulay} [Some properties of enumeration in the theory of modular systems, Proceedings Lect. Math. Ser. (2)26, 531-555 (1927; JFM 53.0104.01)] which is the multiset analog of the celebrated Kruskal-Katona theorem [\textit{P. Frankl}, A new short proof for the Kruskal-Katona theorem, Discrete Math. 48, 327-329 (1984; Zbl 0539.05006); \textit{G. Katona}, A theorem of finite sets, Theory of Graphs, Proc. Colloquium Tihany, Hungary 1966, 187-207 (1968; Zbl 0313.05003); \textit{J. B. Kruskal}, The number of simplices in a complex, Math. Optimization Tech. 251-278 (1963; Zbl 0116.35102)].