ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let r≥2r\geq 2, let X=Xr,n,pX=X_{r,n,p} be the number of copies of K1,rK_{1,r} in Gn,pG_{n,p}, and define

μ:=EX,σ2:=Var⁡X,φ(x):=(1+x)log⁡(1+x)−x.\mu:=\mathbb{E}X,\qquad \sigma^2:=\operatorname{Var}X,\qquad \varphi(x):=(1+x)\log(1+x)-x.

For ξ∈(0,1)\xi\in(0,1), let α=α(r)>0\alpha=\alpha(r)>0 be as in the upper-tail theorem, and for p∈(0,1−ξ]p\in(0,1-\xi] and ε\varepsilon satisfying Φ(ε)≥1\Phi(\varepsilon)\geq 1 and 1≤(1+ε)μ≤Xr,n,11\leq(1+\varepsilon)\mu\leq X_{r,n,1}, where

Φ(ε):=min⁡{φ(ε)μ2/σ2,  max⁡{(εμ)1/r,(εμ)/nr−1}log⁡(e/p)},\Phi(\varepsilon):=\min\left\{\varphi(\varepsilon)\mu^2/\sigma^2,\;\max\left\{(\varepsilon\mu)^{1/r},(\varepsilon\mu)/n^{r-1}\right\}\log(e/p)\right\},

Correct upper-tail behaviour. Theorem~ remains valid without the assumption ε≥n−α\varepsilon\geq n^{-\alpha}; equivalently,

−log⁡P(X≥(1+ε)μ)=Θr,ξ(Φ(ε)).-\log\mathbb{P}(X\geq(1+\varepsilon)\mu)=\Theta_{r,\xi}\bigl(\Phi(\varepsilon)\bigr).

The preceding theorem establishes the correct dependence of the stars' upper tail on ε\varepsilon up to constant factors in the exponent, and in particular resolves a problem of Janson and Ruciński for stars. Removing the lower-bound assumption on ε\varepsilon would extend that result to the remaining parameter range, but the source provides no resolution status for this assertion.

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.