bluuebunny/crossref_metadata_2025 huggingface dataset:
Constructive Lower Bounds on Classical Multicolor Ramsey Numbers
Authors: Xiaodong Xu , Zheng Xie , Exoo Geoffrey , Radziszowski Stanisław P.
Published: January 2020

This paper studies lower bounds for classical multicolor Ramsey numbers, first by giving a short overview of past results, and then by presenting several general constructions establishing new lower bounds for many diagonal and off-diagonal multicolor Ramsey numbers. In particular, we improve several lower bounds for $R_k(4)$ and $R_k(5)$ for some small $k$, including $415 \le R_3(5)$, $634 \le R_4(4)$, $2721 \le R_4(5)$, $3416 \le R_5(4)$ and $26082 \le R_5(5)$. Most of the new lower bounds are consequences of general constructions.
Satisfiability and Computing van der Waerden Numbers
Authors: Dransfield Michael R. , Liu Lengning , Marek Victor W. , Truszczyński Mirosław
Published: January 2020

In this paper we bring together the areas of combinatorics and propositional satisfiability. Many combinatorial theorems establish, often constructively, the existence of positive integer functions, without actually providing their closed algebraic form or tight lower and upper bounds. The area of Ramsey theory is especially rich in such results. Using the problem of computing van der Waerden numbers as an example, we show that these problems can be represented by parameterized propositional theories in such a way that decisions concerning their satisfiability determine the numbers (function) in question. We show that by using general-purpose complete and local-search techniques for testing propositional satisfiability, this approach becomes effective — competitive with specialized approaches. By following it, we were able to obtain several new results pertaining to the problem of computing van der Waerden numbers. We also note that due to their properties, especially their structural simplicity and computational hardness, propositional theories that arise in this research can be of use in development, testing and benchmarking of SAT solvers.
Bijections and Congruences for Generalizations of Partition Identities of Euler and Guy
Authors: Sellers James A. , Sills Andrew V. , Mullen Gary L.
Published: January 2020

In 1958, Richard Guy proved that the number of partitions of $n$ into odd parts greater than one equals the number of partitions of $n$ into distinct parts with no powers of 2 allowed, which is closely related to Euler's famous theorem that the number of partitions of $n$ into odd parts equals the number of partitions of $n$ into distinct parts. We consider extensions of Guy's result, which naturally lead to a new algorithm for producing bijections between various equivalent partition ideals of order 1, as well as to two new infinite families of parity results which follow from Euler's Pentagonal Number Theorem and a well-known series-product identity of Jacobi.
Classification of Six-Point Metrics
Authors: Sturmfels Bernd , Yu Josephine
Published: January 2020

There are $339$ combinatorial types of generic metrics on six points. They correspond to the $339$ regular triangulations of the second hypersimplex $\Delta(6,2)$, which also has $14$ non-regular triangulations.
The Markov-WZ Method
Authors: Mohammed Mohamud , Zeilberger Doron
Published: January 2020

Andrei Markov's 1890 method for convergence-acceleration of series bears an amazing resemblance to WZ theory, as was recently pointed out by M. Kondratieva and S. Sadov. But Markov did not have Gosper and Zeilberger's algorithms, and even if he did, he wouldn't have had a computer to run them on. Nevertheless, his beautiful ad-hoc method, when coupled with WZ theory and Gosper's algorithm, leads to a new class of identities and very fast convergence-acceleration formulas that can be applied to any infinite series of hypergeometric type.
Generalizing Narayana and Schröder Numbers to Higher Dimensions
Authors: Sulanke Robert A.
Published: January 2020

Let ${\cal C}(d,n)$ denote the set of $d$-dimensional lattice paths using the steps $X_1 := (1, 0, \ldots, 0),$ $ X_2 := (0, 1, \ldots, 0),$ $\ldots,$ $ X_d := (0,0, \ldots,1)$, running from $(0,\ldots,0)$ to $(n,\ldots,n)$, and lying in $\{(x_1,x_2, \ldots, x_d) : 0 \le x_1 \le x_2 \le \ldots \le x_d \}$. On any path $P:=p_1p_2 \ldots p_{dn} \in {\cal C}(d,n)$, define the statistics ${\rm asc}(P) := $$|\{i : p_ip_{i+1} = X_jX_{\ell}, j < \ell \}|$ and ${\rm des}(P) := $$|\{i : p_ip_{i+1} = X_jX_{\ell}, j>\ell \}|$. Define the generalized Narayana number $N(d,n,k)$ to count the paths in ${\cal C}(d,n)$ with ${\rm asc}(P)=k$. We consider the derivation of a formula for $N(d,n,k)$, implicit in MacMahon's work. We examine other statistics for $N(d,n,k)$ and show that the statistics ${\rm asc}$ and ${\rm des}-d+1$ are equidistributed. We use Wegschaider's algorithm, extending Sister Celine's (Wilf-Zeilberger) method to multiple summation, to obtain recurrences for $N(3,n,k)$. We introduce the generalized large Schröder numbers $(2^{d-1}\sum_k N(d,n,k)2^k)_{n\ge1}$ to count constrained paths using step sets which include diagonal steps.
A Fast Algorithm for MacMahon's Partition Analysis
Authors: Xin Guoce
Published: January 2020

This paper deals with evaluating constant terms of a special class of rational functions, the Elliott-rational functions. The constant term of such a function can be read off immediately from its partial fraction decomposition. We combine the theory of iterated Laurent series and a new algorithm for partial fraction decompositions to obtain a fast algorithm for MacMahon's Omega calculus, which (partially) avoids the "run-time explosion" problem when eliminating several variables. We discuss the efficiency of our algorithm by investigating problems studied by Andrews and his coauthors; our running time is much less than that of their Omega package.
Convergence in Distribution for Subset Counts Between Random Sets
Authors: Stark Dudley
Published: January 2020

Erdős posed the problem of how many random subsets need to be chosen from a set of $n$ elements, each element appearing in each subset with probability $p=1/2$, in order that at least one subset is contained in another. Rényi answered this question, but could not determine the limiting probability distribution for the number of subset counts because the higher moments diverge to infinity. The model considered by Rényi with $p$ arbitrary is denoted by ${\cal P}(m,n,p)$, where $m$ is the number of random subsets chosen. We give a necessary and sufficient condition on $p(n)$ and $m(n)$ for subset counts to be asymptotically Poisson and find rates of convergence using Stein's method. We discuss how Poisson limits can be shown for other statistics of ${\cal P}(m,n,p)$.
A Positive Proof of the Littlewood-Richardson Rule using the Octahedron Recurrence
Authors: Knutson Allen , Tao Terence , Woodward Christopher
Published: January 2020

We define the hive ring, which has a basis indexed by dominant weights for $GL_n({\Bbb C})$, and structure constants given by counting hives [Knutson-Tao, "The honeycomb model of $GL_n$ tensor products"] (or equivalently honeycombs, or BZ patterns [Berenstein-Zelevinsky, "Involutions on Gel$'$fand-Tsetlin schemes$\dots$ "]). We use the octahedron rule from [Robbins-Rumsey, "Determinants$\dots$"] to prove bijectively that this "ring" is indeed associative. This, and the Pieri rule, give a self-contained proof that the hive ring is isomorphic as a ring-with-basis to the representation ring of $GL_n({\Bbb C})$. In the honeycomb interpretation, the octahedron rule becomes "scattering" of the honeycombs. This recovers some of the "crosses and wrenches" diagrams from Speyer's very recent preprint ["Perfect matchings$\dots$"], whose results we use to give a closed form for the associativity bijection.
Planar Maps as Labeled Mobiles
Authors: Bouttier J. , Di Francesco P. , Guitter E.
Published: January 2020

We extend Schaeffer's bijection between rooted quadrangulations and well-labeled trees to the general case of Eulerian planar maps with prescribed face valences to obtain a bijection with a new class of labeled trees, which we call mobiles. Our bijection covers all the classes of maps previously enumerated by either the two-matrix model used by physicists or by the bijection with blossom trees used by combinatorists. Our bijection reduces the enumeration of maps to that, much simpler, of mobiles and moreover keeps track of the geodesic distance within the initial maps via the mobiles' labels. Generating functions for mobiles are shown to obey systems of algebraic recursion relations.
The cd-index of Bruhat Intervals
Authors: Reading Nathan
Published: January 2020

We study flag enumeration in intervals in the Bruhat order on a Coxeter group by means of a structural recursion on intervals in the Bruhat order. The recursion gives the isomorphism type of a Bruhat interval in terms of smaller intervals, using basic geometric operations which preserve PL sphericity and have a simple effect on the cd-index. This leads to a new proof that Bruhat intervals are PL spheres as well a recursive formula for the cd-index of a Bruhat interval. This recursive formula is used to prove that the cd-indices of Bruhat intervals span the space of cd-polynomials. The structural recursion leads to a conjecture that Bruhat spheres are "smaller" than polytopes. More precisely, we conjecture that if one fixes the lengths of $x$ and $y$, then the cd-index of a certain dual stacked polytope is a coefficientwise upper bound on the cd-indices of Bruhat intervals $[x,y]$. We show that this upper bound would be tight by constructing Bruhat intervals which are the face lattices of these dual stacked polytopes. As a weakening of a special case of the conjecture, we show that the flag h-vectors of lower Bruhat intervals are bounded above by the flag h-vectors of Boolean algebras (i. e. simplices).
Directed Subgraph Complexes
Authors: Hultman Axel
Published: January 2020

Let $G$ be a directed graph, and let $\Delta^{ACY}_G$ be the simplicial complex whose simplices are the edge sets of acyclic subgraphs of $G$. Similarly, we define $\Delta^{NSC}_G$ to be the simplicial complex with the edge sets of not strongly connected subgraphs of $G$ as simplices. We show that $\Delta^{ACY}_G$ is homotopy equivalent to the $(n-1-k)$-dimensional sphere if $G$ is a disjoint union of $k$ strongly connected graphs. Otherwise, it is contractible. If $G$ belongs to a certain class of graphs, the homotopy type of $\Delta^{NSC}_G$ is shown to be a wedge of $(2n-4)$-dimensional spheres. The number of spheres can easily be read off the chromatic polynomial of a certain associated undirected graph. We also consider some consequences related to finite topologies and hyperplane arrangements.
Reconstructing Integer Sets From Their Representation Functions
Authors: Lev Vsevolod F.
Published: January 2020

We give a simple common proof to recent results by Dombi and by Chen and Wang concerning the number of representations of an integer in the form $a_1+a_2$, where $a_1$ and $a_2$ are elements of a given infinite set of integers. Considering the similar problem for differences, we show that there exists a partition ${\Bbb N}=\cup_{k=1}^\infty A_k$ of the set of positive integers such that each $A_k$ is a perfect difference set (meaning that any non-zero integer has a unique representation as $a_1-a_2$ with $a_1,a_2\in A_k$). A number of open problems are presented.
Pólya's Permanent Problem
Authors: McCuaig William
Published: January 2020

A square real matrix is sign-nonsingular if it is forced to be nonsingular by its pattern of zero, negative, and positive entries. We give structural characterizations of sign-nonsingular matrices, digraphs with no even length dicycles, and square nonnegative real matrices whose permanent and determinant are equal. The structural characterizations, which are topological in nature, imply polynomial algorithms.
Hurwitz Equivalence in Tuples of Dihedral Groups, Dicyclic Groups, and Semidihedral Groups
Authors: Sia Charmaine
Published: January 2020

Let $D_{2N}$ be the dihedral group of order $2N$, ${\it Dic}_{4M}$ the dicyclic group of order $4M$, $SD_{2^m}$ the semidihedral group of order $2^m$, and $M_{2^m}$ the group of order $2^m$ with presentation $$M_{2^m} = \langle \alpha, \beta \mid \alpha^{2^{m-1}} = \beta^2 = 1,\ \beta\alpha\beta^{-1} = \alpha^{2^{m-2}+1} \rangle.$$ We classify the orbits in $D_{2N}^n$, ${\it Dic}_{4M}^n$, $SD_{2^m}^n$, and $M_{2^m}^n$ under the Hurwitz action.
Dominance Order and Graphical Partitions
Authors: Kohnert Axel
Published: January 2020

We gave a new criterion for graphical partitions. We derive a new recursion formula, which allows the computation of the number $g(n)$ of graphical partitions of weight $n$ for up to $n>900$.
Tight Estimates for Eigenvalues of Regular Graphs
Authors: Nilli A.
Published: January 2020

It is shown that if a $d$-regular graph contains $s$ vertices so that the distance between any pair is at least $4k$, then its adjacency matrix has at least $s$ eigenvalues which are at least $2 \sqrt {d-1} \cos \big({\pi\over 2 k}\big)$. A similar result has been proved by Friedman using more sophisticated tools.
Weights of Partitions and Character Zeros
Authors: Bessenrodt Christine , Olsson Jørn B.
Published: January 2020

We classify partitions which are of maximal $p$-weight for all odd primes $p$. As a consequence, we show that any non-linear irreducible character of the symmetric and alternating groups vanishes on some element of prime order.
Periodicity in Quasipolynomial Convolution
Authors: Zaslavsky Thomas
Published: January 2020

The leading term of a convolution of quasipolynomials with periods $p$ and $q$ is periodic with period $\gcd(p,q)$, smaller than expected. The degree of the convolution is usually $d+e+1$; we characterize the exceptions. To do this we need to characterize the null space of a circulant matrix.
On the Number of Fully Packed Loop Configurations with a Fixed Associated Matching
Authors: Caselli F. , Krattenthaler C. , Lass B. , Nadeau P.
Published: January 2020

We show that the number of fully packed loop configurations corresponding to a matching with $m$ nested arches is polynomial in $m$ if $m$ is large enough, thus essentially proving two conjectures by Zuber [Electronic J. Combin. 11(1) (2004), Article #R13].
A $q$-Analogue of Faulhaber's Formula for Sums of Powers
Authors: Guo Victor J. W. , Zeng Jiang
Published: January 2020

Let $$ S_{m,n}(q):=\sum_{k=1}^{n}\frac{1-q^{2k}}{1-q^2} \left(\frac{1-q^k}{1-q}\right)^{m-1}q^{\frac{m+1}{2}(n-k)}. $$ Generalizing the formulas of Warnaar and Schlosser, we prove that there exist polynomials $P_{m,k}(q)\in{\Bbb Z}[q]$ such that $$ S_{2m+1,n}(q) =\sum_{k=0}^{m}(-1)^kP_{m,k}(q) \frac{(1-q^n)^{m+1-k}(1-q^{n+1})^{m+1-k}q^{kn}} {(1-q^2)(1-q)^{2m-3k}\prod_{i=0}^{k}(1-q^{m+1-i})}, $$ and solve a problem raised by Schlosser. We also show that there is a similar formula for the following $q$-analogue of alternating sums of powers: $$ T_{m,n}(q):=\sum_{k=1}^{n}(-1)^{n-k} \left(\frac{1-q^k}{1-q}\right)^{m}q^{\frac{m}{2}(n-k)}. $$
RSK Insertion for Set Partitions and Diagram Algebras
Authors: Halverson Tom , Lewandowski Tim
Published: January 2020

We give combinatorial proofs of two identities from the representation theory of the partition algebra ${\Bbb C} A_k(n)$, $n \ge 2k$. The first is $n^k = \sum_\lambda f^\lambda m_k^\lambda$, where the sum is over partitions $\lambda$ of $n$, $f^\lambda$ is the number of standard tableaux of shape $\lambda$, and $m_k^\lambda$ is the number of "vacillating tableaux" of shape $\lambda$ and length $2k$. Our proof uses a combination of Robinson-Schensted-Knuth insertion and jeu de taquin. The second identity is $B(2k) = \sum_\lambda (m_k^\lambda)^2$, where $B(2k)$ is the number of set partitions of $\{1, \ldots, 2k\}$. We show that this insertion restricts to work for the diagram algebras which appear as subalgebras of the partition algebra: the Brauer, Temperley-Lieb, planar partition, rook monoid, planar rook monoid, and symmetric group algebras.
Face Numbers and Nongeneric Initial Ideals
Authors: Babson Eric , Novik Isabella
Published: January 2020

Certain necessary conditions on the face numbers and Betti numbers of simplicial complexes endowed with a proper action of a prime order cyclic group are established. A notion of colored algebraic shifting is defined and its properties are studied. As an application a new simple proof of the characterization of the flag face numbers of balanced Cohen-Macaulay complexes originally due to Stanley (necessity) and Björner, Frankl, and Stanley (sufficiency) is given. The necessity portion of their result is generalized to certain conditions on the face numbers and Betti numbers of balanced Buchsbaum complexes.
A Refinement of Cayley's Formula for Trees
Authors: Gessel Ira M. , Seo Seunghyun
Published: January 2020

A proper vertex of a rooted tree with totally ordered vertices is a vertex that is the smallest of all its descendants. We count several kinds of labeled rooted trees and forests by the number of proper vertices. Our results are all expressed in terms of the polynomials $$P_n(a,b,c)= c\prod_{i=1}^{n-1}(ia+(n-i)b +c),$$ which reduce to $(n+1)^{n-1}$ for $a=b=c=1$. Our study of proper vertices was motivated by Postnikov's hook length formula $$(n+1)^{n-1}={n!\over 2^n}\sum _T \prod_{v}\left(1+{1\over h(v)}\right),$$ where the sum is over all unlabeled binary trees $T$ on $n$ vertices, the product is over all vertices $v$ of $T$, and $h(v)$ is the number of descendants of $v$ (including $v$). Our results give analogues of Postnikov's formula for other types of trees, and we also find an interpretation of the polynomials $P_n(a,b,c)$ in terms of parking functions.
Sequentially Perfect and Uniform One-Factorizations of the Complete Graph
Authors: Dinitz Jeffrey H. , Dukes Peter , Stinson Douglas R.
Published: January 2020

In this paper, we consider a weakening of the definitions of uniform and perfect one-factorizations of the complete graph. Basically, we want to order the $2n-1$ one-factors of a one-factorization of the complete graph $K_{2n}$ in such a way that the union of any two (cyclically) consecutive one-factors is always isomorphic to the same two-regular graph. This property is termed sequentially uniform; if this two-regular graph is a Hamiltonian cycle, then the property is termed sequentially perfect. We will discuss several methods for constructing sequentially uniform and sequentially perfect one-factorizations. In particular, we prove for any integer $n \geq 1$ that there is a sequentially perfect one-factorization of $K_{2n}$. As well, for any odd integer $m \geq 1$, we prove that there is a sequentially uniform one-factorization of $K_{2^t m}$ of type $(4,4,\dots,4)$ for all integers $t \geq 2 + \lceil \log_2 m \rceil$ (where type $(4,4,\dots,4)$ denotes a two-regular graph consisting of disjoint cycles of length four).
Conjectured Statistics for the Higher $q,t$-Catalan Sequences
Authors: Loehr Nicholas A.
Published: January 2020

This article describes conjectured combinatorial interpretations for the higher $q,t$-Catalan sequences introduced by Garsia and Haiman, which arise in the theory of symmetric functions and Macdonald polynomials. We define new combinatorial statistics generalizing those proposed by Haglund and Haiman for the original $q,t$-Catalan sequence. We prove explicit summation formulas, bijections, and recursions involving the new statistics. We show that specializations of the combinatorial sequences obtained by setting $t=1$ or $q=1$ or $t=1/q$ agree with the corresponding specializations of the Garsia-Haiman sequences. A third statistic occurs naturally in the combinatorial setting, leading to the introduction of $q,t,r$-Catalan sequences. Similar combinatorial results are proved for these trivariate sequences.
Counting peaks and valleys in $k$-colored Motzkin paths
Authors: Sapounakis A. , Tsikouras P.
Published: January 2020

This paper deals with the enumeration of $k$-colored Motzkin paths with a fixed number of (left and right) peaks and valleys. Further enumeration results are obtained when peaks and valleys are counted at low and high level. Many well-known results for Dyck paths are obtained as special cases.
A Simple Proof of the Aztec Diamond Theorem
Authors: Eu Sen-Peng , Fu Tung-Shan
Published: January 2020

Based on a bijection between domino tilings of an Aztec diamond and non-intersecting lattice paths, a simple proof of the Aztec diamond theorem is given by means of Hankel determinants of the large and small Schröder numbers.
Atomic Latin Squares based on Cyclotomic Orthomorphisms
Authors: Wanless Ian M.
Published: January 2020

Atomic latin squares have indivisible structure which mimics that of the cyclic groups of prime order. They are related to perfect $1$-factorisations of complete bipartite graphs. Only one example of an atomic latin square of a composite order (namely 27) was previously known. We show that this one example can be generated by an established method of constructing latin squares using cyclotomic orthomorphisms in finite fields. The same method is used in this paper to construct atomic latin squares of composite orders 25, 49, 121, 125, 289, 361, 625, 841, 1369, 1849, 2809, 4489, 24649 and 39601. It is also used to construct many new atomic latin squares of prime order and perfect $1$-factorisations of the complete graph $K_{q+1}$ for many prime powers $q$. As a result, existence of such a factorisation is shown for the first time for $q$ in $\big\{$529, 2809, 4489, 6889, 11449, 11881, 15625, 22201, 24389, 24649, 26569, 29929, 32041, 38809, 44521, 50653, 51529, 52441, 63001, 72361, 76729, 78125, 79507, 103823, 148877, 161051, 205379, 226981, 300763, 357911, 371293, 493039, 571787$\big\}$. We show that latin squares built by the 'orthomorphism method' have large automorphism groups and we discuss conditions under which different orthomorphisms produce isomorphic latin squares. We also introduce an invariant called the train of a latin square, which proves to be useful for distinguishing non-isomorphic examples.
Wilf Classes of Pairs of Permutations of Length 4
Authors: Le Ian
Published: January 2020

$S_n(\pi_1,\pi_2,\dots, \pi_r)$ denotes the set of permutations of length $n$ that have no subsequence with the same order relations as any of the $\pi_i$. In this paper we show that $|S_n(1342,2143)|=|S_n(3142,2341)|$ and $|S_n(1342,3124)|=|S_n(1243,2134)|$. These two facts complete the classification of Wilf-equivalence classes for pairs of permutations of length four. In both instances we exhibit bijections between the sets using the idea of a "block", and in the former we find a generating function for $|S_n(1342,2143)|$.
Sorting Classes
Authors: Albert M. H. , Aldred R. E. L. , Atkinson M. D. , Handley C. C. , Holton D. A. , McCaughan D. J.
Published: January 2020

Weak and strong sorting classes are pattern-closed classes that are also closed downwards under the weak and strong orders on permutations. They are studied using partial orders that capture both the subpermutation order and the weak or strong order. In both cases they can be characterised by forbidden permutations in the appropriate order. The connection with the corresponding forbidden permutations in pattern-closed classes is explored. Enumerative results are found in both cases.
Lower Bound for the Size of Maximal Nontraceable Graphs
Authors: Frick Marietjie , Singleton Joy
Published: January 2020

Let $g(n)$ denote the minimum number of edges of a maximal nontraceable graph of order $n$. Dudek, Katona and Wojda (2003) showed that $ g(n) \geq \lceil {3n-2\over2} \rceil -2$ for $ n \ge 20$ and $ g(n) \le \lceil {3n-2\over2} \rceil$ for $ n \geq 54$ as well as for $n \in I= \{22,23,30,31,38,39,40,41,42,43,46,$ $47,48,49,50,51\}$. We show that $ g(n) = \lceil {3n-2\over2} \rceil$ for $ n \geq 54$ as well as for $n \in I \cup \{12,13\}$ and we determine $g(n)$ for $n \le 9$.
Long Heterochromatic Paths in Edge-Colored Graphs
Authors: Chen He , Li Xueliang
Published: January 2020

Let $G$ be an edge-colored graph. A heterochromatic path of $G$ is such a path in which no two edges have the same color. $d^c(v)$ denotes the color degree of a vertex $v$ of $G$. In a previous paper, we showed that if $d^c(v)\geq k$ for every vertex $v$ of $G$, then $G$ has a heterochromatic path of length at least $\lceil{k+1\over 2}\rceil$. It is easy to see that if $k=1,2$, $G$ has a heterochromatic path of length at least $k$. Saito conjectured that under the color degree condition $G$ has a heterochromatic path of length at least $\lceil{2k+1\over 3}\rceil$. Even if this is true, no one knows if it is a best possible lower bound. Although we cannot prove Saito's conjecture, we can show in this paper that if $3\leq k\leq 7$, $G$ has a heterochromatic path of length at least $k-1,$ and if $k\geq 8$, $G$ has a heterochromatic path of length at least $\lceil{3k\over 5}\rceil+1$. Actually, we can show that for $1\leq k\leq 5$ any graph $G$ under the color degree condition has a heterochromatic path of length at least $k$, with only one exceptional graph $K_4$ for $k=3$, one exceptional graph for $k=4$ and three exceptional graphs for $k=5$, for which $G$ has a heterochromatic path of length at least $k-1$. Our experience suggests us to conjecture that under the color degree condition $G$ has a heterochromatic path of length at least $k-1$.
Indecomposable Tilings of the Integers with Exponentially Long Periods
Authors: Steinberger John P.
Published: January 2020

Let $A$ be a finite multiset of integers. A second multiset of integers $T$ is said to be an $A$-tiling of level $d$ if every integer can be expressed in exactly $d$ ways as the sum of an element of $A$ and of an element of $T$. The set $T$ is indecomposable if it cannot be written as the disjoint union of two proper subsets that are also $A$-tilings. In this paper we show how to construct indecomposable tilings that have exponentially long periods. More precisely, we give a sequence of multisets $(A_k)_{k=1}^{\infty}$ such that each $A_k$ admits an indecomposable tiling $T_k$ of period greater than $e^{c\root 3\of{n_k\log(n_k)}}$ where $n_k = {\rm diam}(A_k) = \max\{j \in A_k\} - \min\{j \in A_k\}$ tends to infinity and where $c > 0$ is some constant independent of $k$.
Erdős-Ko-Rado theorems for uniform set-partition systems
Authors: Meagher Karen , Moura Lucia
Published: January 2020

Two set partitions of an $n$-set are said to $t$-intersect if they have $t$ classes in common. A $k$-partition is a set partition with $k$ classes and a $k$-partition is said to be uniform if every class has the same cardinality $c=n/k$. In this paper, we prove a higher order generalization of the Erdős-Ko-Rado theorem for systems of pairwise $t$-intersecting uniform $k$-partitions of an $n$-set. We prove that for $n$ large enough, any such system contains at most $${1\over(k-t)!} {n-tc \choose c} {n-(t+1)c \choose c} \cdots {n-(k-1)c \choose c}$$ partitions and this bound is only attained by a trivially $t$-intersecting system. We also prove that for $t=1$, the result is valid for all $n$. We conclude with some conjectures on this and other types of intersecting partition systems.
Two-Person Symmetric Whist
Authors: Wästlund Johan
Published: January 2020

We introduce a two-person perfect information model of trick taking games. A set of cards is distributed between two players, and play proceeds in tricks with the obligation to follow suit, as in many real-world card games. We assume that in each suit, the two players have the same number of cards. Under this assumption, we show how to assign a value from a certain semigroup to each single-suit card distribution in such a way that the outcome of a multi-suit deal under optimal play is determined by the sum of the values of the individual suits.
The Generalized Schröder Theory
Authors: Song Chunwei
Published: January 2020

While the standard Catalan and Schröder theories both have been extensively studied, people have only begun to investigate higher dimensional versions of the Catalan number (see, say, the 1991 paper of Hilton and Pedersen, and the 1996 paper of Garsia and Haiman). In this paper, we study a yet more general case, the higher dimensional Schröder theory. We define $m$-Schröder paths, find the number of such paths from $(0,0)$ to $(mn, n)$, and obtain some other results on the $m$-Schröder paths and $m$-Schröder words. Hoping to generalize classical $q$-analogue results of the ordinary Catalan and Schröder numbers, such as in the works of Fürlinger and Hofbauer, Cigler, and Bonin, Shapiro and Simion, we derive a $q$-identity which would welcome a combinatorial interpretation. Finally, we introduce the ($q, t$)-$m$-Schröder polynomial through "$m$-parking functions" and relate it to the $m$-Shuffle Conjecture of Haglund, Haiman, Loehr, Remmel and Ulyanov.
A Note on Three Types of Quasisymmetric Functions
Authors: Petersen T. Kyle
Published: January 2020

In the context of generating functions for $P$-partitions, we revisit three flavors of quasisymmetric functions: Gessel's quasisymmetric functions, Chow's type B quasisymmetric functions, and Poirier's signed quasisymmetric functions. In each case we use the inner coproduct to give a combinatorial description (counting pairs of permutations) to the multiplication in: Solomon's type A descent algebra, Solomon's type B descent algebra, and the Mantaci-Reutenauer algebra, respectively. The presentation is brief and elementary, our main results coming as consequences of $P$-partition theorems already in the literature.
A Combinatorial Proof of a Symmetric $q$-Pfaff-Saalschütz Identity
Authors: Guo Victor J. W. , Zeng Jiang
Published: January 2020

We give a bijective proof of a symmetric $q$-identity on $_4\phi_3$ series, which is a symmetric generalization of the famous $q$-Pfaff-Saalschütz identity. An elementary proof of this identity is also given.
A Pfaffian–Hafnian Analogue of Borchardt's Identity
Authors: Ishikawa Masao , Kawamuko Hiroyuki , Okada Soichi
Published: January 2020

We prove $$ {\rm Pf}\! \left( { x_i - x_j \over (x_i + x_j)^2 } \right)_{1 \le i, j \le 2n} = \prod_{1 \le i < j \le 2n}{ x_i - x_j \over x_i + x_j } {\rm Hf}\! \left( { 1 \over x_i + x_j } \right)_{1 \le i, j \le 2n} $$ (and its variants) by using complex analysis. This identity can be regarded as a Pfaffian–Hafnian analogue of Borchardt's identity and as a generalization of Schur's identity.
Parity Theorems for Statistics on Domino Arrangements
Authors: Shattuck Mark A. , Wagner Carl G.
Published: January 2020

We study special values of Carlitz's $q$-Fibonacci and $q$-Lucas polynomials $F_n(q,t)$ and $L_n(q,t)$. Brief algebraic and detailed combinatorial treatments are presented, the latter based on the fact that these polynomials are bivariate generating functions for a pair of statistics defined, respectively, on linear and circular domino arrangements.
Distinguishing Cartesian Powers of Graphs
Authors: Albertson Michael O.
Published: January 2020

Given a graph $G$, a labeling $c:V(G) \rightarrow \{1, 2, \ldots, d\}$ is said to be $d$-distinguishing if the only element in ${\rm Aut}(G)$ that preserves the labels is the identity. The distinguishing number of $G$, denoted by $D(G)$, is the minimum $d$ such that $G$ has a $d$-distinguishing labeling. If $G \square H$ denotes the Cartesian product of $G$ and $H$, let $G^{^2} = G \square G$ and $G^{^r} = G \square G^{^{r-1}}$. A graph $G$ is said to be prime with respect to the Cartesian product if whenever $G \cong G_1 \square G_2$, then either $G_1$ or $G_2$ is a singleton vertex. This paper proves that if $G$ is a connected, prime graph, then $D(G^{^r}) = 2$ whenever $r \geq 4$.
The Sum of Degrees in Cliques
Authors: Bollobás Béla , Nikiforov Vladimir
Published: January 2020

For every graph $G,$ let $$ \Delta_{r}\left(G\right) =\max\left\{ \sum_{u\in R}d\left( u\right) :R\hbox{ is an }r\hbox{-clique of }G\right\} $$ and let $\Delta_{r}\left( n,m\right) $ be the minimum of $\Delta_{r}\left( G\right)$ taken over all graphs of order $n$ and size $m$. Write $t_{r}\left( n\right) $ for the size of the $r$-chromatic Turán graph of order $n$. Improving earlier results of Edwards and Faudree, we show that for every $r\geq2,$ if $m\geq t_{r}\left( n\right)$, then $$ \Delta_{r}\left( n,m\right) \geq\frac{2rm}{n},\qquad(1) $$ as conjectured by Bollobás and Erdős. It is known that inequality (1) fails for $m < t_{r}\left(n\right)$. However, we show that for every $\varepsilon>0,$ there is $\delta>0$ such that if $m>t_{r}\left( n\right) -\delta n^{2}$ then $$ \Delta_{r}\left( n,m\right) \geq\left( 1-\varepsilon\right) \frac{2rm}{n}. $$
A Tribute to Herbert S. Wilf
Authors: Chung Fan , Hutchinson Joan
Published: January 2020

A Tribute to Herbert S. Wilf
In Praise of an Elementary Identity of Euler
Authors: Bhatnagar Gaurav
Published: January 2020

We survey the applications of an elementary identity used by Euler in one of his proofs of the Pentagonal Number Theorem. Using a suitably reformulated version of this identity that we call Euler's Telescoping Lemma, we give alternate proofs of all the key summation theorems for terminating Hypergeometric Series and Basic Hypergeometric Series, including the terminating Binomial Theorem, the Chu–Vandermonde sum, the Pfaff–Saalschütz sum, and their $q$-analogues. We also give a proof of Jackson's $q$-analog of Dougall's sum, the sum of a terminating, balanced, very-well-poised $_8\phi_7$ sum. Our proofs are conceptually the same as those obtained by the WZ method, but done without using a computer. We survey identities for Generalized Hypergeometric Series given by Macdonald, and prove several identities for $q$-analogs of Fibonacci numbers and polynomials and Pell numbers that have appeared in combinatorial contexts. Some of these identities appear to be new.
The Abel-Zeilberger Algorithm
Authors: Chen William Y.C. , Hou Qing-Hu , Jin Hai-Tao
Published: January 2020

By combining Abel's lemma on summation by parts with Zeilberger's algorithm, we give an algorithm, called the Abel-Zeilberger algorithm, to find recurrence relations for definite summations. The role of Abel's lemma can be extended to the case of linear difference operators with polynomial coefficients. This approach can be used to verify and discover identities involving harmonic numbers and derangement numbers. As examples, we use the Abel-Zeilberger algorithm to prove the Paule-Schneider identities, an identity of Andrews and Paule, and an identity of Calkin.
Continued Fractions Related to $(t,q)$-Tangents and Variants
Authors: Prodinger Helmut
Published: January 2020

For the $q$-tangent function introduced by Foata and Han (this volume) we provide the continued fraction expansion, by creative guessing and a routine verification. Then an even more recent $q$-tangent function due to Cieslinski is also expanded. Lastly, a general version is considered that contains both versions as special cases.
A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid
Authors: Cranston Daniel W. , Yu Gexin
Published: January 2020

Given a graph $G$, an identifying code ${\cal D}\subseteq V(G)$ is a vertex set such that for any two distinct vertices $v_1,v_2\in V(G)$, the sets $N[v_1]\cap{\cal D}$ and $N[v_2]\cap{\cal D}$ are distinct and nonempty (here $N[v]$ denotes a vertex $v$ and its neighbors). We study the case when $G$ is the infinite hexagonal grid $H$. Cohen et.al. constructed two identifying codes for $H$ with density $3/7$ and proved that any identifying code for $H$ must have density at least $16/39\approx0.410256$. Both their upper and lower bounds were best known until now. Here we prove a lower bound of $12/29\approx0.413793$.
The Number of Intervals in the $m$-Tamari Lattices
Authors: Bousquet-Mélou Mireille , Fusy Éric , Préville-Ratelle Louis-François
Published: January 2020

An $m$-ballot path of size $n$ is a path on the square grid consisting of north and east steps, starting at $(0,0)$, ending at $(mn,n)$, and never going below the line $\{x=my\}$. The set of these paths can be equipped with a lattice structure, called the $m$-Tamari lattice and denoted by $\mathcal{T}_n^{(m)}$, which generalizes the usual Tamari lattice $\mathcal{T}_n$ obtained when $m=1$. We prove that the number of intervals in this lattice is $$ \frac {m+1}{n(mn+1)} {(m+1)^2 n+m\choose n-1}. $$ This formula was recently conjectured by Bergeron in connection with the study of diagonal coinvariant spaces. The case $m=1$ was proved a few years ago by Chapoton. Our proof is based on a recursive description of intervals, which translates into a functional equation satisfied by the associated generating function. The solution of this equation is an algebraic series, obtained by a guess-and-check approach. Finding a bijective proof remains an open problem.
Bounds for Identifying Codes in Terms of Degree Parameters
Authors: Foucaud Florent , Perarnau Guillem
Published: January 2020

An identifying code is a subset of vertices of a graph such that each vertex is uniquely determined by its neighbourhood within the identifying code. If $\gamma^{\text{ID}}(G)$ denotes the minimum size of an identifying code of a graph $G$, it was conjectured by F. Foucaud, R. Klasing, A. Kosowski and A. Raspaud that there exists a constant $c$ such that if a connected graph $G$ with $n$ vertices and maximum degree $d$ admits an identifying code, then $\gamma^{\text{ID}}(G)\leq n-\tfrac{n}{d}+c$. We use probabilistic tools to show that for any $d\geq 3$, $\gamma^{\text{ID}}(G)\leq n-\tfrac{n}{\Theta(d)}$ holds for a large class of graphs containing, among others, all regular graphs and all graphs of bounded clique number. This settles the conjecture (up to constants) for these classes of graphs. In the general case, we prove $\gamma^{\text{ID}}(G)\leq n-\tfrac{n}{\Theta(d^{3})}$. In a second part, we prove that in any graph $G$ of minimum degree $\delta$ and girth at least 5, $\gamma^{\text{ID}}(G)\leq(1+o_\delta(1))\tfrac{3\log\delta}{2\delta}n$. Using the former result, we give sharp estimates for the size of the minimum identifying code of random $d$-regular graphs, which is about $\tfrac{\log d}{d}n$.
Efficient Oracles for Generating Binary Bubble Languages
Authors: Sawada J. , Williams A.
Published: January 2020

A simple meta-algorithm is provided to efficiently generate a wide variety of combinatorial objects that can be represented by binary strings with a fixed number of 1s. Such objects include: $k$-ary Dyck words, connected unit interval graphs, binary strings lexicographically larger than $\omega$, those avoiding $10^k$ for fixed $k$, reversible strings and feasible solutions to knapsack problems. Each object requires only a very simple object-specific subroutine (oracle) that plugs into the generic cool-lex framework introduced by Williams.   The result is that each object can be generated in amortized $O(1)$-time.  Moreover, the strings can be listed in either a conventional co-lexicographic order, or in the cool-lex Gray code order.
Surprising Symmetries in Objects Counted by Catalan Numbers
Authors: Bóna Miklós
Published: January 2020

We prove that the total number $S_{n,132}(q)$ of copies of  the pattern $q$ in all 132-avoiding permutations of length $n$ is the same for $q=231$, $q=312$, or $q=213$. We provide a combinatorial proof for this unexpected threefold symmetry. We then significantly generalize this result by proving a large family of non-trivial  equalities of the type $S_{n,132}(q)=S_{n,132}(q')$.
Non-Contiguous Pattern Avoidance in Binary Trees
Authors: Dairyko Michael , Pudwell Lara , Tyner Samantha , Wynn Casey
Published: January 2020

In this paper we consider the enumeration of binary trees avoiding non-contiguous binary tree patterns. We begin by computing closed formulas for the number of trees avoiding a single binary tree pattern with 4 or fewer leaves and compare these results to analogous work for contiguous tree patterns. Next, we give an explicit generating function that counts binary trees avoiding a single non-contiguous tree pattern according to number of leaves and show that there is exactly one Wilf class of k-leaf tree patterns for any positive integer k.  In addition, we give a bijection between between certain sets of pattern-avoiding trees and sets of pattern-avoiding permutations.  Finally, we enumerate binary trees that simultaneously avoid more than one tree pattern.
Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number
Authors: Collins Karen L. , Trenk Ann
Published: January 2020

Nordhaus and Gaddum proved, for any graph $G$, that $\chi(G) + \chi(\overline{G}) \leq n + 1$, where $\chi$ is the chromatic number and $n=|V(G)|$. Finck characterized the class of graphs, which we call NG-graphs, that satisfy equality in this bound. In this paper, we provide a new characterization of NG-graphs, based on vertex degrees, which yields a new polynomial-time recognition algorithm and efficient computation of the chromatic number of NG-graphs. Our motivation comes from our theorem that generalizes the Nordhaus-Gaddum theorem to the distinguishing chromatic number. For any graph $G$, $\chi_D(G) +\chi_D(\overline{G})\leq n+D(G)$. We call the set of graphs that satisfy equality in this bound NGD-graphs, and characterize the set of graphs that are simultaneously NG-graphs and NGD-graphs.
Spectral Extrema for Graphs: The Zarankiewicz Problem
Authors: Babai László , Guiduli Barry
Published: January 2020

Let $G$ be a graph on $n$ vertices with spectral radius $\lambda$ (this is the largest eigenvalue of the adjacency matrix of $G$). We show that if $G$ does not contain the complete bipartite graph $K_{t ,s}$ as a subgraph, where $2\le t \le s$, then $$\lambda \le \Big((s-1)^{1/t }+o(1)\Big)n^{1-1/t }$$ for fixed $t$ and $s$ while $n\to\infty$. Asymptotically, this bound matches the Kővári-Turán-Sós upper bound on the average degree of $G$ (the Zarankiewicz problem).
Andrews' Conjecture on a $_4\phi_3$ Summation and its Extensions
Authors: Mu Yan-Ping
Published: January 2020

We give a computer proof of Andrews' conjecture on a $_4\phi_3$ summation and extend the result to a family of $_4\phi_3$ summations.
Poset Pinball, Highest Forms, and $(n-2,2)$ Springer Varieties
Authors: Dewitt Barry , Harada Megumi
Published: January 2020

In this manuscript we study type $A$ nilpotent Hessenberg varieties equipped with a natural $S^1$-action using techniques introduced by Tymoczko, Harada-Tymoczko, and Bayegan-Harada, with a particular emphasis on a special class of nilpotent Springer varieties corresponding to the partition $\lambda= (n-2,2)$ for $n \geq 4$. First we define the adjacent-pair matrix corresponding to any filling of a Young diagram with $n$ boxes with the alphabet $\{1,2,\ldots,n\}$. Using the adjacent-pair matrix we make more explicit and also extend some statements concerning highest forms of linear operators in previous work of Tymoczko. Second, for a nilpotent operator $N$ and Hessenberg function $h$, we construct an explicit bijection between the $S^1$-fixed points of the nilpotent Hessenberg variety Hess$(N,h)$ and the set of $(h,\lambda_N)$-permissible fillings of the Young diagram $\lambda_N$. Third, we use poset pinball, the combinatorial game introduced by Harada and Tymoczko, to study the $S^1$-equivariant cohomology of type $A$ Springer varieties $\mathcal{S}_{(n-2,2)}$ associated to Young diagrams of shape $(n-2,2)$ for $n\geq 4$. Specifically, we use the dimension pair algorithm for Betti-acceptable pinball described by Bayegan and Harada to specify a subset of the equivariant Schubert classes in the $\mathbb{T}$-equivariant cohomology of the flag variety $\mathcal{F}\ell ags(\mathbb{C}^n) \cong GL(n,\mathbb{C})/B$ which maps to a module basis of $H^*_{S^1}(\mathcal{S}_{(n-2,2)})$ under the projection map $H^*_\mathbb{T}(\mathcal{F}\ell ags(\mathbb{C}^n)) \to H^*_{S^1}(\mathcal{S}_{(n-2,2)})$. Our poset pinball module basis is not poset-upper-triangular; this is the first concrete such example in the literature. A straightforward consequence of our proof is that there exists a simple and explicit change of basis which transforms our poset pinball basis to a poset-upper-triangular module basis for $H^*_{S^1}(\mathcal{S}_{(n-2,2)})$. We close with open questions for future work.
Extensions of Spivey's Bell Number Formula
Authors: Xu Aimin
Published: January 2020

We establish an extension of Spivey's Bell number formula and its associated Bell polynomial extension by using Hsu-Shiue's generalized Stirling numbers. By means of the extension of Spivey's Bell number formula we also extend Gould-Quaintance's new Bell number formulas.
Avoiding $(m,m,m)$-Arrays of Order $n=2^k$
Authors: Andrén Lina J.
Published: January 2020

An $(m,m,m)$-array of order $n$ is an $n\times n$ array such that each cell is assigned a set of at most $m$ symbols from $\left\{1,\dots ,n\right\}$ such that no symbol occurs more than $m$ times in any row or column. An $ (m,m,m)$-array is called avoidable if there exists a Latin square such that no cell in the Latin square contains a symbol that also belongs to the set assigned to the corresponding cell in the array. We show that there is a constant $\gamma $ such that if $m\le\gamma 2^k$ and $k\ge14$, then any $(m,m,m)$-array of order $n=2^k$ is avoidable. Such a constant $\gamma$ has been conjectured to exist for all $n$ by Häggkvist.
Distortion of the Hyperbolicity Constant of a Graph
Authors: Carballosa Walter , Pestana Domingo , Rodríguez José M. , Sigarreta José M.
Published: January 2020

If $X$ is a geodesic metric space and $x_1,x_2,x_3\in X$, a geodesic triangle $T=\{x_1,x_2,x_3\}$ is the union of the three geodesics $[x_1x_2]$, $[x_2x_3]$ and $[x_3x_1]$ in $X$. The space $X$ is $\delta$-hyperbolic $($in the Gromov sense$)$ if any side of $T$ is contained in a $\delta$-neighborhood of the union of the other two sides, for every geodesic triangle $T$ in $X$. We denote by $\delta(X)$ the sharp hyperbolicity constant of $X$, i.e., $\delta(X):=\inf\{\delta\ge 0: \, X \, \text{ is $\delta$-hyperbolic}\,\}$. The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it. One of the main aims of this paper is to obtain quantitative information about the distortion of the hyperbolicity constant of the graph $G\setminus e$ obtained from the graph $G$ by deleting an arbitrary edge $e$ from it. These inequalities allow to obtain the other main result of this paper, which characterizes in a quantitative way the hyperbolicity of any graph in terms of local hyperbolicity.
Parity Index of Binary Words and Powers of Prime Words
Authors: Ilić Aleksandar , Klavžar Sandi , Rho Yoomi
Published: January 2020

Let $f$ be a binary word and let ${\cal F}_d(f)$ be the set of words of length $d$ which do not contain $f$ as a factor (alias words that avoid the pattern $f$). A word is called even/odd if it contains an even/odd number of 1s. The parity index of $f$ (of dimension $d$) is introduced as the difference between the number of even words and the number of odd words in ${\cal F}_d(f)$. A word $f$ is called prime if every nontrivial suffix of $f$ is different from the prefix of $f$ of the same length. It is proved that if $f$ is a power of a prime word, then the absolute value of the parity index of $f$ is at most 1. We conjecture that no other word has this property and prove the conjecture for words $0^r1^s0^t$, $r,s,t \geq 1$. The conjecture has also been verified by computer for all words $f$ of length at most 10 and all $d\le 31$.