×

Lattice points in orthotopes and a huge polynomial Tutte invariant of weighted gain graphs. (English) Zbl 1332.05065

Summary: A gain graph is a graph whose edges are orientably labeled from a group. A weighted gain graph is a gain graph with vertex weights from an abelian semigroup, where the gain group is lattice ordered and acts on the weight semigroup. For weighted gain graphs we establish basic properties and we present general dichromatic and forest-expansion polynomials that are Tutte invariants (they satisfy Tutte’s deletion-contraction and multiplicative identities). In order to do that we develop a relative of the Tutte polynomial of a semimatroid. Our dichromatic polynomial includes the classical graph one by W. T. Tutte [J. Comb. Theory 2, 301–320 (1967; Zbl 0147.42902)], Zaslavsky’s two for gain graphs [T. Zaslavsky, J. Comb. Theory, Ser. B 47, No. 1, 32–52 (1989; Zbl 0714.05057)], Noble and Welsh’s for graphs with positive integer weights [S. D. Noble and D. J. A. Welsh, Ann. Inst. Fourier 49, No. 3, 1057–1087 (1999; Zbl 0917.05025)], and that of rooted integral gain graphs by D. Forge and T. Zaslavsky [J. Comb. Theory, Ser. A 114, No. 1, 97–109 (2007; Zbl 1105.52014)]. It is not a universal Tutte invariant of weighted gain graphs; that remains to be found. { }An evaluation of one example of our polynomial counts proper list colorations of the gain graph from a color set with a gain-group action. When the gain group is \(\mathbb{Z}^d\), the lists are order ideals in the integer lattice \(\mathbb{Z}^d\), and there are specified upper bounds on the colors, then there is a formula for the number of bounded proper colorations that is a piecewise polynomial function of the upper bounds, of degree nd where \(n\) is the order of the graph. This example leads to graph-theoretical formulas for the number of integer lattice points in an orthotope but outside a finite number of affinographic hyperplanes, and for the number of \(n \times d\) integral matrices that lie between two specified matrices but not in any of certain subspaces defined by simple row equations.

MSC:

05C22 Signed and weighted graphs
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ardila, Federico, Enumerative and algebraic aspects of matroids and hyperplane arrangements (2003), Massachusetts Institute of Technology: Massachusetts Institute of Technology Cambridge, Mass, PhD thesis
[2] Ardila, Federico, Computing the Tutte polynomial of a hyperplane arrangement, Pacific J. Math., 230, 2, 1-26 (2007), MR 2318445 (2008g:52034), Zbl. 1152.52011 · Zbl 1152.52011
[3] Ardila, Federico, Semimatroids and their Tutte polynomials, Rev. Colombiana Mat., 41, 1, 39-66 (2007), MR 2355665 (2008j:05082), Zbl. 1136.05008 · Zbl 1136.05008
[4] Björner, Anders, The homology and shellability of matroids and geometric lattices, (White, Neil, Matroid Applications. Matroid Applications, Encyc. Math. Appl., vol. 40 (1992), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 226-283, Ch. 7, MR 94a:52030, Zbl. 772.05027 · Zbl 0772.05027
[5] Brylawski, Thomas H., A decomposition for combinatorial geometries, Trans. Amer. Math. Soc., 171, 235-282 (1972), MR 46 #8869, Zbl. 224.05007, 248.05019 · Zbl 0224.05007
[6] Brylawski, Thomas; Oxley, James, The Tutte polynomial and its applications, (White, Neil, Matroid Applications. Matroid Applications, Encyc. Math. Appl., vol. 40 (1992), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 123-225, Ch. 6, MR 93k:05060, Zbl. 769.05026 · Zbl 0769.05026
[7] Crapo, Henry H., The Tutte polynomial, Aequationes Math., 3, 211-229 (1969), MR 41 #6705, Zbl. 197, 502b (e: 197.50202) · Zbl 0197.50202
[8] Ellis-Monaghan, Joanna A.; Moffatt, Iain, The Tutte-Potts connection in the presence of an external magnetic field, Adv. in Appl. Math., 47, 4, 772-782 (2011), MR 2832375, Zbl. 1232.05100 · Zbl 1232.05100
[9] Etienne, Gwihen; Las Vergnas, Michel, External and internal elements of a matroid basis, Discrete Math., 179, 111-119 (1998), MR 98m:05038, Zbl. 887.05012 · Zbl 0887.05012
[10] Forge, David; Zaslavsky, Thomas, Lattice point counts for the Shi arrangement and other affinographic hyperplane arrangements, J. Combin. Theory Ser. A, 114, 1, 97-109 (2007), MR 2007i:52026, Zbl. 1105.52014 · Zbl 1105.52014
[11] Kook, W.; Reiner, V.; Stanton, D., Combinatorial Laplacians of matroid complexes, J. Amer. Math. Soc., 13, 1, 129-148 (2000), MR 2001e:05028, Zbl. 940.05021 · Zbl 0940.05021
[12] Noble, S. D.; Welsh, D. J.A., A weighted graph polynomial from chromatic invariants of knots, Symposium à la Mémoire de François Jaeger. Symposium à la Mémoire de François Jaeger, Grenoble, 1998. Symposium à la Mémoire de François Jaeger. Symposium à la Mémoire de François Jaeger, Grenoble, 1998, Ann. Inst. Fourier (Grenoble), 49, 3, 1057-1087 (1999), MR 2000h:05066, Zbl. 917.05025 · Zbl 0917.05025
[13] Rota, Gian-Carlo, On the foundations of combinatorial theory: I. Theory of Möbius functions, Z. Wahrsch. Verw. Gebiete, 2, 340-368 (1964), MR 30 #4688, Zbl. 121, 24f (e: 121.02406) · Zbl 0121.02406
[14] Stanley, Richard P., Enumerative Combinatorics, vol. 1 (1986), Wadsworth & Brooks/Cole: Wadsworth & Brooks/Cole Monterey, Calif, MR 87j:05003, Zbl. 608.05001 · Zbl 0608.05001
[15] Tutte, W. T., On dichromatic polynomials, J. Combin. Theory, 2, 301-320 (1967), MR 223272 (36 #6320), Zbl. 147, 429b (e: 147.42902) · Zbl 0147.42902
[16] Wachs, Michelle L.; Walker, James W., On geometric semilattices, Order, 2, 367-385 (1986), MR 87f:06004, Zbl. 589.06005 · Zbl 0589.06005
[17] Zaslavsky, Thomas, Signed graph coloring, Discrete Math., 39, 215-228 (1982), MR 84h:05050a, Zbl. 487.05027 · Zbl 0487.05027
[18] Zaslavsky, Thomas, Biased graphs. III. Chromatic and dichromatic invariants, J. Combin. Theory Ser. B, 64, 17-88 (1995), MR 96g:05139, Zbl. 857.05088 · Zbl 0857.05088
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.