Darij Grinberg - The Elser nuclei sum revisited

dmtcs:7012 - Discrete Mathematics & Theoretical Computer Science, June 3, 2021, vol. 23 no. 1 - https://doi.org/10.46298/dmtcs.7012
The Elser nuclei sum revisitedArticle

Authors: Darij Grinberg

    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)^{\left| F\right|}$ over all pandemic subsets $F$ of $E$ is $0$ if $E\neq \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.


    Volume: vol. 23 no. 1
    Section: Combinatorics
    Published on: June 3, 2021
    Accepted on: May 4, 2021
    Submitted on: December 22, 2020
    Keywords: Mathematics - Combinatorics,05C30, 18G85, 57Q70

    Consultation statistics

    This page has been seen 516 times.
    This article's PDF has been downloaded 220 times.