An Abstraction of Whitney's Broken Circuit Theorem
| Autor: | Klaus Dohmen, Martin Trinks |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
FOS: Computer and information sciences
Hypergraph Discrete Mathematics (cs.DM) Euler's totient function Chromatic polynomial Möbius function Matroid Theoretical Computer Science Combinatorics symbols.namesake FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Number Theory (math.NT) Characteristic polynomial Mathematics Mathematics::Combinatorics Mathematics - Number Theory Applied Mathematics 05A15 05C30 05C31 06A07 11A25 52A01 Riemann zeta function Computational Theory and Mathematics symbols Greatest common divisor Combinatorics (math.CO) Geometry and Topology Computer Science - Discrete Mathematics |
| Zdroj: | The Electronic Journal of Combinatorics. 21 |
| ISSN: | 1077-8926 |
| DOI: | 10.37236/4356 |
| Popis: | We establish a broad generalization of Whitney's broken circuit theorem on the chromatic polynomial of a graph to sums of type $\sum_{A\subseteq S} f(A)$ where $S$ is a finite set and $f$ is a mapping from the power set of $S$ into an abelian group. We give applications to the domination polynomial and the subgraph component polynomial of a graph, the chromatic polynomial of a hypergraph, the characteristic polynomial and Crapo's beta invariant of a matroid, and the principle of inclusion-exclusion. Thus, we discover several known and new results in a concise and unified way. As further applications of our main result, we derive a new generalization of the maximums-minimums identity and of a theorem due to Blass and Sagan on the M\"obius function of a finite lattice, which generalizes Rota's crosscut theorem. For the classical M\"obius function, both Euler's totient function and its Dirichlet inverse, and the reciprocal of the Riemann zeta function we obtain new expansions involving the greatest common divisor resp. least common multiple. We finally establish an even broader generalization of Whitney's broken circuit theorem in the context of convex geometries (antimatroids). Comment: 18 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|