Janson's height and width conjectures for simply generated trees

About 5 years old · traced to

Let w=(wk,k≥0){\mathrm{w}}=(w_k,k \ge 0) be a weight sequence with w0>0w_0>0 and with wk>0w_k>0 for some k≥2k \ge 2. For n≥0n \ge 0 with Zn(w)>0Z_n({\mathrm{w}})>0, let Tn{\mathcal{T}}_n be a simply generated tree of size nn with weight sequence w{\mathrm{w}}. The parameters ν\nu and σ2\sigma^2 are defined from the generating function of the weight sequence as in the setup above. Janson's height and width conjectures. Along integers nn such that Zn(w)>0Z_n({\mathrm{w}})>0, as n→∞n\to\infty, the following hold: (1) if ν=1\nu=1 and σ2=∞\sigma^2=\infty, then

ht(Tn)n1/2→0\frac{{\mathrm{ht}}({\mathcal{T}}_n)}{n^{1/2}}\to 0

in probability; (2) if ν=1\nu=1 and σ2=∞\sigma^2=\infty, then

wid(Tn)n1/2→∞\frac{{\mathrm{wid}}({\mathcal{T}}_n)}{n^{1/2}}\to\infty

in probability; (3) if ν<1\nu<1, then

ht(Tn)n1/2→0\frac{{\mathrm{ht}}({\mathcal{T}}_n)}{n^{1/2}}\to 0

in probability; and (4) if ν<1\nu<1, then

wid(Tn)n1/2→∞\frac{{\mathrm{wid}}({\mathcal{T}}_n)}{n^{1/2}}\to\infty

in probability. These assertions concern simply generated trees in the infinite-variance and condensation regimes, predicting subdiffusive height and superdiffusive width. The paper addresses these conjectures, so their resolution should be checked against the results stated elsewhere in the source.

References

Primary source

Louigi Addario-Berry, Anna Brandenberger, Jad Hamdan and Céline Kerriou, “Universal height and width bounds for random trees”, arXiv:2105.03195 (2022).

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.