Orientations, lattice polytopes, and group arrangements. II: Modular and integral flow polynomials of graphs

DOI10.1007/S00373-011-1080-8MaRDI QIDQ1928281zbMATH OpenOpenAlexFDO

Authors Beifang Chen, Richard P. Stanley

Publication date 3 January 2013

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

characteristic polynomialdirected Eulerian subgraphdual flow polynomialEhrhart polynomialsEulerian equivalence relationflow polytopehyperplane arrangementintegral flowintegral flow polynomiallattice polytopesmodular flow polynomialorientationreciprocity lawsubgroup arrangementtotally cyclic orientationTutte polynomial

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Flows in graphs (05C21) Graph polynomials (05C31) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20)

Abstract: We study modular and integral flow polynomials of graphs by means of subgroup arrangements and lattice polytopes. We introduce an Eulerian equivalence relation on orientations, flow arrangements, and flow polytopes; and we apply the theory of Ehrhart polynomials to obtain properties of modular and integral flow polynomials. The emphasis is on the geometrical treatment through subgroup arrangements and Ehrhart polynomials. Such viewpoint leads to a reciprocity law for the modular flow polynomial, which gives rise to an interpretation on the values of the modular flow polynomial at negative integers, and answers a question by Beck and Zaslavsky.

Recommendations

• Orientations, lattice polytopes, and group arrangements I: Chromatic and tension polynomials of graphs
• Orientations, lattice polytopes, and group arrangements. III: Cartesian product arrangements and applications to Tutte type polynomials
• Lattice of integer flows and the poset of strongly connected orientations for regular matroids
• On mod \((2p+1)\)-orientations of graphs
• On Mod $(2s+1)$-Orientations of Graphs
• The flow lattice of oriented matroids
• Distributive lattices, polyhedra, and generalized flows
• From generalized permutahedra to Grothendieck polynomials via flow polytopes (extended abstract)
• On the skew-permanental polynomials of orientation graphs
• Partial graph orientations and the Tutte polynomial

Cites work

• A combinatorial analysis of topological dissections
• A Contribution to the Theory of Chromatic Polynomials
• Acyclic orientations of graphs
• Ehrhart theory, modular flow reciprocity, and the Tutte polynomial
• Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
• Graph theory
• scientific article; zbMATH DE number 19501 (Why is no real title available?)
• scientific article; zbMATH DE number 67324 (Why is no real title available?)
• scientific article; zbMATH DE number 3512135 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• Lattice points, Dedekind sums, and Ehrhart polynomials of lattice polyhedra
• On characteristic polynomials of subspace arrangements
• On the Euler characteristic of finite unions of convex sets
• On the extension of additive functionals on classes of convex sets
• On the foundations of combinatorial theory I. Theory of M�bius Functions
• On the Imbedding of Linear Graphs in Surfaces
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• On valuations, the characteristic polynomial, and complex subspace arrangements
• Orientations, lattice polytopes, and group arrangements I: Chromatic and tension polynomials of graphs
• Polynomials associated with nowhere-zero flows
• The number of nowhere-zero flows on graphs and signed graphs

Cited in

(11)

• A bijection for Eulerian-equivalence classes of totally cyclic orientations
• A note on flow polynomials of graphs
• Orientations, lattice polytopes, and group arrangements. III: Cartesian product arrangements and applications to Tutte type polynomials
• Polynomials counting nowhere-zero chains in graphs
• Enumerating colorings, tensions and flows in cell complexes
• Dual complementary polynomials of graphs and combinatorial-geometric interpretation on the values of Tutte polynomial at positive integers
• On framed triangulations of flow polytopes, the \(\nu\)-Tamari lattice and Young's lattice
• Viewing counting polynomials as Hilbert functions via Ehrhart theory
• Bounds of characteristic polynomials of regular matroids
• Orientations, lattice polytopes, and group arrangements I: Chromatic and tension polynomials of graphs
• Ehrhart theory, modular flow reciprocity, and the Tutte polynomial

This page was built for publication: Orientations, lattice polytopes, and group arrangements. II: Modular and integral flow polynomials of graphs

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