Asymptotic Normality of Some Graph Sequences

For a simple finite graph G denote by Open image in new windowG into k non-empty independent sets (that is, into classes that span no edges of G). If \(E_n\) is the graph on n vertices with no edges then Open image in new window Open image in new window Open image in new windowgraph Stirling number. Harper showed that the sequence of Stirling numbers of the second kind, and thus the graph Stirling sequence of \(E_n\), is asymptotically normal—essentially, as n grows, the histogram of Open image in new window\((G_n)_{n \ge 0}\) of graphs is there asymptotic normality of Open image in new windown, \(G_n\) is acyclic and has n vertices, then asymptotic normality occurs, and they gave a proof under the added condition that \(G_n\) has no more than \(o(\sqrt{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.