An abstraction of Whitney's broken circuit theorem (Q470960): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Changed an Item |
||
Property / describes a project that uses | |||
Property / describes a project that uses: OEIS / rank | |||
Normal rank |
Revision as of 00:24, 1 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An abstraction of Whitney's broken circuit theorem |
scientific article |
Statements
An abstraction of Whitney's broken circuit theorem (English)
0 references
13 November 2014
0 references
Summary: 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öbius function of a finite lattice, which generalizes Rota's crosscut theorem. For the classical Möbius 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).
0 references
graph polynomial
0 references
domination polynomial
0 references
beta invariant
0 references
broken circuit
0 references
Möbius function
0 references
lattice
0 references
MAX-MIN identity
0 references
totient
0 references
Dirichlet inverse
0 references
Riemann zeta function
0 references
closure system
0 references
convex geometry
0 references