bluuebunny/crossref_metadata_2025 huggingface dataset:
Generalized Bell Polynomials and the Combinatorics of Poisson Central Moments
Authors: Privault Nicolas
Published: January 2020

We introduce a family of polynomials that generalizes the Bell polynomials, in connection with the combinatorics of the central moments of the Poisson distribution. We show that these polynomials are dual of the Charlier polynomials by the Stirling transform, and we study the resulting combinatorial identities for the number of partitions of a set into subsets of size at least $2$.
The Fibonacci Dimension of a Graph
Authors: Cabello Sergio , Eppstein David , Klavžar Sandi
Published: January 2020

The Fibonacci dimension ${\rm fdim}(G)$ of a graph $G$ is introduced as the smallest integer $f$ such that $G$ admits an isometric embedding into $\Gamma_f$, the $f$-dimensional Fibonacci cube. We give bounds on the Fibonacci dimension of a graph in terms of the isometric and lattice dimension, provide a combinatorial characterization of the Fibonacci dimension using properties of an associated graph, and establish the Fibonacci dimension for certain families of graphs. From the algorithmic point of view, we prove that it is NP-complete to decide whether ${\rm fdim}(G)$ equals the isometric dimension of $G$, and show that no algorithm to approximate ${\rm fdim}(G)$ has approximation ratio below $741/740$, unless P$=$NP. We also give a $(3/2)$-approximation algorithm for ${\rm fdim}(G)$ in the general case and a $(1+\varepsilon)$-approximation algorithm for simplex graphs.
Counting Triangulations of Planar Point Sets
Authors: Sharir Micha , Sheffer Adam
Published: January 2020

We study the maximal number of triangulations that a planar set of $n$ points can have, and show that it is at most $30^n$. This new bound is achieved by a careful optimization of the charging scheme of Sharir and Welzl (2006), which has led to the previous best upper bound of $43^n$ for the problem. Moreover, this new bound is useful for bounding the number of other types of planar (i.e., crossing-free) straight-line graphs on a given point set. Specifically, it can be used to derive new upper bounds for the number of planar graphs ($207.84^n$), spanning cycles ($O(68.67^n)$), spanning trees ($O(146.69^n)$), and cycle-free graphs ($O(164.17^n)$).
Product and Puzzle Formulae for $GL_n$ Belkale-Kumar Coefficients
Authors: Knutson Allen , Purbhoo Kevin
Published: January 2020

The Belkale-Kumar product on $H^*(G/P)$ is a degeneration of the usual cup product on the cohomology ring of a generalized flag manifold. In the case $G=GL_n$, it was used by N. Ressayre to determine the regular faces of the Littlewood-Richardson cone. We show that for $G/P$ a $(d-1)$-step flag manifold, each Belkale-Kumar structure constant is a product of $d\choose 2$ Littlewood-Richardson numbers, for which there are many formulae available, e.g. the puzzles of [Knutson-Tao '03]. This refines previously known factorizations into $d-1$ factors. We define a new family of puzzles to assemble these to give a direct combinatorial formula for Belkale-Kumar structure constants. These "BK-puzzles" are related to extremal honeycombs, as in [Knutson-Tao-Woodward '04]; using this relation we give another proof of Ressayre's result. Finally, we describe the regular faces of the Littlewood-Richardson cone on which the Littlewood-Richardson number is always $1$; they correspond to nonzero Belkale-Kumar coefficients on partial flag manifolds where every subquotient has dimension $1$ or $2$.
Rainbow Paths with Prescribed Ends
Authors: Alishahi Meysam , Taherkhani Ali , Thomassen Carsten
Published: January 2020

It was conjectured in [S. Akbari, F. Khaghanpoor, and S. Moazzeni. Colorful paths in vertex coloring of graphs. Preprint] that, if $G$ is a connected graph distinct from $C_7$, then there is a $\chi(G)$-coloring of $G$ in which every vertex $v\in V(G)$ is an initial vertex of a path $P$ with $\chi(G)$ vertices whose colors are different. In [S. Akbari, V. Liaghat, and A. Nikzad. Colorful paths in vertex coloring of graphs. Electron. J. Combin. 18(1): P17, 9pp, 2011] this was proved with $\lfloor\frac{\chi(G)}{2} \rfloor $ vertices instead of $\chi(G)$ vertices. We strengthen this to $\chi(G)-1$ vertices. We also prove that every connected graph with at least one edge has a proper $k$-coloring (for some $k$) such that every vertex of color $i$ has a neighbor of color $i+1$ (mod $k$). $C_5$ shows that $k$ may have to be greater than the chromatic number. However, if the graph is connected, infinite and locally finite, and has finite chromatic number, then the $k$-coloring exists for every $k \geq \chi(G)$. In fact, the $k$-coloring can be chosen such that every vertex is a starting vertex of an infinite path such that the color increases by $1$ (mod $k$) along each edge. The method is based on the circular chromatic number $\chi_c(G)$. In particular, we verify the above conjecture for all connected graphs whose circular chromatic number equals the chromatic number.
Counting the Number of Elements in the Mutation Classes of $\tilde A_n-$Quivers
Authors: Bastian Janine , Prellberg Thomas , Rubey Martin , Stump Christian
Published: January 2020

In this article we prove explicit formulae for the number of non-isomorphic cluster-tilted algebras of type $\tilde A_n$ in the derived equivalence classes. In particular, we obtain the number of elements in the mutation classes of quivers of type $\tilde A_n$. As a by-product, this provides an alternative proof for the number of quivers mutation equivalent to a quiver of Dynkin type $D_n$ which was first determined by Buan and Torkildsen.
Explicit Cayley Covers of Kautz Digraphs
Authors: Brunat Josep M.
Published: January 2020

Given a finite set $V$ and a set $S$ of permutations of $V$, the group action graph $\mathrm{GAG}(V,S)$ is the digraph with vertex set $V$ and arcs $(v,v^\sigma)$ for all $v\in V$ and $\sigma\in S$. Let $\langle S\rangle$ be the group generated by $S$. The Cayley digraph $\textrm{Cay}(\langle S\rangle, S)$ is called a Cayley cover of $\mathrm{GAG}(V,S)$. We define the Kautz digraphs as group action graphs and give an explicit construction of the corresponding Cayley cover. This is an answer to a problem posed by Heydemann in 1996.
Characterizations of Transversal and Fundamental Transversal Matroids
Authors: Bonin Joseph E. , Kung Joseph P. S. , De Mier Anna
Published: January 2020

A result of Mason, as refined by Ingleton, characterizes transversal matroids as the matroids that satisfy a set of inequalities that relate the ranks of intersections and unions of nonempty sets of cyclic flats. We prove counterparts, for fundamental transversal matroids, of this and other characterizations of transversal matroids. In particular, we show that fundamental transversal matroids are precisely the matroids that yield equality in Mason's inequalities and we deduce a characterization of fundamental transversal matroids due to Brylawski from this simpler characterization.
Monomer-Dimer Tatami Tilings of Rectangular Regions
Authors: Erickson Alejandro , Ruskey Frank , Woodcock Jennifer , Schurch Mark
Published: January 2020

In this paper we consider tilings of rectangular regions with two types of tiles, $1 \times 2$ tiles (dimers) and $1 \times 1$ tiles (monomers). The tiles must cover the region and satisfy the constraint that no four corners of the tiles meet; such tilings are called tatami tilings. We provide a structural characterization and use it to prove that the tiling is completely determined by the tiles that are on its border. We prove that the number of tatami tilings of an $n \times n$ square with $n$ monomers is $n2^{n-1}$. We also show that, for fixed-height, the generating function for the number of tatami tilings of a rectangle is a rational function, and outline an algorithm that produces the generating function.
Critical Exponents of Words over 3 Letters
Authors: Vaslet Elise
Published: January 2020

For all $\alpha \geq RT(3)$ (where $RT(3) = 7/4$ is the repetition threshold for the $3$-letter alphabet), there exists an infinite word over 3 letters whose critical exponent is $\alpha$.
Enumeration of Varlet and Comer Hypergroups
Authors: Aghabozorgi H. , Jafarpour M. , Davvaz B.
Published: January 2020

In this paper, we study hypergroups determined by lattices introduced by Varlet and Comer, especially we enumerate Varlet and Comer hypergroups of orders less than 50 and 13, respectively.
On the Area Discrepancy of Triangulations of Squares and Trapezoids
Authors: Schulze Bernd
Published: January 2020

In 1970 P. Monsky showed that a square cannot be triangulated into an odd number of triangles of equal areas; further, in 1990 E. A. Kasimatis and S. K. Stein proved that the trapezoid $T(\alpha)$ whose vertices have the coordinates $(0,0)$, $(0,1)$, $(1,0)$, and $(\alpha,1)$ cannot be triangulated into any number of triangles of equal areas if $\alpha>0$ is transcendental. In this paper we first establish a new asymptotic upper bound for the minimal difference between the smallest and the largest area in triangulations of a square into an odd number of triangles. More precisely, using some techniques from the theory of continued fractions, we construct a sequence of triangulations $T_{n_i}$ of the unit square into $n_i$ triangles, $n_i$ odd, so that the difference between the smallest and the largest area in $T_{n_i}$ is $O\big(\frac{1}{n_i^3}\big)$. We then prove that for an arbitrarily fast-growing function $f:\mathbb{N}\to \mathbb{N}$, there exists a transcendental number $\alpha>0$ and a sequence of triangulations $T_{n_i}$ of the trapezoid $T(\alpha)$ into $n_i$ triangles, so that the difference between the smallest and the largest area in $T_{n_i}$ is $O\big(\frac{1}{f(n_i)}\big)$.
Counting Bordered Partial Words by Critical Positions
Authors: Allen Emily , Blanchet-Sadri F. , Byrum Cameron , Cucuringu Mihai , Mercaş Robert
Published: January 2020

A partial word, sequence over a finite alphabet that may have some undefined positions or holes, is bordered if one of its proper prefixes is compatible with one of its suffixes. The number theoretical problem of enumerating all bordered full words (the ones without holes) of a fixed length $n$ over an alphabet of a fixed size $k$ is well known. It turns out that all borders of a full word are simple, and so every bordered full word has a unique minimal border no longer than half its length. Counting bordered partial words having $h$ holes with the parameters $k, n$ is made extremely more difficult by the failure of that combinatorial property since there is now the possibility of a minimal border that is nonsimple. Here, we give recursive formulas based on our approach of the so-called simple and nonsimple critical positions.
Counting Words by Number of Occurrences of Some Patterns
Authors: Gao Zhicheng , MacFie Andrew , Panario Daniel
Published: January 2020

We give asymptotic expressions for the number of words containing a given number of occurrences of a pattern for two families of patterns with two parameters each. One is the family of classical patterns in the form $22\cdots 212 \cdots 22$ and the other is a family of partially ordered patterns. The asymptotic expressions are in terms of the number of solutions to an equation, and for one subfamily this quantity is the number of integer partitions into $q$th order binomial coefficients.
Long Path Lemma concerning Connectivity and Independence Number
Authors: Fujita Shinya , Halperin Alexander , Magnant Colton
Published: January 2020

We show that, in a $k$-connected graph $G$ of order $n$ with $\alpha(G) = \alpha$, between any pair of vertices, there exists a path $P$ joining them with $$|P| \geq \min \left\{ n, \frac{(k - 1)(n - k)}{\alpha} + k \right\}.$$ This implies that, for any edge $e \in E(G)$, there is a cycle containing $e$ of length at least $$\min \left\{ n, \frac{(k - 1)(n - k)}{\alpha} + k \right\}.$$ Moreover, we generalize our result as follows: for any choice $S$ of $s \leq k$ vertices in $G$, there exists a tree $T$ whose set of leaves is $S$ with $$|T| \geq \min \left\{ n, \frac{(k - s + 1)(n - k)}{\alpha} + k \right\}.$$
Chromatic Statistics for Triangulations and Fuß–Catalan Complexes
Authors: Bacher R. , Krattenthaler C.
Published: January 2020

We introduce Fuß–Catalan complexes as $d$-dimensional generalisations of triangulations of a convex polygon. These complexes are used to refine Catalan numbers and Fuß–Catalan numbers, by introducing colour statistics for triangulations and Fuß–Catalan complexes. Our refinements consist in showing that the number of triangulations, respectively of Fuß–Catalan complexes, with a given colour distribution of its vertices is given by closed product formulae. The crucial ingredient in the proof is the Lagrange–Good inversion formula.
On Han's Hook Length Formulas for Trees
Authors: Chen William Y.C. , Gao Oliver X.Q. , Guo Peter L.
Published: January 2020

Recently, Han obtained two hook length formulas for binary trees and asked for combinatorial proofs. One of Han's formulas has been generalized to $k$-ary trees by Yang. Sagan has found a probabilistic proof of Yang's extension. We give combinatorial proofs of Yang's formula for $k$-ary trees and the other formula of Han for binary trees. Our bijections are based on the structure of $k$-ary trees associated with staircase labelings.
$q,t$-Catalan Numbers and Generators for the Radical Ideal defining the Diagonal Locus of $({\mathbb C}^2)^n$
Authors: Lee Kyungyong , Li Li
Published: January 2020

Let $I$ be the ideal generated by alternating polynomials in two sets of $n$ variables. Haiman proved that the $q,t$-Catalan number is the Hilbert series of the bi-graded vector space $M(=\bigoplus_{d_1,d_2}M_{d_1,d_2})$ spanned by a minimal set of generators for $I$. In this paper we give simple upper bounds on $\text{dim }M_{d_1, d_2}$ in terms of number of partitions, and find all bi-degrees $(d_1,d_2)$ such that $\dim M_{d_1, d_2}$ achieve the upper bounds. For such bi-degrees, we also find explicit bases for $M_{d_1, d_2}$.
Rainbow Matchings in Properly Edge Colored Graphs
Authors: Wang Guanghui
Published: January 2020

Let $G$ be a properly edge colored graph. A rainbow matching of $G$ is a matching in which no two edges have the same color. Let $\delta$ denote the minimum degree of $G$. We show that if $|V(G)|\geq \frac{8\delta}{5}$, then $G$ has a rainbow matching of size at least $\lfloor\frac {3 \delta }{5}\rfloor$. We also prove that if $G$ is a properly colored triangle-free graph, then $G$ has a rainbow matching of size at least $\lfloor\frac {2 \delta }{3}\rfloor$.
On the Path-Avoidance Vertex-Coloring Game
Authors: Mütze Torsten , Spöhel Reto
Published: January 2020

For any graph $F$ and any integer $r\geq 2$, the online vertex-Ramsey density of $F$ and $r$, denoted $m^*(F,r)$, is a parameter defined via a deterministic two-player Ramsey-type game (Painter vs. Builder). This parameter was introduced in a recent paper [arXiv:1103.5849], where it was shown that the online vertex-Ramsey density determines the threshold of a similar probabilistic one-player game (Painter vs. the binomial random graph $G_{n,p}$). For a large class of graphs $F$, including cliques, cycles, complete bipartite graphs, hypercubes, wheels, and stars of arbitrary size, a simple greedy strategy is optimal for Painter and closed formulas for $m^*(F,r)$ are known. In this work we show that for the case where $F=P_\ell$ is a long path, the picture is very different. It is not hard to see that $m^*(P_\ell,r)= 1-1/k^*(P_\ell,r)$ for an appropriately defined integer $k^*(P_\ell,r)$, and that the greedy strategy gives a lower bound of $k^*(P_\ell,r)\geq \ell^r$. We construct and analyze Painter strategies that improve on this greedy lower bound by a factor polynomial in $\ell$, and we show that no superpolynomial improvement is possible.
Graphs with equal Independence and Annihilation Numbers
Authors: Larson C. E. , Pepper R.
Published: January 2020

The annihilation number $a$ of a graph is an upper bound of the independence number $\alpha$ of a graph. In this article we characterize graphs with equal independence and annihilation numbers. In particular, we show that $\alpha=a$ if, and only if, either (1) $a\geq \frac{n}{2}$ and $\alpha' =a$, or (2) $a < \frac{n}{2}$ and there is a vertex $v\in V(G)$ such that $\alpha' (G-v)=a(G)$, where $\alpha'$ is the critical independence number of the graph. Furthermore, we show that it can be determined in polynomial time whether $\alpha=a$. Finally we show that a graph where $\alpha=a$ is either König-Egerváry or almost König-Egerváry.
Applications of the Kelmans Transformation: Extremality of the Threshold Graphs
Authors: Csikvári Péter
Published: January 2020

In this paper we study various extremal problems related to some combinatorially defined graph polynomials such as matching polynomial, chromatic polynomial, Laplacian polynomial. It will turn out that many problems attain its extremal value in the class of threshold graphs. To attack these kinds of problems we survey several applications of the so-called Kelmans transformation.
Shellability and the Strong gcd-Condition
Authors: Berglund Alexander
Published: January 2020

Shellability is a well-known combinatorial criterion on a simplicial complex $\Delta$ for verifying that the associated Stanley-Reisner ring $k[\Delta]$ is Cohen-Macaulay. A notion familiar to commutative algebraists, but which has not received as much attention from combinatorialists as the Cohen-Macaulay property, is the notion of a Golod ring. Recently, Jöllenbeck introduced a criterion on simplicial complexes reminiscent of shellability, called the strong gcd-condition, and he together with the author proved that it implies Golodness of the associated Stanley-Reisner ring. The two algebraic notions were earlier tied together by Herzog, Reiner and Welker, who showed that if $k[\Delta^\vee]$ is sequentially Cohen-Macaulay, where $\Delta^\vee$ is the Alexander dual of $\Delta$, then $k[\Delta]$ is Golod. In this paper, we present a combinatorial companion of this result, namely that if $\Delta^\vee$ is (non-pure) shellable then $\Delta$ satisfies the strong gcd-condition. Moreover, we show that all implications just mentioned are strict in general but that they are equivalences if $\Delta$ is a flag complex.
The Odd and Even Intersection Properties
Authors: Scharaschkin Victor
Published: January 2020

A non-empty family $\mathscr{S}$ of subsets of a finite set $A$ has the odd (respectively, even) intersection property if there exists non-empty $B \subseteq A$ with $|B \cap S|$ odd (respectively, even) for each $S \in \mathscr{S}$. In characterizing sets of integers that are quadratic non-residues modulo infinitely many primes, Wright asked for the number of such $\mathscr{S}$, as a function of $|A|$. We give explicit formulae.
Labeled Trees, Functions, and an Algebraic Identity
Authors: Wagner Stephan
Published: January 2020

We give a short and direct proof of a remarkable identity that arises in the enumeration of labeled trees with respect to their indegree sequence, where all edges are oriented from the vertex with lower label towards the vertex with higher label. This solves a problem posed by Shin and Zeng in a recent article. We also provide a generalization of this identity that translates to a formula for the number of rooted spanning forests with given indegree sequence.
Automorphism Group of the Derangement Graph
Authors: Deng Yun-Ping , Zhang Xiao-Dong
Published: January 2020

In this paper, we prove that the full automorphism group of the derangement graph $\Gamma_n$ ($n\geq3$) is equal to $(R(S_n)\rtimes\hbox{Inn} (S_n))\rtimes Z_2$, where $R(S_n)$ and $\hbox{Inn} (S_n)$ are the right regular representation and the inner automorphism group of $S_n$ respectively, and $Z_2=\langle\varphi\rangle$ with the mapping $\varphi:$ $\sigma^{\varphi}=\sigma^{-1},\,\forall\,\sigma\in S_n.$ Moreover, all orbits on the edge set of $\Gamma_n$ ($n\geq3$) are determined.
How many Faces can the Polycubes of Lattice Tilings by Translation of ${\mathbb R}^3$ have?
Authors: Gambini I. , Vuillon L.
Published: January 2020

We construct a class of polycubes that tile the space by translation in a lattice-periodic way and show that for this class the number of surrounding tiles cannot be bounded. The first construction is based on polycubes with an $L$-shape but with many distinct tilings of the space. Nevertheless, we are able to construct a class of more complicated polycubes such that each polycube tiles the space in a unique way and such that the number of faces is $4k+8$ where $2k+1$ is the volume of the polycube. This shows that the number of tiles that surround the surface of a space-filler cannot be bounded.
A Restricted Version of Wythoff's Game
Authors: Liu Wen An , Li Haifeng , Li Bei
Published: January 2020

E. Duchêne and S. Gravier present the following open problem: In Wythoff's game, each player can either remove at most $R$ tokens from a single heap (i.e. there is an upper bound $R$ on the number of removing tokens), or remove the same number of tokens from both heaps but there is no upper bound on the number of removing tokens. This open problem is investigated and all its P-positions are given.
Conjugacy of Coxeter Elements
Authors: Eriksson Henrik , Eriksson Kimmo
Published: January 2020

For a Coxeter group $(W,S)$, a permutation of the set $S$ is called a Coxeter word and the group element represented by the product is called a Coxeter element. Moving the first letter to the end of the word is called a rotation and two Coxeter elements are rotation equivalent if their words can be transformed into each other through a sequence of rotations and legal commutations. We prove that Coxeter elements are conjugate if and only if they are rotation equivalent. This was known for some special cases but not for Coxeter groups in general.
An Erdős-Ko-Rado Theorem for Multisets
Authors: Meagher Karen , Purdy Alison
Published: January 2020

Let $k$ and $m$ be positive integers. A collection of $k$-multisets from $\{1,\dots, m \}$ is intersecting if every pair of multisets from the collection is intersecting. We prove that for $m \geq k+1$, the size of the largest such collection is $\binom{m+k-2}{k-1}$ and that when $m > k+1$, only a collection of all the $k$-multisets containing a fixed element will attain this bound. The size and structure of the largest intersecting collection of $k$-multisets for $m \leq k$ is also given.
Rotor-Router Aggregation on the Comb
Authors: Huss Wilfried , Sava Ecaterina
Published: January 2020

We prove a shape theorem for rotor-router aggregation on the comb, for a specific initial rotor configuration and clockwise rotor sequence for all vertices. Furthermore, as an application of rotor-router walks, we describe the harmonic measure of the rotor-router aggregate and related shapes, which is useful in the study of other growth models on the comb. We also identify the shape for which the harmonic measure is uniform. This gives the first known example where the rotor-router cluster has non-uniform harmonic measure, and grows with different speeds in different directions.
Average Values of some Z-Parameters in a Random Set Partition
Authors: Kasraoui Anisse
Published: January 2020

We find exact and asymptotic formulas for the average values of several statistics on set partitions: of Carlitz's $q$-Stirling distributions, of the numbers of crossings in linear and circular representations of set partitions, of the numbers of overlappings and embracings, and of the numbers of occurrences of a 2-pattern.
On the Unitary Cayley Signed Graphs
Authors: Sinha Deepa , Garg Pravin
Published: January 2020

A $signed graph$ (or $sigraph$ in short) is an ordered pair $S = (S^u, \sigma)$, where $S^u$ is a graph $G = (V, E)$ and $\sigma : E\rightarrow \{+,-\}$ is a function from the edge set $E$ of $S^u$ into the set $\{+, -\}$. For a positive integer $n > 1$, the unitary Cayley graph $X_n$ is the graph whose vertex set is $Z_n$, the integers modulo $n$ and if $U_n$ denotes set of all units of the ring $Z_n$, then two vertices $a, b$ are adjacent if and only if $a-b \in U_n$. For a positive integer $n > 1$, the unitary Cayley sigraph $\mathcal{S}_n = (\mathcal{S}^u_n, \sigma)$ is defined as the sigraph, where $\mathcal{S}^u_n$ is the unitary Cayley graph and for an edge $ab$ of $\mathcal{S}_n$, $$\sigma(ab) = \begin{cases} + & \text{if } a \in U_n \text{ or } b \in U_n,\\ - & \text{otherwise.} \end{cases}$$ In this paper, we have obtained a characterization of balanced unitary Cayley sigraphs. Further, we have established a characterization of canonically consistent unitary Cayley sigraphs $\mathcal{S}_n$, where $n$ has at most two distinct odd prime factors.
Convergence Rates for Generalized Descents
Authors: Pike John
Published: January 2020

d-descents are permutation statistics that generalize the notions of descents and inversions. It is known that the distribution of d-descents of permutations of length n satisfies a central limit theorem as n goes to infinity. We provide an explicit formula for the mean and variance of these statistics and obtain bounds on the rate of convergence using Stein's method.
Intersecting Families in a Subset of Boolean Lattices
Authors: Wang Jun , Zhang Huajun
Published: January 2020

Let $n, r$ and $\ell$ be distinct positive integers with $r < \ell\leq n/2$, and let $X_1$ and $X_2$ be two disjoint sets with the same size $n$. Define $$\mathcal{F}=\left\{A\in \binom{X}{r+\ell}: \mbox{$|A\cap X_1|=r$ or $\ell$}\right\},$$ where $X=X_1\cup X_2$. In this paper, we prove that if $\mathcal{S}$ is an intersecting family in $\mathcal{F}$, then $|\mathcal{S}|\leq \binom{n-1}{r-1}\binom{n}{\ell}+\binom{n-1}{\ell-1}\binom{n}{r}$, and equality holds if and only if $\mathcal{S}=\{A\in\mathcal{F}: a\in A\}$ for some $a\in X$.
On 3-Harness Weaving: Cataloging Designs Generated by Fundamental Blocks Having Distinct Rows and Columns
Authors: Rasmussen Shelley L.
Published: January 2020

A weaving drawdown is a rectangular grid of black and white squares with at least one black and one white square in each row and column. A pattern results from vertical and horizontal translations of the defining grid. Any such grid defines a tiling pattern. However, from a weaving point of view, some of these grids define actual fabrics while others correspond to collections of threads that fall apart. This article addresses that issue, along with a discussion of binary representations of fabric structures. The article also catalogs all weaving (or tiling) patterns defined by grids having three distinct columns and three to six distinct rows, and groups these patterns into design families based on weaving symmetries.
Automated Proofs for Some Stirling Number Identities
Authors: Kauers Manuel , Schneider Carsten
Published: January 2020

We present computer-generated proofs for some summation identities for ($q$-)Stirling and ($q$-)Eulerian numbers that were obtained by combining a recent summation algorithm for Stirling number identities with a recurrence solver for difference fields.
Osculating Paths and Oscillating Tableaux
Authors: Behrend Roger E.
Published: January 2020

The combinatorics of certain tuples of osculating lattice paths is studied, and a relationship with oscillating tableaux is obtained. The paths being considered have fixed start and end points on respectively the lower and right boundaries of a rectangle in the square lattice, each path can take only unit steps rightwards or upwards, and two different paths within a tuple are permitted to share lattice points, but not to cross or share lattice edges. Such path tuples correspond to configurations of the six-vertex model of statistical mechanics with appropriate boundary conditions, and they include cases which correspond to alternating sign matrices. Of primary interest here are path tuples with a fixed number $l$ of vacancies and osculations, where vacancies or osculations are points of the rectangle through which respectively no or two paths pass. It is shown that there exist natural bijections which map each such path tuple $P$ to a pair $(t,\eta)$, where $\eta$ is an oscillating tableau of length $l$ (i.e., a sequence of $l+1$ partitions, starting with the empty partition, in which the Young diagrams of successive partitions differ by a single square), and $t$ is a certain, compatible sequence of $l$ weakly increasing positive integers. Furthermore, each vacancy or osculation of $P$ corresponds to a partition in $\eta$ whose Young diagram is obtained from that of its predecessor by respectively the addition or deletion of a square. These bijections lead to enumeration formulae for tuples of osculating paths involving sums over oscillating tableaux.
Shifted Set Families, Degree Sequences, and Plethysm
Authors: Klivans C. , Reiner V.
Published: January 2020

We study, in three parts, degree sequences of $k$-families (or $k$-uniform hypergraphs) and shifted $k$-families. $\bullet$ The first part collects for the first time in one place, various implications such as $$ \scriptstyle \hbox{Threshold} \Rightarrow \hbox{Uniquely Realizable} \Rightarrow \hbox{Degree-Maximal} \Rightarrow \hbox{Shifted} $$ which are equivalent concepts for $2$-families (= simple graphs), but strict implications for $k$-families with $k \geq 3$. The implication that uniquely realizable implies degree-maximal seems to be new. $\bullet$ The second part recalls Merris and Roby's reformulation of the characterization due to Ruch and Gutman for graphical degree sequences and shifted $2$-families. It then introduces two generalizations which are characterizations of shifted $k$-families.$\bullet$ The third part recalls the connection between degree sequences of $k$-families of size $m$ and the plethysm of elementary symmetric functions $e_m[e_k]$. It then uses highest weight theory to explain how shifted $k$-families provide the "top part" of these plethysm expansions, along with offering a conjecture about a further relation.
Remarks on Missing Faces and Generalized Lower Bounds on Face Numbers
Authors: Nevo Eran
Published: January 2020

We consider simplicial polytopes, and more general simplicial complexes, without missing faces above a fixed dimension. Sharp analogues of McMullen's generalized lower bounds, and of Barnette's lower bounds, are conjectured for these families of complexes. Partial results on these conjectures are presented.
Spherical F-Tilings by Triangles and $r$-Sided Regular Polygons, $r \ge 5$
Authors: Avelino Catarina P. , Santos Altino F.
Published: January 2020

The study of dihedral f-tilings of the sphere $S^2$ by spherical triangles and equiangular spherical quadrangles (which includes the case of 4-sided regular polygons) was presented by Breda and Santos [Beiträge zur Algebra und Geometrie, 45 (2004), 447–461]. Also, in a subsequent paper, the study of dihedral f-tilings of $S^2$ whose prototiles are an equilateral triangle (a 3-sided regular polygon) and an isosceles triangle was described (we believe that the analysis considering scalene triangles as the prototiles will lead to a wide family of f-tilings). In this paper we extend these results, presenting the study of dihedral f-tilings by spherical triangles and $r$-sided regular polygons, for any $r \ge 5$. The combinatorial structure, including the symmetry group of each tiling, is given.
Promotion and Evacuation
Authors: Stanley Richard P.
Published: January 2020

Promotion and evacuation are bijections on the set of linear extensions of a finite poset first defined by Schützenberger. This paper surveys the basic properties of these two operations and discusses some generalizations. Linear extensions of a finite poset $P$ may be regarded as maximal chains in the lattice $J(P)$ of order ideals of $P$. The generalizations concern permutations of the maximal chains of a wider class of posets, or more generally bijective linear transformations on the vector space with basis consisting of the maximal chains of any poset. When the poset is the lattice of subspaces of ${\Bbb F}_q^n$, then the results can be stated in terms of the expansion of certain Hecke algebra products.
The 99th Fibonacci Identity
Authors: Benjamin Arthur T. , Eustis Alex K. , Plott Sean S.
Published: January 2020

We provide elementary combinatorial proofs of several Fibonacci and Lucas number identities left open in the book Proofs That Really Count [1], and generalize these to Gibonacci sequences $G_n$ that satisfy the Fibonacci recurrence, but with arbitrary real initial conditions. We offer several new identities as well. Among these, we prove $\sum_{k\geq 0}{n \choose k}G_{2k} = 5^n G_{2n}$ and $\sum_{k\geq 0}{n \choose k}G_{qk}(F_{q-2})^{n-k} = (F_q)^n G_{2n}$.
The Combinatorics of the Garsia-Haiman Modules for Hook Shapes
Authors: Adin Ron M. , Remmel Jeffrey B. , Roichman Yuval
Published: January 2020

Several bases of the Garsia-Haiman modules for hook shapes are given, as well as combinatorial decomposition rules for these modules. These bases and rules extend the classical ones for the coinvariant algebra of type $A$. We also give a decomposition of the Garsia-Haiman modules into descent representations.
Induced Trees in Triangle-Free Graphs
Authors: Matoušek Jiří , Šámal Robert
Published: January 2020

We prove that every connected triangle-free graph on $n$ vertices contains an induced tree on $\exp(c\sqrt{\log n}\,)$ vertices, where $c$ is a positive constant. The best known upper bound is $(2+o(1))\sqrt n$. This partially answers questions of Erdős, Saks, and Sós and of Pultr.
Codes from Cubic Curves and their Extensions
Authors: Alderson T. L. , Bruen A. A.
Published: January 2020

We study the linear codes and their extensions associated with sets of points in the plane corresponding to cubic curves. Instead of merely studying linear extensions, all possible extensions of the code are studied. In this way several new results are obtained and some existing results are strengthened. This type of analysis was carried out by Alderson, Bruen, and Silverman [J. Combin. Theory Ser. A, 114(6), 2007] for the case of MDS codes and by the present authors [Des. Codes Cryptogr., 47(1-3), 2008] for a broader range of codes. The methods cast some light on the question as to when a linear code can be extended to a nonlinear code. For example, for $p$ prime, it is shown that a linear $[n,3,n-3]_p$ code corresponding to a non-singular cubic curve comprising $n> p+4$ points admits only extensions that are equivalent to linear codes. The methods involve the theory of Rédei blocking sets and the use of the Bruen-Silverman model of linear codes.
A Refinement of the Formula for $k$-ary Trees and the Gould-Vandermonde's Convolution
Authors: Chen Ricky X. F.
Published: January 2020

In this paper, we present an involution on some kind of colored $k$-ary trees which provides a combinatorial proof of a combinatorial sum involving the generalized Catalan numbers $C_{k,\gamma}(n)={\gamma\over k n+\gamma}{k n+\gamma\choose n}$. From the combinatorial sum, we refine the formula for $k$-ary trees and obtain an implicit formula for the generating function of the generalized Catalan numbers which obviously implies a Vandermonde type convolution generalized by Gould. Furthermore, we also obtain a combinatorial sum involving a vector generalization of the Catalan numbers by an extension of our involution.
On the Failing Cases of the Johnson Bound for Error-Correcting Codes
Authors: Haas Wolfgang
Published: January 2020

A central problem in coding theory is to determine $A_q(n,2e+1)$, the maximal cardinality of a $q$-ary code of length $n$ correcting up to $e$ errors. When $e$ is fixed and $n$ is large, the best upper bound for $A(n,2e+1)$ (the binary case) is the well-known Johnson bound from 1962. This however simply reduces to the sphere-packing bound if a Steiner system $S(e+1,2e+1,n)$ exists. Despite the fact that no such system is known whenever $e\geq 5$, they possibly exist for a set of values for $n$ with positive density. Therefore in these cases no non-trivial numerical upper bounds for $A(n,2e+1)$ are known. In this paper the author demonstrates a technique for upper-bounding $A_q(n,2e+1)$, which closes this gap in coding theory. The author extends his earlier work on the system of linear inequalities satisfied by the number of elements of certain codes lying in $k$-dimensional subspaces of the Hamming Space. The method suffices to give the first proof, that the difference between the sphere-packing bound and $A_q(n,2e+1)$ approaches infinity with increasing $n$ whenever $q$ and $e\geq 2$ are fixed. A similar result holds for $K_q(n,R)$, the minimal cardinality of a $q$-ary code of length $n$ and covering radius $R$. Moreover the author presents a new bound for $A(n,3)$ giving for instance $A(19,3)\leq 26168$.
Completing Partial Latin Squares with Two Filled Rows and Two Filled Columns
Authors: Adams Peter , Bryant Darryn , Buchanan Melinda
Published: January 2020

It is shown that any partial Latin square of order at least six which consists of two filled rows and two filled columns can be completed.
Large Holes in Quasi-Random Graphs
Authors: Polcyn Joanna
Published: January 2020

Quasi-random graphs have the property that the densities of almost all pairs of large subsets of vertices are similar, and therefore we cannot expect too large empty or complete bipartite induced subgraphs in these graphs. In this paper we answer the question what is the largest possible size of such subgraphs. As an application, a degree condition that guarantees the connection by short paths in quasi-random pairs is stated.
Major Indices and Perfect Bases for Complex Reflection Groups
Authors: Shwartz Robert , Adin Ron M. , Roichman Yuval
Published: January 2020

It is shown that, under mild conditions, a complex reflection group $G(r,p,n)$ may be decomposed into a set-wise direct product of cyclic subgroups. This property is then used to extend the notion of major index and a corresponding Hilbert series identity to these and other closely related groups.
The Garnir Relations for Weyl Groups of Type $C_n$
Authors: Can Himmet
Published: January 2020

The Garnir relations play a very important role in giving combinatorial constructions of representations of the symmetric groups. For the Weyl groups of type $C_n$, having obtained the alternacy relation, we give an explicit combinatorial description of the Garnir relation associated with a $\Delta$-tableau in terms of root systems. We then use these relations to find a $K$-basis for the Specht modules of the Weyl groups of type $C_n$.
The Lollipop Graph is Determined by its Spectrum
Authors: Boulet R. , Jouve B.
Published: January 2020

An even (resp. odd) lollipop is the coalescence of a cycle of even (resp. odd) length and a path with pendant vertex as distinguished vertex. It is known that the odd lollipop is determined by its spectrum and the question is asked by W. Haemers, X. Liu and Y. Zhang for the even lollipop. A private communication of Behruz Tayfeh-Rezaie pointed out that an even lollipop with a cycle of length at least $6$ is determined by its spectrum but the result for lollipops with a cycle of length $4$ is still unknown. We give an unified proof for lollipops with a cycle of length not equal to $4$, generalize it for lollipops with a cycle of length $4$ and therefore answer the question. Our proof is essentially based on a method of counting closed walks.
On Euclidean Designs and Potential Energy
Authors: Miezaki Tsuyoshi , Tagami Makoto
Published: January 2020

We study Euclidean designs from the viewpoint of the potential energy. For a finite set in Euclidean space, we formulate a linear programming bound for the potential energy by applying harmonic analysis on a sphere. We also introduce the concept of strong Euclidean designs from the viewpoint of the linear programming bound, and we give a Fisher type inequality for strong Euclidean designs. A finite set on Euclidean space is called a Euclidean $a$-code if any distinct two points in the set are separated at least by $a$. As a corollary of the linear programming bound, we give a method to determine an upper bound on the cardinalities of Euclidean $a$-codes on concentric spheres of given radii. Similarly we also give a method to determine a lower bound on the cardinalities of Euclidean $t$-designs as an analogue of the linear programming bound.
Semidefinite Functions on Categories
Authors: Lovász László , Schrijver Alexander
Published: January 2020

Freedman, Lovász and Schrijver characterized graph parameters that can be represented as the (weighted) number of homomorphisms into a fixed graph. Several extensions of this result have been proved. We use the framework of categories to prove a general theorem of this kind. Similarly as previous resuts, the characterization uses certain infinite matrices, called connection matrices, which are required to be positive semidefinite.
Dihedral F-Tilings of the Sphere by Equilateral and Scalene Triangles - II
Authors: Breda A. M. d'Azevedo , Ribeiro Patrícia S. , Santos Altino F.
Published: January 2020

The study of dihedral f-tilings of the Euclidean sphere $S^2$ by triangles and $r$-sided regular polygons was initiated in 2004 where the case $r=4$ was considered [5]. In a subsequent paper [1], the study of all spherical f-tilings by triangles and $r$-sided regular polygons, for any $r\ge 5$, was described. Later on, in [3], the classification of all f-tilings of $S^2$ whose prototiles are an equilateral triangle and an isosceles triangle is obtained. The algebraic and combinatorial description of spherical f-tilings by equilateral triangles and scalene triangles of angles $\beta$, $\gamma$ and $\delta$ $(\beta>\gamma>\delta)$ whose edge adjacency is performed by the side opposite to $\beta$ was done in [4]. In this paper we extend these results considering the edge adjacency performed by the side opposite to $\delta$.
Counting Defective Parking Functions
Authors: Cameron Peter J , Johannsen Daniel , Prellberg Thomas , Schweitzer Pascal
Published: January 2020

Suppose that $m$ drivers each choose a preferred parking space in a linear car park with $n$ spaces. Each driver goes to the chosen space and parks there if it is free, and otherwise takes the first available space with a larger number (if any). If all drivers park successfully, the sequence of choices is called a parking function. In general, if $k$ drivers fail to park, we have a defective parking function of defect $k$. Let ${\rm cp}(n,m,k)$ be the number of such functions. In this paper, we establish a recurrence relation for the numbers ${\rm cp}(n,m,k)$, and express this as an equation for a three-variable generating function. We solve this equation using the kernel method, and extract the coefficients explicitly: it turns out that the cumulative totals are partial sums in Abel's binomial identity. Finally, we compute the asymptotics of ${\rm cp}(n,m,k)$. In particular, for the case $m=n$, if choices are made independently at random, the limiting distribution of the defect (the number of drivers who fail to park), scaled by the square root of $n$, is the Rayleigh distribution. On the other hand, in the case $m=\omega(n)$, the probability that all spaces are occupied tends asymptotically to one.
New Infinite Families of Almost-Planar Crossing-Critical Graphs
Authors: Hliněný Petr
Published: January 2020

We show that, for all choices of integers $k>2$ and $m$, there are simple $3$-connected $k$-crossing-critical graphs containing more than $m$ vertices of each even degree $\leq2k-2$. This construction answers one half of a question raised by Bokal, while the other half asking analogously about vertices of odd degrees at least $7$ in crossing-critical graphs remains open. Furthermore, our newly constructed graphs have several other interesting properties; for instance, they are almost planar and their average degree can attain any rational value in the interval $\big[3+{1\over5},6-{8\over k+1}\big)$.
Distribution of Segment Lengths in Genome Rearrangements
Authors: Tesler Glenn
Published: January 2020

The study of gene orders for constructing phylogenetic trees was introduced by Dobzhansky and Sturtevant in 1938. Different genomes may have homologous genes arranged in different orders. In the early 1990s, Sankoff and colleagues modelled this as ordinary (unsigned) permutations on a set of numbered genes $1,2,\ldots,n$, with biological events such as inversions modelled as operations on the permutations. Signed permutations may be used when the relative strands of the genes are known, and "circular permutations" may be used for circular genomes. We use combinatorial methods (generating functions, commutative and noncommutative formal power series, asymptotics, recursions, and enumeration formulas) to study the distributions of the number and lengths of conserved segments of genes between two or more unichromosomal genomes, including signed and unsigned genomes, and linear and circular genomes. This generalizes classical work on permutations from the 1940s–60s by Wolfowitz, Kaplansky, Riordan, Abramson, and Moser, who studied decompositions of permutations into strips of ascending or descending consecutive numbers. In our setting, their work corresponds to comparison of two unsigned genomes (known gene orders, unknown gene orientations). Maple software implementing our formulas is available at http://www.math.ucsd.edu/$\sim$gptesler/strips.
Cubical Convex Ear Decompositions
Authors: Woodroofe Russ
Published: January 2020

We consider the problem of constructing a convex ear decomposition for a poset. The usual technique, introduced by Nyman and Swartz, starts with a $CL$-labeling and uses this to shell the 'ears' of the decomposition. We axiomatize the necessary conditions for this technique as a "$CL$-ced" or "$EL$-ced". We find an $EL$-ced of the $d$-divisible partition lattice, and a closely related convex ear decomposition of the coset lattice of a relatively complemented finite group. Along the way, we construct new $EL$-labelings of both lattices. The convex ear decompositions so constructed are formed by face lattices of hypercubes. We then proceed to show that if two posets $P_{1}$ and $P_{2}$ have convex ear decompositions ($CL$-ceds), then their products $P_{1}\times P_{2}$, $P_{1}\check{\times} P_{2}$, and $P_{1}\hat{\times} P_{2}$ also have convex ear decompositions ($CL$-ceds). An interesting special case is: if $P_{1}$ and $P_{2}$ have polytopal order complexes, then so do their products.
The Loebl–Komlós–Sós Conjecture for Trees of Diameter $5$ and for Certain Caterpillars
Authors: Piguet Diana , Stein Maya Jakobine
Published: January 2020

Loebl, Komlós, and Sós conjectured that if at least half the vertices of a graph $G$ have degree at least some $k\in \Bbb N$, then every tree with at most $k$ edges is a subgraph of $G$. We prove the conjecture for all trees of diameter at most $5$ and for a class of caterpillars. Our result implies a bound on the Ramsey number $r(T,T')$ of trees $T,T'$ from the above classes.
Distinct Distances in Graph Drawings
Authors: Carmi Paz , Dujmović Vida , Morin Pat , Wood David R.
Published: January 2020

The distance-number of a graph $G$ is the minimum number of distinct edge-lengths over all straight-line drawings of $G$ in the plane. This definition generalises many well-known concepts in combinatorial geometry. We consider the distance-number of trees, graphs with no $K^-_4$-minor, complete bipartite graphs, complete graphs, and cartesian products. Our main results concern the distance-number of graphs with bounded degree. We prove that $n$-vertex graphs with bounded maximum degree and bounded treewidth have distance-number in ${\cal O}(\log n)$. To conclude such a logarithmic upper bound, both the degree and the treewidth need to be bounded. In particular, we construct graphs with treewidth $2$ and polynomial distance-number. Similarly, we prove that there exist graphs with maximum degree $5$ and arbitrarily large distance-number. Moreover, as $\Delta$ increases the existential lower bound on the distance-number of $\Delta$-regular graphs tends to $\Omega(n^{0.864138})$.