bluuebunny/crossref_metadata_2025 huggingface dataset:
The Generating Function of Ternary Trees and Continued Fractions
Authors: Gessel Ira M. , Xin Guoce
Published: January 2020

Michael Somos conjectured a relation between Hankel determinants whose entries ${1\over 2n+1}{3n\choose n}$ count ternary trees and the number of certain plane partitions and alternating sign matrices. Tamm evaluated these determinants by showing that the generating function for these entries has a continued fraction that is a special case of Gauss's continued fraction for a quotient of hypergeometric series. We give a systematic application of the continued fraction method to a number of similar Hankel determinants. We also describe a simple method for transforming determinants using the generating function for their entries. In this way we transform Somos's Hankel determinants to known determinants, and we obtain, up to a power of $3$, a Hankel determinant for the number of alternating sign matrices. We obtain a combinatorial proof, in terms of nonintersecting paths, of determinant identities involving the number of ternary trees and more general determinant identities involving the number of $r$-ary trees.
On Some Ramsey and Turán-Type Numbers for Paths and Cycles
Authors: Dzido Tomasz , Kubale Marek , Piwakowski Konrad
Published: January 2020

For given graphs $G_{1}, G_{2}, ... , G_{k}$, where $k \geq 2$, the multicolor Ramsey number $R(G_{1}, G_{2}, ... , G_{k})$ is the smallest integer $n$ such that if we arbitrarily color the edges of the complete graph on $n$ vertices with $k$ colors, there is always a monochromatic copy of $G_{i}$ colored with $i$, for some $1 \leq i \leq k$. Let $P_k$ (resp. $C_k$) be the path (resp. cycle) on $k$ vertices. In the paper we show that $R(P_3,C_k,C_k)=R(C_k,C_k)=2k-1$ for odd $k$. In addition, we provide the exact values for Ramsey numbers $R(P_{4}, P_{4}, C_{k})=k+2$ and $R(P_{3}, P_{5}, C_{k})=k+1$.
Relaxations of Ore's Condition on Cycles
Authors: Ainouche Ahmed
Published: January 2020

A simple, undirected $2$-connected graph $G$ of order $n$ belongs to class ${\cal O}(n$,$\varphi)$, $\varphi\geq0$, if $\sigma_{2}=n-\varphi.$ It is well known (Ore's theorem) that $G$ is hamiltonian if $\varphi= 0$, in which case the $2$-connectedness hypothesis is implied. In this paper we provide a method for studying this class of graphs. As an application we give a full characterization of graphs $G$ in ${\cal O}(n$,$\varphi)$, $\varphi\leq3$, in terms of their dual hamiltonian closure.
Classifying Descents According to Equivalence mod k
Authors: Kitaev Sergey , Remmel Jeffrey
Published: January 2020

In an earlier paper the authors refine the well-known permutation statistic "descent" by fixing parity of (exactly) one of the descent's numbers. In the current paper, we generalize the results of that earlier paper by studying descents according to whether the first or the second element in a descent pair is divisible by $k$ for some $k\geq 2$. We provide either an explicit or an inclusion-exclusion type formula for the distribution of the new statistics. Based on our results we obtain combinatorial proofs of a number of remarkable identities. We also provide bijective proofs of some of our results and state a number of open problems.
Hard Squares with Negative Activity and Rhombus Tilings of the Plane
Authors: Jonsson Jakob
Published: January 2020

Let $S_{m,n}$ be the graph on the vertex set ${\Bbb Z}_m \times {\Bbb Z}_n$ in which there is an edge between $(a,b)$ and $(c,d)$ if and only if either $(a,b) = (c,d\pm 1)$ or $(a,b) = (c \pm 1,d)$ modulo $(m,n)$. We present a formula for the Euler characteristic of the simplicial complex $\Sigma_{m,n}$ of independent sets in $S_{m,n}$. In particular, we show that the unreduced Euler characteristic of $\Sigma_{m,n}$ vanishes whenever $m$ and $n$ are coprime, thereby settling a conjecture in statistical mechanics due to Fendley, Schoutens and van Eerten. For general $m$ and $n$, we relate the Euler characteristic of $\Sigma_{m,n}$ to certain periodic rhombus tilings of the plane. Using this correspondence, we settle another conjecture due to Fendley et al., which states that all roots of $\det (xI-T_m)$ are roots of unity, where $T_m$ is a certain transfer matrix associated to $\{\Sigma_{m,n} : n \ge 1\}$. In the language of statistical mechanics, the reduced Euler characteristic of $\Sigma_{m,n}$ coincides with minus the partition function of the corresponding hard square model with activity $-1$.
Shift-Induced Dynamical Systems on Partitions and Compositions
Authors: Hopkins Brian , Jones Michael A.
Published: January 2020

The rules of "Bulgarian solitaire" are considered as an operation on the set of partitions to induce a finite dynamical system. We focus on partitions with no preimage under this operation, known as Garden of Eden points, and their relation to the partitions that are in cycles. These are the partitions of interest, as we show that starting from the Garden of Eden points leads through the entire dynamical system to all cycle partitions. A primary result concerns the number of Garden of Eden partitions (the number of cycle partitions is known from Brandt). The same operation and questions can be put in the context of compositions (ordered partitions), where we give stronger results.
Identifying $X$-Trees with Few Characters
Authors: Bordewich Magnus , Semple Charles , Steel Mike
Published: January 2020

Previous work has shown the perhaps surprising result that, for any binary phylogenetic tree ${\cal T}$, there is a set of four characters that define ${\cal T}$. Here we deal with the general case, where ${\cal T}$ is an arbitrary $X$-tree. We show that if $d$ is the maximum degree of any vertex in ${\cal T}$, then the minimum number of characters that identify ${\cal T}$ is $\log_2 d$ (up to a small multiplicative constant).
Asymptotics for Incidence Matrix Classes
Authors: Cameron Peter , Prellberg Thomas , Stark Dudley
Published: January 2020

We define incidence matrices to be zero-one matrices with no zero rows or columns. We are interested in counting incidence matrices with a given number of ones, irrespective of the number of rows or columns. A classification of incidence matrices is considered for which conditions of symmetry by transposition, having no repeated rows/columns, or identification by permutation of rows/columns are imposed. We find asymptotics and relationships for the number of matrices with $n$ ones in some of these classes as $n\to\infty$.
New Regular Partial Difference Sets and Strongly Regular Graphs with Parameters (96,20,4,4) and (96,19,2,4)
Authors: Golemac Anka , Mandić Joško , Vučičić Tanja
Published: January 2020

New (96,20,4,4) and (96,19,2,4) regular partial difference sets are constructed, together with the corresponding strongly regular graphs. Our source are (96,20,4) regular symmetric designs.
On a Balanced Property of Derangements
Authors: Bóna Miklós
Published: January 2020

We prove an interesting fact describing the location of the roots of the generating polynomials of the numbers of derangements of length $n$, counted by their number of cycles. We then use this result to prove that if $k$ is the number of cycles of a randomly selected derangement of length $n$, then the probability that $k$ is congruent to a given $r$ modulo a given $q$ converges to $1/q$. Finally, we generalize our results to $a$-derangements, which are permutations in which each cycle is longer than $a$.
Hayman Admissible Functions in Several Variables
Authors: Gittenberger Bernhard , Mandlburger Johannes
Published: January 2020

An alternative generalisation of Hayman's concept of admissible functions to functions in several variables is developed and a multivariate asymptotic expansion for the coefficients is proved. In contrast to existing generalisations of Hayman admissibility, most of the closure properties which are satisfied by Hayman's admissible functions can be shown to hold for this class of functions as well.
Permutation Reconstruction
Authors: Smith Rebecca
Published: January 2020

In this paper, we consider the problem of permutation reconstruction. This problem is an analogue of graph reconstruction, a famous question in graph theory. In the case of permutations, the problem can be stated as follows: In all possible ways, delete $k$ entries of the permutation $p=p_1p_2p_3...p_n$ and renumber accordingly, creating $n \choose k$ substrings. How large must $n$ be in order for us to be able to reconstruct $p$ from this multiset of substrings? That is, how large must $n$ be to guarantee that this multiset is unique to $p$? Alternatively, one can look at the sets of substrings created this way. We show that in the case when $k=1$, regardless of whether we consider sets or multisets of these substrings, a random permutation needs to be of length at least five to guarantee reconstruction. This in turn yields an interesting result about the symmetries of the poset of permutations. We also give some partial results in the cases when $k=2$ and $k=3$, and finally we give a lower bound on the length of a permutation for general $k$.
Two Extremal Problems in Graph Theory
Authors: Brualdi Richard A. , Mellendorf Stephen
Published: January 2020

We consider the following two problems. (1) Let $t$ and $n$ be positive integers with $n\geq t\geq 2$. Determine the maximum number of edges of a graph of order $n$ that contains neither $K_t$ nor $K_{t,t}$ as a subgraph. (2) Let $r$, $t$ and $n$ be positive integers with $n\geq rt$ and $t\geq 2$. Determine the maximum number of edges of a graph of order $n$ that does not contain $r$ disjoint copies of $K_t$. Problem 1 for $n < 2t$ is solved by Turán's theorem and we solve it for $n=2t$. We also solve Problem 2 for $n=rt$.
On Ramsey Minimal Graphs
Authors: Łuczak Tomasz
Published: January 2020

An elementary probabilistic argument is presented which shows that for every forest $F$ other than a matching, and every graph $G$ containing a cycle, there exists an infinite number of graphs $J$ such that $J\to (F,G)$ but if we delete from $J$ any edge $e$ the graph $J-e$ obtained in this way does not have this property.
The independence number of graphs with large odd girth
Authors: Denley Tristan
Published: January 2020

Let $G$ be an $r$-regular graph of order $n$ and independence number $\alpha(G)$. We show that if $G$ has odd girth $2k+3$ then $\alpha(G)\geq n^{1-1/k}r^{1/k}$. We also prove similar results for graphs which are not regular. Using these results we improve on the lower bound of Monien and Speckenmeyer, for the independence number of a graph of order $n$ and odd girth $2k+3$.
An On-Line Version of the Encyclopedia of Integer Sequences
Authors: Sloane N. J. A.
Published: January 2020

A Handbook of Integer Sequences was published by Academic Press in 1973, and contained an annotated list of 2372 sequences arranged in lexicographic order. Since then a great deal of new material has been added, and many improvements have been made to the original entries. The purpose of this note is to announce that the new version of the collection, The On-Line Encyclopedia of Integer Sequences can now be accessed by electronic mail.
The size of Fulton's essential set
Authors: Eriksson Kimmo , Linusson Svante
Published: January 2020

The essential set of a permutation was defined by Fulton as the set of southeast corners of the diagram of the permutation. In this paper we determine explicit formulas for the average size of the essential set in the two cases of arbitrary permutations in $S_n$ and $321$-avoiding permutations in $S_n$. Vexillary permutations are discussed too. We also prove that the generalized Catalan numbers ${r+k-1\choose n}-{r+k-1\choose n-2}$ count $r\times k$-matrices dotted with $n$ dots that are extendable to $321$-avoiding permutation matrices.
Maximal Sets of Integers with Distinct Divisors
Authors: Balasubramanian R. , Soundararajan K.
Published: January 2020

A set of positive integers is said to have the distinct divisor property if there is an injective map that sends every integer in the set to one of its proper divisors. In 1983, P. Erdős and C. Pomerance showed that for every $c>1$, a largest subset of $[N,cN]$ with the distinct divisor property has cardinality $\sim \delta(c)N$, for some constant $\delta(c)>0$. They conjectured that $\delta(c)\sim c/2$ as $c \to \infty$. We prove their conjecture. In fact we show that there exist positive absolute constants $D_1,D_2$ such that $D_1\le c^{\beta}(c/2-\delta(c))\le D_2$ where $\beta = \log 2/\log (3/2)$.
On a Strange Recursion of Golomb
Authors: Barbeau Ed , Tanny Steve
Published: January 2020

Golomb proposed a family of "strange" recursions of metafibonacci type, parameterized by $k$, and, for each $k$, identified what he speculated was the unique increasing solution. We show that, to the contrary, there are many increasing solutions for each $k$, and we indicate explicitly how to construct them. We also provide some additional general results concerning the nature of the strictly increasing solutions for this unusual family of recursions.
Repeated Patterns of Dense Packings of Equal Disks in a Square
Authors: Graham R. L. , Lubachevsky B. D.
Published: January 2020

We examine sequences of dense packings of $n$ congruent non-overlapping disks inside a square which follow specific patterns as $n$ increases along certain values, $n = n(1), n(2),... n(k),...$. Extending and improving previous work of Nurmela and Östergård where previous patterns for $n = n(k)$ of the form $ k^2$, $ k^2-1$, $k^2-3$, $k(k+1)$, and $4k^2+k$ were observed, we identify new patterns for $n = k^2-2$ and $n = k^2+ \lfloor k/2 \rfloor$. We also find denser packings than those in Nurmela and Östergård for $n =$21, 28, 34, 40, 43, 44, 45, and 47. In addition, we produce what we conjecture to be optimal packings for $n =$51, 52, 54, 55, 56, 60, and 61. Finally, for each identified sequence $n(1), n(2),... n(k),...$ which corresponds to some specific repeated pattern, we identify a threshold index $k_0$, for which the packing appears to be optimal for $k \le k_0$, but for which the packing is not optimal (or does not exist) for $k > k_0$.
A Note on Alternating Sums
Authors: Kirschenhofer Peter
Published: January 2020

We present some results on a certain type of alternating sums which frequently arise in connection with the average-case analysis of algorithms and data. Whereas the so-called Rice's method for treating such sums uses complex contour integration we perform manipulations of generating functions in order to get explicit results from which asymptotic estimates follow immediately.
Two Congruences Involving 4-cores
Authors: Hirschhorn Michael , Sellers James A.
Published: January 2020

The goal of this paper is to prove two new congruences involving 4–cores using elementary techniques; namely, if $a_4(n)$ denotes the number of 4–cores of $n$, then $a_4(9n+2)\equiv 0$ (mod 2) and $a_4(9n+8)\equiv 0$ (mod 4).
Pfaff's Method (III): Comparison With the WZ Method
Authors: Andrews George E.
Published: January 2020

In the 1990's, the WZ method has been the method of choice in resolving new conjectures for hypergeometric identities. The object here is to compare the WZ method with Pfaff's method. Such a comparison should (it is hoped) provide some suggestions for the further development of each method.
Fruit Salad
Authors: Gyárfás András
Published: January 2020

Paul Erdős liked fruit salad. I mixed this one for him from ingredients obtained while working on some of his problems. He was pleased by it and carried it to several places to offer to others as well. It is very sad that I have to add to the manuscript: dedicated to his memory.
An Exact Performance Bound for an ${O (m+n)}$ Time Greedy Matching Procedure
Authors: Shapira Andrew
Published: January 2020

We prove an exact lower bound on $\gamma(G)$, the size of the smallest matching that a certain $O(m+n)$ time greedy matching procedure may find for a given graph $G$ with $n$ vertices and $m$ edges. The bound is precisely Erdős and Gallai's extremal function that gives the size of the smallest maximum matching, over all graphs with $n$ vertices and $m$ edges. Thus the greedy procedure is optimal in the sense that when only $n$ and $m$ are specified, no algorithm can be guaranteed to find a larger matching than the greedy procedure. The greedy procedure and augmenting path algorithms are seen to be complementary: the greedy procedure finds a large matching for dense graphs, while augmenting path algorithms are fast for sparse graphs. Well known hybrid algorithms consisting of the greedy procedure followed by an augmenting path algorithm are shown to be faster than the augmenting path algorithm alone. The lower bound on $\gamma(G)$ is a stronger version of Erdős and Gallai's result, and so the proof of the lower bound is a new way of proving of Erdős and Gallai's result.
Hypergeometric Series Acceleration Via the WZ method
Authors: Amdeberhan Tewodros , Zeilberger Doron
Published: January 2020

Based on the WZ method, some series acceleration formulas are given. These formulas allow us to write down an infinite family of parameterized identities from any given identity of WZ type. Further, this family, in the case of the Zeta function, gives rise to many accelerated expressions for $\zeta(3)$.
On the Number of Descendants and Ascendants in Random Search Trees
Authors: Martínez Conrado , Panholzer Alois , Prodinger Helmut
Published: January 2020

The number of descendants of a node in a binary search tree (BST) is the size of the subtree having this node as a root; the number of ascendants is the number of nodes on the path connecting this node with the root. Using a purely combinatorial approach (generating functions and differential equations) we are able to extend previous results. For the number of descendants we get explicit formulæ for all moments; for the number of ascendants, which is harder, we get the variance. A natural extension of binary search trees occurs when performing local reorganisations. Poblete and Munro have already analyzed some aspects of these locally balanced binary search trees (LBSTs). Here, we relate these structures with the performance of median–of–three Quicksort. We get as new results the variances for ascendants and descendants in this setting. If the rank of the node itself is picked at random ("grand averages"), the corresponding parameters only depend on the size $n$. In this instance, we get all the moments for the descendants (BST and LBST), as well as the probabilities. For ascendants (LBST), we get the variance and (in principle) the higher moments, as well as the (normal) limiting distribution. The emphasis is on explicit formulæ, and these are sometimes quite involved. Thus, in some instances, we have decided to state abridged versions in the paper and collect the long forms into an appendix that can be downloaded from the URLs http://info.tuwien.ac.at/theoinf/abstract/abs_120.htm and http://www.lsi.upc.es/~conrado/research/.
Lattice Paths Between Diagonal Boundaries
Authors: Niederhausen Heinrich
Published: January 2020

A bivariate symmetric backwards recursion is of the form $d[m,n]=w_{0}(d[m-1,n]+d[m,n-1])+\omega_{1}(d[m-r_{1},n-s_{1}]+d[m-s_{1},n-r_{1}])+\dots+\omega_{k}(d[m-r_{k},n-s_{k}]+d[m-s_{k},n-r_{k}])$ where $\omega_{0},\dots\omega_{k}$ are weights, $r_{1},\dots r_{k}$ and $s_{1},\dots s_{k}$ are positive integers. We prove three theorems about solving symmetric backwards recursions restricted to the diagonal band $x+u < y < x-l$. With a solution we mean a formula that expresses $d[m,n]$ as a sum of differences of recursions without the band restriction. Depending on the application, the boundary conditions can take different forms. The three theorems solve the following cases: $d[x+u,x]=0$ for all $x\geq0$, and $d[x-l,x]=0$ for all $x\geq l$ (applies to the exact distribution of the Kolmogorov-Smirnov two-sample statistic), $d[x+u,x]=0$ for all $x\geq0$, and $d[x-l+1,x]=d[x-l+1,x-1]$ for $x\geq l$ (ordinary lattice paths with weighted left turns), and $d[y,y-u+1]=d[y-1,y-u+1]$ for all $y\geq u$ and $d[x-l+1,x]=d[x-l+1,x-1]$ for $x\geq l$. The first theorem is a general form of what is commonly known as repeated application of the Reflection Principle. The second and third theorem are new; we apply them to lattice paths which in addition to the usual North and East steps also make two hook moves, East-North-North and North-East-East. Hook moves differ from knight moves (covered by the first theorem) by being blocked by any piece of the barrier they encounter along their three part move.
A Macdonald Vertex Operator and Standard Tableaux Statistics
Authors: Zabrocki Mike
Published: January 2020

The two parameter family of coefficients $K_{\lambda \mu}(q,t)$ introduced by Macdonald are conjectured to $(q,t)$ count the standard tableaux of shape $\lambda $. If this conjecture is correct, then there exist statistics $a_\mu(T)$ and $b_\mu(T)$ such that the family of symmetric functions $H_\mu[X;q,t] = \sum_\lambda K_{\lambda \mu}(q,t) s_\lambda [X]$ are generating functions for the standard tableaux of size $|\mu|$ in the sense that $H_\mu[X;q,t] = \sum_{T} q^{a_\mu(T)} t^{b_\mu(T)} s_{\lambda (T)}[X]$ where the sum is over standard tableau of of size $|\mu|$. We give a formula for a symmetric function operator $H_2^{qt}$ with the property that $H_2^{qt} H_{(2^a1^b)}[X;q,t]= H_{(2^{a+1}1^b)}[X;q,t]$. This operator has a combinatorial action on the Schur function basis. We use this Schur function action to show by induction that $H_{(2^a1^b)}[X;q,t]$ is the generating function for standard tableaux of size $2a+b$ (and hence that $K_{\lambda (2^a1^b)}(q,t)$ is a polynomial with non-negative integer coefficients). The inductive proof gives an algorithm for 'building' the standard tableaux of size $n+2$ from the standard tableaux of size $n$ and divides the standard tableaux into classes that are generalizations of the catabolism type. We show that reversing this construction gives the statistics $a_\mu(T)$ and $b_\mu(T)$ when $\mu$ is of the form $(2^a1^b)$ and that these statistics prove conjectures about the relationship between adjacent rows of the $(q,t)$-Kostka matrix that were suggested by Lynne Butler.
Labeled Factorization of Integers
Authors: Munagi Augustine O.
Published: January 2020

The labeled factorizations of a positive integer $n$ are obtained as a completion of the set of ordered factorizations of $n$. This follows a new technique for generating ordered factorizations found by extending a method for unordered factorizations that relies on partitioning the multiset of prime factors of $n$. Our results include explicit enumeration formulas and some combinatorial identities. It is proved that labeled factorizations of $n$ are equinumerous with the systems of complementing subsets of $\{0,1,\dots,n-1\}$. We also give a new combinatorial interpretation of a class of generalized Stirling numbers.
Descents of Permutations in a Ferrers Board
Authors: Song Chunwei , Yan Catherine
Published: January 2020

The classical Eulerian polynomials are defined by setting $$A_n(t)= \sum_{\sigma \in \mathfrak{S}_n} t^{1+\mathrm{des}(\sigma)}= \sum_{k=1}^n A_{n,k} t^k$$where  $A_{n,k}$ is the number of permutations of length $n$ with $k-1$ descents. Let $A_n(t, q) = \sum_{\pi \in \mathfrak{S}_n} t^{1+{\rm des}(\pi)}q^{{\rm inv}(\pi)} $ be the $\mathrm{inv}$ $q$-analogue of the classical Eulerian polynomials whose generating function is well known: \begin{eqnarray}\sum_{n \geq 0} \frac{u^n A_n(t, q)}{[n]_q!} = \frac{1}{\displaystyle 1-t\sum_{k \geq 1} \frac{(1-t)^ku^k}{[k]_q!}}.\qquad\qquad(*)\label{perm_gf abs}\end{eqnarray}In this paper we consider permutations  restricted in a Ferrers board and study their descent polynomials. For a general Ferrers board $F$, we derive a formula in the form of permanent for the restricted $q$-Eulerian polynomial $$A_F(t,q) := \sum_{\sigma \in F} t^{1+{\rm des}(\sigma)} q^{{\rm inv}(\sigma)}.$$ If the Ferrers board has the special shape of an $n\times n$ square  with a triangular board of size $s$ removed, we prove that $A_F(t,q)$ is  a sum of $s+1$ terms, each satisfying an equation that is similar to (*).   Then we apply our results to permutations with bounded drop (or excedance) size, for which the descent polynomial was first studied by Chung et al. (European J. Combin., 31(7) (2010):1853-1867). Our method presents an alternative approach.
A Rainbow $k$-Matching in the Complete Graph with $r$ Colors
Authors: Fujita Shinya , Kaneko Atsushi , Schiermeyer Ingo , Suzuki Kazuhiro
Published: January 2020

An $r$-edge-coloring of a graph is an assignment of $r$ colors to the edges of the graph. An exactly $r$-edge-coloring of a graph is an $r$-edge-coloring of the graph that uses all $r$ colors. A matching of an edge-colored graph is called rainbow matching, if no two edges have the same color in the matching. In this paper, we prove that an exactly $r$-edge-colored complete graph of order $n$ has a rainbow matching of size $k(\ge 2)$ if $r \ge max\{{2k-3\choose 2}+2, {k-2\choose 2}+(k-2)(n-k+2)+2 \}$, $k \ge 2$, and $n \ge 2k+1$. The bound on $r$ is best possible.
A van der Waerden Variant
Authors: Compton Kevin J.
Published: January 2020

The classical van der Waerden Theorem says that for every every finite set $S$ of natural numbers and every $k$-coloring of the natural numbers, there is a monochromatic set of the form $aS+b$ for some $a>0$ and $b\geq 0$. I.e., monochromatism is obtained by a dilation followed by a translation. We investigate the effect of reversing the order of dilation and translation. $S$ has the variant van der Waerden property for $k$ colors if for every $k$-coloring there is a monochromatic set of the form $a(S+b)$ for some $a>0$ and $b\geq 0$. On the positive side it is shown that every two-element set has the variant van der Waerden property for every $k$. Also, for every finite $S$ and $k$ there is an $n$ such that $nS$ has the variant van der Waerden property for $k$ colors. This extends the classical van der Waerden Theorem. On the negative side it is shown that if $S$ has at least three elements, the variant van der Waerden property fails for a sufficiently large $k$. The counterexamples to the variant van der Waerden property are constructed by specifying colorings as Thue-Morse sequences.
On Sums Over Partially Ordered Sets
Authors: Dohmen Klaus
Published: January 2020

We establish a general theorem for reducing sums of type $\sum_{y\ge x} g(y)$ where $g$ is a mapping from a partially ordered set into an abelian group. Conclusions concern the Möbius function, the principle of inclusion-exclusion, the Tutte polynomial and Crapo's beta invariant.
Induced Complete $h$-partite Graphs in Dense Clique-less Graphs
Authors: Fischer Eldar
Published: January 2020

It is proven that for every fixed $h$, $a$ and $b$, a graph with $n$ vertices and minimum degree at least ${h-1 \over h}n$, which contains no copy of $K_b$ (the complete graph with $b$ vertices), contains at least $(1-o(1)){n \over ha}$ vertex disjoint induced copies of the complete $h$-partite graph with $a$ vertices in each color class.
Some Pairwise Balanced Designs
Authors: Greig Malcolm
Published: January 2020

A pairwise balanced design, $B(K;v)$, is a block design on $v$ points, with block sizes taken from $K$, and with every pair of points occurring in a unique block; for a fixed $K$, $B(K)$ is the set of all $v$ for which a $B(K;v)$ exists. A set, $S$, is a PBD-basis for the set, $T$, if $T=B(S)$. Let $N_{a(m)}=\{n:n\equiv a\bmod m\}$, and $N_{\geq m}=\{n:n\geq m\}$; with $Q$ the corresponding restriction of $N$ to prime powers. This paper addresses the existence of three PBD-basis sets. 1. It is shown that $Q_{1(8)}$ is a basis for $N_{1(8)}\setminus E$, where $E$ is a set of 5 definite and 117 possible exceptions. 2. We construct a 78 element basis for $N_{1(8)}$ with, at most, 64 inessential elements. 3. Bennett and Zhu have shown that $Q_{\geq8}$ is a basis for $N_{\geq8}\setminus E'$, where $E'$ is a set of 43 definite and 606 possible exceptions. Their result is improved to 48 definite and 470 possible exceptions. (Constructions for 35 of these possible exceptions are known.) Finally, we provide brief details of some improvements and corrections to the generating/exception sets published in The CRC Handbook of Combinatorial Designs.
A Note on the Non-Colorability Threshold of a Random Graph
Authors: Kaporis Alexis C. , Kirousis Lefteris M. , Stamatiou Yannis C.
Published: January 2020

In this paper we consider the problem of establishing a value $r_0$ such that almost all random graphs with $n$ vertices and $rn$ edges, $r > r_0$, are asymptotically not 3-colorable. In our approach we combine the concept of rigid legal colorings introduced by Achlioptas and Molloy with the occupancy problem for random allocations of balls into bins. Using the sharp estimates obtained by Kamath et al. of the probability that no bin is empty after the random placement of the balls and exploiting the relationship between the placement of balls and the rigid legal colorings, we improve the value $r_0 = 2.522$ previously obtained by Achlioptas and Molloy to $r_0 = 2.495$.
Bound Graph Polysemy
Authors: Tanenbaum Paul J.
Published: January 2020

Bound polysemy is the property of any pair $(G_1, G_2)$ of graphs on a shared vertex set $V$ for which there exists a partial order on $V$ such that any pair of vertices has an upper bound precisely when the pair is an edge in $G_1$ and a lower bound precisely when it is an edge in $G_2$. We examine several special cases and prove a characterization of the bound polysemic pairs that illuminates a connection with the squared graphs.
Two New Extensions of the Hales-Jewett Theorem
Authors: McCutcheon Randall
Published: January 2020

We prove two extensions of the Hales-Jewett coloring theorem. The first is a polynomial version of a finitary case of Furstenberg and Katznelson's multiparameter elaboration of a theorem, due to Carlson, about variable words. The second is an "idempotent" version of a result of Carlson and Simpson.
On Descents in Standard Young Tableaux
Authors: Hästö Peter A.
Published: January 2020

In this paper, explicit formulae for the expectation and the variance of descent functions on random standard Young tableaux are presented. Using these, it is shown that the normalized variance, $V/E^2$, is bounded if and only if a certain inequality relating the tableau shape to the descent function holds.
Colouring Planar Mixed Hypergraphs
Authors: Kündgen André , Mendelsohn Eric , Voloshin Vitaly
Published: January 2020

A mixed hypergraph is a triple ${\cal H} = (V,{\cal C}, {\cal D})\;$ where $V$ is the vertex set and ${\cal C}$ and ${\cal D}$ are families of subsets of $V$, the ${\cal C}$-edges and ${\cal D}$-edges, respectively. A $k$-colouring of ${\cal H}$ is a mapping $c: V\rightarrow [k]$ such that each ${\cal C}$-edge has at least two vertices with a ${\cal C}$ommon colour and each ${\cal D}$-edge has at least two vertices of ${\cal D}$ifferent colours. ${\cal H}$ is called a planar mixed hypergraph if its bipartite representation is a planar graph. Classic graphs are the special case of mixed hypergraphs when ${\cal C}=\emptyset$ and all the ${\cal D}$-edges have size 2, whereas in a bi-hypergraph ${\cal C} = {\cal D}$. We investigate the colouring properties of planar mixed hypergraphs. Specifically, we show that maximal planar bi-hypergraphs are 2-colourable, find formulas for their chromatic polynomial and chromatic spectrum in terms of 2-factors in the dual, prove that their chromatic spectrum is gap-free and provide a sharp estimate on the maximum number of colours in a colouring.
Determinantal Expression and Recursion for Jack Polynomials
Authors: Lapointe Luc , Lascoux A. , Morse J.
Published: January 2020

We describe matrices whose determinants are the Jack polynomials expanded in terms of the monomial basis. The top row of such a matrix is a list of monomial functions, the entries of the sub-diagonal are of the form $-(r\alpha+s)$, with $r$ and $s \in {\bf N^+}$, the entries above the sub-diagonal are non-negative integers, and below all entries are 0. The quasi-triangular nature of these matrices gives a recursion for the Jack polynomials allowing for efficient computation. A specialization of these results yields a determinantal formula for the Schur functions and a recursion for the Kostka numbers.
Parking Functions, Empirical Processes, and the Width of Rooted Labeled Trees
Authors: Chassaing Philippe , Marckert Jean-François
Published: January 2020

This paper provides tight bounds for the moments of the width of rooted labeled trees with $n$ nodes, answering an open question of Odlyzko and Wilf (1987). To this aim, we use one of the many one-to-one correspondences between trees and parking functions, and also a precise coupling between parking functions and the empirical processes of mathematical statistics. Our result turns out to be a consequence of the strong convergence of empirical processes to the Brownian bridge (Komlós, Major and Tusnády, 1975).
A Reciprocity Theorem for Domino Tilings
Authors: Propp James
Published: January 2020

Let $T(m,n)$ denote the number of ways to tile an $m$-by-$n$ rectangle with dominos. For any fixed $m$, the numbers $T(m,n)$ satisfy a linear recurrence relation, and so may be extrapolated to negative values of $n$; these extrapolated values satisfy the relation $$T(m,-2-n)=\epsilon_{m,n}T(m,n),$$ where $\epsilon_{m,n}=-1$ if $m \equiv 2$ (mod 4) and $n$ is odd and where $\epsilon_{m,n}=+1$ otherwise. This is equivalent to a fact demonstrated by Stanley using algebraic methods. Here I give a proof that provides, among other things, a uniform combinatorial interpretation of $T(m,n)$ that applies regardless of the sign of $n$.
The Umbral Transfer-Matrix Method. IV. Counting Self-Avoiding Polygons and Walks
Authors: Zeilberger Doron
Published: January 2020

This is the fourth installment of the five-part saga on the Umbral Transfer-Matrix method, based on Gian-Carlo Rota's seminal notion of the umbra. In this article we describe the Maple packages USAP, USAW, and MAYLIS. USAP automatically constructs, for any specific $r$, an Umbral Scheme for enumerating, according to perimeter, the number of self-avoiding polygons with $\leq 2r$ horizontal edges per vertical cross-section. The much more complicated USAW does the analogous thing for self-avoiding walks. Such Umbral Schemes enable counting these classes of self-avoiding polygons and walks in polynomial time as opposed to the exponential time that is required by naive counting. Finally MAYLIS is targeted to the special case of enumerating classes of saps with at most two horizontal edges per vertical cross-section (equivalently column-convex polyominoes by perimeter), and related classes. In this computationally trivial case we can actually automatically solve the equations that were automatically generated by USAP. As an example, we give the first fully computer-generated proof of the celebrated Delest-Viennot result that the number of convex polyominoes with perimeter $2n+8$ equals $(2n+11)4^n-4(2n+1)!/n!^2$.
An Extension of a Criterion for Unimodality
Authors: Alvarez Jenny , Amadis Miguel , Boros George , Karp Dagan , Moll Victor H. , Rosales Leobardo
Published: January 2020

We prove that if $P(x)$ is a polynomial with nonnegative nondecreasing coefficients and $n$ is a positive integer, then $P(x+n)$ is unimodal. Applications and open problems are presented.
Maximal Flat Antichains of Minimum Weight
Authors: Grüttmüller Martin , Hartmann Sven , Kalinowski Thomas , Leck Uwe , Roberts Ian T.
Published: January 2020

We study maximal families ${\cal A}$ of subsets of $[n]=\{1,2,\dots,n\}$ such that ${\cal A}$ contains only pairs and triples and $A\not\subseteq B$ for all $\{A,B\}\subseteq{\cal A}$, i.e. ${\cal A}$ is an antichain. For any $n$, all such families ${\cal A}$ of minimum size are determined. This is equivalent to finding all graphs $G=(V,E)$ with $|V|=n$ and with the property that every edge is contained in some triangle and such that $|E|-|T|$ is maximum, where $T$ denotes the set of triangles in $G$. The largest possible value of $|E|-|T|$ turns out to be equal to $\lfloor(n+1)^2/8\rfloor$. Furthermore, if all pairs and triples have weights $w_2$ and $w_3$, respectively, the problem of minimizing the total weight $w({\cal A})$ of ${\cal A}$ is considered. We show that $\min w({\cal A})=(2w_2+w_3)n^2/8+o(n^2)$ for $3/n\leq w_3/w_2=:\lambda=\lambda(n) < 2$. For $\lambda\ge 2$ our problem is equivalent to the (6,3)-problem of Ruzsa and Szemerédi, and by a result of theirs it follows that $\min w({\cal A})=w_2n^2/2+o(n^2)$.
The Multiplicities of a Dual-thin $Q$-polynomial Association Scheme
Authors: Sagan Bruce E. , Caughman, IV John S.
Published: January 2020

Let $Y=(X, \{ R_i \}_{1\le i\le D})$ denote a symmetric association scheme, and assume that $Y$ is $Q$-polynomial with respect to an ordering $E_0,...,E_D$ of the primitive idempotents. Bannai and Ito conjectured that the associated sequence of multiplicities $m_i$ $(0 \leq i \leq D)$ of $Y$ is unimodal. Talking to Terwilliger, Stanton made the related conjecture that $m_i \leq m_{i+1}$ and $m_i \leq m_{D-i}$ for $i < D/2$. We prove that if $Y$ is dual-thin in the sense of Terwilliger, then the Stanton conjecture is true.
Minimum Connected Dominating Sets of Random Cubic Graphs
Authors: Duckworth W.
Published: January 2020

We present a simple heuristic for finding a small connected dominating set of cubic graphs. The average-case performance of this heuristic, which is a randomised greedy algorithm, is analysed on random $n$-vertex cubic graphs using differential equations. In this way, we prove that the expected size of the connected dominating set returned by the algorithm is asymptotically almost surely less than $0.5854n$.
A Note on Odd Cycle-Complete Graph Ramsey Numbers
Authors: Sudakov Benny
Published: January 2020

The Ramsey number $r(C_l, K_n)$ is the smallest positive integer $m$ such that every graph of order $m$ contains either cycle of length $l$ or a set of $n$ independent vertices. In this short note we slightly improve the best known upper bound on $r(C_l, K_n)$ for odd $l$.
On a Theorem of Erdős, Rubin, and Taylor on Choosability of Complete Bipartite Graphs
Authors: Kostochka Alexandr
Published: January 2020

Erdős, Rubin, and Taylor found a nice correspondence between the minimum order of a complete bipartite graph that is not $r$-choosable and the minimum number of edges in an $r$-uniform hypergraph that is not $2$-colorable (in the ordinary sense). In this note we use their ideas to derive similar correspondences for complete $k$-partite graphs and complete $k$-uniform $k$-partite hypergraphs.
$321$-Polygon-Avoiding Permutations and Chebyshev Polynomials
Authors: Mansour Toufik , Stankova Zvezdelina
Published: January 2020

A $321$-$k$-gon-avoiding permutation $\pi$ avoids $321$ and the following four patterns: $$k(k+2)(k+3)\cdots(2k-1)1(2k)23\cdots(k-1)(k+1),$$ $$k(k+2)(k+3)\cdots(2k-1)(2k)12\cdots(k-1)(k+1),$$ $$(k+1)(k+2)(k+3)\cdots(2k-1)1(2k)23\cdots k,$$ $$(k+1)(k+2)(k+3)\cdots(2k-1)(2k)123\cdots k.$$ The $321$-$4$-gon-avoiding permutations were introduced and studied by Billey and Warrington [BW] as a class of elements of the symmetric group whose Kazhdan-Lusztig, Poincaré polynomials, and the singular loci of whose Schubert varieties have fairly simple formulas and descriptions. Stankova and West [SW] gave an exact enumeration in terms of linear recurrences with constant coefficients for the cases $k=2,3,4$. In this paper, we extend these results by finding an explicit expression for the generating function for the number of $321$-$k$-gon-avoiding permutations on $n$ letters. The generating function is expressed via Chebyshev polynomials of the second kind.
A Generalization of Simion-Schmidt's Bijection for Restricted Permutations
Authors: Reifegerste Astrid
Published: January 2020

We consider the two permutation statistics which count the distinct pairs obtained from the final two terms of occurrences of patterns $\tau_1\cdots\tau_{m-2}m(m-1)$ and $\tau_1\cdots\tau_{m-2}(m-1)m$ in a permutation, respectively. By a simple involution in terms of permutation diagrams we will prove their equidistribution over the symmetric group. As a special case we derive a one-to-one correspondence between permutations which avoid each of the patterns $\tau_1\cdots\tau_{m-2}m(m-1)\in{\cal S}_m$ and those which avoid each of the patterns $\tau_1\cdots\tau_{m-2}(m-1)m\in{\cal S}_m$. For $m=3$ this correspondence coincides with the bijection given by Simion and Schmidt in [Europ. J. Combin. 6 (1985), 383-406].
Improved Bounds for the Number of Forests and Acyclic Orientations in the Square Lattice
Authors: Calkin N. , Merino C. , Noble S. , Noy M.
Published: January 2020

In a recent paper Merino and Welsh (1999) studied several counting problems on the square lattice $L_n$. There the authors gave the following bounds for the asymptotics of $f(n)$, the number of forests of $L_n$, and $\alpha(n)$, the number of acyclic orientations of $L_n$: $$3.209912 \le \lim_{n\to\infty} f(n)^{1/n^2} \le 3.84161$$ and $$22/7 \le \lim_{n\to\infty} \alpha(n)^{1/n^2} \le 3.70925.$$ In this paper we improve these bounds as follows: $$3.64497 \le \lim_{n\to\infty} f(n)^{1/n^2} \le 3.74101$$ and $$3.41358 \le \lim_{n\to\infty} \alpha(n)^{1/n^2} \le 3.55449.$$ We obtain this by developing a method for computing the Tutte polynomial of the square lattice and other related graphs based on transfer matrices.
Nowhere-Zero 3-Flows in Squares of Graphs
Authors: Xu Rui , Zhang Cun-Quan
Published: January 2020

It was conjectured by Tutte that every 4-edge-connected graph admits a nowhere-zero $3$-flow. In this paper, we give a complete characterization of graphs whose squares admit nowhere-zero $3$-flows and thus confirm Tutte's $3$-flow conjecture for the family of squares of graphs.
The $q$-Binomial Theorem and two Symmetric $q$-Identities
Authors: Guo Victor J. W.
Published: January 2020

We notice two symmetric $q$-identities, which are special cases of the transformations of $_2\phi_1$ series in Gasper and Rahman's book (Basic Hypergeometric Series, Cambridge University Press, 1990, p. 241). In this paper, we give combinatorial proofs of these two identities and the $q$-binomial theorem by using conjugation of $2$-modular diagrams.
Skolem-type Difference Sets for Cycle Systems
Authors: Bryant Darryn , Gavlas Heather , Ling Alan C. H.
Published: January 2020

Cyclic $m$-cycle systems of order $v$ are constructed for all $m\geq 3$, and all $v\equiv 1(\hbox{mod }2m)$. This result has been settled previously by several authors. In this paper, we provide a different solution, as a consequence of a more general result, which handles all cases using similar methods and which also allows us to prove necessary and sufficient conditions for the existence of a cyclic $m$-cycle system of $K_v-F$ for all $m\geq 3$, and all $v\equiv 2(\hbox{mod }2m)$.
On a Two-Sided Turán Problem
Authors: Mubayi Dhruv , Zhao Yi
Published: January 2020

Given positive integers $n,k,t$, with $2 \le k\le n$, and $t < 2^k$, let $m(n,k,t)$ be the minimum size of a family ${\cal F}$ of nonempty subsets of $[n]$ such that every $k$-set in $[n]$ contains at least $t$ sets from ${\cal F}$, and every $(k-1)$-set in $[n]$ contains at most $t-1$ sets from ${\cal F}$. Sloan et al. determined $m(n, 3, 2)$ and Füredi et al. studied $m(n, 4, t)$ for $t=2, 3$. We consider $m(n, 3, t)$ and $m(n, 4, t)$ for all the remaining values of $t$ and obtain their exact values except for $k=4$ and $t= 6, 7, 11, 12$. For example, we prove that $ m(n, 4, 5) = {n \choose 2}-17$ for $n\ge 160$. The values of $m(n, 4, t)$ for $t=7,11,12$ are determined in terms of well-known (and open) Turán problems for graphs and hypergraphs. We also obtain bounds of $m(n, 4, 6)$ that differ by absolute constants.
Finding Induced Acyclic Subgraphs in Random Digraphs
Authors: Subramanian C. R.
Published: January 2020

Consider the problem of finding a large induced acyclic subgraph of a given simple digraph $D=(V,E)$. The decision version of this problem is $NP$-complete and its optimization is not likely to be approximable within a ratio of $O(n^{\epsilon})$ for some $\epsilon>0$. We study this problem when $D$ is a random instance. We show that, almost surely, any maximal solution is within an $o(\ln n)$ factor from the optimal one. In addition, except when $D$ is very sparse (having $n^{1+o(1)}$ edges), this ratio is in fact $O(1)$. Thus, the optimal solution can be approximated in a much better way over random instances.
Some Remarks on the Plotkin Bound
Authors: Quistorff Jörn
Published: January 2020

In coding theory, Plotkin's upper bound on the maximal cadinality of a code with minimum distance at least $d$ is well known. He presented it for binary codes where Hamming and Lee metric coincide. After a brief discussion of the generalization to $q$-ary codes preserved with the Hamming metric, the application of the Plotkin bound to $q$-ary codes preserved with the Lee metric due to Wyner and Graham is improved.
Forestation in Hypergraphs: Linear $k$-Trees
Authors: Parekh Ojas
Published: January 2020

We present a new proof of a result of Lovász on the maximum number of edges in a $k$-forest. We also apply a construction used in our proof to generalize the notions of a $k$-hypertree and $k$-forest to a class which extends some properties of trees, to which both specialize when $k=2$.
Distinguishing Numbers for Graphs and Groups
Authors: Tymoczko Julianna
Published: January 2020

A graph $G$ is distinguished if its vertices are labelled by a map $\phi: V(G) \longrightarrow \{1,2,\ldots, k\}$ so that no non-trivial graph automorphism preserves $\phi$. The distinguishing number of $G$ is the minimum number $k$ necessary for $\phi$ to distinguish the graph. It measures the symmetry of the graph.

We extend these definitions to an arbitrary group action of $\Gamma$ on a set $X$. A labelling $\phi: X \longrightarrow \{1,2,\ldots,k\}$ is distinguishing if no element of $\Gamma$ preserves $\phi$ except those which fix each element of $X$. The distinguishing number of the group action on $X$ is the minimum $k$ needed for $\phi$ to distinguish the group action. We show that distinguishing group actions is a more general problem than distinguishing graphs.

We completely characterize actions of $S_n$ on a set with distinguishing number $n$, answering an open question of Albertson and Collins.
Almost All Trees have an Even Number of Independent Sets
Authors: Wagner Stephan G.
Published: January 2020

This paper is devoted to the proof of the surprising fact that almost all trees have an even number of independent vertex subsets (in the sense that the proportion of those trees with an odd number of independent sets tends to $0$ as the number of vertices approaches $\infty$) and to its generalisation to other moduli: for fixed $m$, the probability that a randomly chosen tree on $n$ vertices has a number of independent subsets that is divisible by $m$ tends to $1$ as $n \to \infty$.
Some Results on Chromatic Polynomials of Hypergraphs
Authors: Walter Manfred
Published: January 2020

In this paper, chromatic polynomials of (non-uniform) hypercycles, unicyclic hypergraphs, hypercacti and sunflower hypergraphs are presented. The formulae generalize known results for $r$-uniform hypergraphs due to Allagan, Borowiecki/Łazuka, Dohmen and Tomescu. Furthermore, it is shown that the class of (non-uniform) hypertrees with $m$ edges, where $m_r$ edges have size $r$, $r\geq 2$, is chromatically closed if and only if $m\leq4$, $m_2\geq m-1$.
Half-Simple Symmetric Venn Diagrams
Authors: Killian Charles E. , Ruskey Frank , Savage Carla D. , Weston Mark
Published: January 2020

A Venn diagram is simple if at most two curves intersect at any given point. A recent paper of Griggs, Killian, and Savage [Elec. J. Combinatorics, Research Paper 2, 2004] shows how to construct rotationally symmetric Venn diagrams for any prime number of curves. However, the resulting diagrams contain only ${n \choose {\lfloor n/2 \rfloor}}$ intersection points, whereas a simple Venn diagram contains $2^n-2$ intersection points. We show how to modify their construction to give symmetric Venn diagrams with asymptotically at least $2^{n-1}$ intersection points, whence the name "half-simple."