An abstraction of Whitney's broken circuit theorem (Q470960): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / review text | |||
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). | |||
Property / review text: 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). / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C31 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05A15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C30 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 06A07 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 11A25 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 52A01 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6369278 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
graph polynomial | |||
Property / zbMATH Keywords: graph polynomial / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
domination polynomial | |||
Property / zbMATH Keywords: domination polynomial / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
beta invariant | |||
Property / zbMATH Keywords: beta invariant / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
broken circuit | |||
Property / zbMATH Keywords: broken circuit / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Möbius function | |||
Property / zbMATH Keywords: Möbius function / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
lattice | |||
Property / zbMATH Keywords: lattice / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
MAX-MIN identity | |||
Property / zbMATH Keywords: MAX-MIN identity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
totient | |||
Property / zbMATH Keywords: totient / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Dirichlet inverse | |||
Property / zbMATH Keywords: Dirichlet inverse / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Riemann zeta function | |||
Property / zbMATH Keywords: Riemann zeta function / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
closure system | |||
Property / zbMATH Keywords: closure system / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
convex geometry | |||
Property / zbMATH Keywords: convex geometry / rank | |||
Normal rank | |||
Property / describes a project that uses | |||
Property / describes a project that uses: OEIS / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1404.5480 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4101884 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Mean value for the matching and dominating polynomial / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Graph Polynomial Arising from Community Structure (Extended Abstract) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3993087 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Graph Polynomial Approach to Primitivity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Möbius functions of lattices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A higher invariant for matroids / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3577833 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A broken-circuits-theorem for hypergraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An improvement of the inclusion-exclusion principle / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4449286 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Domination reliability / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5313291 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The theory of convex geometries / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On extremal hypergraphs for Hamiltonian cycles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4399900 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3922685 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Note on the subgraph component polynomial / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Abstract tubes, improved inclusion-exclusion identities and inequalities and importance sampling / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Principle of inclusion-exclusion on semilattices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4092698 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the foundations of combinatorial theory I. Theory of M�bius Functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Supersolvable lattices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5411628 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The enumeration of vertex induced subgraphs with respect to the number of components / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on a broken-cycle theorem for hypergraphs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 07:41, 9 July 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
0 references