The Elser nuclei sum revisited

Abstract

Fix a finite undirected graph $\Gamma$ and a vertex $v$ of $\Gamma$. Let $E$ be the set of edges of $\Gamma$. We call a subset $F$ of $E$ pandemic if each edge of $\Gamma$ has at least one endpoint that can be connected to $v$ by an $F$-path (i.e., a path using edges from $F$ only). In 1984, Elser showed that the sum of ${\left(-1\right)}^{|F|}$ over all pandemic subsets $F$ of $E$ is $0$ if $E\ne \varnothing$. We give a simple proof of this result via a sign-reversing involution, and discuss variants, generalizations and refinements, revealing connections to abstract convexity (the notion of an antimatroid) and discrete Morse theory.

25 pages. Final version (published in DMTCS, 2021). More detailed variants of the text can be found in version 8 (arXiv:2009.11527v8)

References in corpus (3)

• Combinatorial Alexander Duality -- a Short and Elementary Proof
• A positivity phenomenon in Elser's Gaussian-cluster percolation model
• On the Activities and Partitions of the Vertex Subsets of Graphs