Partial graph orientations and the Tutte polynomial

DOI10.1016/J.AAM.2017.05.003zbMATH Open1378.05093arXiv1408.3962OpenAlexW2963347042MaRDI QIDQ679543FDOQ679543

Authors: Spencer Backman 

Publication date: 11 January 2018

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

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$.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• Topological bijections for oriented matroids
• Oriented flip graphs of polygonal subdivisions and noncrossing tree partitions

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)