Bounds on the coefficients of tension and flow polynomials

DOI10.1007/S10801-010-0254-4MaRDI QIDQ633281zbMATH OpenOpenAlexFDO

Authors Felix Breuer, Aaron Dall

Publication date 31 March 2011

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

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

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)

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.

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

Cites work

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

Cited in

(12)

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

Describes a project that uses

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)