Bounds on the coefficients of tension and flow polynomials

DOI10.1007/S10801-010-0254-4zbMATH Open1227.05159arXiv1004.3470OpenAlexW2091826719MaRDI QIDQ633281FDOQ633281

Authors: Felix Breuer, Aaron Dall 

Publication date: 31 March 2011

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

Abstract: The goal of this article is to obtain bounds on the coefficients of modular and integral flow and tension polynomials of graphs. To this end we make use of the fact that these polynomials can be realized as Ehrhart polynomials of inside-out polytopes. Inside-out polytopes come with an associated relative polytopal complex and, for a wide class of inside-out polytopes, we show that this complex has a convex ear decomposition. This leads to the desired bounds on the coefficients of these polynomials.

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

Recommendations

• Bounds for the coefficients of flow polynomials
• Binomial inequalities for chromatic, flow, and tension polynomials
• Bounding the coefficients of the characteristic polynomials of simple binary matroids
• Tension-flow polynomials on graphs
• A note on flow polynomials of graphs

zbMATH Keywords

Ehrhart polynomialpolytopal complexinside-out polytopeconvex ear decomposition\(M\)-vectorregular subdivision

Mathematics Subject Classification ID

Graph polynomials (05C31) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Flows in graphs (05C21) Combinatorial aspects of simplicial complexes (05E45)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing the Continuous Discretely
• Polytopes, Rings, and K-Theory
• Lectures on Polytopes
• Title not available (Why is that?)
• Combinatorics and commutative algebra.
• Two Decompositions in Topological Combinatorics with Applications to Matroid Complexes
• Title not available (Why is that?)
• Orientations, lattice polytopes, and group arrangements I: Chromatic and tension polynomials of graphs
• Inside-out polytopes
• Dual polytopes of rational convex polytopes
• A monotonicity property of \(h\)-vectors and \(h^*\)-vectors
• Convex polytopes all of whose reverse lexicographic initial ideals are squarefree
• \(g\)-elements, finite buildings and higher Cohen-Macaulay connectivity.
• \(h\)-vectors of Gorenstein polytopes
• Quadratic Gröbner bases for smooth \(3\times 3\) transportation polytopes
• The topology of the coloring complex
• Coloring complexes and arrangements
• The coloring ideal and coloring complex of a graph
• Link complexes of subspace arrangements
• Viewing counting polynomials as Hilbert functions via Ehrhart theory
• Ehrhart theory, modular flow reciprocity, and the Tutte polynomial
• The number of nowhere-zero flows on graphs and signed graphs
• Distributive lattices, polyhedra, and generalized flows
• Polynomials associated with nowhere-zero flows

Cited In (12)

• Scheduling problems
• Polynomial algorithms for canonical forms of orientations
• Enumeration of balanced finite group valued functions on directed graphs
• Title not available (Why is that?)
• Bounding the coefficients of the characteristic polynomials of simple binary matroids
• Bounds for the coefficients of flow polynomials
• Balanced abelian group-valued functions on directed graphs
• Tension-flow polynomials on graphs
• Binomial inequalities for chromatic, flow, and tension polynomials
• Enumerating colorings, tensions and flows in cell complexes
• Existence of unimodular triangulations -- positive results
• ALGEBRAIC STRUCTURES RELATED TO BALANCED FUNCTIONS ON GRAPHS: RESULTS AND OPEN PROBLEMS

Uses Software

• OEIS

This page was built for publication: Bounds on the coefficients of tension and flow polynomials

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