2013/08/31 by David Galvin, Galvin, David
Mathematics · #05C15 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1309.0124
openalex publication_date 2013/08/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a simple finite graph G denote by G \brace k 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 En is the graph on n vertices with no edges then En \brace k coincides with n \brace k, the ordinary Stirling number of the second kind, and so we refer to G \brace k as a graph Stirling number. Harper showed that the sequence of Stirling numbers of the second kind, and thus the graph Stirling sequence of En, is asymptotically normal --- essentially, as n grows, the histogram of (En \brace k)k ≥ 0, 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 (Gn)n ≥ 0 of graphs is there asymptotic normality of (Gn \brace k)k ≥ 0. Do and Galvin conjectured that if for each n, Gn is acylic and has n vertices, then asymptotic normality occurs, and they gave a proof under the added condition that Gn has no more than o(√(n/log n)) components. Here we settle Do 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 a Weyl algebra, and work of Kahn on the matching polynomial of a graph.