@article{hanusa_savage_2018, title={Lecture hall partitions and the affine hyperoctahedral group}, volume={25}, number={1}, journal={Electronic Journal of Combinatorics}, author={Hanusa, C. R. H. and Savage, C. D.}, year={2018} }
 @article{martinez_savage_2018, title={Patterns in inversion sequences II: Inversion sequences avoiding triples of relations}, volume={21}, number={2}, journal={Journal of Integer Sequences}, author={Martinez, M. and Savage, C.}, year={2018} }
 @article{beck_braun_koppe_savage_zafeirakopoulos_2016, title={GENERATING FUNCTIONS AND TRIANGULATIONS FOR LECTURE HALL CONES}, volume={30}, ISSN={["1095-7146"]}, DOI={10.1137/15m1036907}, abstractNote={We investigate the arithmetic-geometric structure of the lecture hall cone $L_n \ := \ \big\{\lambda\in \mathbb{R}^n: \, 0\leq \frac{\lambda_1}{1}\leq \frac{\lambda_2}{2}\leq \frac{\lambda_3}{3}\leq \cdots \leq \frac{\lambda_n}{n}\big\}$. We show that $L_n$ is isomorphic to the cone over the lattice pyramid of a reflexive simplex whose Ehrhart $h^*$-polynomial is given by the $(n-1)$st Eulerian polynomial and prove that lecture hall cones admit regular, flag, unimodular triangulations. After explicitly describing the Hilbert basis for $L_n$, we conclude with observations and a conjecture regarding the structure of unimodular triangulations of $L_n$, including connections between enumerative and algebraic properties of $L_n$ and cones over unit cubes.}, number={3}, journal={SIAM JOURNAL ON DISCRETE MATHEMATICS}, author={Beck, Matthias and Braun, Benjamin and Koppe, Matthias and Savage, Carla D. and Zafeirakopoulos, Zafeirakis}, year={2016}, pages={1470–1479} }
 @article{savage_2016, title={The mathematics of lecture hall partitions}, volume={144}, ISSN={["1096-0899"]}, DOI={10.1016/j.jcta.2016.06.006}, abstractNote={Over the past twenty years, lecture hall partitions have emerged as fundamental combinatorial structures, leading to new generalizations and interpretations of classical theorems and new results. In recent years, geometric approaches to lecture hall partitions have used polyhedral geometry to discover further properties of these rich combinatorial objects. In this paper we give an overview of some of the surprising connections that have surfaced in the process of trying to understand the lecture hall partitions.}, journal={JOURNAL OF COMBINATORIAL THEORY SERIES A}, author={Savage, Carla D.}, year={2016}, month={Nov}, pages={443–475} }
 @article{corteel_lovejoy_savage_2015, title={Anti-lecture hall compositions and Andrews' generalization of the Watson–Whipple transformation}, volume={134}, ISSN={0097-3165}, url={http://dx.doi.org/10.1016/J.JCTA.2015.03.002}, DOI={10.1016/J.JCTA.2015.03.002}, abstractNote={For fixed n and k, we find a three-variable generating function for the set of sequences (λ1,…,λn) satisfyingk≥λ1a1≥λ2a2≥…≥λnan≥0, where a:=(a1,…,an)=(1,2,…,n) or (n,n−1,…,1). When k→∞ we recover the refined anti-lecture hall and lecture hall theorems. When a=(1,2,…,n) and n→∞, we obtain a refinement of a recent result of Chen, Sang and Shi. The main tools are elementary combinatorics and Andrews' generalization of the Watson–Whipple transformation.}, journal={Journal of Combinatorial Theory, Series A}, publisher={Elsevier BV}, author={Corteel, Sylvie and Lovejoy, Jeremy and Savage, Carla}, year={2015}, month={Aug}, pages={188–195} }
 @article{savage_visontai_2015, title={The s-Eulerian polynomials have only real roots}, volume={367}, DOI={10.1090/s0002-9947-2014-06256-9}, abstractNote={We study the roots of generalized Eulerian polynomials via a novel approach. We interpret Eulerian polynomials as the generating polynomials of a statistic over inversion sequences. Inversion sequences (also known as Lehmer codes or subexcedant functions) were recently generalized by Savage and Schuster, to arbitrary sequences s of positive integers, which they called s-inversion sequences. Our object of study is the generating polynomial of the ascent statistic over the set of s-inversion sequences of length n. Since this ascent statistic over inversion sequences is equidistributed with the descent statistic over permutations, we call this generalized polynomial the s-Eulerian polynomial. The main result of this paper is that, for any sequence s of positive integers, the s-Eulerian polynomial has only real roots. This result is first shown to generalize several existing results about the real-rootedness of various Eulerian polynomials. We then show that it can be used to settle a conjecture of Brenti, that Eulerian polynomials for all finite Coxeter groups have only real roots, and partially settle a conjecture of Dilks, Petersen, Stembridge on type B affine Eulerian polynomials. It is then extended to several q-analogs. We show that the MacMahon-Carlitz q-Eulerian polynomial has only real roots whenever q is a positive real number, confirming a conjecture of Chow and Gessel. The same holds true for the hyperoctahedral group and the wreath product groups, confirming further conjectures of Chow and Gessel, and Chow and Mansour, respectively. Our results have interesting geometric consequences as well.}, number={2}, journal={Transactions of the American Mathematical Society}, author={Savage, Carla and Visontai, M.}, year={2015}, pages={1441–1466} }
 @article{beck_braun_koeppe_savage_zafeirakopoulos_2015, title={s-Lecture hall partitions, self-reciprocal polynomials, and Gorenstein cones}, volume={36}, ISSN={["1572-9303"]}, DOI={10.1007/s11139-013-9538-3}, abstractNote={In 1997, Bousquet-Melou and Eriksson initiated the study of lecture hall partitions, a fascinating family of partitions that yield a finite version of Euler's celebrated odd/distinct partition theorem. In subsequent work on s-lecture hall partitions, they considered the self-reciprocal property for various associated generating functions, with the goal of characterizing those sequences s that give rise to generating functions of the form $((1-q^{e_1})(1-q^{e_2})...(1-q^{e_n}))^{-1}$. We continue this line of investigation, connecting their work to the more general context of Gorenstein cones. We focus on the Gorenstein condition for s-lecture hall cones when s is a positive integer sequence generated by a second-order homogeneous linear recurrence with initial values 0 and 1. Among such sequences s, we prove that the n-dimensional s-lecture hall cone is Gorenstein for all n greater than or equal to 1 if and only if s is an l-sequence. One consequence is that among such sequences s, unless s is an l-sequence, the generating function for the s-lecture hall partitions can have the form $((1-q^{e_1})(1-q^{e_2})...(1-q^{e_n}))^{-1}$ for at most finitely many n. We also apply the results to establish several conjectures by Pensyl and Savage regarding the symmetry of h*-vectors for s-lecture hall polytopes. We end with open questions and directions for further research.}, number={1-2}, journal={RAMANUJAN JOURNAL}, author={Beck, Matthias and Braun, Benjamin and Koeppe, Matthias and Savage, Carla D. and Zafeirakopoulos, Zafeirakis}, year={2015}, month={Feb}, pages={123–147} }
 @inbook{andrews_savage_wilf_2013, title={Hypergeometric Identities Associated with Statistics on Words}, ISBN={9783642309786 9783642309793}, url={http://dx.doi.org/10.1007/978-3-642-30979-3_4}, DOI={10.1007/978-3-642-30979-3_4}, booktitle={Advances in Combinatorics}, publisher={Springer Berlin Heidelberg}, author={Andrews, George E. and Savage, Carla D. and Wilf, Herbert S.}, year={2013}, pages={77–100} }
 @article{beck_bliem_braun_savage_2013, title={Lattice point generating functions and symmetric cones}, volume={38}, ISSN={["1572-9192"]}, DOI={10.1007/s10801-012-0414-9}, abstractNote={We show that a recent identity of Beck–Gessel–Lee–Savage on the generating function of symmetrically constrained compositions of integers generalizes naturally to a family of convex polyhedral cones that are invariant under the action of a finite reflection group. We obtain general expressions for the multivariate generating functions of such cones, and work out their general form more specifically for all symmetry groups of type A (previously known) and types B and D (new). We obtain several applications of these expressions in type B, including identities involving permutation statistics and lecture hall partitions.}, number={3}, journal={JOURNAL OF ALGEBRAIC COMBINATORICS}, author={Beck, Matthias and Bliem, Thomas and Braun, Benjamin and Savage, Carla D.}, year={2013}, month={Nov}, pages={543–566} }
 @article{pensyl_savage_2013, title={Rational lecture hall polytopes and inflated Eulerian polynomials}, volume={31}, ISSN={["1382-4090"]}, DOI={10.1007/s11139-012-9393-7}, number={1-2}, journal={RAMANUJAN JOURNAL}, author={Pensyl, ThomasW. and Savage, Carla D.}, year={2013}, month={Jun}, pages={97–114} }
 @article{savage_schuster_2012, title={Ehrhart series of lecture hall polytopes and Eulerian polynomials for inversion sequences}, volume={119}, ISSN={["1096-0899"]}, DOI={10.1016/j.jcta.2011.12.005}, abstractNote={For a sequence s=(s1,…,sn) of positive integers, an s-lecture hall partition is an integer sequence λ satisfying 0⩽λ1/s1⩽λ2/s2⩽⋯⩽λn/sn. In this work, we introduce s-lecture hall polytopes, s-inversion sequences, and relevant statistics on both families. We show that for any sequence s of positive integers: (i) the h⁎-vector of the s-lecture hall polytope is the ascent polynomial for the associated s-inversion sequences; (ii) the ascent polynomials for s-inversion sequences generalize the Eulerian polynomials, including a q-analog that tracks a generalization of major index on s-inversion sequences; and (iii) the generating function for the s-lecture hall partitions can be interpreted in terms of a new q-analog of the s-Eulerian polynomials, which tracks a “lecture hall” statistic on s-inversion sequences. We show how four different statistics are related through the three s-families of partitions, polytopes, and inversion sequences. Our approach uses Ehrhart theory to relate the partition theory of lecture hall partitions to their geometry.}, number={4}, journal={JOURNAL OF COMBINATORIAL THEORY SERIES A}, author={Savage, Carla D. and Schuster, Michael J.}, year={2012}, month={May}, pages={850–870} }
 @article{sagan_savage_2012, title={Mahonian pairs}, volume={119}, ISSN={["0097-3165"]}, DOI={10.1016/j.jcta.2011.11.003}, abstractNote={We introduce the notion of a Mahonian pair. Consider the set, P ⁎ , of all words having the positive integers as alphabet. Given finite subsets S , T ⊂ P ⁎ , we say that ( S , T ) is a Mahonian pair if the distribution of the major index, maj, over S is the same as the distribution of the inversion number, inv, over T . So the well-known fact that maj and inv are equidistributed over the symmetric group, S n , can be expressed by saying that ( S n , S n ) is a Mahonian pair. We investigate various Mahonian pairs ( S , T ) with S ≠ T . Our principal tool is Foataʼs fundamental bijection ϕ : P ⁎ → P ⁎ since it has the property that maj w = inv ϕ ( w ) for any word w . We consider various families of words associated with Catalan and Fibonacci numbers. We show that, when restricted to words in { 1 , 2 } ⁎ , ϕ transforms familiar statistics on words into natural statistics on integer partitions such as the size of the Durfee square. The Rogers–Ramanujan identities, the Catalan triangle, and various q -analogues also make an appearance. We generalize the definition of Mahonian pairs to infinite sets and use this as a tool to connect a partition bijection of Corteel–Savage–Venkatraman with the Greene–Kleitman decomposition of a Boolean algebra into symmetric chains. We close with comments about future work and open problems.}, number={3}, journal={JOURNAL OF COMBINATORIAL THEORY SERIES A}, author={Sagan, Bruce E. and Savage, Carla D.}, year={2012}, month={Apr}, pages={526–545} }
 @article{savage_viswanathan_2012, title={The 1/k-Eulerian polynomials}, volume={19}, number={1}, journal={Electronic Journal of Combinatorics}, author={Savage, C. D. and Viswanathan, G.}, year={2012} }
 @article{savage_sills_2011, title={On an identity of Gessel and Stanton and the new little Göllnitz identities}, volume={46}, ISSN={0196-8858}, url={http://dx.doi.org/10.1016/j.aam.2009.12.009}, DOI={10.1016/j.aam.2009.12.009}, abstractNote={We show that an identity of Gessel and Stanton [I. Gessel, D. Stanton, Applications of q -Lagrange inversion to basic hypergeometric series, Trans. Amer. Math. Soc. 277 (1983) 197, Eq. (7.24)] can be viewed as a symmetric version of a recent analytic variation of the little Göllnitz identities. This is significant, since the Göllnitz–Gordon identities are considered the usual symmetric counterpart to little Göllnitz theorems. Is it possible, then, that the Gessel–Stanton identity is part of an infinite family of identities like those of Göllnitz–Gordon? Toward this end, we derive partners and generalizations of the Gessel–Stanton identity. We show that the new little Göllnitz identities enumerate partitions into distinct parts in which even-indexed (resp. odd-indexed) parts are even, and derive a refinement of the Gessel–Stanton identity that suggests a similar interpretation is possible. We study an associated system of q -difference equations to show that the Gessel–Stanton identity and its partner are actually two members of a three-element family.}, number={1-4}, journal={Advances in Applied Mathematics}, publisher={Elsevier BV}, author={Savage, Carla D. and Sills, Andrew V.}, year={2011}, month={Jan}, pages={563–575} }
 @article{beck_gessel_lee_savage_2010, title={Symmetrically constrained compositions}, volume={23}, ISSN={["1572-9303"]}, DOI={10.1007/s11139-010-9232-7}, abstractNote={Given integers a 1,a 2,…,a n , with a 1+a 2+⋅⋅⋅+a n ≥1, a symmetrically constrained composition λ 1+λ 2+⋅⋅⋅+λ n =M of M into n nonnegative parts is one that satisfies each of the n! constraints $\{\sum_{i=1}^{n}a_{i}\lambda_{\pi(i)}\geq 0:\pi \in S_{n}\}$ . We show how to compute the generating function of these compositions, combining methods from partition theory, permutation statistics, and lattice-point enumeration.}, number={1-3}, journal={RAMANUJAN JOURNAL}, author={Beck, Matthias and Gessel, Ira M. and Lee, Sunyoung and Savage, Carla D.}, year={2010}, month={Dec}, pages={355–369} }
 @article{shields_shields_savage_2009, title={An update on the middle levels problem}, volume={309}, ISSN={["0012-365X"]}, DOI={10.1016/j.disc.2007.11.010}, abstractNote={The middle levels problem is to find a Hamilton cycle in the middle levels, M2k+1, of the Hasse diagram of B2k+1 (the partially-ordered set of subsets of a 2k+1-element set ordered by inclusion). Previously, the best known, from [I. Shields, C.D. Savage, A Hamilton path heuristic with applications to the middle two levels problem, in: Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999), vol. 140, 1999], was that M2k+1 is Hamiltonian for all positive k through k=15. In this note we announce that M33 and M35 have Hamilton cycles. The result was achieved by an algorithmic improvement that made it possible to find a Hamilton path in a reduced graph (of complementary necklace pairs) having 129,644,790 vertices, using a 64-bit personal computer.}, number={17}, journal={DISCRETE MATHEMATICS}, author={Shields, Ian and Shields, Brendan J. and Savage, Carla D.}, year={2009}, month={Sep}, pages={5271–5277} }
 @article{iyer_dutta_savage_2009, title={Minimizing transceivers in optical path networks}, volume={8}, ISSN={["1536-5379"]}, DOI={10.1364/JON.8.000454}, abstractNote={The problem of routing traffic on multihop clear optical channels and deciding the virtual topology of optical channels to form on a physical network of fibers to minimize the cost of electronic switching equipment has become known as traffic grooming in optical networks. Traffic grooming is recognized as an important research area, because the joint opto-electric routing problem is a hard one, yet necessary because of the large cost of pure electronic switching. This problem has been shown to be NP-complete (nondeterminstic polynomial complete) even for very simple practical topologies such as a path network. In previous work, we have shown that at least the subproblem of routing traffic on a given virtual topology to minimize electronic switching (NP-hard for path networks with arbitrary traffic matrices) becomes polynomial when the traffic on the path is restricted to be egress traffic, that is, all traffic requests are destined for a single egress node. In that work, the objective was to minimize the raw OEO (opto-electro-optic) metric (number of bits electronically switched per second) totaled over all network nodes. Of late, it has become clear that electronic switching equipment cost is best counted in quantized units, e.g., in the number of transceiver interfaces at network nodes. In this paper, we consider the traffic grooming problem in unidirectional, WDM path networks with the goal of minimizing the number of transceivers. We conclusively show that the problem is NP-hard, even under the restriction of the egress traffic model. In the case of egress traffic, we give a simple heuristic that will never be worse than twice the optimal.}, number={5}, journal={JOURNAL OF OPTICAL NETWORKING}, author={Iyer, Prashant and Dutta, Rudra and Savage, Carla D.}, year={2009}, month={May}, pages={454–461} }
 @article{andrews_corteel_savage_2009, title={ON q-SERIES IDENTITIES ARISING FROM LECTURE HALL PARTITIONS}, volume={5}, ISSN={["1793-0421"]}, DOI={10.1142/S1793042109002134}, abstractNote={ In this paper, we highlight two q-series identities arising from the "five guidelines" approach to enumerating lecture hall partitions and give direct, q-series proofs. This requires two new finite corollaries of a q-analog of Gauss's second theorem. In fact, the method reveals stronger results about lecture hall partitions and anti-lecture hall compositions that are only partially explained combinatorially. }, number={2}, journal={INTERNATIONAL JOURNAL OF NUMBER THEORY}, author={Andrews, George E. and Corteel, Sylvie and Savage, Carla D.}, year={2009}, month={Mar}, pages={327–337} }
 @article{jiang_savage_2009, title={On the existence of symmetric chain decompositions in a quotient of the Boolean lattice}, volume={309}, ISSN={["1872-681X"]}, DOI={10.1016/j.disc.2007.11.036}, abstractNote={We highlight a question about binary necklaces, i.e., equivalence classes of binary strings under rotation. Is there a way to choose representatives of the n-bit necklaces so that the subposet of the Boolean lattice induced by those representatives has a symmetric chain decomposition? Alternatively, is the quotient of the Boolean lattice Bn, under the action of the cyclic group Zn, a symmetric chain order? The answer is known to be yes for all prime n and for composite n≤18, but otherwise the question appears to be open. In this note we describe how it suffices to focus on subposets induced by necklaces with periodic block codes, substantially reducing the size of the problem. We mention a motivating application: determining whether minimum-region rotationally symmetric independent families of n curves exist for all n.}, number={17}, journal={DISCRETE MATHEMATICS}, author={Jiang, Zongliang and Savage, Carla D.}, year={2009}, month={Sep}, pages={5278–5283} }
 @article{savage_yee_2008, title={Euler's partition theorem and the combinatorics of l-sequences}, volume={115}, ISSN={["0097-3165"]}, DOI={10.1016/j.jcta.2007.11.006}, abstractNote={Euler's partition theorem states that the number of partitions of an integer N into odd parts is equal to the number of partitions of N in which the ratio of successive parts is greater than 1. It was shown by Bousquet-Mélou and Eriksson in [M. Bousquet-Mélou, K. Eriksson, Lecture hall partitions II, Ramanujan J. 1 (2) (1997) 165–185] that a similar result holds when “odd parts” is replaced by “parts that are sums of successive terms of an ℓ -sequence” and the ratio “1” is replaced by a root of the characteristic polynomial of the ℓ -sequence. This generalization of Euler's theorem is intrinsically different from the many others that have appeared, as it involves a family of partitions constrained by the ratio of successive parts. In this paper, we provide a surprisingly simple bijection for this result, a question suggested by Richard Stanley. In fact, we give a parametrized family of bijections, that include, as special cases, Sylvester's bijection and a bijection for the lecture hall theorem. We introduce Sylvester diagrams as a way to visualize these bijections and deduce their properties. In proving the bijections, we uncover the intrinsic role played by the combinatorics of ℓ -sequences and use this structure to give a combinatorial characterization of the partitions defined by the ratio constraint. Several open questions suggested by this work are described.}, number={6}, journal={JOURNAL OF COMBINATORIAL THEORY SERIES A}, author={Savage, Carla D. and Yee, Ae Ja}, year={2008}, month={Aug}, pages={967–996} }
 @article{iyer_dutta_savage_2007, title={Complexity of path traffic grooming}, volume={6}, ISSN={["1536-5379"]}, DOI={10.1364/JON.6.001270}, abstractNote={Feature Issue on Transmission in Optically Transparent Core NetworksThe problem of efficiently designing lightpaths and routing traffic on them in hybrid electro-optic data communication networks so that optical pass-through is maximized and the electronic switching cost is minimized is known as traffic grooming and has been studied extensively. Traffic grooming is known to be an inherently difficult problem. It has been shown to be NP-complete even for path networks, a simple topology in which lightpath wavelength assignment is tractable. In this paper, we explore the borderline between tractability and intractability by considering grooming in unidirectional path networks in which all traffic requests are destined for a single egress node. Whether the complete grooming problem is NP-hard with this restriction is an open question. We show that at least the problem of routing traffic on a given virtual topology to minimize electronic switching (NP-hard for path networks with arbitrary traffic matrices) becomes polynomial on the egress model. We also show that in the egress model, if the capacity constraint is relaxed, the entire problem becomes polynomial. If, in addition, traffic requests are uniform, we provide an explicit combinatorial formula for the optimum solution as well as an algorithm that constructs a routing that achieves this optimum. For the case of finite capacity and unit traffic requests, we show how to polynomially find a feasible solution that is optimal under reasonable assumptions.}, number={11}, journal={JOURNAL OF OPTICAL NETWORKING}, author={Iyer, Prashant and Dutta, Rudra and Savage, Carla D.}, year={2007}, month={Nov}, pages={1270–1281} }
 @article{corteel_gessel_savage_wiif_2007, title={The joint distribution of descent and major index over restricted sets of permutations}, volume={11}, ISSN={["0219-3094"]}, DOI={10.1007/s00026-007-0325-y}, number={3-4}, journal={ANNALS OF COMBINATORICS}, author={Corteel, Sylvie and Gessel, Ira M. and Savage, Carla D. and Wiif, Herbert S.}, year={2007}, pages={375–386} }
 @article{savage_wilf_2006, title={Pattern avoidance in compositions and multiset permutations}, volume={36}, ISSN={["1090-2074"]}, DOI={10.1016/j.aam.2005.06.003}, abstractNote={We show that among the compositions of n into positive parts, the number g(n) that avoid a given pattern π of three letters is independent of π. We find the generating function of {g(n)}, and it shows that the sequence {g(n)} is not P-recursive. If S is a given multiset, we show that the number of permutations of S that avoid a pattern π of three letters is independent of π. Finally, we give a bijective proof of the fact that if M=1a1…kak is a given multiset then the number of permutations of M that avoid the pattern (123) is a symmetric function of the multiplicities a1,…,ak. The bijection uses the Greene–Kleitman symmetric chain decomposition of the Boolean lattice.}, number={2}, journal={ADVANCES IN APPLIED MATHEMATICS}, author={Savage, CD and Wilf, HS}, year={2006}, month={Feb}, pages={194–201} }
 @article{heber_savage_2005, title={Common intervals of trees}, volume={93}, ISSN={["1872-6119"]}, DOI={10.1016/j.ipl.2004.09.016}, abstractNote={In this survey, we review practical algorithms for graph-theoretic problems that are expressible in monadic second-order logic. Monadic second-order (MSO) logic allows quantifications over unary relations (sets) and can be used to express a host of useful graph properties such as connectivity, c-colorability (for a fixed c), Hamiltonicity and minor inclusion. A celebrated theorem in this area by Courcelle states that any graph problem expressible in MSO can be solved in linear time on graphs that admit a tree-decomposition of constant width. Courcelle’s Theorem has been used thus far as a theoretic tool to establish that linear-time algorithms exist for graph problems by demonstrating that the problem in question is expressible by an MSO formula. A straightforward implementation of the algorithm in the proof of Courcelle’s Theorem is useless as it runs into space-explosion problems even for small values of treewidth. Of late, there have been several attempts to circumvent these problems and we review some of these in this survey. This survey also introduces the reader to the notions of tree-decompositions and the basics of monadic second order logic.}, number={2}, journal={INFORMATION PROCESSING LETTERS}, author={Heber, S and Savage, CD}, year={2005}, month={Jan}, pages={69–74} }
 @article{killian_savage_2004, title={Antipodal gray codes}, volume={281}, ISSN={["0012-365X"]}, DOI={10.1016/j.disc.2003.07.012}, abstractNote={An n-bit Gray code is a circular listing of the 2n n-bit strings so that successive strings differ only in one bit position. An n-bit antipodal Gray code has the additional property that the complement of any string appears exactly n steps away in the list. The problem of determining for which values of n antipodal Gray codes can exist was posed by Hunter Snevily, who showed them to be possible for n=1,2,3, and 4. In this paper, we show they are not possible for odd n>3 or for n=6. However, we provide a recursive construction to prove existence when n is a power of 2. The question remains open for any even n>6 which is not a power of 2.}, number={1-3}, journal={DISCRETE MATHEMATICS}, author={Killian, CE and Savage, CD}, year={2004}, month={Apr}, pages={221–236} }
 @article{corteel_savage_2004, title={Lecture hall theorems, q-series and truncated objects}, volume={108}, ISSN={["1096-0899"]}, DOI={10.1016/j.jcta.2004.05.006}, abstractNote={We show here that the refined theorems for both lecture hall partitions and anti-lecture hall compositions can be obtained as straightforward consequences of two q -Chu Vandermonde identities, once an appropriate recurrence is derived. We use this approach to get new lecture hall-type theorems for truncated objects. The truncated lecture hall partitions are sequences ( λ 1 , … , λ k ) such that λ 1 n ⩾ λ 2 n - 1 ⩾ ⋯ ⩾ λ k n - k + 1 ⩾ 0 and we show that their generating function is ∑ m = 0 k n m q q m + 1 2 ( - q n - m + 1 ; q ) m ( q 2 n - m + 1 ; q ) m . From this, we are able to give a combinatorial characterization of truncated lecture hall partitions and new finite versions of refinements of Euler's theorem. The truncated anti-lecture hall compositions are sequences ( λ 1 , … , λ k ) such that λ 1 n - k + 1 ⩾ λ 2 n - k + 2 ⩾ ⋯ ⩾ λ k n ⩾ 0 . We show that their generating function is n k q ( - q n - k + 1 ; q ) k ( q 2 ( n - k + 1 ) ; q ) k , giving a finite version of a well-known partition identity. We give two different multivariate refinements of these new results: the q -calculus approach gives ( u , v , q ) -refinements, while a completely different approach gives odd / even ( x , y ) -refinements.}, number={2}, journal={JOURNAL OF COMBINATORIAL THEORY SERIES A}, author={Corteel, S and Savage, CD}, year={2004}, month={Nov}, pages={217–245} }
 @article{hitczenko_savage_2004, title={On the multiplicity of parts in a random composition of a large integer}, volume={18}, ISSN={["0895-4801"]}, DOI={10.1137/s0895480199363155}, abstractNote={In this paper we study the following question posed by H. S. Wilf: what is, asymptotically as $n\rightarrow \infty$, the probability that a randomly chosen part size in a random composition of an integer n has multiplicity m? More specifically, given positive integers n and m, suppose that a composition $\lambda$ of n is selected uniformly at random and then, out of the set of part sizes in $\lambda$, a part size j is chosen uniformly at random. Let $\P(A_n^{(m)})$ be the probability that j has multiplicity m. We show that for fixed m, $\P(A_n^{(m)}$) goes to 0 at the rate $1/\ln n$. A more careful analysis uncovers an unexpected result: $(\ln n)\P(A_n^{(m)})$ does not have a limit but instead oscillates around the value $1/m$ as $n\to\infty$. 
This work is a counterpart of a recent paper of Corteel, Pittel, Savage, and Wilf, who studied the same problem in the case of partitions rather than compositions.}, number={2}, journal={SIAM JOURNAL ON DISCRETE MATHEMATICS}, author={Hitczenko, PL and Savage, CD}, year={2004}, pages={418–435} }
 @article{corteel_savage_2004, title={Partitions and compositions defined by inequalities}, volume={8}, ISSN={["1572-9303"]}, DOI={10.1007/s11139-004-0144-2}, abstractNote={We consider sequences of integers (λ1,..., λ k ) defined by a system of linear inequalities λ i ≥ ∑ j>iaijλ j with integer coefficients. We show that when the constraints are strong enough to guarantee that all λ i are nonnegative, the generating function for the integer solutions of weight n has a finite product form $$\prod_{i} (1-q^{b_i})^{-1}$$ , where the b i are positive integers that can be computed from the coefficients of the inequalities. The results are proved bijectively and are used to give several examples of interesting identities for integer partitions and compositions. The method can be adapted to accommodate equalities along with inequalities and can be used to obtain multivariate forms of the generating function. We show how to extend the technique to obtain the generating function when the coefficients ai,i+1 are allowed to be rational, generalizing the case of lecture hall partitions. Our initial results were conjectured thanks to the Omega package (G.E. Andrews, P. Paule, and A. Riese, European J. Comb. 22(7) (2001), 887–904).}, number={3}, journal={RAMANUJAN JOURNAL}, author={Corteel, S and Savage, CD}, year={2004}, month={Sep}, pages={357–381} }
 @article{canfield_savage_wilf_2004, title={Regularly spaced subsums of integer partitions}, volume={115}, ISSN={["0065-1036"]}, DOI={10.4064/aa115-3-1}, abstractNote={For integer partitions $\lambda :n=a_1+...+a_k$, where $a_1\ge a_2\ge >...\ge a_k\ge 1$, we study the sum $a_1+a_3+...$ of the parts of odd index. We show that the average of this sum, over all partitions $\lambda$ of $n$, is of the form $n/2+(\sqrt{6}/(8\pi))\sqrt{n}\log{n}+c_{2,1}\sqrt{n}+O(\log{n}).$ More generally, we study the sum $a_i+a_{m+i}+a_{2m+i}+...$ of the parts whose indices lie in a given arithmetic progression and we show that the average of this sum, over all partitions of $n$, is of the form $n/m+b_{m,i}\sqrt{n}\log{n}+c_{m,i}\sqrt{n}+O(\log{n})$, with explicitly given constants $b_{m,i},c_{m,i}$. Interestingly, for $m$ odd and $i=(m+1)/2$ we have $b_{m,i}=0$, so in this case the error term is of lower order. The methods used involve asymptotic formulas for the behavior of Lambert series and the Zeta function of Hurwitz. 
We also show that if $f(n,j)$ is the number of partitions of $n$ the sum of whose parts of even index is $j$, then for every $n$, $f(n,j)$ agrees with a certain universal sequence, Sloane's sequence \texttt{#A000712}, for $j\le n/3$ but not for any larger $j$.}, number={3}, journal={ACTA ARITHMETICA}, author={Canfield, ER and Savage, CD and Wilf, HS}, year={2004}, pages={205–216} }
 @article{griggs_killian_savage_2004, title={Venn diagrams and symmetric chain decompositions in the Boolean lattice}, volume={11}, number={1}, journal={Electronic Journal of Combinatorics}, author={Griggs, J. and Killian, C. E. and Savage, C. D.}, year={2004} }
 @article{corteel_savage_2003, title={Anti-lecture hall compositions}, volume={263}, DOI={10.1016/S0012-365X(02)00768-9}, abstractNote={We study the set Ak of integer sequences λ=(λ1,…,λk), defined byλ11⩾λ22⩾⋯λkk⩾0and show that the generating function is∑λ∈Akq|λ|=∏i=1k1+qi1−qi+1,where |λ|=λ1+⋯+λk. We establish this by giving a bijective proof of the following refinement:∑λ∈Akq|λ|u|⌊λ⌋|vo(⌊λ⌋)=∏i=1k1+uvqi1−u2qi+1.To our knowledge this is a new result that complements the family of the Lecture Hall Theorems (Ramanujan J. 1(1,2) (1997) 101, 165; J. Combin. Theory Ser. A 86(1) (1999) 63).}, number={1-3}, journal={Discrete Mathematics}, author={Corteel, S. and Savage, Carla}, year={2003}, pages={275–280} }
 @article{savage_shields_west_2003, title={On the existence of Hamiltonian paths in the cover graph of M(n)}, volume={262}, ISSN={["0012-365X"]}, DOI={10.1016/S0012-365X(02)00503-4}, abstractNote={The poset M(n) has as its elements the n-tuples of integers a=(a1,a2,…,an) satisfying 0=a1=⋯=aj<aj+1<⋯<an⩽n for some j,0⩽j⩽n. The order relation is defined by a⩽b iff ai⩽bi for 1⩽i⩽n. We show that the cover graph of M(n) has a Hamiltonian path if and only if (n+12) is odd and n≠5.}, number={1-3}, journal={DISCRETE MATHEMATICS}, author={Savage, CD and Shields, I and West, DB}, year={2003}, month={Feb}, pages={241–252} }
 @article{hitczenko_rousseau_savage_2002, title={A generating functionology approach to a problem of Wilf}, volume={142}, ISSN={["0377-0427"]}, DOI={10.1016/S0377-0427(01)00462-9}, abstractNote={Wilf posed the following problem: determine asymptotically as $n\to\infty$ the probability that a randomly chosen part size in a randomly chosen composition of n has multiplicity m. One solution of this problem was given by Hitczenko and Savage. In this paper, we study this question using the techniques of generating functions and singularity analysis.}, number={1}, journal={JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS}, author={Hitczenko, P and Rousseau, C and Savage, CD}, year={2002}, month={May}, pages={107–114} }
 @article{burstein_corteel_postnikov_savage_2002, title={A lattice path approach to counting partitions with minimum rank t}, volume={249}, ISSN={["0012-365X"]}, DOI={10.1016/S0012-365X(01)00225-4}, abstractNote={In this paper, we give a combinatorial proof via lattice paths of the following result due to Andrews and Bressoud: for t⩽1, the number of partitions of n with all successive ranks at least t is equal to the number of partitions of n with no part of size 2−t. The identity is a special case of a more general theorem proved by Andrews and Bressoud using a sieve.}, number={1-3}, journal={DISCRETE MATHEMATICS}, author={Burstein, A and Corteel, S and Postnikov, A and Savage, CD}, year={2002}, month={Apr}, pages={31–39} }
 @article{frank_savage_sellers_2002, title={On the number of graphical forest partitions}, volume={65}, number={2002 Oct}, journal={Ars Combinatoria}, author={Frank, D. A. and Savage, C. D. and Sellers, J. A.}, year={2002}, pages={33–37} }
 @article{jing_misra_savage_2001, title={On multi-color partitions and the generalized Rogers-Ramanujan identities}, volume={3}, ISSN={["0219-1997"]}, DOI={10.1142/S0219199701000482}, abstractNote={ Basil Gordon, in the sixties, and George Andrews, in the seventies, generalized the Rogers–Ramanujan identities to higher moduli. These identities arise in many areas of mathematics and mathematical physics. One of these areas is representation theory of infinite dimensional Lie algebras, where various known interpretations of these identities have led to interesting applications. Motivated by their connections with Lie algebra representation theory, we give a new interpretation of a sum related to generalized Rogers–Ramanujan identities in terms of multi-color partitions. }, number={4}, journal={COMMUNICATIONS IN CONTEMPORARY MATHEMATICS}, author={Jing, NH and Misra, KC and Savage, CD}, year={2001}, month={Nov}, pages={533–548} }
 @article{chinburg_savage_wilf_1999, title={Combinatorial families that are exponentially far from being listable in Gray code sequence}, volume={351}, ISSN={["0002-9947"]}, DOI={10.1090/S0002-9947-99-02229-1}, abstractNote={Let S(n) be a collection of subsets of {1, ..., n}. In this paper we study numerical obstructions to the existence of orderings of S(n) for which the cardinalities of successive subsets satisfy congruence conditions. Gray code orders provide an example of such orderings. We say that an ordering of S(n) is a Gray code order if successive subsets differ by the adjunction or deletion of a single element of {1, . . . , n}. The cardinalities of successive subsets in a Gray code order must alternate in parity. It follows that if d(S(n)) is the difference between the number of elements of S(n) having even (resp. odd) cardinality, then |d(S(n))| − 1 is a lower bound for the cardinality of the complement of any subset of S(n) which can be listed in Gray code order. For g ≥ 2, the collection B(n, g) of g-blockfree subsets of {1, . . . , n} is defined to be the set of all subsets S of {1, . . . , n} such that |a − b| ≥ g if a, b ∈ S and a 6= b. We will construct a Gray code order for B(n, 2). In contrast, for g > 2 we find the precise (positive) exponential growth rate of d(B(n, g)) with n as n →∞. This implies B(n, g) is far from being listable in Gray code order if n is large. Analogous results for other kinds of orderings of subsets of B(n, g) are proved using generalizations of d(B(n, g)) . However, we will show that for all g, one can order B(n, g) so that successive elements differ by the adjunction and/or deletion of an integer from {1, . . . , n}. We show that, over an A-letter alphabet, the words of length n which contain no block of k consecutive letters cannot, in general, be listed so that successive words differ by a single letter. However, if k > 2 and A > 2 or if k = 2 and A > 3, such a listing is always possible.}, number={1}, journal={TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY}, author={Chinburg, T and Savage, CD and Wilf, HS}, year={1999}, month={Jan}, pages={379–402} }
 @article{corteel_pittel_savage_wilf_1999, title={On the multiplicity of parts in a random partition}, volume={14}, ISSN={["1042-9832"]}, DOI={10.1002/(SICI)1098-2418(199903)14:2<185::AID-RSA4>3.0.CO;2-F}, abstractNote={Let λ be a partition of an integer n chosen uniformly at random among all such partitions. Let s(λ) be a part size chosen uniformly at random from the set of all part sizes that occur in λ. We prove that, for every fixed m≥1, the probability that s(λ) has multiplicity m in λ approaches 1/(m(m+1)) as n→∞. Thus, for example, the limiting probability that a random part size in a random partition is unrepeated is 1/2. In addition, (a) for the average number of different part sizes, we refine an asymptotic estimate given by Wilf, (b) we derive an asymptotic estimate of the average number of parts of given multiplicity m, and (c) we show that the expected multiplicity of a randomly chosen part size of a random partition of n is asymptotic to (log n)/2. The proofs of the main result and of (c) use a conditioning device of Fristedt. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 185–197, 1999}, number={2}, journal={RANDOM STRUCTURES & ALGORITHMS}, author={Corteel, S and Pittel, B and Savage, CD and Wilf, HS}, year={1999}, month={Mar}, pages={185–197} }
 @article{corteel_savage_venkatraman_1998, title={A bijection for partitions with all ranks at least t}, volume={83}, ISSN={["0097-3165"]}, DOI={10.1006/jcta.1998.2873}, abstractNote={It follows from the work of Andrews and Bressoud that fort?1, the number of partitions ofnwith all successive ranks at leasttis equal to the number of partitions ofnwith no part of size 2?t. We give a simple bijection for this identity which generalizes a result of Cheema and Gordon for 2-rowed plane partitions. The bijection yields several refinements of the identity when the partition counts are parametrized by the number of parts and/or the size of the Durfee rectangle. In addition, it gives an interpretation of the difference of (shifted) successive Gaussian polynomials which we relate to other interpretations of Andrews and Fishel.}, number={2}, journal={JOURNAL OF COMBINATORIAL THEORY SERIES A}, author={Corteel, S and Savage, CD and Venkatraman, R}, year={1998}, month={Aug}, pages={202–220} }
 @article{corteel_savage_wilf_zeilberger_1998, title={A pentagonal number sieve}, volume={82}, ISSN={["0097-3165"]}, DOI={10.1006/jcta.1997.2846}, abstractNote={We prove a general “pentagonal sieve” theorem that has corollaries such as the following. First, the number of pairs of partitions of n that have no parts in common isp(n)2?p(n?1)2?p(n?2)2+p(n?5)2+p(n?7)2??.Second, if two unlabeled rooted forests of the same number of vertices are chosen i.u.a.r., then the probability that they have no common tree is .8705? . Third, iff,gare two monic polynomials of the same degree over the fieldGF(q), then the probability thatf,gare relatively prime is 1?1/q. We give explicit involutions for the pentagonal sieve theorem, generalizing earlier mappings found by Bressoud and Zeilberger.}, number={2}, journal={JOURNAL OF COMBINATORIAL THEORY SERIES A}, author={Corteel, S and Savage, CD and Wilf, HS and Zeilberger, D}, year={1998}, month={May}, pages={186–192} }
 @article{nolan_savage_wilf_1998, title={Basis partitions}, volume={179}, ISSN={["0012-365X"]}, DOI={10.1016/S0012-365X(97)00101-5}, abstractNote={We study basis partitions , introduced by Hansraj Gupta in 1978. For this family of partitions, we give a recurrence, a generating function, identities relating basis partitions to more familiar families of partitions, and a new characterization of basis partitions.}, number={1-3}, journal={DISCRETE MATHEMATICS}, author={Nolan, JM and Savage, CD and Wilf, HS}, year={1998}, month={Jan}, pages={277–283} }
 @article{canfield_corteel_savage_1998, title={Durfee polynomials}, volume={5}, number={1, Research paper 32}, journal={Electronic Journal of Combinatorics}, author={Canfield, E. R. and Corteel, S. and Savage, C. D.}, year={1998}, pages={1–21} }
 @article{nolan_sivaraman_savage_tiwari_1998, title={Graphical basis partitions}, volume={14}, ISSN={["0911-0119"]}, DOI={10.1007/s003730050029}, abstractNote={A partition of an integer n is graphical if it is the degree sequence of a simple, undirected graph. It is an open question whether the fraction of partitions of n which are graphical approaches 0 as n approaches infinity. A partition π is basic if the number of dots in its Ferrers graph is minimum among all partitions with the same rank vector as π. In this paper, we investigate graphical partitions via basis partitions. We show how to efficiently count and generate graphical basis partitions and how to use them to count graphical partitions. We give empirical evidence which leads us to conjecture that, as n approaches infinity, the fraction of basis partitions of n which are graphical approaches the same limit as the fraction of all partitions of n which are graphical.}, number={3}, journal={GRAPHS AND COMBINATORICS}, author={Nolan, JM and Sivaraman, V and Savage, CD and Tiwari, PK}, year={1998}, pages={241–261} }
 @article{savage_zhang_1998, title={The connectivity of acyclic orientation graphs}, volume={184}, ISSN={["0012-365X"]}, DOI={10.1016/S0012-365X(97)00201-X}, abstractNote={The acyclic orientation graph, AO(G), of an undirected graph, G, is the graph whose vertices are the acyclic orientations of G and whose edges are the pairs of orientations differing only by the reversal of one edge. Edelman (1984) has observed that it follows from results on polytopes that when G is simple, the connectivity of AO(G) is at least n − c, where n is the number of vertices and c is the number of components of G. In this paper we give a simple graph-theoretic proof of this fact. Our proof uses a result of independent interest. We establish that if H is a triangle-free graph with minimum degree at least k, and the graph obtained by contracting the edges of a matching in H is k-connected, then H is k-connected. The connectivity bound on AO(G) is tight for various graphs including Kn, Kp,q, and trees. Applications and extensions are discussed, as well as the connection with polytopes.}, number={1-3}, journal={DISCRETE MATHEMATICS}, author={Savage, CD and Zhang, CQ}, year={1998}, month={Apr}, pages={281–287} }
 @misc{savage_1997, title={A survey of combinational Gray codes}, volume={39}, ISSN={["1095-7200"]}, DOI={10.1137/S0036144595295272}, abstractNote={The term combinatorial Gray code was introduced in 1980 to refer to any method for generating combinatorial objects so that successive objects differ in some prespecified, small way. This notion generalizes the classical binary reflected Gray code scheme for listing n-bit binary numbers so that successive numbers differ in exactly one bit position, as well as work in the 1960s and 1970s on minimal change listings for other combinatorial families, including permutations and combinations. 
The area of combinatorial Gray codes was popularized by Herbert Wilf in his invited address at the SIAM Conference on Discrete Mathematics in 1988 and his subsequent SIAM monograph [Combinatorial Algorithms: An Update, 1989] in which he posed some open problems and variations on the theme. This resulted in much recent activity in the area, and most of the problems posed by Wilf are now solved. 
In this paper, we survey the area of combinatorial Gray codes, describe recent results, variations, and trends, and highlight some open problems.}, number={4}, journal={SIAM REVIEW}, author={Savage, C}, year={1997}, month={Dec}, pages={605–629} }
 @article{barnes_savage_1997, title={Efficient generation of graphical partitions}, volume={78}, ISSN={["0166-218X"]}, DOI={10.1016/s0166-218x(97)00022-x}, abstractNote={Given a positive even integer n, we show how to generate the set G(n) of graphical partitions of n, that is, those partitions of n which correspond to the degree sequences of simple, undirected graphs. The algorithm is based on a recurrence for G(n), and the total time used by the algorithm, independent of output, is O(¦G(n)¦), which is constant average time per graphical partition. This is the first algorithm shown to achieve such efficiency for generating G(n) and the direct approach differs from earlier ‘generate and reject’ schemes and the ‘interval/gap’ approach.}, number={1-3}, journal={DISCRETE APPLIED MATHEMATICS}, author={Barnes, TM and Savage, CD}, year={1997}, month={Oct}, pages={17–26} }
 @inbook{dutta_savage, title={A Note on the complexity of converter placement supporting broadcast in WDM optical networks}, ISBN={0971625336}, booktitle={2005 International Conference on Telecommunication Systems, Modeling and Analysis}, author={Dutta, R. and Savage, C.}, pages={23–31} }
 @inbook{iyer_dutta_savage, title={On the complexity of path traffic grooming.}, ISBN={0780392779}, booktitle={Proceedings of the Second International IEEE/Create-net workshop on traffic grooming}, publisher={Los Alamitos, CA: IEEE Computer Society}, author={Iyer, P. and Dutta, R. and Savage, C. D.}, pages={295–301} }