Cubic graphs, their Ehrhart quasi-polynomials, and a scissors congruence phenomenon. (English) Zbl 1458.05113
Summary: The scissors congruence conjecture for the unimodular group is an analogue of Hilbert’s third problem, for the equidecomposability of polytopes. F. Liu and B. Osserman [J. Algebr. Comb. 23, No. 2, 125–136 (2006; Zbl 1090.14009)] studied the Ehrhart quasi-polynomials of polytopes naturally associated to graphs whose vertices have degree one or three. In this paper, we prove the scissors congruence conjecture, posed by C. Haase and T. B. McAllister [Contemp. Math. 452, 115–122 (2008; Zbl 1163.52006)], for this class of polytopes. The key ingredient in the proofs is the nearest neighbor interchange (NNI) move on graphs and a naturally arising piecewise unimodular transformation. We provide a generalization of the context in which the NNI moves appear, to connected graphs with the same degree sequence. We also show that, up to a dilation factor of 4 and an integer translation, all of these Liu-Osserman polytopes are reflexive.
MSC:
| 05C30 | Enumeration in graph theory |
| 05C76 | Graph operations (line graphs, products, etc.) |
| 52B45 | Dissections and valuations (Hilbert’s third problem, etc.) |
| 14H60 | Vector bundles on curves and their moduli |
Keywords:
nearest neighbour interchange; Ehrhart polynomials; polytopes; cubic graphs; scissors congruenceReferences:
| [1] | Baldoni, V., Berline, N., Loera, J.D., Dutra, B., Köppe, M., Moreinis, S., Pinto, G., Vergne, M., Wu, J.: Software and user’s guide for LattE integrale (2014). https://www.math.ucdavis.ed/ latte |
| [2] | Beck, M.; Robins, S., Computing the Continuous Discretely (2007), New York: Springer, New York · Zbl 1114.52013 |
| [3] | Bondy, J.; Murty, U., Graph Theory (2008), New York: Springer, New York · Zbl 1134.05001 · doi:10.1007/978-1-84628-970-5 |
| [4] | Culik, K.; Wood, D., A note on some tree similarity measures, Inf. Process. Lett., 15, 1, 39-42 (1982) · Zbl 0489.68058 · doi:10.1016/0020-0190(82)90083-7 |
| [5] | Deza, MM; Laurent, M., Geometry of Cuts and Metrics (1997), Berlin: Springer, Berlin · Zbl 1210.52001 · doi:10.1007/978-3-642-04295-9 |
| [6] | Ehrhart, E., Polynômes Arithmétiques et Méthode des Polyèdres en Combinatoire (1977), Basel: Birkhäuser, Basel · Zbl 0337.10019 |
| [7] | Gordon, K.; Ford, E.; St. John, K., Hamiltonian walks of phylogenetic treespaces, IEEE ACM Trans. Comput. Biol. Bioinform., 10, 4, 1076-1079 (2013) · doi:10.1109/TCBB.2013.105 |
| [8] | Haase, Ch; McAllister, TB, Quasi-period collapse and \(\text{GL}_n({\mathbb{Z}})\)-scissors congruence in rational polytopes, Integer Points in Polyhedra-Geometry: Number Theory, Representation Theory, Algebra, Optimization, Statistics, 115-122 (2008), Providence: American Mathematical Society, Providence · Zbl 1163.52006 · doi:10.1090/conm/452/08777 |
| [9] | Haase, Ch; Melnikov, IV, The reflexive dimension of a lattice polytope, Ann. Comb., 10, 2, 211-217 (2006) · Zbl 1125.52008 · doi:10.1007/s00026-006-0283-9 |
| [10] | Huber, KT; Moulton, V.; Wu, T., Transforming phylogenetic networks: moving beyond tree space, J. Theor. Biol., 404, 30-39 (2016) · Zbl 1343.92348 · doi:10.1016/j.jtbi.2016.05.030 |
| [11] | Laurent, M.: Graphic vertices of the metric polytope. Discrete Math. 151(1-3), 131-153 (1996) · Zbl 0854.05095 |
| [12] | Linke, E., Rational Ehrhart quasi-polynomials, J. Comb. Theory Ser. A, 118, 7, 1966-1978 (2011) · Zbl 1234.52010 · doi:10.1016/j.jcta.2011.03.007 |
| [13] | Liu, F.; Osserman, B., Mochizuki’s indigenous bundles and Ehrhart polynomials, J. Algebra. Comb., 23, 2, 125-136 (2006) · Zbl 1090.14009 · doi:10.1007/s10801-006-6920-x |
| [14] | Mochizuki, S., A theory of ordinary \(p\)-adic curves, Publ. Res. Inst. Math. Sci., 32, 6, 957-1152 (1996) · Zbl 0879.14009 · doi:10.2977/prims/1195145686 |
| [15] | Robinson, DF, Comparison of labeled trees with valency three, J. Comb. Theory Ser. B, 11, 105-119 (1971) · Zbl 0185.27704 · doi:10.1016/0095-8956(71)90020-7 |
| [16] | Royer, T.: Semi-reflexive polytopes (2017). arXiv:1712.04381 |
| [17] | Tsukui, Y., Transformations of cubic graphs, J. Franklin Inst. B, 333, 4, 565-575 (1996) · Zbl 0859.05069 · doi:10.1016/0016-0032(96)00015-4 |
| [18] | Wakabayashi, Y., Spin networks, Ehrhart quasipolynomials, and combinatorics of dormant indigenous bundles, Kyoto J. Math., 59, 3, 649-684 (2019) · Zbl 1440.14147 · doi:10.1215/21562261-2019-0020 |
| [19] | Zagier, D.: Elementary aspects of the Verlinde formula and of the Harder-Narasimhan-Atiyah-Bott formula. In: Proceedings of the Hirzebruch 65 Conference on Algebraic Geometry (Ramat Gan, 1993). Israel Mathematics Conference Proceedings, vol. 9, pp. 445-462. Bar-Ilan University, Ramat Gan (1996) · Zbl 0854.14020 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
