Broken circuit complexes of series-parallel networks

DOI10.1016/J.EJC.2015.04.009zbMATH Open1321.05037arXiv1404.1728OpenAlexW2115077094MaRDI QIDQ499446FDOQ499446

Authors: Dinh Van Le 

Publication date: 30 September 2015

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $(h_0,h_1,ldots,h_s)$ with $h_{s}e0$ be the $h$-vector of the broken circuit complex of a series-parallel network $M$. Let $G$ be a graph whose cycle matroid is $M$. We give a formula for the difference $h_{s-1}-h_1$ in terms of an ear decomposition of $G$. A number of applications of this formula are provided, including several bounds for $h_{s-1}-h_1$, a characterization of outerplanar graphs, and a solution to a conjecture on $A$-graphs posed by Fenton. We also prove that $h_{s-2}geq{h}_2$ when $sgeq4$.

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

Recommendations

• On the broken-circuit complex of graphs
• Flawlessness of \(h\)-vectors of broken circuit complexes
• Circuit and bond polytopes on series-parallel graphs
• Monomial bases for broken circuit complexes
• Zeros of Reliability Polynomials and f-vectors of Matroids

zbMATH Keywords

projective equivalencetransversal matroidmatrix representation for matroids

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Combinatorics and commutative algebra.
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the foundations of combinatorial theory I. Theory of M�bius Functions
• What can be said about pure O-sequences?
• Two Decompositions in Topological Combinatorics with Applications to Matroid Complexes
• Broken circuit complexes: Factorizations and generalizations
• Title not available (Why is that?)
• Hyperplane arrangement cohomology and monomials in the exterior algebra
• A higher invariant for matroids
• A Combinatorial Model for Series-Parallel Networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• A characterisation of binary transversal structures
• The Broken-Circuit Complex
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• \(g\)-elements of matroid complexes.
• The broken-circuit complex: its structure and factorizations
• Parallel recognition of series-parallel graphs
• Face number inequalities for matroid complexes and Cohen-Macaulay types of Stanley-Reisner rings of distributive lattices
• \( h\)-vectors of matroids and logarithmic concavity
• Chromatic polynomials and order ideals of monomials
• Induced cycle structure and outerplanarity
• On the Gorensteinness of broken circuit complexes and Orlik-Terao ideals
• Broken circuit complexes and hyperplane arrangements
• The Tutte polynomial. I: General theory
• On Crapo's Beta Invariant for Matroids
• CHARACTERIZATION OF ATOMIC MATROIDS
• The Tutte polynomial characterizes simple outerplanar graphs
• TRANSVERSAL MATROIDS, BASE-ORDERABLE MATROIDS, AND GRAPHS
• Homological properties of Orlik-Solomon algebras

Cited In (1)

• The \(h\)-vectors of PS ear-decomposable graphs

This page was built for publication: Broken circuit complexes of series-parallel networks

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