bluuebunny/crossref_metadata_2025 huggingface dataset:
Partitions, Kostka Polynomials and Pairs of Trees
Authors: Zoque Eliana
Published: January 2020

Bennett et al. presented a recursive algorithm to create a family of partitions from one or several partitions. They were mainly interested in the cases when we begin with a single square partition or with several partitions with only one part. The cardinalities of those families of partitions are the Catalan and ballot numbers, respectively. In this paper we present a non-recursive description for those families and prove that the generating function of the size of those partitions is a Kostka number. We also present bijections between those sets of partitions and sets of trees and forests enumerated by the Catalan an ballot numbers, respectively.
A Bijective Proof of Borchardt's Identity
Authors: Singer Dan
Published: January 2020

We prove Borchardt's identity $$\hbox{det}\left({1\over x_i-y_j}\right) \hbox{per}\left({1\over x_i-y_j}\right)= \hbox{det}\left({1\over(x_i-y_j)^2}\right)$$ by means of sign-reversing involutions.
Partition Identities I: Sandwich Theorems and Logical 0–1 Laws
Authors: Bell Jason P. , Burris Stanley N.
Published: January 2020

The Sandwich Theorems proved in this paper give a new method to show that the partition function $a(n)$ of a partition identity $$ {\bf A}(x) \ :=\ \sum_{n=0}^\infty a(n)x^n\ =\ \prod_{n=1}^\infty (1-x^n)^{-p(n)} $$ satisfies the condition RT$_1$ $$ \lim_{n\rightarrow \infty}{a(n-1)\over a(n)} \ =\ 1\,. $$ This leads to numerous examples of naturally occuring classes of relational structures whose finite members enjoy a logical 0–1 law.
On the Chromatic Number of Intersection Graphs of Convex Sets in the Plane
Authors: Kim Seog-Jin , Kostochka Alexandr , Nakprasit Kittikorn
Published: January 2020

Let $G$ be the intersection graph of a finite family of convex sets obtained by translations of a fixed convex set in the plane. We show that every such graph with clique number $k$ is $(3k-3)$-degenerate. This bound is sharp. As a consequence, we derive that $G$ is $(3k-2)$-colorable. We show also that the chromatic number of every intersection graph $H$ of a family of homothetic copies of a fixed convex set in the plane with clique number $k$ is at most $6k-6$.
Flag Vectors of Multiplicial Polytopes
Authors: Bayer Margaret M.
Published: January 2020

Bisztriczky introduced the multiplex as a generalization of the simplex. A polytope is multiplicial if all its faces are multiplexes. In this paper it is proved that the flag vectors of multiplicial polytopes depend only on their face vectors. A special class of multiplicial polytopes, also discovered by Bisztriczky, is comprised of the ordinary polytopes. These are a natural generalization of the cyclic polytopes. The flag vectors of ordinary polytopes are determined. This is used to give a surprisingly simple formula for the $h$-vector of the ordinary $d$-polytope with $n+1$ vertices and characteristic $k$: $h_i={k-d+i\choose i}+(n-k){k-d+i-1\choose i-1}$, for $i\le d/2$. In addition, a construction is given for 4-dimensional multiplicial polytopes having two-thirds of their vertices on a single facet, answering a question of Bisztriczky.
$q$-Analogues of the Sums of Consecutive Integers, Squares, Cubes, Quarts and Quints
Authors: Schlosser Michael
Published: January 2020

We first show how a special case of Jackson's ${}_8\phi_7$ summation immediately gives Warnaar's $q$-analogue of the sum of the first $n$ cubes, as well as $q$-analogues of the sums of the first $n$ integers and first $n$ squares. Similarly, by appropriately specializing Bailey's terminating very-well-poised balanced ${}_{10}\phi_9$ transformation and applying the terminating very-well-poised ${}_6\phi_5$ summation, we find $q$-analogues for the respective sums of the first $n$ quarts and first $n$ quints. We also derive $q$-analogues of the alternating sums of squares, cubes and quarts, respectively.
On the Graphs of Hoffman-Singleton and Higman-Sims
Authors: Hafner Paul R.
Published: January 2020

We propose a new elementary definition of the Higman-Sims graph in which the 100 vertices are parametrised with ${\Bbb Z}_4\times{\Bbb Z}_5\times{\Bbb Z}_5$ and adjacencies are described by linear and quadratic equations. This definition extends Robertson's pentagon-pentagram definition of the Hoffman-Singleton graph and is obtained by studying maximum cocliques of the Hoffman-Singleton graph in Robertson's parametrisation. The new description is used to count the 704 Hoffman-Singleton subgraphs in the Higman-Sims graph, and to describe the two orbits of the simple group HS on them, including a description of the doubly transitive action of HS within the Higman-Sims graph. Numerous geometric connections are pointed out. As a by-product we also have a new construction of the Steiner system $S(3,6,22)$.
Packing Densities of Patterns
Authors: Barton Reid W.
Published: January 2020

The packing density of a permutation $\pi$ of length $n$ is the maximum proportion of subsequences of length $n$ which are order-isomorphic to $\pi$ in arbitrarily long permutations $\sigma$. For the generalization to patterns $\pi$ which may have repeated letters, two notions of packing density have been defined. In this paper, we show that these two definitions are equivalent, and we compute the packing density for new classes of patterns.
Bounds on the Turán Density of ${\rm PG}(3,2)$
Authors: Cioabă Sebastian M.
Published: January 2020

We prove that the Turán density of ${\rm PG}(3,2)$ is at least ${27/32}=0.84375$ and at most ${27/28}=0.96428...$.
On the Functions with Values in $[\alpha(G), \overline \chi(G)]$
Authors: Dobrynin V. , Pliskin M. , Prosolupov E.
Published: January 2020

Let $$ {\cal B}(G) =\{X : X \in{\Bbb R}^{n \times n}, X=X^T, I \le X \le I+A(G)\} $$ and $$ {\cal C}(G) =\{X : X \in{\Bbb R}^{n \times n}, X=X^T, I-A(G) \le X \le I+A(G)\} $$ be classes of matrices associated with graph $G$. Here $n$ is the number of vertices in graph $G$, and $A(G)$ is the adjacency matrix of this graph. Denote $r(G)=\min_{X \in {\cal C}(G)} {\rm rank}(X)$, $r_+(G)=\min_{X \in {\cal B}(G)} {\rm rank}(X)$. We have shown previously that for every graph $G$, $\alpha(G) \le r_+(G) \le \overline \chi(G)$ holds and $\alpha(G)=r_+(G)$ implies $\alpha(G)=\overline \chi(G)$. In this article we show that there is a graph $G$ such that $\alpha(G)=r(G)$ but $ \alpha(G) < \overline \chi(G).$ In the case when the graph $G$ doesn't contain two chordless cycles $C_4$ with a common edge, the equality $\alpha(G)=r(G)$ implies $ \alpha(G) = \overline \chi(G)$. Corollary: the last statement holds for $d(G)$ – the minimal dimension of the orthonormal representation of the graph $G$.
$n$-Color Partition Theoretic Interpretations of some Mock Theta Functions
Authors: Agarwal A. K.
Published: January 2020

Using $n$-color partitions we provide new number theoretic interpretations of four mock theta functions of S. Ramanujan.
Filling a Box with Translates of Two Bricks
Authors: Kolountzakis Mihail N.
Published: January 2020

We give a new proof of the following interesting fact recently proved by Bower and Michael: if a $d$-dimensional rectangular box can be tiled using translates of two types of rectangular bricks, then it can also be tiled in the following way. We can cut the box across one of its sides into two boxes, one of which can be tiled with the first brick only and the other one with the second brick. Our proof relies on the Fourier Transform. We also show that no such result is true for translates of more than two types of bricks.
Geometrically Constructed Bases for Homology of Partition Lattices of Types $A$, $B$ and $D$
Authors: Björner Anders , Wachs Michelle L.
Published: January 2020

We use the theory of hyperplane arrangements to construct natural bases for the homology of partition lattices of types $A$, $B$ and $D$. This extends and explains the "splitting basis" for the homology of the partition lattice given by M. L. Wachs, thus answering a question asked by R. Stanley. More explicitly, the following general technique is presented and utilized. Let ${\cal A}$ be a central and essential hyperplane arrangement in ${\Bbb{R}}^d$. Let $R_1,\dots,R_k$ be the bounded regions of a generic hyperplane section of ${\cal A}$. We show that there are induced polytopal cycles $\rho_{R_i}$ in the homology of the proper part $\overline{L}_{\cal A}$ of the intersection lattice such that $\{\rho_{R_i}\}_{i=1,\dots,k}$ is a basis for $\widetilde{H}_{d-2} (\overline{L}_{\cal A})$. This geometric method for constructing combinatorial homology bases is applied to the Coxeter arrangements of types $A$, $B$ and $D$, and to some interpolating arrangements.
Orthogonal Polynomials Represented by $CW$-Spheres
Authors: Hetyei Gábor
Published: January 2020

Given a sequence $\{Q_n(x)\}_{n=0}^{\infty}$ of symmetric orthogonal polynomials, defined by a recurrence formula $Q_n(x)=\nu_n\cdot x\cdot Q_{n-1}(x)-(\nu_n-1)\cdot Q_{n-2}(x)$ with integer $\nu_i$'s satisfying $\nu_i\geq 2$, we construct a sequence of nested Eulerian posets whose $ce$-index is a non-commutative generalization of these polynomials. Using spherical shellings and direct calculations of the $cd$-coefficients of the associated Eulerian posets we obtain two new proofs for a bound on the true interval of orthogonality of $\{Q_n(x)\}_{n=0}^{\infty}$. Either argument can replace the use of the theory of chain sequences. Our $cd$-index calculations allow us to represent the orthogonal polynomials as an explicit positive combination of terms of the form $x^{n-2r}(x^2-1)^r$. Both proofs may be extended to the case when the $\nu_i$'s are not integers and the second proof is still valid when only $\nu_i>1$ is required. The construction provides a new "limited testing ground" for Stanley's non-negativity conjecture for Gorenstein$^*$ posets, and suggests the existence of strong links between the theory of orthogonal polynomials and flag-enumeration in Eulerian posets.
Sign-Graded Posets, Unimodality of $W$-Polynomials and the Charney-Davis Conjecture
Authors: Brändén Petter
Published: January 2020

We generalize the notion of graded posets to what we call sign-graded (labeled) posets. We prove that the $W$-polynomial of a sign-graded poset is symmetric and unimodal. This extends a recent result of Reiner and Welker who proved it for graded posets by associating a simplicial polytopal sphere to each graded poset. By proving that the $W$-polynomials of sign-graded posets has the right sign at $-1$, we are able to prove the Charney-Davis Conjecture for these spheres (whenever they are flag).
The Redheffer Matrix of a Partially Ordered Set
Authors: Wilf Herbert S.
Published: January 2020

R. Redheffer described an $n\times n$ matrix of 0's and 1's the size of whose determinant is connected to the Riemann Hypothesis. We describe the permutations that contribute to its determinant and its permanent in terms of integer factorizations. We generalize the Redheffer matrix to finite posets that have a 0 element and find the analogous results in the more general situation.
Regenerative Partition Structures
Authors: Gnedin Alexander , Pitman Jim
Published: January 2020

A partition structure is a sequence of probability distributions for $\pi_n$, a random partition of $n$, such that if $\pi_n$ is regarded as a random allocation of $n$ unlabeled balls into some random number of unlabeled boxes, and given $\pi_n$ some $x$ of the $n$ balls are removed by uniform random deletion without replacement, the remaining random partition of $n-x$ is distributed like $\pi_{n-x}$, for all $1 \le x \le n$. We call a partition structure regenerative if for each $n$ it is possible to delete a single box of balls from $\pi_n$ in such a way that for each $1 \le x \le n$, given the deleted box contains $x$ balls, the remaining partition of $n-x$ balls is distributed like $\pi_{n-x}$. Examples are provided by the Ewens partition structures, which Kingman characterised by regeneration with respect to deletion of the box containing a uniformly selected random ball. We associate each regenerative partition structure with a corresponding regenerative composition structure, which (as we showed in a previous paper) is associated in turn with a regenerative random subset of the positive halfline. Such a regenerative random set is the closure of the range of a subordinator (that is an increasing process with stationary independent increments). The probability distribution of a general regenerative partition structure is thus represented in terms of the Laplace exponent of an associated subordinator, for which exponent an integral representation is provided by the Lévy-Khintchine formula. The extended Ewens family of partition structures, previously studied by Pitman and Yor, with two parameters $(\alpha,\theta)$, is characterised for $0 \le \alpha < 1$ and $\theta >0$ by regeneration with respect to deletion of each distinct part of size $x$ with probability proportional to $(n-x)\tau+x(1-\tau)$, where $\tau = \alpha/(\alpha+\theta)$.
Tight Quotients and Double Quotients in the Bruhat Order
Authors: Stembridge John R.
Published: January 2020

It is a well-known theorem of Deodhar that the Bruhat ordering of a Coxeter group is the conjunction of its projections onto quotients by maximal parabolic subgroups. Similarly, the Bruhat order is also the conjunction of a larger number of simpler quotients obtained by projecting onto two-sided (i.e., "double") quotients by pairs of maximal parabolic subgroups. Each one-sided quotient may be represented as an orbit in the reflection representation, and each double quotient corresponds to the portion of an orbit on the positive side of certain hyperplanes. In some cases, these orbit representations are "tight" in the sense that the root system induces an ordering on the orbit that yields effective coordinates for the Bruhat order, and hence also provides upper bounds for the order dimension. In this paper, we (1) provide a general characterization of tightness for one-sided quotients, (2) classify all tight one-sided quotients of finite Coxeter groups, and (3) classify all tight double quotients of affine Weyl groups.
Canonical Characters on Quasi-Symmetric Functions and Bivariate Catalan Numbers
Authors: Aguiar Marcelo , Hsiao Samuel K.
Published: January 2020

Every character on a graded connected Hopf algebra decomposes uniquely as a product of an even character and an odd character (Aguiar, Bergeron, and Sottile, math.CO/0310016). We obtain explicit formulas for the even and odd parts of the universal character on the Hopf algebra of quasi-symmetric functions. They can be described in terms of Legendre's beta function evaluated at half-integers, or in terms of bivariate Catalan numbers: $$C(m,n)={(2m)!(2n)!\over m!(m+n)!n!}\,.$$ Properties of characters and of quasi-symmetric functions are then used to derive several interesting identities among bivariate Catalan numbers and in particular among Catalan numbers and central binomial coefficients.
$P$-Partitions and a Multi-Parameter Klyachko Idempotent
Authors: McNamara Peter , Reutenauer Christophe
Published: January 2020

Because they play a role in our understanding of the symmetric group algebra, Lie idempotents have received considerable attention. The Klyachko idempotent has attracted interest from combinatorialists, partly because its definition involves the major index of permutations. For the symmetric group $S_n$, we look at the symmetric group algebra with coefficients from the field of rational functions in $n$ variables $q_1, \ldots, q_n$. In this setting, we can define an $n$-parameter generalization of the Klyachko idempotent, and we show it is a Lie idempotent in the appropriate sense. Somewhat surprisingly, our proof that it is a Lie element emerges from Stanley's theory of $P$-partitions.
Reciprocal Domains and Cohen–Macaulay $d$-Complexes in ${\Bbb R}^d$
Authors: Miller Ezra , Reiner Victor
Published: January 2020

We extend a reciprocity theorem of Stanley about enumeration of integer points in polyhedral cones when one exchanges strict and weak inequalities. The proof highlights the roles played by Cohen–Macaulayness and canonical modules. The extension raises the issue of whether a Cohen–Macaulay complex of dimension $d$ embedded piecewise-linearly in ${\Bbb R}^d$ is necessarily a $d$-ball. This is observed to be true for $d \leq 3$, but false for $d=4$.
A Combinatorial Proof of the Log-Concavity of a Famous Sequence Counting Permutations
Authors: Bóna Miklós
Published: January 2020

We provide a combinatorial proof for the fact that for any fixed $n$, the sequence $\{i(n,k)\}_{0\leq k\leq {n\choose 2}}$ of the numbers of permutations of length $n$ having $k$ inversions is log-concave.
The $h$-Vector of a Gorenstein Toric Ring of a Compressed Polytope
Authors: Ohsugi Hidefumi , Hibi Takayuki
Published: January 2020

A compressed polytope is an integral convex polytope all of whose pulling triangulations are unimodular. A $(q - 1)$-simplex $\Sigma$ each of whose vertices is a vertex of a convex polytope ${\cal P}$ is said to be a special simplex in ${\cal P}$ if each facet of ${\cal P}$ contains exactly $q - 1$ of the vertices of $\Sigma$. It will be proved that there is a special simplex in a compressed polytope ${\cal P}$ if (and only if) its toric ring $K[{\cal P}]$ is Gorenstein. In consequence it follows that the $h$-vector of a Gorenstein toric ring $K[{\cal P}]$ is unimodal if ${\cal P}$ is compressed.
New Directions in Enumerative Chess Problems
Authors: Elkies Noam D.
Published: January 2020

Normally a chess problem must have a unique solution, and is deemed unsound even if there are alternatives that differ only in the order in which the same moves are played. In an enumerative chess problem, the set of moves in the solution is (usually) unique but the order is not, and the task is to count the feasible permutations via an isomorphic problem in enumerative combinatorics. Almost all enumerative chess problems have been "series-movers"$\!$, in which one side plays an uninterrupted series of moves, unanswered except possibly for one move by the opponent at the end. This can be convenient for setting up enumeration problems, but we show that other problem genres also lend themselves to composing enumerative problems. Some of the resulting enumerations cannot be shown (or have not yet been shown) in series-movers.
Optimal Decision Trees on Simplicial Complexes
Authors: Jonsson Jakob
Published: January 2020

We consider topological aspects of decision trees on simplicial complexes, concentrating on how to use decision trees as a tool in topological combinatorics. By Robin Forman's discrete Morse theory, the number of evasive faces of a given dimension $i$ with respect to a decision tree on a simplicial complex is greater than or equal to the $i$th reduced Betti number (over any field) of the complex. Under certain favorable circumstances, a simplicial complex admits an "optimal" decision tree such that equality holds for each $i$; we may hence read off the homology directly from the tree. We provide a recursive definition of the class of semi-nonevasive simplicial complexes with this property. A certain generalization turns out to yield the class of semi-collapsible simplicial complexes that admit an optimal discrete Morse function in the analogous sense. In addition, we develop some elementary theory about semi-nonevasive and semi-collapsible complexes. Finally, we provide explicit optimal decision trees for several well-known simplicial complexes.
Generating Function for $K$-Restricted Jagged Partitions
Authors: Fortin J.-F. , Jacob P. , Mathieu P.
Published: January 2020

We present a natural extension of Andrews' multiple sums counting partitions of the form $(\lambda_1,\cdots,\lambda_m)$ with $\lambda_i\geq \lambda_{i+k-1}+2$. The multiple sum that we construct is the generating function for the so-called $K$-restricted jagged partitions. A jagged partition is a sequence of non-negative integers $(n_1,n_2,\cdots , n_m)$ with $n_m\geq 1$ subject to the weakly decreasing conditions $n_i\geq n_{i+1}-1$ and $n_i\geq n_{i+2}$. The $K$-restriction refers to the following additional conditions: $n_i \geq n_{i+K-1} +1$ or $n_i = n_{i+1}-1 = n_{i+K-2}+1= n_{i+K-1}$. The corresponding generalization of the Rogers-Ramunjan identities is displayed, together with a novel combinatorial interpretation.
Construction of Codes Identifying Sets of Vertices
Authors: Gravier Sylvain , Moncel Julien
Published: January 2020

In this paper the problem of constructing graphs having a $(1,\le \ell)$-identifying code of small cardinality is addressed. It is known that the cardinality of such a code is bounded by $\Omega\left({\ell^2\over\log \ell}\log n\right)$. Here we construct graphs on $n$ vertices having a $(1,\le \ell)$-identifying code of cardinality $O\left(\ell^4 \log n\right)$ for all $\ell \ge 2$. We derive our construction from a connection between identifying codes and superimposed codes, which we describe in this paper.
Subsequence Containment by Involutions
Authors: Jaggard Aaron D.
Published: January 2020

Inspired by work of McKay, Morse, and Wilf, we give an exact count of the involutions in ${\cal S}_{n}$ which contain a given permutation $\tau\in{\cal S}_{k}$ as a subsequence; this number depends on the patterns of the first $j$ values of $\tau$ for $1\leq j\leq k$. We then use this to define a partition of ${\cal S}_{k}$, analogous to Wilf-classes in the study of pattern avoidance, and examine properties of this equivalence. In the process, we show that a permutation $\tau_1\ldots\tau_k$ is layered iff, for $1\leq j\leq k$, the pattern of $\tau_1\ldots\tau_j$ is an involution. We also obtain a result of Sagan and Stanley counting the standard Young tableaux of size $n$ which contain a fixed tableau of size $k$ as a subtableau.
Trees and Reflection Groups
Authors: Talpo Humberto Luiz , Firer Marcelo
Published: January 2020

We define a reflection in a tree as an involutive automorphism whose set of fixed points is a geodesic and prove that, for the case of a homogeneous tree of degree $4k$, the topological closure of the group generated by reflections has index $2$ in the group of automorphisms of the tree.
Ramsey ($K_{1,2},K_3$)-Minimal Graphs
Authors: Borowiecki M. , Schiermeyer I. , Sidorowicz E.
Published: January 2020

For graphs $G,F$ and $H$ we write $G\rightarrow (F,H)$ to mean that if the edges of $G$ are coloured with two colours, say red and blue, then the red subgraph contains a copy of $F$ or the blue subgraph contains a copy of $H$. The graph $G$ is $(F,H)$-minimal (Ramsey-minimal) if $G\rightarrow (F,H)$ but $G'\not\rightarrow (F,H)$ for any proper subgraph $G'\subseteq G$. The class of all $(F,H)$-minimal graphs shall be denoted by $R (F,H)$. In this paper we will determine the graphs in $R(K_{1,2},K_3)$.
Noncommutative determinants, Cauchy–Binet formulae, and Capelli-type identities I. Generalizations of the Capelli and Turnbull identities
Authors: Caracciolo Sergio , Sokal Alan D. , Sportiello Andrea
Published: January 2020

We prove, by simple manipulation of commutators, two noncommutative generalizations of the Cauchy–Binet formula for the determinant of a product. As special cases we obtain elementary proofs of the Capelli identity from classical invariant theory and of Turnbull's Capelli-type identities for symmetric and antisymmetric matrices.
On the Kronecker Product $s_{(n-p,p)}\ast s_{\lambda}$
Authors: Ballantine C. M. , Orellana R. C.
Published: January 2020

The Kronecker product of two Schur functions $s_{\lambda}$ and $s_{\mu}$, denoted $s_{\lambda}\ast s_{\mu}$, is defined as the Frobenius characteristic of the tensor product of the irreducible representations of the symmetric group indexed by partitions of $n$, $\lambda$ and $\mu$, respectively. The coefficient, $g_{\lambda,\mu,\nu}$, of $s_{\nu}$ in $s_{\lambda}\ast s_{\mu}$ is equal to the multiplicity of the irreducible representation indexed by $\nu$ in the tensor product. In this paper we give an algorithm for expanding the Kronecker product $s_{(n-p,p)}\ast s_{\lambda}$ if $\lambda_1-\lambda_2\geq 2p$. As a consequence of this algorithm we obtain a formula for $g_{(n-p,p), \lambda ,\nu}$ in terms of the Littlewood-Richardson coefficients which does not involve cancellations. Another consequence of our algorithm is that if $\lambda_1-\lambda_2\geq 2p$ then every Kronecker coefficient in $s_{(n-p,p)}\ast s_{\lambda}$ is independent of $n$, in other words, $g_{(n-p,p),\lambda,\nu}$ is stable for all $\nu$.
Computing the Period of an Ehrhart Quasi-Polynomial
Authors: Woods Kevin
Published: January 2020

If $P\subset {\Bbb R}^d$ is a rational polytope, then $i_P(t):=\#(tP\cap {\Bbb Z}^d)$ is a quasi-polynomial in $t$, called the Ehrhart quasi-polynomial of $P$. A period of $i_P(t)$ is ${\cal D}(P)$, the smallest ${\cal D}\in {\Bbb Z}_+$ such that ${\cal D}\cdot P$ has integral vertices. Often, ${\cal D}(P)$ is the minimum period of $i_P(t)$, but, in several interesting examples, the minimum period is smaller. We prove that, for fixed $d$, there is a polynomial time algorithm which, given a rational polytope $P\subset{\Bbb R}^d$ and an integer $n$, decides whether $n$ is a period of $i_P(t)$. In particular, there is a polynomial time algorithm to decide whether $i_P(t)$ is a polynomial. We conjecture that, for fixed $d$, there is a polynomial time algorithm to compute the minimum period of $i_P(t)$. The tools we use are rational generating functions.
$q$-Identities Related to Overpartitions and Divisor Functions
Authors: Fu Amy M. , Lascoux Alain
Published: January 2020

We generalize and prove two conjectures of Corteel and Lovejoy related to overpartitions and divisor functions.
Counting Segmented Permutations Using Bicoloured Dyck Paths
Authors: Claesson Anders
Published: January 2020

A bicoloured Dyck path is a Dyck path in which each up-step is assigned one of two colours, say, red and green. We say that a permutation $\pi$ is $\sigma$-segmented if every occurrence $o$ of $\sigma$ in $\pi$ is a segment-occurrence (i.e., $o$ is a contiguous subword in $\pi$). We show combinatorially the following two results: The $132$-segmented permutations of length $n$ with $k$ occurrences of $132$ are in one-to-one correspondence with bicoloured Dyck paths of length $2n-4k$ with $k$ red up-steps. Similarly, the $123$-segmented permutations of length $n$ with $k$ occurrences of $123$ are in one-to-one correspondence with bicoloured Dyck paths of length $2n-4k$ with $k$ red up-steps, each of height less than $2$. We enumerate the permutations above by enumerating the corresponding bicoloured Dyck paths. More generally, we present a bivariate generating function for the number of bicoloured Dyck paths of length $2n$ with $k$ red up-steps, each of height less than $h$. This generating function is expressed in terms of Chebyshev polynomials of the second kind.
Steiner Triple Systems and Existentially Closed Graphs
Authors: Forbes A. D. , Grannell M. J. , Griggs T. S.
Published: January 2020

We investigate the conditions under which a Steiner triple system can have a 2- or 3-existentially closed block intersection graph.
Generalized Schur Numbers for $x_1 + x_2 + c = 3x_3$
Authors: Kézdy André E. , Snevily Hunter S. , White Susan C.
Published: January 2020

Let $r(c)$ be the least positive integer $n$ such that every two coloring of the integers $1,\ldots,n$ contains a monochromatic solution to $x_1 + x_2 + c = 3x_3$. Verifying a conjecture of Martinelli and Schaal, we prove that $$ r(c) = \left\lceil{2\lceil{2+c\over3}\rceil + c\over3}\right\rceil, $$ for all $c \ge 13$, and $$ r(c) = \left\lceil{3\lceil{3-c\over2}\rceil - c\over2}\right\rceil, $$ for all $c \le -4$.
An Asymptotic Result for the Path Partition Conjecture
Authors: Frick Marietjie , Schiermeyer Ingo
Published: January 2020

The detour order of a graph $G$, denoted by $\tau \left( G\right) ,$ is the order of a longest path in $G.$ A partition of the vertex set of $G$ into two sets, $A$ and $B,$ such that $\tau (\left\langle A\right\rangle )\leq a$ and $\tau (\left\langle B\right\rangle )\leq b$ is called an $(a,b)$-partition of $G$. If $G$ has an $(a,b)$-partition for every pair $(a,b)$ of positive integers such that $a+b=\tau (G),$ then we say that $G$ is $\tau $-partitionable. The Path Partition Conjecture (PPC), which was discussed by Lovász and Mihók in 1981 in Szeged, is that every graph is $\tau $-partitionable. It is known that a graph $G$ of order $n$ and detour order $\tau =n-p$ is $\tau $-partitionable if $p=0,1.$ We show that this is also true for $p=2,3,$ and for all $p\geq 4$ provided that $n\geq p(10p-3).$
Minimum Common String Partition Problem: Hardness and Approximations
Authors: Goldstein Avraham , Kolman Petr , Zheng Jie
Published: January 2020

String comparison is a fundamental problem in computer science, with applications in areas such as computational biology, text processing and compression. In this paper we address the minimum common string partition problem, a string comparison problem with tight connection to the problem of sorting by reversals with duplicates, a key problem in genome rearrangement. A partition of a string $A$ is a sequence ${\cal P} = (P_1,P_2,\dots,P_m)$ of strings, called the blocks, whose concatenation is equal to $A$. Given a partition ${\cal P}$ of a string $A$ and a partition ${\cal Q}$ of a string $B$, we say that the pair $\langle{{\cal P},{\cal Q}}\rangle$ is a common partition of $A$ and $B$ if ${\cal Q}$ is a permutation of ${\cal P}$. The minimum common string partition problem (MCSP) is to find a common partition of two strings $A$ and $B$ with the minimum number of blocks. The restricted version of MCSP where each letter occurs at most $k$ times in each input string, is denoted by $k$-MCSP. In this paper, we show that $2$-MCSP (and therefore MCSP) is NP-hard and, moreover, even APX-hard. We describe a $1.1037$-approximation for $2$-MCSP and a linear time $4$-approximation algorithm for $3$-MCSP. We are not aware of any better approximations.
Discrepancy Games
Authors: Alon Noga , Krivelevich Michael , Spencer Joel , Szabó Tibor
Published: January 2020

We investigate a game played on a hypergraph $H=(V,E)$ by two players, Balancer and Unbalancer. They select one element of the vertex set $V$ alternately until all vertices are selected. Balancer wins if at the end of the game all edges $e\in E$ are roughly equally distributed between the two players. We give a polynomial time algorithm for Balancer to win provided the allowed deviation is large enough. In particular, it follows from our result that if $H$ is $n$-uniform and has $m$ edges, then Balancer can achieve having between $n/2-\sqrt{\ln(2m)n/2}$ and $n/2+\sqrt{\ln(2m)n/2}$ of his vertices on every edge $e$ of $H$. We also discuss applications in positional game theory.
Some Cyclic Solutions to the Three Table Oberwolfach Problem
Authors: Ollis M. A.
Published: January 2020

We use graceful labellings of paths to give a new way of constructing terraces for cyclic groups. These terraces are then used to find cyclic solutions to the three table Oberwolfach problem, ${\rm OP}(r,r,s)$, where two of the tables have equal size. In particular we show that, for every odd $r \geq 3$ and even $r$ with $4 \leq r \leq 16$, there is a number $N_r$ such that there is a cyclic solution to ${\rm OP}(r,r,s)$ whenever $s \geq N_r$. The terraces we are able to construct also prove a conjecture of Anderson: For all $m \geq 3$, there is a terrace of ${\Bbb Z}_{2m}$ which begins $0, 2k, k, \ldots$ for some $k$.
Combinatorics of Singly-Repairable Families
Authors: Luks Eugene M. , Roy Amitabha
Published: January 2020

A non-empty set ${\cal F}$ of $n$-bit vectors over alphabet $\{0,1\}$ is called singly repairable, if every vector $u \in {\cal F}$ satisfies the following conditions:(i) if any bit of $u$ is changed (from $0$ to $1$ or vice versa), the new vector does not belong to ${\cal F}$(ii) there is a unique choice of a different bit that can then be changed to give another vector $\neq u$ in ${\cal F}$.Such families ${\cal F}$ exist only for even $n$ and we show that $2^{n/2} \leq |{\cal F}| \leq {2^{n+1} \over (n+2)}$. The lower bound is tight for all even $n$ and we show that the families of this size are unique under a natural notion of isomorphism (namely, translations and permutation of coordinates). We also construct families that achieve the upper bound when $n$ is of the form $2^m-2$. For general even $n$, we construct families of size at least $2^n/n$. Of particular interest are minimal singly-repairable families. We show that such families have size at most $2^n/n$ and we construct families achieving this upper bound when $n$ is a power of $2$. For general even $n$, we construct minimal families of size $\Omega(2^{n}/n^2)$. The study of these families was inspired by a computational scheduling problem.
An Introduction to $q$-Species
Authors: Morrison Kent E.
Published: January 2020

The combinatorial theory of species developed by Joyal provides a foundation for enumerative combinatorics of objects constructed from finite sets. In this paper we develop an analogous theory for the enumerative combinatorics of objects constructed from vector spaces over finite fields. Examples of these objects include subspaces, flags of subspaces, direct sum decompositions, and linear maps or matrices of various types. The unifying concept is that of a "$q$-species", defined to be a functor from the category of finite dimensional vector spaces over a finite field to the category of finite sets.
Perfect Codes in Cartesian Products of 2-Paths and Infinite Paths
Authors: Dorbec Paul , Mollard Michel
Published: January 2020

We introduce and study a common generalization of 1-error binary perfect codes and perfect single error correcting codes in Lee metric, namely perfect codes on products of paths of length 2 and of infinite length. Both existence and nonexistence results are given.
Isomorphism Classes of Maximal Intersecting Uniform Families Are Few
Authors: McKenna Geoffrey
Published: January 2020

Denote by $f(k, m)$ the number of isomorphism classes of maximal intersecting $k$-uniform families of subsets of $[m]$. In this note we prove the existence of a constant $f(k)$ such that $f(k, m) \leq f(k)$ for all values of $m$.
5-sparse Steiner Triple Systems of Order $n$ Exist for Almost All Admissible $n$
Authors: Wolfe Adam
Published: January 2020

Steiner triple systems are known to exist for orders $n \equiv 1,3$ mod $6$, the admissible orders. There are many known constructions for infinite classes of Steiner triple systems. However, Steiner triple systems that lack prescribed configurations are harder to find. This paper gives a proof that the spectrum of orders of 5-sparse Steiner triple systems has arithmetic density $1$ as compared to the admissible orders.
A Partition of Connected Graphs
Authors: Wiseman Gus
Published: January 2020

We define an algorithm $k$ which takes a connected graph $G$ on a totally ordered vertex set and returns an increasing tree $R$ (which is not necessarily a subtree of $G$). We characterize the set of graphs $G$ such that $k(G)=R$. Because this set has a simple structure (it is isomorphic to a product of non-empty power sets), it is easy to evaluate certain graph invariants in terms of increasing trees. In particular, we prove that, up to sign, the coefficient of $x^q$ in the chromatic polynomial $\chi_G(x)$ is the number of increasing forests with $q$ components that satisfy a condition that we call $G$-connectedness. We also find a bijection between increasing $G$-connected trees and broken circuit free subtrees of $G$.
A Note on an Identity of Andrews
Authors: Zhang Zhizheng
Published: January 2020

In this note we use the $q$-exponential operator technique on an identity of Andrews.
Chain Polynomials of Distributive Lattices are 75% Unimodal
Authors: Björner Anders , Farley Jonathan David
Published: January 2020

It is shown that the numbers $c_i$ of chains of length $i$ in the proper part $L\setminus\{0,1\}$ of a distributive lattice $L$ of length $\ell +2$ satisfy the inequalities $$c_0 < \ldots < c_{\lfloor{\ell /2}\rfloor} \quad\hbox{ and }\quad c_{\lfloor{3 \ell /4}\rfloor}>\ldots>c_{\ell}.$$ This proves 75% of the inequalities implied by the Neggers unimodality conjecture.
A Note on Graphs Without Short Even Cycles
Authors: Lam Thomas , Verstraëte Jacques
Published: January 2020

In this note, we show that any $n$-vertex graph without even cycles of length at most $2k$ has at most ${1\over2}n^{1 + 1/k} + O(n)$ edges, and polarity graphs of generalized polygons show that this is asymptotically tight when $k \in \{2,3,5\}$.
Extending Arcs: An Elementary Proof
Authors: Alderson T.
Published: January 2020

In a finite projective plane $\pi$ we consider two configuration conditions involving arcs in $\pi$ and show via combinatorial means that they are equivalent. When the conditions hold we are able to obtain embeddability results for arcs, all proofs being elementary. In particular, when $\pi=PG(2,q)$ with $q$ even we provide short proofs of some well known embeddability results.
The Turán Problem for Hypergraphs of Fixed Size
Authors: Keevash Peter
Published: January 2020

We obtain a general bound on the Turán density of a hypergraph in terms of the number of edges that it contains. If ${\cal F}$ is an $r$-uniform hypergraph with $f$ edges we show that $$\pi({\cal F}) < {f-2\over f-1} - \big(1+o(1)\big)(2r!^{2/r}f^{3-2/r})^{-1},$$ for fixed $r \geq 3$ and $f \rightarrow \infty$.
A Note on Two Multicolor Ramsey Numbers
Authors: Engström Alexander
Published: January 2020

Two new bounds for multicolor Ramsey numbers are proved: $R(K_3,K_3,C_4,C_4)\geq 27$ and $R_4(C_4)\leq 19$.
Une Base Symétrique de l'Algèbre des Coinvariants Quasi-Symétriques
Authors: Chapoton Frédéric
Published: January 2020

On décrit une nouvelle base de l'algèbre des coinvariants quasi-symétriques, qui est stable par l'involution naturelle et indexée par les triangulations d'un polygone régulier. [We describe a new basis of the ring of quasi-symmetric coinvariants, which is stable by the natural reversal of the set of variables. The indexing set is the set of triangulations of a regular polygon, instead of the set of Dyck paths used for the known basis.]
The Intersection Structure of $t$-Intersecting Families
Authors: Talbot John
Published: January 2020

A family of sets is $t$-intersecting if any two sets from the family contain at least $t$ common elements. Given a $t$-intersecting family of $r$-sets from an $n$-set, how many distinct sets of size $k$ can occur as pairwise intersections of its members? We prove an asymptotic upper bound on this number that can always be achieved. This result can be seen as a generalization of the Erdős-Ko-Rado theorem.
Actions and Identities on Set Partitions
Authors: Marberg Eric
Published: January 2020

A labeled set partition is a partition of a set of integers whose arcs are labeled by nonzero elements of an abelian group $\mathbb{A}$. Inspired by the action of the linear characters of the unitriangular group on its supercharacters, we define a group action of $\mathbb{A}^n$ on the set of $\mathbb{A}$-labeled partitions of an $(n+1)$-set. By investigating the orbit decomposition of various families of set partitions under this action, we derive new combinatorial proofs of Coker's identity for the Narayana polynomial and its type B analogue, and establish a number of other related identities. In return, we also prove some enumerative results concerning André and Neto's supercharacter theories of type B and D.
A Construction for the Hat Problem on a Directed Graph
Authors: Hod Rani , Krzywkowski Marcin
Published: January 2020

A team of $n$ players plays the following game. After a strategy session, each player is randomly fitted with a blue or red hat. Then, without further communication, everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. Visibility is defined by a directed graph; that is, vertices correspond to players, and a player can see each player to whom he is connected by an arc. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The team aims to maximize the probability of a win, and this maximum is called the hat number of the graph.Previous works focused on the hat problem on complete graphs and on undirected graphs. Some cases were solved, e.g., complete graphs of certain orders, trees, cycles, and bipartite graphs. These led Uriel Feige to conjecture that the hat number of any graph is equal to the hat number of its maximum clique.We show that the conjecture does not hold for directed graphs. Moreover, for every value of the maximum clique size, we provide a tight characterization of the range of possible values of the hat number. We construct families of directed graphs with a fixed clique number the hat number of which is asymptotically optimal. We also determine the hat number of tournaments to be one half.
Mesh Patterns and the Expansion of Permutation Statistics as Sums of Permutation Patterns
Authors: Brändén Petter , Claesson Anders
Published: January 2020

Any permutation statistic $f:{\mathfrak{S}}\to{\mathbb C}$ may be represented uniquely as a, possibly infinite, linear combination of (classical) permutation patterns: $f= \Sigma_\tau\lambda_f(\tau)\tau$. To provide explicit expansions for certain statistics, we introduce a new type of permutation patterns that we call mesh patterns. Intuitively, an occurrence of the mesh pattern $p=(\pi,R)$ is an occurrence of the permutation pattern $\pi$ with additional restrictions specified by $R$ on the relative position of the entries of the occurrence. We show that, for any mesh pattern $p=(\pi,R)$, we have $\lambda_p(\tau) = (-1)^{|\tau|-|\pi|}{p}^{\star}(\tau)$ where ${p}^{\star}=(\pi,R^c)$ is the mesh pattern with the same underlying permutation as $p$ but with complementary restrictions. We use this result to expand some well known permutation statistics, such as the number of left-to-right maxima, descents, excedances, fixed points, strong fixed points, and the major index. We also show that alternating permutations, André permutations of the first kind and simsun permutations occur naturally as permutations avoiding certain mesh patterns. Finally, we provide new natural Mahonian statistics.
Concave Compositions
Authors: Andrews George E.
Published: January 2020

Concave compositions are compositions (i.e. ordered partitions) of a number in which the parts decrease up to the middle summand(s) and increase thereafter. Perhaps the most surprising result is for even length, concave compositions where the generating function turns out to be the quotient of two instances of the pentagonal number theorem with variations of sign. The false theta function discoveries also lead to new facts about concatenatable, spiral, self-avoiding walks.
The $(t,q)$-Analogs of Secant and Tangent Numbers
Authors: Foata Dominique , Han Guo-Niu
Published: January 2020

The secant and tangent numbers are given $(t,q)$-analogs with an explicit combinatorial interpretation. This extends, both analytically and combinatorially, the classical evaluations of the Eulerian and Roselle polynomials at $t=-1$.
Reducibility and Solvability of Some Classes of Kryuchkov Binary Tree Pairs
Authors: Madonia Maria , Scollo Giuseppe
Published: January 2020

This paper addresses the problem of characterizing classes of pairs of binary trees of equal size for which a signed reassociation sequence, in the Eliahou-Kryuchkov sense, can be shown to exist, either with a size induction hypothesis (reducible pairs), or without it (solvable pairs). A few concepts proposed by Cooper, Rowland and Zeilberger, in the context of a language-theoretic approach to the problem, are here reformulated in terms of signed reassociation sequences, and some of their results are recasted and proven in this framework. A few strategies, tactics and combinations thereof for signed reassociation are introduced, which prove useful to extend the results obtained by the aforementioned authors to new classes of binary tree pairs. In particular, with reference to path trees, i.e. binary trees that have a leaf at every level, we show the reducibility of pairs where (at least) one of the two path trees has a triplication at the first turn below the top level, and we characterize a class of weakly mutually crooked path tree pairs that are neither reducible nor solvable by any previously known result, but prove solvable by appropriate reassociation strategies. This class also includes a subclass of mutually crooked path tree pairs. A summary evaluation of the achieved results, followed by an outline of open questions and future research directions conclude the paper.
The Double Riordan Group
Authors: Davenport Dennis E. , Shapiro Louis W. , Woodson Leon C.
Published: January 2020

The Riordan group is a group of infinite lower triangular matrices that are defined by two generating functions, $g$ and $f$. The kth column of the matrix has the generating function $gf^k$. In the Double Riordan group there are two generating function $f_1$ and $f_2$ such that the columns, starting at the left, have generating functions using $f_1$ and $f_2$ alternately. Examples include Dyck paths with level steps of length 2  allowed at even height and also ordered trees with differing degree possibilities at even and odd height(perhaps representing summer and winter). The Double Riordan group is a generalization not of the Riordan group itself but of the checkerboard subgroup. In this context both familiar and far less familiar sequences occur such as the Motzkin numbers and the number of spoiled child trees. The latter is a slightly enhanced cousin of ordered trees which are counted by the Catalan numbers.
The Negative $q$-Binomial
Authors: Fu Shishuo , Reiner V. , Stanton Dennis , Thiem Nathaniel
Published: January 2020

Interpretations for the $q$-binomial coefficient evaluated at $-q$ are discussed.  A $(q,t)$-version is established, including an instance of a cyclic sieving phenomenon involving unitary spaces.
Pattern-Avoiding Set Partitions and Catalan Numbers
Authors: Mansour Toufik , Shattuck Mark
Published: January 2020

We identify several subsets of the partitions of $[n]$, each characterized by the avoidance of a pair of patterns, respectively of lengths four and five.  Each of the classes we consider is enumerated by the Catalan numbers.  Furthermore, the members of each class having a prescribed number of blocks are enumerated by the Narayana numbers.  We use both algebraic and combinatorial methods to establish our results.  In some of the cases, we make use of the kernel method to solve the recurrence arising when a further statistic is considered.  In other cases, we define bijections with previously enumerated classes which preserve the number of blocks.  Two of our bijections are of an algorithmic nature and systematically replace the occurrences of one pattern with those of another having the same length.
Bivariate Identities for Values of the Hurwitz Zeta Function and Supercongruences
Authors: Pilehrood Kh. Hessami , Pilehrood T. Hessami
Published: January 2020

In this paper, we prove a new identity for values of the Hurwitz zeta function which contains as particular cases Koecher's identity for odd zeta values, the Bailey-Borwein-Bradley identity for even zeta values and many other interesting formulas related to values of the Hurwitz zeta function. We also get an extension of the bivariate identity of Cohen to values of the Hurwitz zeta function. The main tool we use here is a construction of new Markov-WZ pairs. As application of our results, we prove several conjectures on supercongruences proposed by J. Guillera, W. Zudilin, and Z. W. Sun.