An abstraction of Whitney's broken circuit theorem

zbMATH Open1302.05086arXiv1404.5480MaRDI QIDQ470960FDOQ470960

Authors: Klaus Dohmen, Martin Trinks 

Publication date: 13 November 2014

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

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).

Full work available at URL: https://arxiv.org/abs/1404.5480

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

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

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)

Cites Work

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

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
• A broken cycle theorem for the restrained chromatic function
• Recursion relations for chromatic coefficients for graphs and hypergraphs

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)