Partial graph orientations and the Tutte polynomial

DOI10.1016/J.AAM.2017.05.003MaRDI QIDQ679543zbMATH OpenOpenAlexFDO

Authors Spencer Backman

Publication date 11 January 2018

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Tutte polynomialEhrhart polynomialreliability polynomialcycle-cocycle reversal systempartial graph orientationLawrence idealwin vector polytope

Mathematics Subject Classification ID

Graph polynomials (05C31) Combinatorial aspects of commutative algebra (05E40)

Abstract: Gessel and Sagan investigated the Tutte polynomial, $T(x,y)$ using depth first search, and applied their techniques to show that the number of acyclic partial orientations of a graph is $2^{g}T(3,1/2)$. We provide a short deletion-contraction proof of this result and demonstrate that dually, the number of strongly connected partial orientations is $2^{n-1}T(1/2,3)$. We then prove that the number of partial orientations modulo cycle reversals is $2^{g}T(3,1)$ and the number of partial orientations modulo cut reversals is $2^{n-1}T(1,3)$. To prove these results, we introduce cut and cycle minimal partial orientations which provide distinguished representatives for partial orientations modulo cut and cycle reversals. These extend classes of total orientations introduced by Gioan, and Greene and Zaslavksy, and we highlight a close connection with graphic and cographic Lawrence ideals. We conclude with edge chromatic generalizations of the quantities presented, which allow for a new interpretation of the reliability polynomial for all probabilities, $p$ with $0<p<1/2$.

Recommendations

• The Tutte polynomial of oriented matroids
• The Tutte polynomial for graphs
• Completing orientations of partially oriented graphs
• On graphs determined by their Tutte polynomials
• Tutte polynomial of some multigraphs
• scientific article; zbMATH DE number 5247088
• Parametrized Tutte Polynomials of Graphs and Matroids
• Tutte polynomials for directed graphs
• Even Orientations and Pfaffian graphs
• On the orientation of graphs and hypergraphs

Cites work

• scientific article; zbMATH DE number 3885920 (Why is no real title available?)
• scientific article; zbMATH DE number 1369835 (Why is no real title available?)
• scientific article; zbMATH DE number 835749 (Why is no real title available?)
• scientific article; zbMATH DE number 3411070 (Why is no real title available?)
• A family of quasisymmetry models
• Acyclic orientations of graphs
• Bigraphical arrangements
• Canonical representatives for divisor classes on tropical curves and the matrix-tree theorem
• Circuit-cocircuit reversing systems in regular matroids
• Convexity in oriented matroids
• Convolution-multiplication identities for Tutte polynomials of graphs and matroids
• Decompositions of Rational Convex Polytopes
• Divisors on graphs, binomial and monomial ideals, and cellular resolutions
• Divisors on graphs, orientations, syzygies, and system reliability
• Enumerating degree sequences in digraphs and a cycle--cocycle reversing system
• Enumeration of Golomb rulers and acyclic orientations of mixed graphs
• Forced orientation of graphs
• Fourientation activities and the Tutte polynomial
• Fourientations and the Tutte polynomial
• Generalized activities and the Tutte polynomial
• Geometric bijections for regular matroids, zonotopes, and Ehrhart theory
• Inside-out polytopes
• Lectures on algebraic statistics
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• On weak chromatic polynomials of mixed graphs
• Orientations, lattice polytopes, and group arrangements I: Chromatic and tension polynomials of graphs
• Orientations, semiorders, arrangements, and parking functions
• Permutohedra, Associahedra, and Beyond
• Riemann-Roch theory for graph orientations
• The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions
• The polytope of win vectors
• Tropical curves, their Jacobians and theta functions
• Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings
• \(G\)-parking functions, acyclic orientations and spanning trees

Cited in

(14)

• On the number of circuit-cocircuit reversal classes of an oriented matroid
• Geometric bijections for regular matroids, zonotopes, and Ehrhart theory
• Orientations, lattice polytopes, and group arrangements. II: Modular and integral flow polynomials of graphs
• On maximum graphs in Tutte polynomial posets
• Fourientation activities and the Tutte polynomial
• Tutte polynomials for directed graphs
• Geometric bijections for regular matroids, zonotopes, and Ehrhart theory
• Fourientations and the Tutte polynomial
• Extremal graphs for the Tutte polynomial
• Geometric bijections between spanning trees and break divisors
• Completing orientations of partially oriented graphs
• scientific article; zbMATH DE number 7203409 (Why is no real title available?)
• Oriented flip graphs of polygonal subdivisions and noncrossing tree partitions
• Topological bijections for oriented matroids

This page was built for publication: Partial graph orientations and the Tutte polynomial

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