Fourientations and the Tutte polynomial
A fourientation of a graph is a choice for each edge of the graph whether to orient that edge in either direction, leave it unoriented, or biorient it. Fixing a total order on the edges and a reference orientation of the graph, we investigate properties of cuts and cycles in fourientations which giv...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer International Publishing
2018
|
| Online Access: | http://hdl.handle.net/1721.1/117000 https://orcid.org/0000-0002-0985-4788 |
| _version_ | 1826198087467532288 |
|---|---|
| author | Backman, Spencer Hopkins, Sam |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Backman, Spencer Hopkins, Sam |
| author_sort | Backman, Spencer |
| collection | MIT |
| description | A fourientation of a graph is a choice for each edge of the graph whether to orient that edge in either direction, leave it unoriented, or biorient it. Fixing a total order on the edges and a reference orientation of the graph, we investigate properties of cuts and cycles in fourientations which give trivariate generating functions that are generalized Tutte polynomial evaluations of the form (k + m)[superscript n−1](k + l)[superscript gT](αk + βl + m/k + m , γ k + l + δm/ k + l) for α, γ ∈ {0, 1, 2} and β, δ ∈ {0, 1}. We introduce an intersection lattice of 64 cut–cycle fourientation classes enumerated by generalized Tutte polynomial evaluations of this form. We prove these enumerations using a single deletion–contraction argument and
classify axiomatically the set of fourientation classes to which our deletion–contraction argument applies. This work unifies and extends earlier results for fourientations due to Gessel and Sagan (Electron J Combin 3(2):Research Paper 9, 1996), results for partial orientations due to Backman (Adv Appl Math, forthcoming, 2014. arXiv:1408.3962), and
Hopkins and Perkinson (Trans Am Math Soc 368(1):709–725, 2016), as well as results for total orientations due to Stanley (Discrete Math 5:171–178, 1973; Higher combinatorics (Proceedings of NATO Advanced Study Institute, Berlin, 1976). NATO Advanced Study Institute series, series C: mathematical and physical sciences, vol 31, Reidel, Dordrecht, pp 51–62, 1977), Las Vergnas (Progress in graph theory (Proceedings, Waterloo silver
jubilee conference 1982), Academic Press, New York, pp 367–380, 1984), Greene and Zaslavsky (Trans Am Math Soc 280(1):97–126, 1983), and Gioan (Eur J Combin 28(4):1351–1366, 2007), which were previously unified by Gioan (2007), Bernardi (Electron J Combin 15(1):Research Paper 109, 2008), and Las Vergnas (Tutte polynomial of a morphism of matroids 6. A multi-faceted counting formula for hyperplane regions and acyclic orientations, 2012. arXiv:1205.5424). We conclude by describing how these
classes of fourientations relate to geometric, combinatorial, and algebraic objects including bigraphical arrangements, cycle–cocycle reversal systems, graphic Lawrence ideals, Riemann–Roch theory for graphs, zonotopal algebra, and the reliability polynomial. Keywords: Partial graph orientations, Tutte polynomial, Deletion–contraction, Hyperplane arrangements, Cycle–cocycle reversal system, Chip-firing, G-parking functions, Abelian sandpile model, Riemann–Roch theory for graphs, Lawrence ideals, Zonotopal algebra, Reliability polynomial |
| first_indexed | 2024-09-23T10:58:39Z |
| format | Article |
| id | mit-1721.1/117000 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:58:39Z |
| publishDate | 2018 |
| publisher | Springer International Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1170002022-10-01T00:22:34Z Fourientations and the Tutte polynomial Backman, Spencer Hopkins, Sam Massachusetts Institute of Technology. Department of Mathematics Hopkins, Sam A fourientation of a graph is a choice for each edge of the graph whether to orient that edge in either direction, leave it unoriented, or biorient it. Fixing a total order on the edges and a reference orientation of the graph, we investigate properties of cuts and cycles in fourientations which give trivariate generating functions that are generalized Tutte polynomial evaluations of the form (k + m)[superscript n−1](k + l)[superscript gT](αk + βl + m/k + m , γ k + l + δm/ k + l) for α, γ ∈ {0, 1, 2} and β, δ ∈ {0, 1}. We introduce an intersection lattice of 64 cut–cycle fourientation classes enumerated by generalized Tutte polynomial evaluations of this form. We prove these enumerations using a single deletion–contraction argument and classify axiomatically the set of fourientation classes to which our deletion–contraction argument applies. This work unifies and extends earlier results for fourientations due to Gessel and Sagan (Electron J Combin 3(2):Research Paper 9, 1996), results for partial orientations due to Backman (Adv Appl Math, forthcoming, 2014. arXiv:1408.3962), and Hopkins and Perkinson (Trans Am Math Soc 368(1):709–725, 2016), as well as results for total orientations due to Stanley (Discrete Math 5:171–178, 1973; Higher combinatorics (Proceedings of NATO Advanced Study Institute, Berlin, 1976). NATO Advanced Study Institute series, series C: mathematical and physical sciences, vol 31, Reidel, Dordrecht, pp 51–62, 1977), Las Vergnas (Progress in graph theory (Proceedings, Waterloo silver jubilee conference 1982), Academic Press, New York, pp 367–380, 1984), Greene and Zaslavsky (Trans Am Math Soc 280(1):97–126, 1983), and Gioan (Eur J Combin 28(4):1351–1366, 2007), which were previously unified by Gioan (2007), Bernardi (Electron J Combin 15(1):Research Paper 109, 2008), and Las Vergnas (Tutte polynomial of a morphism of matroids 6. A multi-faceted counting formula for hyperplane regions and acyclic orientations, 2012. arXiv:1205.5424). We conclude by describing how these classes of fourientations relate to geometric, combinatorial, and algebraic objects including bigraphical arrangements, cycle–cocycle reversal systems, graphic Lawrence ideals, Riemann–Roch theory for graphs, zonotopal algebra, and the reliability polynomial. Keywords: Partial graph orientations, Tutte polynomial, Deletion–contraction, Hyperplane arrangements, Cycle–cocycle reversal system, Chip-firing, G-parking functions, Abelian sandpile model, Riemann–Roch theory for graphs, Lawrence ideals, Zonotopal algebra, Reliability polynomial National Science Foundation (U.S.) (Grant 1122374) 2018-07-19T14:29:35Z 2018-07-19T14:29:35Z 2017-09 2016-08 2017-09-12T03:46:34Z Article http://purl.org/eprint/type/JournalArticle 2197-9847 http://hdl.handle.net/1721.1/117000 Backman, Spencer, and Sam Hopkins. “Fourientations and the Tutte Polynomial.” Research in the Mathematical Sciences, vol. 4, no. 1, Dec. 2017. © 2017 The Authors https://orcid.org/0000-0002-0985-4788 en http://dx.doi.org/10.1186/s40687-017-0107-z Research in the Mathematical Sciences Creative Commons Attribution http://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf Springer International Publishing Springer International Publishing |
| spellingShingle | Backman, Spencer Hopkins, Sam Fourientations and the Tutte polynomial |
| title | Fourientations and the Tutte polynomial |
| title_full | Fourientations and the Tutte polynomial |
| title_fullStr | Fourientations and the Tutte polynomial |
| title_full_unstemmed | Fourientations and the Tutte polynomial |
| title_short | Fourientations and the Tutte polynomial |
| title_sort | fourientations and the tutte polynomial |
| url | http://hdl.handle.net/1721.1/117000 https://orcid.org/0000-0002-0985-4788 |
| work_keys_str_mv | AT backmanspencer fourientationsandthetuttepolynomial AT hopkinssam fourientationsandthetuttepolynomial |