Asymptotic Normality of Some Graph Sequences
Asymptotic Normality of Some Graph Sequences
复制标题
DOI：
10.1007/s00373-015-1596-4
复制
发表时间：
2013-08
影响因子：
0.7
通讯作者：
David J. Galvin
中科院分区：
文献类型：
--
作者：
David J. Galvin
对于一个简单的有限图G，表示将G的顶点集划分为k个非空独立集（即划分为不跨越G的边的类）的方法的数量。如果E_n E_n是n个顶点上的无边图，则E_n与第二类普通的斯特林数重合，因此我们称之为图的斯特林数。哈珀表明，序列的斯特林数的第二种，从而图斯特林序列E_n E n，是渐近正常的基本上，作为n的增长，直方图，适当规范，接近密度函数的标准正态分布。根据哈珀的结果，很自然地要问哪些图的序列（Gn）n ≥ 0（Gn）n≥ 0是渐近正态的. Thanh和Galvin证明了如果对每个n，G_nG_n是无圈的且有n个顶点，则G_nG_n是渐近正态的，并在G_nG_n有不超过o（n/\logn）o（n/logn）个分量的条件下给出了证明.在这里，我们解决了Thanh和Galvin的猜想在肯定的，并显着扩展它，取代“无环”在他们的猜想与“共色与准阈值图，并与可忽略的色数”。我们的证明结合了老工作的Navon和最近的工作Engbers，高尔文和Hilyard的正常秩序问题的Weyl代数，和工作的卡恩的匹配多项式的一个图。
For a simple finite graph G denote by the number of ways of partitioning the vertex set of G into k non-empty independent sets (that is, into classes that span no edges of G). If E_n E n is the graph on n vertices with no edges then coincides with, the ordinary Stirling number of the second kind, and so we refer to as a graph Stirling number. Harper showed that the sequence of Stirling numbers of the second kind, and thus the graph Stirling sequence of E_n E n, is asymptotically normal—essentially, as n grows, the histogram of, suitably normalized, approaches the density function of the standard normal distribution. In light of Harper’s result, it is natural to ask for which sequences (G_n) _ n ≥ 0 (G n) n≥ 0 of graphs is there asymptotic normality of. Thanh and Galvin conjectured that if for each n, G_n G n is acyclic and has n vertices, then asymptotic normality occurs, and they gave a proof under the added condition that G_n G n has no more than o (n/\log n) o (n/log n) components. Here we settle Thanh and Galvin’s conjecture in the affirmative, and significantly extend it, replacing “acyclic” in their conjecture with “co-chromatic with a quasi-threshold graph, and with negligible chromatic number”. Our proof combines old work of Navon and recent work of Engbers, Galvin and Hilyard on the normal order problem in the Weyl algebra, and work of Kahn on the matching polynomial of a graph.