ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.