Betti numbers and anti-lecture Hall compositions of random threshold graphs (Q2171873): Difference between revisions

Let \(M\) be a finitely generated module over a polynomial ring. It is of interest to calculate the graded Betti numbers of \(M\) (cohomological invariants associated with the module, see e.g. [\textit{D. Eisenbud}, Commutative algebra. With a view toward algebraic geometry. Berlin: Springer-Verlag (1995; Zbl 0819.13001)] for details). In [\textit{A. Engström} and \textit{M. T. Stamps}, Algebra Number Theory 7, No. 7, 1725--1742 (2013; Zbl 1300.13013)] it is shown that when \(M\) is a quotient of the polynomial ring by a so-called 2-linear ideal (2-linear ideals are a well-studied class of ideals) then there is a 1-1 correspondence between the possible Betti numbers and so-called threshold graphs. One of the equivalent definitions of threshold graphs \(G\) is those for which there is a function \(\omega: V(G)\rightarrow \mathbb{R}\) and a \(t\in \mathbb{R}\) such that \(uv\in E(G)\) if and only if \(\omega(u)+\omega(v)\geq t\). A useful equivalent characterisation of threshold graphs is that they can be obtained from a single vertex by repeatedly applying one of two operations: adding either a dominating vertex (one that is adjacent to all the vertices already in the graph) or an isolated vertex (one adjacent to no vertex already in the graph). In the paper under review, a model for random threshold graphs is used. Let \(T(n,\sigma)\) be a threshold graph with vertex set \(V=\{0, 1,2,\ldots, n\}\) and where \(\sigma\subseteq V\) is precisely the set of isolated vertices. Abusing notation, for a probability \(p\in [0,1]\) say \(T(n,p)\) is the threshold graph generated when \(\sigma\) is a random subset of \(V\), with every element included with probability \(p\) independently of all other elements of \(V\). Note that \(T(n,1/2)\) is the uniform distribution on threshold graphs on \(V\). By making more explicit the correspondence established by Engström and Stamps [loc. cit.], the authors can calculate the expected values of the Betti numbers associated to a random threshold graph \(T(n,p)\). Another set of objects in 1-1 correspondence with threshold graphs and Betti numbers are so-called anti-lecture hall compositions: again the authors make more explicit the correspondence between this class and the other two, and can thus find the anti-lecture hall composition associated to a random threshold graph \(T(n,p)\).