论文标题
稀疏常规图中的子图计数的上尾
Upper Tails of Subgraph Counts in Sparse Regular Graphs
论文作者
论文摘要
稀疏的$ n $ vertex随机$ d $ - regular Graph $ g_n^d $，$ n^{1-c} <d = o（n）$包含固定图$ k $多的副本多？我们确定了该上尾的行为到指数中的对数间隙内。对于大多数图，$ k $（例如，对于任何平均度的$ k $大于$ 4 $），我们确定上尾最高为$ 1+o（1）$（1）$ factor。但是，我们还提供了一个图的示例，通过将边缘添加到$ k_ {2,4} $给出，其中上尾的概率与以前研究的行为的行为不同，在此稀疏状态下的稀疏随机常规和稀疏Erdős-rényi模型中。
What is the probability that a sparse $n$-vertex random $d$-regular graph $G_n^d$, $n^{1-c}<d=o(n)$ contains many more copies of a fixed graph $K$ than expected? We determine the behavior of this upper tail to within a logarithmic gap in the exponent. For most graphs $K$ (for instance, for any $K$ of average degree greater than $4$) we determine the upper tail up to a $1+o(1)$ factor in the exponent. However, we also provide an example of a graph, given by adding an edge to $K_{2,4}$, where the upper tail probability behaves differently from previously studied behavior in both the sparse random regular and sparse Erdős-Rényi models in this sparsity regime.
