Janson's height and width conjectures for simply generated trees

Let w=(wk,k0){\mathrm{w}}=(w_k,k \ge 0) be a weight sequence with w0>0w_0>0 and with wk>0w_k>0 for some k2k \ge 2. For n0n \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 nn\to\infty, the following hold: (1) if ν=1\nu=1 and σ2=\sigma^2=\infty, then

ht(Tn)n1/20\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/20\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.

Sources & referencesView supporting material

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.