A positivity phenomenon in Elser's Gaussian-cluster percolation model

Abstract

Veit Elser proposed a random graph model for percolation in which physical dimension appears as a parameter. Studying this model combinatorially leads naturally to the consideration of numerical graph invariants which we call \emph{Elser numbers} ${\mathsf{els}}_k(G)$, where $G$ is a connected graph and $k$ a nonnegative integer. Elser had proven that ${\mathsf{els}}_1(G)=0$ for all $G$. By interpreting the Elser numbers as Euler characteristics of appropriate simplicial complexes called \emph{nucleus complexes}, we prove that for all graphs $G$, they are nonpositive when $k=0$ and nonnegative for $k\ge 2$. The last result confirms a conjecture of Elser. Furthermore, we give necessary and sufficient conditions, in terms of the 2-connected structure of~$G$, for the nonvanishing of the Elser numbers.

Corrected two errors in published version: (i) Conjecture 9.1 should read $k=|E(G)|-|V(G)|+1$ rather than $k=|E(G)|-|V(G)|-1$, and (ii) Theorems 1.2 and 7.5 should read "has no cut-vertex" rather than "is 2-connected" (so as to include $K_2$)