Search

For $0\leq k\leq n-1$, we introduce a family of $k$-skeletal paths which are counted by the $n$-th Catalan number for each $k$, and specialize to Dyck paths when $k=n-1$. We similarly introduce $k$-skeletal parking functions which are equinumerous with the spanning trees on $n+1$ vertices for each $k$, and specialize to classical parking functions for $k=n-1$. The preceding constructions are generalized to paths lying in a trapezoid with base $c > 0$ and southeastern diagonal of slope $1/m$; $c$ and $m$ need not be integers. We give bijections among these families when $k$ varies with $m$ and $c$ fixed. Our constructions are motivated by chip firing and have connections to combinatorial representation theory and tropical geometry., Comment: 29 pages, 9 figures

Richard Stanley defined the chromatic symmetric function $X_G$ of a graph $G$ and asked whether there are non-isomorphic trees $T$ and $U$ with $X_T=X_U$. We study variants of the chromatic symmetric function for rooted graphs, where we require the root vertex to either use or avoid a specified color. We present combinatorial identities and recursions satisfied by these rooted chromatic polynomials, explain their relation to pointed chromatic functions and rooted $U$-polynomials, and prove three main theorems. First, for all non-empty connected graphs $G$, Stanley's polynomial $X_G(x_1,\ldots,x_N)$ is irreducible in $\mathbb{Q}[x_1,\ldots,x_N]$ for all large enough $N$. The same result holds for our rooted variant where the root node must avoid a specified color. We prove irreducibility by a novel combinatorial application of Eisenstein's Criterion. Second, we prove the rooted version of Stanley's Conjecture: two rooted trees are isomorphic as rooted graphs if and only if their rooted chromatic polynomials are equal. In fact, we prove that a one-variable specialization of the rooted chromatic polynomial (obtained by setting $x_0=x_1=q$, $x_2=x_3=1$, and $x_n=0$ for $n>3$) already distinguishes rooted trees. Third, we answer a question of Pawlowski by providing a combinatorial interpretation of the monomial expansion of pointed chromatic functions., Comment: 21 pages; v2: added a short algebraic proof to Theorem 2 (now Theorem 15), we also answer a question of Pawlowski about monomial expansions; v3: added additional one-variable specialization results, simplified main proofs

Creation operators act on symmetric functions to build Schur functions, Hall--Littlewood polynomials, and related symmetric functions one row at a time. Haglund, Morse, Zabrocki, and others have studied more general symmetric functions $H_{\alpha}$, $C_{\alpha}$, and $B_{\alpha}$ obtained by applying any sequence of creation operators to $1$. We develop new combinatorial models for the Schur expansions of these and related symmetric functions using objects called abacus-histories. These formulas arise by chaining together smaller abacus-histories that encode the effect of an individual creation operator on a given Schur function. We give a similar treatment for operators such as multiplication by $h_m$, $h_m^{\perp}$, $\omega$, etc., which serve as building blocks to construct the creation operators. We use involutions on abacus-histories to give bijective proofs of properties of the Bernstein creation operator and Hall-Littlewood polynomials indexed by three-row partitions., Comment: 23 pages, 11 figures

We introduce simulated packing and cracking as a technique for evaluating partisan-gerrymandering measures. We apply it to historical congressional and legislative elections to evaluate four measures: partisan bias, declination, efficiency gap, and mean-median difference. While the efficiency gap recognizes simulated packing and cracking in a completely predictable manner (a fact that follows immediately from the efficiency gap's definition) and the declination does a very good job of recording simulated packing and cracking, we conclude that both of the other two measures record it poorly. This deficiency is especially notable given the frequent use of such measures in outlier analyses., Comment: The SPC technique was used in arXiv:1707.08681 for the purpose of estimating seats shifts due to gerrymandering. There is overlap with Section 2.1 of that paper. 18 pages, 6 figures, 1 table. Ver 2: Added ref. to 2014 work of McGhee that uses the basic idea of this technique. Ver 3: Rewrote intro and discussion; added appendix

We propose a new graphical format for instant-runoff voting election results. We call this proposal an "accumulation chart." This model, a modification of standard bar charts, is easy to understand, clearly indicates the winner, depicts the instant-runoff algorithm, and summarizes the votes cast. Moreover, it includes the pedigree of each accumulated vote and gives a clear depiction of candidates' coalitions., Comment: to appear in Notices of the AMS

The actions of packing and cracking are central to the construction of gerrymandered district plans. The US Supreme Court opinion in Gill v. Whitford makes clear that vote dilution arguments require showing that individual voters have been packed or cracked. In this article we provide precise definitions of what it means for a voter to be packed or cracked. These definitions, which depend crucially on the existence of at least one comparator plan, are illustrated using a simple hypothetical example. We also explore who might be considered packed or cracked for congressional plans in Maryland and North Carolina, and for the current state assembly plan in Wisconsin., Comment: 17 pages, 9 figures; added analyses of Wisconsin and North Carolina plans using simulations generated by other researchers; added section on relevant literature

We compare and contrast fourteen measures that have been proposed for the purpose of quantifying partisan gerrymandering. We consider measures that, rather than examining the shapes of districts, utilize only the partisan vote distribution among districts. The measures considered are two versions of partisan bias; the efficiency gap and several of its variants; the mean-median difference and the equal vote weight standard; the declination and one variant; and the lopsided-means test. Our primary means of evaluating these measures is a suite of hypothetical elections we classify from the start as fair or unfair. We conclude that the declination is the most successful measure in terms of avoiding false positives and false negatives on the elections considered. We include in an appendix the most extreme outliers for each measure among historical congressional and state legislative elections., Comment: 21 pages + 12-page appendix, 5 figures, 4 tables. Changes from v2: Some material removed and some clarifying remarks added

The declination is a quantitative method for identifying possible partisan gerrymanders by analyzing vote distributions. In this expository note we explain and motivate the definition of the declination. The minimal computer code required for computing the declination is included. We end by computing its value on several recent elections., Comment: 8 pages, 11 figures, python code, introduction to work in arXiv:1705.09393

Using the recently introduced declination function, we estimate the net number of seats won in the US House of Representatives due to asymmetries in vote distributions. Such asymmetries can arise from combinations of partisan gerrymandering and inherent geographic advantage. Our estimates show significant biases in favor of the Democrats prior to the mid 1990s and significant biases in favor of Republicans since then. We find net differences of 28, 20 and 25 seats in favor of the Republicans in the years 2012, 2014 and 2016, respectively. The validity of our results is supported by the technique of simulated packing and cracking. We also use this technique to show that the presidential-vote logistic regression model is insensitive to the packing and cracking by which partisan gerrymanders are achieved., Comment: 18 pages, 9 figures. Revisions: Emphasized fact that S-declination measures asymmetry in vote distribution and cannot account directly for geographic clustering; added "greedy" packing/cracking algorithm; added paragraph on simulations; other minor edits and corrections

To assess the presence of gerrymandering, one can consider the shapes of districts or the distribution of votes. The "efficiency gap," which does the latter, plays a central role in a 2016 federal court case on the constitutionality of Wisconsin's state legislative district plan. Unfortunately, however, the efficiency gap reduces to proportional representation, an expectation that is not a constitutional right. We present a new measure of partisan asymmetry that does not rely on the shapes of districts, is simple to compute, is provably related to the "packing and cracking" integral to gerrymandering, and that avoids the constitutionality issue presented by the efficiency gap. In addition, we introduce a generalization of the efficiency gap that also avoids the equivalency to proportional representation. We apply the first function to US congressional and state legislative plans from recent decades to identify candidate gerrymanders., Comment: 32 pages, 4 tables, 11 figures

We give a simple construction of an orthogonal basis for the space of m by n matrices with row and column sums equal to zero. This vector space corresponds to the affine space naturally associated with the Birkhoff polytope, contingency tables and Latin squares. We also provide orthogonal bases for the spaces underlying magic squares and Sudoku boards. Our construction combines the outer (i.e., tensor or dyadic) product on vectors with certain rooted, vector-labeled, binary trees. Our bases naturally respect the decomposition of a vector space into centrosymmetric and skew-centrosymmetric pieces; the bases can be easily modified to respect the usual matrix symmetry and skew-symmetry as well., Comment: 14 pages, 2 figures

We define a family of maps on lattice paths, called sweep maps, that assign levels to each step in the path and sort steps according to their level. Surprisingly, although sweep maps act by sorting, they appear to be bijective in general. The sweep maps give concise combinatorial formulas for the q,t-Catalan numbers, the higher q,t-Catalan numbers, the q,t-square numbers, and many more general polynomials connected to the nabla operator and rational Catalan combinatorics. We prove that many algorithms that have appeared in the literature (including maps studied by Andrews, Egge, Gorsky, Haglund, Hanusa, Jones, Killpatrick, Krattenthaler, Kremer, Orsina, Mazin, Papi, Vaille, and the present authors) are all special cases of the sweep maps or their inverses. The sweep maps provide a very simple unifying framework for understanding all of these algorithms. We explain how inversion of the sweep map (which is an open problem in general) can be solved in known special cases by finding a "bounce path" for the lattice paths under consideration. We also define a generalized sweep map acting on words over arbitrary alphabets with arbitrary weights, which is also conjectured to be bijective., Comment: 21 pages; full version of FPSAC 2014 extended abstract

The classical parking functions, counted by the Cayley number (n+1)^(n-1), carry a natural permutation representation of the symmetric group S_n in which the number of orbits is the n'th Catalan number. In this paper, we will generalize this setup to rational parking functions indexed by a pair (a,b) of coprime positive integers. We show that these parking functions, which are counted by b^(a-1), carry a permutation representation of S_a in which the number of orbits is a rational Catalan number. We compute the Frobenius characteristic of the S_a-module of (a,b)-parking functions. Next we propose a combinatorial formula for a q-analogue of the rational Catalan numbers and relate this formula to a new combinatorial model for q-binomial coefficients. Finally, we discuss q,t-analogues of rational Catalan numbers and parking functions (generalizing the shuffle conjecture for the classical case) and present several conjectures., Comment: 29 pages, 12 figures

The random chemistry algorithm of Kauffman can be used to determine an unknown subset S of a fixed set V. The algorithm proceeds by zeroing in on S through a succession of nested subsets V=V_0,V_1,...,V_m=S. In Kauffman's original algorithm, the size of each V_i is chosen to be half the size of V_{i-1}. In this paper we determine the optimal sequence of sizes so as to minimize the expected run time of the algorithm., Comment: 7 pages, 3 figures; added one reference, minor typos fixed

The game of memory is played with a deck of n pairs of cards. The cards in each pair are identical. The deck is shuffled and the cards laid face down. A move consists of flipping over first one card then another. The cards are removed from play if they match. Otherwise, they are flipped back over and the next move commences. A game ends when all pairs have been matched. We determine that, when the game is played optimally, as n tends to infinity: 1) The expected number of moves is (3 - 2 ln 2)n + 7/8 - 2 ln 2 (approximately 1.61 n), 2) The expected number of times two matching cards are unwittingly flipped over is ln 2, and 3) The expected number of flips until two matching cards have been seen is asymptotically sqrt{pi n}., Comment: 16 pages

In Martin Gardner's October, 1976 Mathematical Games column in Scientific American, he posed the following problem: "What is the smallest number of [queens] you can put on a board of side n such that no [queen] can be added without creating three in a row, a column, or a diagonal?" We use the Combinatorial Nullstellensatz to prove that this number is at least n, except in the case when n is congruent to 3 modulo 4, in which case one less may suffice. A second, more elementary proof is also offered in the case that n is even., Comment: 11 pages; lower bound in main theorem corrected to n-1 (from n) in the case of n congruent to 3 mod 4, minor edits, added journal reference

We introduce explicit combinatorial interpretations for the coefficients in some of the transition matrices relating to skew Hall-Littlewood polynomials P_lambda/mu(x;t) and Hivert's quasisymmetric Hall-Littlewood polynomials G_gamma(x;t). More specifically, we provide: 1) the G-expansions of the Hall-Littlewood polynomials P_lambda, the monomial quasisymmetric polynomials M_alpha, the quasisymmetric Schur polynomials S_alpha, and the peak quasisymmetric functions K_alpha; 2) an expansion of P_lambda/mu in terms of the F_alpha's. The F-expansion of P_lambda/mu is facilitated by introducing starred tableaux., Comment: 28 pages; added brief discussion of the Hall-Littlewood Q', typos corrected, added references in response to referee suggestions

Every word has a shape determined by its image under the Robinson-Schensted-Knuth correspondence. We show that when a word w contains a separable (i.e., 3142- and 2413-avoiding) permutation \sigma\ as a pattern, the shape of w contains the shape of \sigma. As an application, we exhibit lower bounds for the lengths of supersequences of sets containing separable permutations., Comment: 8 pages, 2 figures. Changed emphasis and structure towards shapes containment based on referee's suggestions

We study equivalence classes relating to the Kazhdan-Lusztig mu(x,w) coefficients in order to help explain the scarcity of distinct values. Each class is conjectured to contain a "crosshatch" pair. We also compute the values attained by mu(x,w) for the permutation groups S_10 and S_11., Comment: 13 pages, 6 figures

J. J. Sylvester's four-point problem asks for the probability that four points chosen uniformly at random in the plane have a triangle as their convex hull. Using a combinatorial classification of points in the plane due to Goodman and Pollack, we generalize Sylvester's problem to one involving reduced expressions for the long word in the symmetric group. We conjecture an answer of 1/4 for this new version of the problem., Comment: 5 pages, 4 figures. Reference added to fact that the main conjecture has been proven by O. Angel and A. E. Holroyd, Electron. J. Combin., 17(1):Note 23, 7, 2010. Additional references also added

We conjecture a combinatorial formula for the monomial expansion of the image of any Schur function under the Bergeron-Garsia nabla operator. The formula involves nested labeled Dyck paths weighted by area and a suitable "diagonal inversion" statistic. Our model includes as special cases many previous conjectures connecting the nabla operator to quantum lattice paths. The combinatorics of the inverse Kostka matrix leads to an elementary proof of our proposed formula when q=1. We also outline a possible approach for proving all the extant nabla conjectures that reduces everything to the construction of sign-reversing involutions on explicit collections of signed, weighted objects., Comment: 23 pages

Garsia-Haiman modules are quotient rings in variables X_n={x_1, x_2, ..., x_n} and Y_n=y_1, y_2, ..., y_n} that generalize the quotient ring C[X_n]/I, where I is the ideal generated by the elementary symmetric polynomials e_j(X_n) for 1 <= j <= n. A bitableaux basis for the Garsia-Haiman modules of hollow type is constructed. Applications of this basis to representation theory and other related polynomial spaces are considered., Comment: 26 pages

Consider lattice paths in Z^2 taking unit steps north (N) and east (E). Fix positive integers r,s and put an equivalence relation on points of Z^2 by letting v,w be equivalent if v - w = m (r,s) for some m in Z. Call a lattice path valid if whenever it enters a point v with an E-step, then any further points of the path in the class of v are also entered with an E-step. Loehr and Warrington conjectured that the number of valid paths from (0,0) to (nr,ns) is (r+s choose r)^n. We prove this conjecture when s = 2., Comment: 9 pages, 6 figures

We study the determinant of the pxp circulant matrix whose first row is (1,-x,0,...,0,-y,0,...,0), the -y being in position q+1. The coefficients of this polynomial are integers that count certain classes of permutations. We show that all of the permutations that contribute to a fixed monomial x^ry^s have the same sign, and we determine that sign. We prove that a monomial x^ry^s appears if and only if p divides r+sq. Finally, we show that the size of the largest coefficient of the monomials that appear grows exponentially with p. We do this by proving that the permanent of the circulant whose first row is (1,1,0,...,0,1,0,...,0) is the sum of the absolute values of the coefficients of the monomials in the original determinant., Comment: 16 pages; 3 figures

The act of a person juggling can be viewed as a Markov process if we assume that the juggler throws to random heights. I make this association for the simplest reasonable model of random juggling and compute the steady state probabilities in terms of the Stirling numbers of the second kind. I also explore several alternate models of juggling., Comment: 11 pages, 5 eps figures. psfrag

For permutations x and w, let mu(x,w) be the coefficient of highest possible degree in the Kazhdan-Lusztig polynomial P_{x,w}. It is well-known that the coefficients mu(x,w) arise as the edge labels of certain graphs encoding the representations of S_n. The 0-1 Conjecture states that the mu(x,w) are either 0 or 1. We present two counterexamples to this conjecture, the first in S_16, for which x and w are in the same left cell, and the second in S_10. The proof of the counterexample in S_16 relies on computer calculations., Comment: 15 pages, 4 figures; code for computer calculations included in source package

Let w_0 denote the permutation [n,n-1,...,2,1]. We give two new explicit formulae for the Kazhdan-Lusztig polynomials P_{w_0w,w_0x} in S_n when x is a maximal element in the singular locus of the Schubert variety X_w. To do this, we utilize a standard identity that relates P_{x,w} and P_{w_0w,w_0x}., Comment: 9 pages, 4 figures

We give an explicit combinatorial description of the irreducible components of the singular locus of the Schubert variety X_w for any element w in S_n. Our description of the irreducible components is computationally more efficient (O(n^6)) than the previously best known algorithms. This result proves a conjecture of Lakshmibai and Sandhya regarding this singular locus. Furthermore, we give simple formulas for calculating the Kazhdan-Lusztig polynomials at the maximum singular points., Comment: 50 pages, 50 figures

We give a combinatorial formula for the Kazhdan-Lusztig polynomials $P_{x,w}$ in the symmetric group when $w$ is a 321-hexagon-avoiding permutation. Our formula, which depends on a combinatorial framework developed by Deodhar, can be expressed in terms of a simple statistic on all subexpressions of any fixed reduced expression for $w$. We also show that $w$ being 321-hexagon-avoiding is equivalent to several other conditions, such as the Bott-Samelson resolution of the Schubert variety $X_w$ being small. We conclude with a simple method for completely determining the singular locus of $X_w$ when $w$ is 321-hexagon-avoiding., Comment: 24 pages, 18 figures, AMS-LaTeX