An abstraction of Whitney's broken circuit theorem

MaRDI QIDQ470960zbMATH OpenFDO

Authors Klaus Dohmen, Martin Trinks

Publication date 13 November 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.5480, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p32

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Riemann zeta functionlatticegraph polynomialdomination polynomialclosure systemconvex geometrybroken circuitbeta invariantDirichlet inverseMAX-MIN identitytotientMöbius function

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Graph polynomials (05C31) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Combinatorics of partially ordered sets (06A07) Arithmetic functions; related numbers; inversion formulas (11A25) Axiomatic and generalized convexity (52A01)

Abstract: We establish a broad generalization of Whitney's broken circuit theorem on the chromatic polynomial of a graph to sums of type $su{m}_{AsubseteqS}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).

Recommendations

• scientific article; zbMATH DE number 1137984
• Bijective proofs of two broken circuit theorems
• A note on a broken-cycle theorem for hypergraphs
• Broken circuits in matroids -- Dohmen's inductive proof
• A generalization of the Whitney rank generating function

Cites work

• scientific article; zbMATH DE number 3735816 (Why is no real title available?)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 3513051 (Why is no real title available?)
• scientific article; zbMATH DE number 3523640 (Why is no real title available?)
• scientific article; zbMATH DE number 1181276 (Why is no real title available?)
• scientific article; zbMATH DE number 2038883 (Why is no real title available?)
• scientific article; zbMATH DE number 2199828 (Why is no real title available?)
• A Graph Polynomial Approach to Primitivity
• A broken-circuits-theorem for hypergraphs
• A graph polynomial arising from community structure (extended abstract)
• A higher invariant for matroids
• A note on a broken-cycle theorem for hypergraphs
• Abstract tubes, improved inclusion-exclusion identities and inequalities and importance sampling
• An improvement of the inclusion-exclusion principle
• Domination reliability
• EAGLE-STARTING AID. Technical informatics. Logical funcions -- Boolean models
• Graph theory
• Mean value for the matching and dominating polynomial
• Möbius functions of lattices
• Note on the subgraph component polynomial
• On extremal hypergraphs for Hamiltonian cycles
• On the foundations of combinatorial theory I. Theory of M�bius Functions
• Principle of inclusion-exclusion on semilattices
• Supersolvable lattices
• The enumeration of vertex induced subgraphs with respect to the number of components
• The theory of convex geometries

Cited in

(9)

• A note on a broken-cycle theorem for hypergraphs
• The list-coloring function of signed graphs
• Broken circuits in matroids -- Dohmen's inductive proof
• The odd-valued chromatic polynomial of a signed graph
• Inclusion-exclusion by ordering-free cancellation
• Bijective proofs of two broken circuit theorems
• Flow polynomials of a signed graph
• Recursion relations for chromatic coefficients for graphs and hypergraphs
• A broken cycle theorem for the restrained chromatic function

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: An abstraction of Whitney's broken circuit theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q470960)