An abstraction of Whitney's broken circuit theorem (Q470960): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
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 / namelinks / 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
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    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