论文标题
在恒定平均度的随机图中，三角形数量的上尾巴行为
Upper tail behavior of the number of triangles in random graphs with constant average degree
论文作者
论文摘要
令$ n $为erdős-rényi图中的三角形数量$ \ mathcal {g}（n，p）$上的$ n $ vertices，带有边缘密度$ p = d/n，$ d> 0 $是固定常数。众所周知，$ n $弱收敛到泊松分布，平均$ {d^3}/{6} $作为$ n \ rightarrow \ infty $。我们解决了$ n的上尾问题，即我们研究了$ k $必须增长的速度，以便相应的poisson变量的尾巴不再近似$ \ {n \ ge k \} $的概率。证明尾巴表现出急剧的阶段过渡，我们本质上表明，上尾部仅在$ k^{1/3} \ log k <（\ frac {3} {\ sqrt {2}}}} {\ sqrt {2}}}} \ log k <（ （\ frac {3} {\ sqrt {2}}）^{2/3} \ log n $（super-Critical corgimime）。我们进一步证明了一个结构定理，表明亚临界的上尾巴行为是由几乎$ k $ tertex-disshingles三角形的出现决定的，而在超临界状态中，多余的三角形源自大约$（6K）^{1/3} $的大小的结构。在这种情况下，这解决了一个长期存在的上尾问题，回答了一个善良的问题，补充了一长串作品，跨越了数十年，最终导致（Harel，Moussat，samotij，'19，19）仅在政权中分析了该问题，该问题仅在该政权中$ p \ gg \ gg \ frac \ frac {1} {1} {n} {n} {n} n}。
Let $N$ be the number of triangles in an Erdős-Rényi graph $\mathcal{G}(n,p)$ on $n$ vertices with edge density $p=d/n,$ where $d>0$ is a fixed constant. It is well known that $N$ weakly converges to the Poisson distribution with mean ${d^3}/{6}$ as $n\rightarrow \infty$. We address the upper tail problem for $N,$ namely, we investigate how fast $k$ must grow, so that the probability of $\{N\ge k\}$ is not well approximated anymore by the tail of the corresponding Poisson variable. Proving that the tail exhibits a sharp phase transition, we essentially show that the upper tail is governed by Poisson behavior only when $k^{1/3} \log k< (\frac{3}{\sqrt{2}})^{2/3} \log n$ (sub-critical regime) as well as pin down the tail behavior when $k^{1/3} \log k> (\frac{3}{\sqrt{2}})^{2/3} \log n$ (super-critical regime). We further prove a structure theorem, showing that the sub-critical upper tail behavior is dictated by the appearance of almost $k$ vertex-disjoint triangles whereas in the supercritical regime, the excess triangles arise from a clique like structure of size approximately $(6k)^{1/3}$. This settles the long-standing upper-tail problem in this case, answering a question of Aldous, complementing a long sequence of works, spanning multiple decades, culminating in (Harel, Moussat, Samotij,'19) which analyzed the problem only in the regime $p\gg \frac{1}{n}.$ The proofs rely on several novel graph theoretical results which could have other applications.
