An Abstraction of Whitney's Broken Circuit Theorem. Dohmen, K. & Trinks, M. April, 2014. abstract bibtex We establish a broad generalization of Whitney's broken circuit theorem on the chromatic polynomial of a graph to sums of type $∑_A⊂eq 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).
@misc{ DT:2014:AWBCT,
author = {Klaus Dohmen and Martin Trinks},
title = {An Abstraction of {Whitney}'s Broken Circuit Theorem},
year = {2014},
month = {April},
pubstate = {Submitted for publication},
eprinttype = {arXiv},
eprint = {1404.5480},
eprintclass = {math-CO},
abstract = {We establish a broad generalization of Whitney's broken
circuit theorem on the chromatic polynomial of a graph to
sums of type $∑_{A⊂eq 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).},
keywords = {graph, hypergraph, matroid, chromatic polynomial,
domination polynomial, subgraph component polynomial,
characteristic polynomial, beta invariant, broken circuit,
broken neighbourhood, inclusion-exclusion, Möbius
function, lattice, maximum-minimums identity, totient,
Dirichlet inverse, Riemann zeta function, closure system,
convex geometry}
}
Downloads: 0
{"_id":{"_str":"536dfff04c6bdacb280007d2"},"__v":1,"authorIDs":[],"author_short":["Dohmen, K.","Trinks, M."],"bibbaseid":"dohmen-trinks-anabstractionofwhitneysbrokencircuittheorem-2014","bibdata":{"downloads":0,"keyword":["graph","hypergraph","matroid","chromatic polynomial","domination polynomial","subgraph component polynomial","characteristic polynomial","beta invariant","broken circuit","broken neighbourhood","inclusion-exclusion","Möbius function","lattice","maximum-minimums identity","totient","Dirichlet inverse","Riemann zeta function","closure system","convex geometry"],"bibbaseid":"dohmen-trinks-anabstractionofwhitneysbrokencircuittheorem-2014","urls":{},"role":"author","abstract":"We establish a broad generalization of Whitney's broken circuit theorem on the chromatic polynomial of a graph to sums of type $∑_A⊂eq 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).","author":["Dohmen, Klaus","Trinks, Martin"],"author_short":["Dohmen, K.","Trinks, M."],"bibtex":"@misc{ DT:2014:AWBCT,\n author = {Klaus Dohmen and Martin Trinks},\n title = {An Abstraction of {Whitney}'s Broken Circuit Theorem},\n year = {2014},\n month = {April},\n pubstate = {Submitted for publication},\n eprinttype = {arXiv},\n eprint = {1404.5480},\n eprintclass = {math-CO},\n abstract = {We establish a broad generalization of Whitney's broken\n circuit theorem on the chromatic polynomial of a graph to\n sums of type $∑_{A⊂eq S} f(A)$ where $S$ is a\n finite set and $f$ is a mapping from the power set of $S$\n into an abelian group. We give applications to the\n domination polynomial and the subgraph component polynomial\n of a graph, the chromatic polynomial of a hypergraph, the\n characteristic polynomial and Crapo's beta invariant of a\n matroid, and the principle of inclusion-exclusion. Thus, we\n discover several known and new results in a concise and\n unified way. As further applications of our main result, we\n derive a new generalization of the maximums-minimums\n identity and of a theorem due to Blass and Sagan on the\n Möbius function of a finite lattice, which generalizes\n Rota's crosscut theorem. For the classical Möbius\n function, both Euler's totient function and its Dirichlet\n inverse, and the reciprocal of the Riemann zeta function we\n obtain new expansions involving the greatest common divisor\n resp. least common multiple. We finally establish an even\n broader generalization of Whitney's broken circuit theorem\n in the context of convex geometries (antimatroids).},\n keywords = {graph, hypergraph, matroid, chromatic polynomial,\n domination polynomial, subgraph component polynomial,\n characteristic polynomial, beta invariant, broken circuit,\n broken neighbourhood, inclusion-exclusion, Möbius\n function, lattice, maximum-minimums identity, totient,\n Dirichlet inverse, Riemann zeta function, closure system,\n convex geometry}\n}","bibtype":"misc","eprint":"1404.5480","eprintclass":"math-CO","eprinttype":"arXiv","id":"DT:2014:AWBCT","key":"DT:2014:AWBCT","keywords":"graph, hypergraph, matroid, chromatic polynomial, domination polynomial, subgraph component polynomial, characteristic polynomial, beta invariant, broken circuit, broken neighbourhood, inclusion-exclusion, Möbius function, lattice, maximum-minimums identity, totient, Dirichlet inverse, Riemann zeta function, closure system, convex geometry","month":"April","pubstate":"Submitted for publication","title":"An Abstraction of Whitney's Broken Circuit Theorem","type":"misc","year":"2014"},"bibtype":"misc","biburl":"https://www.mni.hs-mittweida.de/fileadmin/verzeichnisfreigaben/dohmen/Publikationen/Dohmen.bib","downloads":0,"keywords":["graph","hypergraph","matroid","chromatic polynomial","domination polynomial","subgraph component polynomial","characteristic polynomial","beta invariant","broken circuit","broken neighbourhood","inclusion-exclusion","möbius function","lattice","maximum-minimums identity","totient","dirichlet inverse","riemann zeta function","closure system","convex geometry"],"search_terms":["abstraction","whitney","broken","circuit","theorem","dohmen","trinks"],"title":"An Abstraction of Whitney's Broken Circuit Theorem","year":2014,"dataSources":["QAQCDmtGHsz8zZBdf"]}