Combinatorial Reciprocity Theorems
Tóm tắt
A common theme of enumerative combinatorics is formed by counting functions that are polynomials evaluated at positive integers. In this expository paper, we focus on four families of such counting functions connected to hyperplane arrangements, lattice points in polyhedra, proper colorings of graphs, and P-partitions. We will see that in each instance we get interesting information out of a counting function when we evaluate it at a negative integer (and so, a priori the counting function does not make sense at this number). Our goals are to convey some of the charm these “alternative” evaluations of counting functions exhibit, and to weave a unifying thread through various combinatorial reciprocity theorems by looking at them through the lens of geometry, which will include some scenic detours through other combinatorial concepts.
Tài liệu tham khảo
Baldoni, V., Berline, N., Köppe, M., Vergne, M.: Intermediate sums on polyhedra: Computation and real Ehrhart theory. Preprint: arXiv:1011.6002v1 (2010)
Barvinok, A.: Computing the Ehrhart quasi-polynomial of a rational simplex. Math. Comput. 75(255), 1449–1466 (2006). arXiv:math/0504444
Beck, M., Braun, B.: Nowhere-harmonic colorings of graphs, Proc. Am. Math. Soc. (to appear). arXiv:0907.1272 (2011)
Beck, M., Braun, B., Le, N.: Mahonian partition identities via polyhedral geometry. Devel. Math. (to appear). arXiv:1103.1070 (2011)
Beck, M., Gessel, I.M., Lee, S., Savage, C.D.: Symmetrically constrained compositions. Ramanujan J. 23(1–3), 355–369 (2010). arXiv:0906.5573
Beck, M., Robins, S.: Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra. Undergraduate Texts in Mathematics. Springer, New York (2007). Electronically available at http://math.sfsu.edu/beck/ccd.html
Beck, M., Zaslavsky, T.: An enumerative geometry for magic and magilatin labellings. Ann. Comb. 10(4), 395–413 (2006). arXiv:math.CO/0506315
Beck, M., Zaslavsky, T.: Inside-out polytopes. Adv. Math. 205(1), 134–162 (2006). arXiv:math.CO/0309330
Beck, M., Zaslavsky, T.: The number of nowhere-zero flows on graphs and signed graphs. J. Comb. Theory, Ser. B 96(6), 901–918 (2006). arXiv:math.CO/0309331
Birkhoff, G.D.: A determinant formula for the number of ways of coloring a map. Ann. Math. 14(1–4), 42–46 (1912/13)
Breuer, F., Dall, A.: Bounds on the coefficients of tension and flow polynomials. J. Algebr. Comb. 33(3), 465–482 (2011). arXiv:1004.3470
Breuer, F., Sanyal, R.: Ehrhart theory, modular flow reciprocity, and the Tutte polynomial, Math. Z. (to appear) (2011). arXiv:0907.0845v1
De Loera, J.A., Rambau, J., Santos, F.: Triangulations. Algorithms and Computation in Mathematics, vol. 25. Springer, Berlin (2010)
Ehrhart, E.: Sur les polyèdres rationnels homothétiques à n dimensions. C. R. Acad. Sci. Paris 254, 616–618 (1962)
Euler, L.: Demonstatio nonnullarum insignium proprietatum, quibus solida hedris planis inclusa sunt praedita. Novi Commun. Acad. Sci. Imp. Petropol. 4, 140–160 (1752/53)
Euler, L.: Elementa doctrinae solidorum. Novi Commun. Acad. Sci. Imp. Petropol. 4, 109–140 (1752/53)
Greene, C.: Acyclic orientations. In: Aigner, M. (ed.) Higher Combinatorics. NATO Adv. Study Inst. Ser., Ser. C: Math. Phys. Sci., vol. 31, pp. 65–68. Reidel, Dordrecht (1977)
Greene, C., Zaslavsky, T.: On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs. Trans. Am. Math. Soc. 280(1), 97–126 (1983)
Haase, C., Nill, B., Payne, S.: Cayley decompositions of lattice polytopes and upper bounds for h ∗-polynomials. J. Reine Angew. Math. 637, 207–216 (2009). arXiv:0804.3667
Hibi, T.: Algebraic Combinatorics on Convex Polytopes. Carslaw (1992)
Linke, E.: Rational Ehrhart quasi-polynomials. Preprint: arXiv:1006.5612v2 (2011)
Macdonald, I.G.: Polynomials associated with finite cell-complexes. J. Lond. Math. Soc. 4, 181–192 (1971)
Orlik, P., Terao, H.: Arrangements of Hyperplanes. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 300. Springer, Berlin (1992)
Poincaré, H.: Sur la généralisation d’un theorem d’Euler relatif aux polyèdres. C. R. Acad. Sci. Paris 117, 144–145 (1893)
Sam, S.V.: A bijective proof for a theorem of Ehrhart. Am. Math. Mon. 116(8), 688–701 (2009). arXiv:0801.4432v5
Stanley, R.P.: Ordered Structures and Partitions. Memoirs of the American Mathematical Society, No. 119. American Mathematical Society, Providence (1972)
Stanley, R.P.: Acyclic orientations of graphs. Discrete Math. 5, 171–178 (1973)
Stanley, R.P.: Enumerative Combinatorics, vol. 1. Cambridge Studies in Advanced Mathematics, vol. 49. Cambridge University Press, Cambridge (1997)
Stanley, R.P.: An introduction to hyperplane arrangements. Geometric Combinatorics. IAS/Park City Math. Ser., vol. 13. Amer. Math. Soc., Providence (2007), pp. 389–496
Stapledon, A.: Inequalities and Ehrhart δ-vectors. Trans. Am. Math. Soc. 361(10), 5615–5626 (2009). arXiv:0801.0873
Stapledon, A.: Additive number theory and inequalities in Ehrhart theory. Preprint: arXiv:0904.3035v2 (2010)
Whitney, H.: A logical expansion in mathematics. Bull. Am. Math. Soc. 38(8), 572–579 (1932)
Zaslavsky, T.: Facing up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes. Mem. Amer. Math. Soc., vol. 154 (1975)
Stapledon, A.: Biased graphs. VII. Contrabalance and antivoltages. J. Comb. Theory, Ser. B 97(6), 1019–1040 (2007)
Ziegler, G.M.: Lectures on Polytopes. Springer, New York (1995)