The Elser nuclei sum revisited
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 s...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2021-06-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/7012/pdf |
| _version_ | 1797270040304680960 |
|---|---|
| author | Darij Grinberg |
| author_facet | Darij Grinberg |
| author_sort | Darij Grinberg |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:57:57Z |
| format | Article |
| id | doaj.art-dd83933ae7ad4d8fa1ab339ed05d5010 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:57Z |
| publishDate | 2021-06-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-dd83933ae7ad4d8fa1ab339ed05d50102024-03-07T15:44:09ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502021-06-01vol. 23 no. 1Combinatorics10.46298/dmtcs.70127012The Elser nuclei sum revisitedDarij GrinbergFix 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.https://dmtcs.episciences.org/7012/pdfmathematics - combinatorics05c30, 18g85, 57q70 |
| spellingShingle | Darij Grinberg The Elser nuclei sum revisited Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics 05c30, 18g85, 57q70 |
| title | The Elser nuclei sum revisited |
| title_full | The Elser nuclei sum revisited |
| title_fullStr | The Elser nuclei sum revisited |
| title_full_unstemmed | The Elser nuclei sum revisited |
| title_short | The Elser nuclei sum revisited |
| title_sort | elser nuclei sum revisited |
| topic | mathematics - combinatorics 05c30, 18g85, 57q70 |
| url | https://dmtcs.episciences.org/7012/pdf |
| work_keys_str_mv | AT darijgrinberg theelsernucleisumrevisited AT darijgrinberg elsernucleisumrevisited |