bluuebunny/crossref_metadata_2025 huggingface dataset:
Motzkin Paths and Reduced Decompositions for Permutations with Forbidden Patterns
Authors: Chen William Y. C. , Deng Yu-Ping , Yang Laura L. M.
Published: January 2020

We obtain a characterization of $(321, 3\bar{1}42)$-avoiding permutations in terms of their canonical reduced decompositions. This characterization is used to construct a bijection for a recent result that the number of $(321,3\bar{1}42)$-avoiding permutations of length $n$ equals the $n$-th Motzkin number, due to Gire, and further studied by Barcucci, Del Lungo, Pergola, Pinzani and Guibert. Similarly, we obtain a characterization of $(231,4\bar{1}32)$-avoiding permutations. For these two classes, we show that the number of descents of a permutation equals the number of up steps on the corresponding Motzkin path. Moreover, we find a relationship between the inversion number of a permutation and the area of the corresponding Motzkin path.
Four Classes of Pattern-Avoiding Permutations Under One Roof: Generating Trees with Two Labels
Authors: Bousquet-Mélou Mireille
Published: January 2020

Many families of pattern-avoiding permutations can be described by a generating tree in which each node carries one integer label, computed recursively via a rewriting rule. A typical example is that of $123$-avoiding permutations. The rewriting rule automatically gives a functional equation satisfied by the bivariate generating function that counts the permutations by their length and the label of the corresponding node of the tree. These equations are now well understood, and their solutions are always algebraic series. Several other families of permutations can be described by a generating tree in which each node carries two integer labels. To these trees correspond other functional equations, defining 3-variate generating functions. We propose an approach to solving such equations. We thus recover and refine, in a unified way, some results on Baxter permutations, $1234$-avoiding permutations, $2143$-avoiding (or: vexillary) involutions and $54321$-avoiding involutions. All the generating functions we obtain are D-finite, and, more precisely, are diagonals of algebraic series. Vexillary involutions are exceptionally simple: they are counted by Motzkin numbers, and thus have an algebraic generating function. In passing, we exhibit an interesting link between Baxter permutations and the Tutte polynomial of planar maps.
An Apéry-like Difference Equation for Catalan's Constant
Authors: Zudilin W.
Published: January 2020

Applying Zeilberger's algorithm of creative telescoping to a family of certain very-well-poised hypergeometric series involving linear forms in Catalan's constant with rational coefficients, we obtain a second-order difference equation for these forms and their coefficients. As a consequence we derive a new way of fast calculation of Catalan's constant as well as a new continued-fraction expansion for it. Similar arguments are put forward to deduce a second-order difference equation and a new continued fraction for $\zeta(4)=\pi^4/90$.
Updown Numbers and the Initial Monomials of the Slope Variety
Authors: Martin Jeremy L. , Wagner Jennifer D.
Published: January 2020

Let $I_n$ be the ideal of all algebraic relations on the slopes of the ${n\choose2}$ lines formed by placing $n$ points in a plane and connecting each pair of points with a line. Under each of two natural term orders, the ideal of $I_n$ is generated by monomials corresponding to permutations satisfying a certain pattern-avoidance condition. We show bijectively that these permutations are enumerated by the updown (or Euler) numbers, thereby obtaining a formula for the number of generators of the initial ideal of $I_n$ in each degree.
Translational Tilings of the Integers with Long Periods
Authors: Kolountzakis Mihail N.
Published: January 2020

Suppose that $A \subseteq {\Bbb{Z}}$ is a finite set of integers of diameter $D=\max A - \min A$. Suppose also that $B \subseteq {\Bbb{Z}}$ is such that $A\oplus B = {\Bbb{Z}}$, that is each $n\in{\Bbb{Z}}$ is uniquely expressible as $a+b$, $a\in A$, $b\in B$. We say then that $A$ tiles the integers if translated at the locations $B$ and it is well known that $B$ must be a periodic set in this case and that the smallest period of $B$ is at most $2^D$. Here we study the relationship between the diameter of $A$ and the least period ${\cal P}(B)$ of $B$. We show that ${\cal P}(B) \le c_2 \exp(c_3 \sqrt D \log D \sqrt{\log\log D})$ and that we can have ${\cal P}(B) \ge c_1 D^2$, where $c_1, c_2, c_3 > 0$ are constants.
Coding Parking Functions by Pairs of Permutations
Authors: Burman Yurii , Shapiro Michael
Published: January 2020

We introduce a new class of admissible pairs of triangular sequences and prove a bijection between the set of admissible pairs of triangular sequences of length $n$ and the set of parking functions of length $n$. For all $u$ and $v=0,1,2,3$ and all $n\le 7$ we describe in terms of admissible pairs the dimensions of the bi-graded components $h_{u,v}$ of diagonal harmonics ${\Bbb{C}}[x_1,\dots,x_n;y_1,\dots,y_n]/S_n$, i.e., polynomials in two groups of $n$ variables modulo the diagonal action of symmetric group $S_n$.
On Rainbow Arithmetic Progressions
Authors: Axenovich Maria , Fon-Der-Flaass Dmitri
Published: January 2020

Consider natural numbers $\{1, \cdots, n\}$ colored in three colors. We prove that if each color appears on at least $(n+4)/6$ numbers then there is a three-term arithmetic progression whose elements are colored in distinct colors. This variation on the theme of Van der Waerden's theorem proves the conjecture of Jungić et al.
On Regular Factors in Regular Graphs with Small Radius
Authors: Hoffmann Arne , Volkmann Lutz
Published: January 2020

In this note we examine the connection between vertices of high eccentricity and the existence of $k$-factors in regular graphs. This leads to new results in the case that the radius of the graph is small ($\leq 3$), namely that a $d$-regular graph $G$ has all $k$-factors, for $k|V(G)|$ even and $k\le d$, if it has at most $2d+2$ vertices of eccentricity $>3$. In particular, each regular graph $G$ of diameter $\leq3$ has every $k$-factor, for $k|V(G)|$ even and $k\le d$.
There Exist Binary Circular $5/2^+$ Power Free Words of Every Length
Authors: Aberkane Ali , Currie James D.
Published: January 2020

We show that there exist binary circular $5/2^+$ power free words of every length.
The Plethysm $s_\lambda[s_\mu]$ at Hook and Near-Hook Shapes
Authors: Langley T. M. , Remmel J. B.
Published: January 2020

We completely characterize the appearance of Schur functions corresponding to partitions of the form $\nu = (1^a, b)$ (hook shapes) in the Schur function expansion of the plethysm of two Schur functions, $$s_\lambda[s_\mu] = \sum_{\nu} a_{\lambda, \mu, \nu} s_\nu.$$ Specifically, we show that no Schur functions corresponding to hook shapes occur unless $\lambda$ and $\mu$ are both hook shapes and give a new proof of a result of Carbonara, Remmel and Yang that a single hook shape occurs in the expansion of the plethysm $s_{(1^c, d)}[s_{(1^a, b)}]$. We also consider the problem of adding a row or column so that $\nu$ is of the form $(1^a,b,c)$ or $(1^a, 2^b, c)$. This proves considerably more difficult than the hook case and we discuss these difficulties while deriving explicit formulas for a special case.
On the Entropy and Letter Frequencies of Ternary Square-Free Words
Authors: Richard Christoph , Grimm Uwe
Published: January 2020

We enumerate ternary length-$\ell$ square-free words, which are words avoiding squares of all words up to length $\ell$, for $\ell\le 24$. We analyse the singular behaviour of the corresponding generating functions. This leads to new upper entropy bounds for ternary square-free words. We then consider ternary square-free words with fixed letter densities, thereby proving exponential growth for certain ensembles with various letter densities. We derive consequences for the free energy and entropy of ternary square-free words.
Goldberg-Coxeter Construction for $3$- and $4$-valent Plane Graphs
Authors: Dutour Mathieu , Deza Michel
Published: January 2020

We consider the Goldberg-Coxeter construction $GC_{k,l}(G_0)$ (a generalization of a simplicial subdivision of the dodecahedron considered by Goldberg [Tohoku Mathematical Journal, 43 (1937) 104–108] and Coxeter [A Spectrum of Mathematics, OUP, (1971) 98–107]), which produces a plane graph from any $3$- or $4$-valent plane graph for integer parameters $k,l$. A zigzag in a plane graph is a circuit of edges, such that any two, but no three, consecutive edges belong to the same face; a central circuit in a $4$-valent plane graph $G$ is a circuit of edges, such that no two consecutive edges belong to the same face. We study the zigzag (or central circuit) structure of the resulting graph using the algebraic formalism of the moving group, the $(k,l)$-product and a finite index subgroup of $SL_2(\Bbb{Z})$, whose elements preserve the above structure. We also study the intersection pattern of zigzags (or central circuits) of $GC_{k,l}(G_0)$ and consider its projections, obtained by removing all but one zigzags (or central circuits).
Class-Uniformly Resolvable Group Divisible Structures I: Resolvable Group Divisible Designs
Authors: Danziger Peter , Stevens Brett
Published: January 2020

We consider Class-Uniformly Resolvable Group Divisible Designs (CURGDD), which are resolvable group divisible designs in which each of the resolution classes has the same number of blocks of each size. We derive the fully general necessary conditions including a number of extremal bounds. We present some general constructions including a novel construction for shrinking the index of a master design. We construct a number of infinite families, primarily with block sizes 2 and $k$, including some extremal cases.
Class-Uniformly Resolvable Group Divisible Structures II: Frames.
Authors: Danziger Peter , Stevens Brett
Published: January 2020

We consider Class-Uniformly Resolvable frames (CURFs), which are group divisible designs with partial resolution classes subject to the class-uniform condition. We derive the necessary conditions, including extremal bounds, build the foundation for general CURF constructions, including a frame variant of the $\lambda$ blow-up construction from part I. We also establish a PBD-closure result. For CURFs with blocks of size two and three we determine the existence of CURFs of type $g^u$, completely for $g=3$, with a small list of exceptions for $g=6$, asymptotically for $g=4,5$ and give some other infinite families.
Decomposing Infinite 2-Connected Graphs into 3-Connected Components
Authors: Richter R. Bruce
Published: January 2020

In the 1960's, Tutte presented a decomposition of a 2-connected finite graph into 3-connected graphs, cycles and bonds. This decomposition has been used to reduce problems on 2-connected graphs to problems on 3-connected graphs. Motivated by a problem concerning accumulation points of infinite planar graphs, we generalize Tutte's decomposition to include all infinite 2-connected graphs.
A Scaling Result for Explosive Processes
Authors: Mitzenmacher M. , Oliveira R. , Spencer J.
Published: January 2020

We consider the asymptotic behavior of the following model: balls are sequentially thrown into bins so that the probability that a bin with $n$ balls obtains the next ball is proportional to $f(n)$ for some function $f$. A commonly studied case where there are two bins and $f(n) = n^p$ for $p > 1$. In this case, one of the two bins eventually obtains a monopoly, in the sense that it obtains all balls thrown past some point. This model is motivated by the phenomenon of positive feedback, where the "rich get richer." We derive a simple asymptotic expression for the probability that bin 1 obtains a monopoly when bin 1 starts with $x$ balls and bin 2 starts with $y$ balls for the case $f(n) = n^p$. We then demonstrate the effectiveness of this approximation with some examples and demonstrate how it generalizes to a wide class of functions $f$.
Ground State Incongruence in 2D Spin Glasses Revisited
Authors: Loebl Martin
Published: January 2020

A construction supporting a conjecture that different ground state pairs exist in the 2-dimensional Edwards-Anderson Ising spin glass is presented.
Operations on Well-Covered Graphs and the Roller-Coaster Conjecture
Authors: Matchett Philip
Published: January 2020

A graph $G$ is well-covered if every maximal independent set has the same cardinality. Let $s_k$ denote the number of independent sets of cardinality $k$, and define the independence polynomial of $G$ to be $S(G,z) = \sum s_kz^k$. This paper develops a new graph theoretic operation called power magnification that preserves well-coveredness and has the effect of multiplying an independence polynomial by $z^c$ where $c$ is a positive integer. We will apply power magnification to the recent Roller-Coaster Conjecture of Michael and Traves, proving in our main theorem that for sufficiently large independence number $\alpha$, it is possible to find well-covered graphs with the last $(.17)\alpha$ terms of the independence sequence in any given linear order. Also, we will give a simple proof of a result due to Alavi, Malde, Schwenk, and Erdős on possible linear orderings of the independence sequence of not-necessarily well-covered graphs, and we will prove the Roller-Coaster Conjecture in full for independence number $\alpha \leq 11$. Finally, we will develop two new graph operations that preserve well-coveredness and have interesting effects on the independence polynomial.
Vertex-Partitioning into Fixed Additive Induced-Hereditary Properties is NP-hard
Authors: Farrugia Alastair
Published: January 2020

Can the vertices of an arbitrary graph $G$ be partitioned into $A \cup B$, so that $G[A]$ is a line-graph and $G[B]$ is a forest? Can $G$ be partitioned into a planar graph and a perfect graph? The NP-completeness of these problems are special cases of our result: if ${\cal P}$ and ${\cal Q}$ are additive induced-hereditary graph properties, then $({\cal P}, {\cal Q})$-colouring is NP-hard, with the sole exception of graph $2$-colouring (the case where both ${\cal P}$ and ${\cal Q}$ are the set ${\cal O}$ of finite edgeless graphs). Moreover, $({\cal P}, {\cal Q})$-colouring is NP-complete iff ${\cal P}$- and ${\cal Q}$-recognition are both in NP. This completes the proof of a conjecture of Kratochvíl and Schiermeyer, various authors having already settled many sub-cases.
Uniform Edge Distribution in Hypergraphs is Hereditary
Authors: Mubayi Dhruv , Rödl Vojtĕch
Published: January 2020

Let $\alpha \in (0,1), l \ge 2$ and let ${\cal H}_n$ be an $l$-graph on $n$ vertices. ${\cal H}_n$ is $(\alpha, \xi)$-uniform if every $\xi n$ vertices of ${\cal H}_n$ span $(\alpha \pm\xi) {\xi n\choose l}$ edges. Our main result is the following. For all $\widetilde{\delta}$, there exist $\delta, r, n_0$ such that, if $n>n_0$ and ${\cal H}_n^{(l)}$ is $(\alpha, \delta)$-uniform, then all but $\exp\{-r^{1/l}/20\}{n\choose r}$ $r$-sets of vertices induce a subhypergraph that is $(\alpha,\widetilde{\delta})$-uniform. We also present the following application. Let ${\cal F}$ be a fixed $l$-graph, and $c>0$. Then there is an $n_0$ and $r'$ such that: If ${\cal H}$ is an $n$ vertex $l$-graph ($n>n_0$) such that the deletion of any $c n^l$ edges of ${\cal H}$ leaves an $l$-graph that admits no homomorphism into ${\cal F}$, then there exists ${\cal H}' \subset {\cal H}$ on $r'$ vertices, that also admits no homomorphism into ${\cal F}$. This extends a recent result of Alon and Shapira, who proved it when ${\cal F}$ is a complete graph.
Defective Choosability of Graphs without Small Minors
Authors: Wood Rupert G. , Woodall Douglas R.
Published: January 2020

For each proper subgraph $H$ of $K_5$, we determine all pairs $(k,d)$ such that every $H$-minor-free graph is $(k,d)^*$-choosable or $(k,d)^-$-choosable. The main structural lemma is that the only 3-connected $(K_5-e)$-minor-free graphs are wheels, the triangular prism, and $K_{3,3}$; this is used to prove that every $(K_5-e)$-minor-free graph is 4-choosable and $(3,1)$-choosable.
A Bijection Between Classes of Fully Packed Loops and Plane Partitions
Authors: Di Francesco P. , Zinn-Justin P. , Zuber J.-B.
Published: January 2020

It has recently been observed empirically that the number of FPL configurations with 3 sets of $a$, $b$ and $c$ nested arches equals the number of plane partitions in a box of size $a\times b \times c$. In this note, this result is proved by constructing explicitly the bijection between these FPL and plane partitions.
The Cube Recurrence
Authors: Carroll Gabriel D. , Speyer David
Published: January 2020

We construct a combinatorial model that is described by the cube recurrence, a quadratic recurrence relation introduced by Propp, which generates families of Laurent polynomials indexed by points in ${\Bbb Z}^3$. In the process, we prove several conjectures of Propp and of Fomin and Zelevinsky about the structure of these polynomials, and we obtain a combinatorial interpretation for the terms of Gale-Robinson sequences, including the Somos-6 and Somos-7 sequences. We also indicate how the model might be used to obtain some interesting results about perfect matchings of certain bipartite planar graphs.
Outerplanar Crossing Numbers, the Circular Arrangement Problem and Isoperimetric Functions
Authors: Czabarka Éva , Sýkora Ondrej , Székely László A. , Vrťo Imrich
Published: January 2020

We extend a lower bound due to Shahrokhi, Sýkora, Székely and Vrťo for the outerplanar crossing number (in other terminologies also called convex, circular and one-page book crossing number) to a more general setting. In this setting we can show a better lower bound for the outerplanar crossing number of hypercubes than the best lower bound for the planar crossing number. We exhibit further sequences of graphs, whose outerplanar crossing number exceeds by a factor of $\log n$ the planar crossing number of the graph. We study the circular arrangement problem, as a lower bound for the linear arrangement problem, in a general fashion. We obtain new lower bounds for the circular arrangement problem. All the results depend on establishing good isoperimetric functions for certain classes of graphs. For several graph families new near-tight isoperimetric functions are established.
MacMahon-type Identities for Signed Even Permutations
Authors: Bernstein Dan
Published: January 2020

MacMahon's classic theorem states that the length and major index statistics are equidistributed on the symmetric group $S_n$. By defining natural analogues or generalizations of those statistics, similar equidistribution results have been obtained for the alternating group $A_n$ by Regev and Roichman, for the hyperoctahedral group $B_n$ by Adin, Brenti and Roichman, and for the group of even-signed permutations $D_n$ by Biagioli. We prove analogues of MacMahon's equidistribution theorem for the group of signed even permutations and for its subgroup of even-signed even permutations.
Rook Theory, Generalized Stirling Numbers and $(p,q)$-Analogues
Authors: Remmel J. B. , Wachs Michelle L.
Published: January 2020

In this paper, we define two natural $(p,q)$-analogues of the generalized Stirling numbers of the first and second kind $S^1(\alpha,\beta,r)$ and $S^2(\alpha,\beta,r)$ as introduced by Hsu and Shiue [Adv. in Appl. Math. 20 (1998), 366–384]. We show that in the case where $\beta =0$ and $\alpha$ and $r$ are nonnegative integers both of our $(p,q)$-analogues have natural interpretations in terms of rook theory and derive a number of generating functions for them. We also show how our $(p,q)$-analogues of the generalized Stirling numbers of the second kind can be interpreted in terms of colored set partitions and colored restricted growth functions. Finally we show that our $(p,q)$-analogues of the generalized Stirling numbers of the first kind can be interpreted in terms of colored permutations and how they can be related to generating functions of permutations and signed permutations according to certain natural statistics.
On Some Non-Holonomic Sequences
Authors: Gerhold Stefan
Published: January 2020

A sequence of complex numbers is holonomic if it satisfies a linear recurrence with polynomial coefficients. A power series is holonomic if it satisfies a linear differential equation with polynomial coefficients, which is equivalent to its coefficient sequence being holonomic. It is well known that all algebraic power series are holonomic. We show that the analogous statement for sequences is false by proving that the sequence $\{\sqrt{n}\}_n$ is not holonomic. In addition, we show that $\{n^n\}_n$, the Lambert $W$ function and $\{\log{n}\}_n$ are not holonomic, where in the case of $\{\log{n}\}_n$ we have to rely on an open conjecture from transcendental number theory.
Voltage Graphs, Group Presentations and Cages
Authors: Exoo Geoffrey
Published: January 2020

We construct smallest known trivalent graphs for girths 16 and 18. One construction uses voltage graphs, and the other coset enumeration techniques for group presentations.
Two New Criteria for Comparison in the Bruhat Order
Authors: Drake Brian , Gerrish Sean , Skandera Mark
Published: January 2020

We give two new criteria by which pairs of permutations may be compared in defining the Bruhat order (of type $A$). One criterion utilizes totally nonnegative polynomials and the other utilizes Schur functions.
When Can You Tile a Box With Translates of Two Given Rectangular Bricks?
Authors: Bower Richard J. , Michael T. S.
Published: January 2020

When can a $d$-dimensional rectangular box $R$ be tiled by translates of two given $d$-dimensional rectangular bricks $B_1$ and $B_2$? We prove that $R$ can be tiled by translates of $B_1$ and $B_2$ if and only if $R$ can be partitioned by a hyperplane into two sub-boxes $R_1$ and $R_2$ such that $R_i$ can be tiled by translates of the brick $B_i$ alone $(i=1,2).$ Thus an obvious sufficient condition for a tiling is also a necessary condition. (However, there may be tilings that do not give rise to a bipartition of $R.$) There is an equivalent formulation in terms of the (not necessarily integer) edge lengths of $R,$ $B_1,$ and $B_2.$ Let $R$ be of size $z_1\times z_2\times \cdots\times z_d,$ and let $B_1$ and $B_2$ be of respective sizes $v_1\times v_2\times \cdots\times v_d$ and $w_1\times w_2\times \cdots\times w_d.$ Then there is a tiling of the box $R$ with translates of the bricks $B_1$ and $B_2$ if and only if (a) $z_i/v_i$ is an integer for $i=1,2,\ldots, d;$ or (b) $z_i/w_i$ is an integer for $i=1,2,\ldots,d;$ or (c) there is an index $k$ such that $z_i/v_i$ and $z_i/w_i$ are integers for all $i\neq k,$ and $z_k=\alpha v_k+\beta w_k$ for some nonnegative integers $\alpha$ and $\beta.$ Our theorem extends some well known results (due to de Bruijn and Klarner) on tilings of rectangles by rectangles with integer edge lengths.
An Answer to a Question by Wilf on Packing Distinct Patterns in a Permutation
Authors: Coleman Micah
Published: January 2020

We present a class of permutations for which the number of distinctly ordered subsequences of each permutation approaches an almost optimal value as the length of the permutation grows to infinity.
Rectilinear Spanning Trees Versus Bounding Boxes
Authors: Rautenbach D.
Published: January 2020

For a set $P\subseteq {\Bbb R}^2$ with $2\leq n=|P| < \infty$ we prove that ${{\rm mst}(P)\over{\rm bb}(P)} \leq{1\over\sqrt{2}}\sqrt{n}+{3\over2}$ where ${\rm mst}(P)$ is the minimum total length of a rectilinear spanning tree for $P$ and ${\rm bb}(P)$ is half the perimeter of the bounding box of $P$. Since the constant ${1\over\sqrt{2}}$ in the above bound is best-possible, this result settles a problem that was mentioned by Brenner and Vygen (Networks 38 (2001), 126-139).
Random Matrices, Magic Squares and Matching Polynomials
Authors: Diaconis Persi , Gamburd Alex
Published: January 2020

Characteristic polynomials of random unitary matrices have been intensively studied in recent years: by number theorists in connection with Riemann zeta-function, and by theoretical physicists in connection with Quantum Chaos. In particular, Haake and collaborators have computed the variance of the coefficients of these polynomials and raised the question of computing the higher moments. The answer turns out to be intimately related to counting integer stochastic matrices (magic squares). Similar results are obtained for the moments of secular coefficients of random matrices from orthogonal and symplectic groups. Combinatorial meaning of the moments of the secular coefficients of GUE matrices is also investigated and the connection with matching polynomials is discussed.
$h^*$-Vectors, Eulerian Polynomials and Stable Polytopes of Graphs
Authors: Athanasiadis Christos A.
Published: January 2020

Conditions are given on a lattice polytope $P$ of dimension $m$ or its associated affine semigroup ring which imply inequalities for the $h^*$-vector $(h^*_0, h^*_1,\dots,h^*_m)$ of $P$ of the form $h^*_i \ge h^*_{d-i}$ for $1 \le i \le \lfloor d / 2 \rfloor$ and $h^*_{\lfloor d / 2 \rfloor} \ge h^*_{\lfloor d / 2 \rfloor + 1} \ge \cdots \ge h^*_d$, where $h^*_i = 0$ for $d < i \le m$. Two applications to order polytopes of posets and stable polytopes of perfect graphs are included.
On Plethysm Conjectures of Stanley and Foulkes: The $2 \times n$ Case
Authors: Pylyavskyy Pavlo
Published: January 2020

We prove Stanley's plethysm conjecture for the $2 \times n$ case, which composed with the work of Black and List provides another proof of Foulkes conjecture for the $2 \times n$ case. We also show that the way Stanley formulated his conjecture, it is false in general, and suggest an alternative formulation.
Positivity in Coefficient-Free Rank Two Cluster Algebras
Authors: Dupont G.
Published: January 2020

Let $b,c$ be positive integers, $x_1,x_2$ be indeterminates over ${\Bbb Z}$ and $x_m, m \in {\Bbb Z}$ be rational functions defined by $x_{m-1}x_{m+1}=x_m^b+1$ if $m$ is odd and $x_{m-1}x_{m+1}=x_m^c+1$ if $m$ is even. In this short note, we prove that for any $m,k \in {\Bbb Z}$, $x_k$ can be expressed as a substraction-free Laurent polynomial in ${\Bbb Z}[x_m^{\pm 1},x_{m+1}^{\pm 1}]$. This proves Fomin-Zelevinsky's positivity conjecture for coefficient-free rank two cluster algebras.
The Order Dimension of Bruhat Order on Infinite Coxeter Groups
Authors: Reading Nathan , Waugh Debra J.
Published: January 2020

We give a quadratic lower bound and a cubic upper bound on the order dimension of the Bruhat (or strong) ordering of the affine Coxeter group ${\tilde{A}}_n$. We also demonstrate that the order dimension of the Bruhat order is infinite for a large class of Coxeter groups.
Tiling Parity Results and the Holey Square Solution
Authors: Tenner Bridget Eileen
Published: January 2020

We prove combinatorially that the parity of the number of domino tilings of a region is equal to the parity of the number of domino tilings of a particular subregion. Using this result we can resolve the holey square conjecture. We furthermore give combinatorial proofs of several other tiling parity results, including that the number of domino tilings of a particular family of rectangles is always odd.
Monomial Nonnegativity and the Bruhat Order
Authors: Drake Brian , Gerrish Sean , Skandera Mark
Published: January 2020

We show that five nonnegativity properties of polynomials coincide when restricted to polynomials of the form $x_{1,\pi(1)}\cdots x_{n,\pi(n)} - x_{1,\sigma(1)}\cdots x_{n,\sigma(n)}$, where $\pi$ and $\sigma$ are permutations in $S_n$. In particular, we show that each of these properties may be used to characterize the Bruhat order on $S_n$.
Profiles of Permutations
Authors: Lugo Michael
Published: January 2020

This paper develops an analogy between the cycle structure of, on the one hand, random permutations with cycle lengths restricted to lie in an infinite set $S$ with asymptotic density $\sigma$ and, on the other hand, permutations selected according to the Ewens distribution with parameter $\sigma$. In particular we show that the asymptotic expected number of cycles of random permutations of $[n]$ with all cycles even, with all cycles odd, and chosen from the Ewens distribution with parameter $1/2$ are all ${1 \over 2} \log n + O(1)$, and the variance is of the same order. Furthermore, we show that in permutations of $[n]$ chosen from the Ewens distribution with parameter $\sigma$, the probability of a random element being in a cycle longer than $\gamma n$ approaches $(1-\gamma)^\sigma$ for large $n$. The same limit law holds for permutations with cycles carrying multiplicative weights with average $\sigma$. We draw parallels between the Ewens distribution and the asymptotic-density case and explain why these parallels should exist using permutations drawn from weighted Boltzmann distributions.
Stable Equivalence over Symmetric Functions
Authors: Chen William Y. C. , Yang Arthur L. B.
Published: January 2020

By using cutting strips and transformations on outside decompositions of a skew diagram, we show that the Giambelli-type matrices for a given skew Schur function are stably equivalent to each other over symmetric functions. As a consequence, the Jacobi-Trudi matrix and the transpose of the dual Jacobi-Trudi matrix are stably equivalent over symmetric functions. This leads to an affirmative answer to a question proposed by Kuperberg.
A Relative Laplacian Spectral Recursion
Authors: Duval Art M.
Published: January 2020

The Laplacian spectral recursion, satisfied by matroid complexes and shifted complexes, expresses the eigenvalues of the combinatorial Laplacian of a simplicial complex in terms of its deletion and contraction with respect to vertex $e$, and the relative simplicial pair of the deletion modulo the contraction. We generalize this recursion to relative simplicial pairs, which we interpret as convex subsets of the Boolean algebra. The deletion modulo contraction term is replaced by the result of removing from the convex set $\Phi$ all pairs of faces in $\Phi$ that differ only by vertex $e$. We show that shifted pairs and some matroid pairs satisfy this recursion. We also show that the class of convex sets satisfying this recursion is closed under a wide variety of operations, including duality and taking skeleta.
Words Avoiding a Reflexive Acyclic Relation
Authors: Dollhopf John , Goulden Ian , Greene Curtis
Published: January 2020

Let ${\cal A}\subseteq {\bf [n]}\times{\bf [n]}$ be a set of pairs containing the diagonal ${\cal D} = \{(i,i)\,|\, i=1,\ldots,n\}$, and such that $a\leq b$ for all $(a,b) \in {\cal A}$. We study formulae for the generating series $F_{\cal A} ({\bf x}) = \sum_w {\bf x}^w$ where the sum is over all words $w \in {\bf [n]}^*$ that avoid ${\cal A}$, i.e., $(w_i,w_{i+1})\notin {\cal A}$ for $i=1,\ldots,|w|-1$. This series is a rational function, with denominator of the form $1-\sum_{T}\mu_{{\cal A}}(T){\bf x}^T$, where the sum is over all nonempty subsets $T$ of $[n]$. Our principal focus is the case where the relation ${\cal A}$ is $\mu$-positive, i.e., $\mu_{\cal A}(T)\ge 0$ for all $T\subseteq {\bf [n]}$, in which case the form of the generating function suggests a cancellation-free combinatorial encoding of words avoiding ${\cal A}$. We supply such an interpretation for several classes of examples, including the interesting class of cycle-free (or crown-free) posets.
A Combinatorial Proof of Postnikov's Identity and a Generalized Enumeration of Labeled Trees
Authors: Seo Seunghyun
Published: January 2020

In this paper, we give a simple combinatorial explanation of a formula of A. Postnikov relating bicolored rooted trees to bicolored binary trees. We also present generalized formulas for the number of labeled $k$-ary trees, rooted labeled trees, and labeled plane trees.
Reconstruction of Partitions
Authors: Pretzel Oliver , Siemons Johannes
Published: January 2020

For the partition $x=[x_1\ge x_2\ge \cdots\ge x_k]$ of the integer $n=\sum_{i}\, x_{i}$ a $t$-deletion is a partition $y=[y_1\ge y_2\ge \cdots\ge y_k]$ with $x_{i}\geq y_{i}\geq 0$ and $\sum_{i}\, (x_{i}-y_{i})=t$. We prove that all partitions of $n$ are reconstructible from their $t$–deletions if $n$ is sufficiently large in relation to $t$.
On the Non-Holonomic Character of Logarithms, Powers, and the $n$th Prime Function
Authors: Flajolet Philippe , Gerhold Stefan , Salvy Bruno
Published: January 2020

We establish that the sequences formed by logarithms and by "fractional" powers of integers, as well as the sequence of prime numbers, are non-holonomic, thereby answering three open problems of Gerhold [El. J. Comb. 11 (2004), R87]. Our proofs depend on basic complex analysis, namely a conjunction of the Structure Theorem for singularities of solutions to linear differential equations and of an Abelian theorem. A brief discussion is offered regarding the scope of singularity-based methods and several naturally occurring sequences are proved to be non-holonomic.
Schur Functions and Alternating Sums
Authors: Van Leeuwen Marc A. A.
Published: January 2020

We discuss several well known results about Schur functions that can be proved using cancellations in alternating summations; notably we shall discuss the Pieri and Murnaghan-Nakayama rules, the Jacobi-Trudi identity and its dual (Von Nägelsbach-Kostka) identity, their proofs using the correspondence with lattice paths of Gessel and Viennot, and finally the Littlewood-Richardson rule. Our our goal is to show that the mentioned statements are closely related, and can be proved using variations of the same basic technique. We also want to emphasise the central part that is played by matrices over $\{0,1\}$ and over $\Bbb N$; we show that the Littlewood-Richardson rule as generalised by Zelevinsky has elegant formulations using either type of matrix, and that in both cases it can be obtained by two successive reductions from a large signed enumeration of such matrices, where the sign depends only on the row and column sums of the matrix.
$k$-Colour Partitions of Acyclic Tournaments
Authors: Barcia Paulo , Cerdeira J. Orestes
Published: January 2020

Let $G_{1}$ be the acyclic tournament with the topological sort $0 < 1 < 2 < \dots < n < n+1$ defined on node set $N\cup \{0,n+1\}$, where $N=\{1,2,\dots,n\}$. For integer $k\geq 2$, let $G_{k}$ be the graph obtained by taking $k$ copies of every arc in $G_{1}$ and colouring every copy with one of $k$ different colours. A $k$-colour partition of $N$ is a set of $k$ paths from 0 to $n+1$ such that all arcs of each path have the same colour, different paths have different colours, and every node of $N$ is included in exactly one path. If there are costs associated with the arcs of $G_{k}$, the cost of a $k$-colour partition is the sum of the costs of its arcs. For determining minimum cost $k$-colour partitions we describe an $O(k^{2}n^{2k})$ algorithm, and show this is an NP-$hard$ problem. We also study the convex hull of the incidence vectors of $k$-colour partitions. We derive the dimension, and establish a minimal equality set. For $k>2$ we identify a class of facet inducing inequalities. For $k=2$ we show that these inequalities turn out to be equations, and that no other facet defining inequalities exists besides the trivial nonnegativity constraints.
Around the Razumov–Stroganov Conjecture: Proof of a Multi-Parameter Sum Rule
Authors: Di Francesco P. , Zinn-Justin P.
Published: January 2020

We prove that the sum of entries of the suitably normalized groundstate vector of the $O(1)$ loop model with periodic boundary conditions on a periodic strip of size $2n$ is equal to the total number of $n\times n$ alternating sign matrices. This is done by identifying the state sum of a multi-parameter inhomogeneous version of the $O(1)$ model with the partition function of the inhomogeneous six-vertex model on a $n\times n$ square grid with domain wall boundary conditions.
The Edmonds-Gallai Decomposition for the $k$-Piece Packing Problem
Authors: Janata Marek , Loebl Martin , Szabó Jácint
Published: January 2020

Generalizing Kaneko's long path packing problem, Hartvigsen, Hell and Szabó consider a new type of undirected graph packing problem, called the $k$-piece packing problem. A $k$-piece is a simple, connected graph with highest degree exactly $k$ so in the case $k=1$ we get the classical matching problem. They give a polynomial algorithm, a Tutte-type characterization and a Berge-type minimax formula for the $k$-piece packing problem. However, they leave open the question of an Edmonds-Gallai type decomposition. This paper fills this gap by describing such a decomposition. We also prove that the vertex sets coverable by $k$-piece packings have a certain matroidal structure.
Tight Bounds for Quasirandom Rumor Spreading
Authors: Angelopoulos Spyros , Doerr Benjamin , Huber Anna , Panagiotou Konstantinos
Published: January 2020

This paper addresses the following fundamental problem: Suppose that in a group of $n$ people, where each person knows all other group members, a single person holds a piece of information that must be disseminated to everybody within the group. How should the people propagate the information so that after short time everyone is informed? The classical approach, known as the push model, requires that in each round, every informed person selects some other person in the group at random, whom it then informs. In a different model, known as the quasirandom push model, each person maintains a cyclic list, i.e., permutation, of all members in the group (for instance, a contact list of persons). Once a person is informed, it chooses a random member in its own list, and from that point onwards, it informs a new person per round, in the order dictated by the list. In this paper we show that with probability $1-o(1)$ the quasirandom protocol informs everybody in $(1 \pm o(1))\log_2 n+\ln n$ rounds; furthermore we also show that this bound is tight. This result, together with previous work on the randomized push model, demonstrates that irrespectively of the choice of lists, quasirandom broadcasting is as fast as broadcasting in the randomized push model, up to lower order terms. At the same time it reduces the number of random bits from $O(\log^2 n)$ to only $\lceil\log_2 n\rceil$ per person.
Splitting Numbers of Grids
Authors: Duffus Dwight , Sands Bill
Published: January 2020

For a subset $S$ of a finite ordered set $P$, let $$S\!\uparrow\;=\{x\in P:x\ge s \hbox{ for some }s\in S\}\quad\hbox{and} \quad S\!\downarrow\;=\{x\in P:x\le s \hbox{ for some }s\in S\}.$$ For a maximal antichain $A$ of $P$, let $$s(A)=\max_{A=U\cup D}{|U\!\uparrow|+|D\!\downarrow|\over|P|}\ ,$$ the maximum taken over all partitions $U\cup D$ of $A$, and $$s_k(P)=\min_{A\in {\cal A}(P),|A|=k}s(A)$$ where we assume $P$ contains at least one maximal antichain of $k$ elements. Finally, for a class ${\cal C}$ of finite ordered sets, we define $$s_k({\cal C})=\inf_{P\in {\cal C}}s_k(P).$$ Thus $s_k({\cal C})$ is the greatest proportion $r$ satisfying: every $k$-element maximal antichain of a member $P$ of ${\cal C}$ can be "split" into sets $U$ and $D$ so that $U\!\uparrow\cup\; D\!\downarrow$ contains at least $r|P|$ elements. In this paper we determine $s_k({\cal G}_k)$ for all $k\ge 1$, where ${\cal G}_k=\{{\bf k}\times{\bf n}:n\ge k\}$ is the family of all $k$ by $n$ "grids".
The Combinatorics of Orbital Varieties Closures of Nilpotent Order 2 in sl${}_n$
Authors: Melnikov Anna
Published: January 2020

We consider two partial orders on the set of standard Young tableaux. The first one is induced to this set from the weak right order on symmetric group by Robinson-Schensted algorithm. The second one is induced to it from the dominance order on Young diagrams by considering a Young tableau as a chain of Young diagrams. We prove that these two orders of completely different nature coincide on the subset of Young tableaux with 2 columns or with 2 rows. This fact has very interesting geometric implications for orbital varieties of nilpotent order 2 in special linear algebra $sl_n.$
Random Orders and Gambler's Ruin
Authors: Blass Andreas , Braun Gábor
Published: January 2020

We prove a conjecture of Droste and Kuske about the probability that $1$ is minimal in a certain random linear ordering of the set of natural numbers. We also prove generalizations, in two directions, of this conjecture: when we use a biased coin in the random process and when we begin the random process with a specified ordering of a finite initial segment of the natural numbers. Our proofs use a connection between the conjecture and a question about the game of gambler's ruin. We exhibit several different approaches (combinatorial, probabilistic, generating function) to the problem, of course ultimately producing equivalent results.
Packing Unit Squares in a Rectangle
Authors: Nagamochi Hiroshi
Published: January 2020

For a positive integer $N$, let $s(N)$ be the side length of the minimum square into which $N$ unit squares can be packed. This paper shows that, for given real numbers $a,b\geq 2$, no more than $ab -(a+1-\lceil a\rceil) -(b+1-\lceil b\rceil)$ unit squares can be packed in any $a'\times b'$ rectangle $R$ with $a' < a$ and $b' < b$. From this, we can deduce that, for any integer $N\geq 4$, $s(N)\geq \min\{\lceil \sqrt{N} \rceil, \sqrt{N -2 \lfloor \sqrt{N}\rfloor +1 }+1\}$. In particular, for any integer $n\geq 2$, $s(n^2)=s(n^2-1)=s(n^2-2)=n$ holds.
Sets in the Plane with Many Concyclic Subsets
Authors: Jeurissen R. H.
Published: January 2020

We study sets of points in the Euclidean plane having property $R(t,s)$: every $t$-tuple of its points contains a concyclic $s$-tuple. Typical examples of the kind of theorems we prove are: a set with $R(19,10)$ must have all its points on two circles or all its points, with the exception of at most 9, are on one circle; of a set with $R(8,5)$ and $N\geq 28$ points at least $N-3$ points lie on one circle; a set of at least 109 points with $R(7,4)$ has $R(109,7)$. We added some results on the analogous configurations in 3-space.
A Solution of Two-Person Single-Suit Whist
Authors: Wästlund Johan
Published: January 2020

We give a complete solution of the combinatorial game of two-person single-suit whist. This game is played with a deck consisting of a single totally ordered suit of $2n$ cards. Each of the two players receives $n$ cards. Hence both players have complete information about the distribution of the cards. One of the players is said to be on lead. Play proceeds in rounds called tricks. The player on lead plays one of his cards, and with knowledge of this card, the other player plays one of his cards. The player with the higher card wins the trick, and obtains the lead. The cards that are played are then removed. Play continues until all cards are exhausted. Each player tries to win as many tricks as possible. Our solution provides an efficient algorithm for calculating the game theoretical value of any distribution of the cards.
A Relationship between the Major Index for Tableaux and the Charge Statistic for Permutations
Authors: Killpatrick Kendra
Published: January 2020

The widely studied $q$-polynomial $f^{\lambda}(q)$, which specializes when $q=1$ to $f^{\lambda}$, the number of standard Young tableaux of shape $\lambda$, has multiple combinatorial interpretations. It represents the dimension of the unipotent representation $S_q^{\lambda}$ of the finite general linear group $GL_n(q)$, it occurs as a special case of the Kostka-Foulkes polynomials, and it gives the generating function for the major index statistic on standard Young tableaux. Similarly, the $q$-polynomial $g^{\lambda}(q)$ has combinatorial interpretations as the $q$-multinomial coefficient, as the dimension of the permutation representation $M_q^{\lambda}$ of the general linear group $GL_n(q)$, and as the generating function for both the inversion statistic and the charge statistic on permutations in $W_{\lambda}$. It is a well known result that for $\lambda$ a partition of $n$, $dim(M_q^{\lambda}) = \Sigma_{\mu} K_{\mu \lambda} dim(S_q^{\mu})$, where the sum is over all partitions $\mu$ of $n$ and where the Kostka number $K_{\mu \lambda}$ gives the number of semistandard Young tableaux of shape $\mu$ and content $\lambda$. Thus $g^{\lambda}(q) - f^{\lambda}(q)$ is a $q$-polynomial with nonnegative coefficients. This paper gives a combinatorial proof of this result by defining an injection $f$ from the set of standard Young tableaux of shape $\lambda$, $SYT(\lambda)$, to $W_{\lambda}$ such that $maj(T) = ch(f(T))$ for $T \in SYT(\lambda)$.
$\omega$-Periodic Graphs
Authors: Benjamini Itai , Hoffman Christopher
Published: January 2020

$\omega$-Periodic graphs are introduced and studied. These are graphs which arise as the limits of periodic extensions of the nearest neighbor graph on the integers. We observe that all bounded degree $\omega$-periodic graphs are amenable. We also provide examples of $\omega$-periodic graphs which have exponential volume growth, non-linear polynomial volume growth and intermediate volume growth.
Decompositions of Graphs into 5-Cycles and Other Small Graphs
Authors: Sousa Teresa
Published: January 2020

In this paper we consider the problem of finding the smallest number $q$ such that any graph $G$ of order $n$ admits a decomposition into edge disjoint copies of a fixed graph $H$ and single edges with at most $q$ elements. We solve the case when $H$ is the 5-cycle, the 5-cycle with a chord and any connected non-bipartite non-complete graph of order 4.
Longest Induced Cycles in Circulant Graphs
Authors: Fuchs Elena D.
Published: January 2020

In this paper we study the length of the longest induced cycle in the unit circulant graph $X_n = Cay({\Bbb Z}_n; {\Bbb Z}_n^*)$, where ${\Bbb Z}_n^*$ is the group of units in ${\Bbb Z}_n$. Using residues modulo the primes dividing $n$, we introduce a representation of the vertices that reduces the problem to a purely combinatorial question of comparing strings of symbols. This representation allows us to prove that the multiplicity of each prime dividing $n$, and even the value of each prime (if sufficiently large) has no effect on the length of the longest induced cycle in $X_n$. We also see that if $n$ has $r$ distinct prime divisors, $X_n$ always contains an induced cycle of length $2^r+2$, improving the $r \ln r$ lower bound of Berrezbeitia and Giudici. Moreover, we extend our results for $X_n$ to conjunctions of complete $k_i$-partite graphs, where $k_i$ need not be finite, and also to unit circulant graphs on any quotient of a Dedekind domain.
Packing and Covering a Unit Equilateral Triangle with Equilateral Triangles
Authors: Zhang Yuqin , Fan Yonghui
Published: January 2020

Packing and covering are elementary but very important in combinatorial geometry, they have great practical and theoretical significance. In this paper, we discuss a problem on packing and covering a unit equilateral triangle with smaller triangles which is originated from one of Erdős' favorite problems.
Locally Restricted Compositions I. Restricted Adjacent Differences
Authors: Bender Edward A. , Canfield E. Rodney
Published: January 2020

We study compositions of the integer $n$ in which the first part, successive differences, and the last part are constrained to lie in prescribed sets ${\cal L,D,R}$, respectively. A simple condition on ${\cal D}$ guarantees that the generating function $f(x,{\cal L,D,R})$ has only a simple pole on its circle of convergence and this at $r({\cal D})$, a function independent of ${\cal L}$ and ${\cal R}$. Thus the number of compositions is asymptotic to $Ar({\cal D})^{-n}$ for a suitable constant $A=A({\cal L,D,R})$. We prove a multivariate central and local limit theorem and apply it to various statistics of random locally restricted compositions of $n$, such as number of parts, numbers of parts of given sizes, and number of rises. The first and last parts are shown to have limiting distributions and to be asymptotically independent. If ${\cal D}$ has only finitely many positive elements ${\cal D}^+$, or finitely many negative elements ${\cal D}^-$, then the largest part and number of distinct part sizes are almost surely $\Theta((\log n)^{1/2})$. On the other hand, when both ${\cal D}^+$ and ${\cal D}^-$ have a positive asymptotic lower "local log-density", we prove that the largest part and number of distinct part sizes are almost surely $\Theta(\log n)$, and we give sufficient conditions for the largest part to be almost surely asymptotic to $\log_{1/r({\cal D})}n$.