An abstraction of Whitney's broken circuit theorem
type: Item
instance of: scholarly article
title: An abstraction of Whitney's broken circuit theorem
zbMATH Open document ID: 1302.05086
author: Klaus Dohmen
author: Martin Trinks
published in: The Electronic Journal of Combinatorics
publication date: 2014-11-13T00:00:00Z
full work available at URL: https://arxiv.org/abs/1404.5480
full work available at URL: v21i4p32
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).
Mathematics Subject Classification ID: 05C31
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 11A25
Mathematics Subject Classification ID: 52A01
zbMATH DE Number: 6369278
zbMATH Keywords: graph polynomial
zbMATH Keywords: domination polynomial
zbMATH Keywords: beta invariant
zbMATH Keywords: broken circuit
zbMATH Keywords: Möbius function
zbMATH Keywords: lattice
zbMATH Keywords: MAX-MIN identity
zbMATH Keywords: totient
zbMATH Keywords: Dirichlet inverse
zbMATH Keywords: Riemann zeta function
zbMATH Keywords: closure system
zbMATH Keywords: convex geometry
describes a project that uses: OEIS
MaRDI profile type: Publication
arXiv ID: 1404.5480
cites work: Q4101884
cites work: Mean value for the matching and dominating polynomial
cites work: A Graph Polynomial Arising from Community Structure (Extended Abstract)
cites work: Q3993087
cites work: A Graph Polynomial Approach to Primitivity
cites work: Möbius functions of lattices
cites work: A higher invariant for matroids
cites work: Q3577833
cites work: A broken-circuits-theorem for hypergraphs
cites work: An improvement of the inclusion-exclusion principle
cites work: Q4449286
cites work: Domination reliability
cites work: Q5313291
cites work: The theory of convex geometries
cites work: On extremal hypergraphs for Hamiltonian cycles
cites work: Q4399900
cites work: Q3922685
cites work: Note on the subgraph component polynomial
cites work: Abstract tubes, improved inclusion-exclusion identities and inequalities and importance sampling
cites work: Principle of inclusion-exclusion on semilattices
cites work: Q4092698
cites work: On the foundations of combinatorial theory I. Theory of M�bius Functions
cites work: Supersolvable lattices
cites work: Q5411628
cites work: The enumeration of vertex induced subgraphs with respect to the number of components
cites work: A note on a broken-cycle theorem for hypergraphs
description: scientific article; zbMATH DE number 6369278