bluuebunny/crossref_metadata_2025 huggingface dataset:
Permutations of Type $B$ with Fixed Number of Descents and Minus Signs
Authors: Kril Katarzyna , Młotkowski Wojciech
Published: January 2020

We study three dimensional array of numbers $B(n,k,j)$, $0\le j,k\le n$, where $B(n,k,j)$ is the number of type $B$ permutations of order $n$ with $k$ descents and $j$ minus signs. We prove in particular, that $b(n,k,j):=B(n,k,j)/\binom{n}{j}$ is an integer and provide two combinatorial interpretations for these numbers.
A Splitter Theorem for 3-Connected 2-Polymatroids
Authors: Oxley James , Semple Charles , Whittle Geoff
Published: January 2020

Seymour's Splitter Theorem is a basic inductive tool for dealing with $3$-connected matroids. This paper proves a generalization of that theorem for the class of $2$-polymatroids. Such structures include matroids, and they model  both sets of points and lines in a projective space and sets of edges in a graph.  A series compression in such a structure is an analogue of contracting an edge of a graph that is in a series pair. A $2$-polymatroid $N$ is an s-minor of a $2$-polymatroid $M$ if $N$ can be obtained from $M$ by a sequence of contractions, series compressions, and  dual-contractions, where the last are modified deletions. The main result proves that if $M$ and $N$ are $3$-connected $2$-polymatroids such that $N$ is an s-minor of $M$, then $M$ has a $3$-connected  s-minor  $M'$ that has an s-minor isomorphic to $N$ and has $|E(M)| - 1$ elements unless $M$ is a whirl or the cycle matroid of a wheel. In the exceptional case, such an $M'$ can be found with $|E(M)| - 2$ elements.
Proof of Chapoton's Conjecture on Newton Polygons of $q$-Ehrhart Polynomials
Authors: Kim Jang Soo , Song U-Keun
Published: January 2020

Recently, Chapoton found a $q$-analog of Ehrhart polynomials, which are polynomials in $x$ whose coefficients are rational functions in $q$. Chapoton conjectured the shape of the Newton polygon of the numerator of the $q$-Ehrhart polynomial of an order polytope. In this paper, we prove Chapoton's conjecture.
Partial Characterization of Graphs Having a Single Large Laplacian Eigenvalue
Authors: Allem L. Emilio , Cafure Antonio , Dratman Ezequiel , Grippo Luciano N. , Safe Martín D. , Trevisan Vilmar
Published: January 2020

The parameter $\sigma(G)$ of a graph $G$ stands for the number of Laplacian eigenvalues greater than or equal to the average degree of $G$. In this work, we address the problem of characterizing those graphs $G$ having $\sigma(G)=1$. Our conjecture is that these graphs are stars plus a (possible empty) set of isolated vertices. We establish a link between $\sigma(G)$ and the number of anticomponents of $G$. As a by-product, we present some results which support the conjecture, by restricting our analysis to cographs, forests, and split graphs.
A Refined Count of Coxeter Element Reflection Factorizations
Authors: DelMas Elise , Hameister Thomas , Reiner Victor
Published: January 2020

For well-generated complex reflection groups, Chapuy and Stump gave a simple product for a generating function counting reflection factorizations of a Coxeter element by their length. This is refined here to record the numberof reflections used from each orbit of hyperplanes. The proof is case-by-case via the classification of well-generated groups. It implies a new expression for the Coxeter number, expressed via data coming from a hyperplane orbit; a case-free proof of this due to J. Michel is included.
Equivalence of Edge Bicolored Graphs on Surfaces
Authors: Dasbach Oliver T. , Russell Heather M.
Published: January 2020

Consider the collection of edge bicolorings of a graph that are cellularly embedded on an orientable surface. In this work, we count the number of equivalence classes of such colorings under two relations: reversing colors around a face and reversing colors around a vertex. In the case of the plane, this is well studied, but for other surfaces, the computation is more subtle. While this question can be stated purely graph theoretically, it has interesting applications in knot theory.
Connected Chord Diagrams and Bridgeless Maps
Authors: Courtiel Julien , Yeats Karen , Zeilberger Noam
Published: January 2020

We present a surprisingly new connection between two well-studied combinatorial classes: rooted connected chord diagrams on one hand, and rooted bridgeless combinatorial maps on the other hand. We describe a bijection between these two classes, which naturally extends to indecomposable diagrams and general rooted maps. As an application, this bijection provides a simplifying framework for some technical quantum field theory work realized by some of the authors. Most notably, an important but technical parameter naturally translates to vertices at the level of maps. We also give a combinatorial proof to a formula which previously resulted from a technical recurrence, and with similar ideas we prove a conjecture of Hihn. Independently, we revisit an equation due to Arquès and Béraud for the generating function counting rooted maps with respect to edges and vertices, giving a new bijective interpretation of this equation directly on indecomposable chord diagrams, which moreover can be specialized to connected diagrams and refined to incorporate the number of crossings. Finally, we explain how these results have a simple application to the combinatorics of lambda calculus, verifying the conjecture that a certain natural family of lambda terms is equinumerous with bridgeless maps.
Toward the Schur Expansion of Macdonald Polynomials
Authors: Assaf Sami
Published: January 2020

We give an explicit combinatorial formula for the Schur expansion of Macdonald polynomials indexed by partitions with second part at most two. This gives a uniform formula for both hook and two column partitions. The proof comes as a corollary to the result that generalized dual equivalence classes of permutations are in explicit bijection with unions of standard dual equivalence classes of permutations for certain cases, establishing an earlier conjecture of the author, and suggesting that this result might be generalized to arbitrary partitions.
The cd-Indices of Intervals in the Uncrossing Partial Order on Matchings
Authors: Kim Younghwan
Published: January 2020

We study flag enumeration in intervals in the uncrossing partial order on matchings. We produce a recursion for the cd-indices of intervals in the uncrossing poset $P_n$. We explicitly describe the matchings by constructing an order-reversing bijection. We obtain a recursion for the ab-indices of intervals in the poset $\hat{P}_n$, the poset $P_n$ with a unique minimum $\hat0$ adjoined.
On Two-Sided Gamma-Positivity for Simple Permutations
Authors: Adin Ron M. , Bagno Eli , Eisenberg Estrella , Reches Shulamit , Sigron Moriah
Published: January 2020

Gessel conjectured that the two-sided Eulerian polynomial, recording the common distribution of the descent number of a permutation and that of its inverse, has non-negative integer coefficients when expanded in terms of the gamma basis. This conjecture has been proved recently by Lin.We conjecture that an analogous statement holds for simple permutations, and use the substitution decomposition tree of a permutation (by repeated inflation) to show that this would imply the Gessel-Lin result. We provide supporting evidence for this stronger conjecture.
On Graph-Theoretical Invariants of Combinatorial Manifolds
Authors: Cavicchioli Alberto , Spaggiari Fulvia
Published: January 2020

The goal of this paper is to give some theorems which relate to the problem of classifying combinatorial (resp. smooth)  closed manifolds up to piecewise-linear (PL) homeomorphism. For this, we use the combinatorial approach to the topology of PL manifolds by means of a special kind of edge-colored graphs, called crystallizations. Within this representation theory, Bracho and Montejano introduced in 1987 a nonnegative numerical invariant, called the reduced complexity, for any closed $n$-dimensional PL manifold.  Here we consider this invariant, and extend in this context the concept of average order first introduced by Luo and Stong in 1993, and successively investigated by Tamura in 1996 and 1998. Then  we obtain some  classification  results for  closed connected smooth low-dimensional manifolds according to  reduced complexity and average order. Finally, we answer to a question posed by Trout in 2013.
Quasirandomness in Hypergraphs
Authors: Aigner-Horev Elad , Conlon David , Hàn Hiệp , Person Yury , Schacht Mathias
Published: January 2020

An $n$-vertex graph $G$ of edge density $p$ is considered to be quasirandom if it shares several important properties with the random graph $G(n,p)$. A well-known theorem of Chung, Graham and Wilson states that many such `typical' properties are asymptotically equivalent and, thus, a graph $G$ possessing one such property automatically satisfies the others.In recent years, work in this area has focused on uncovering more quasirandom graph properties and on extending the known results to other discrete structures. In the context of hypergraphs, however, one may consider several different notions of quasirandomness. A complete description of these notions has been provided recently by Towsner, who proved several central equivalences using an analytic framework. We give short and purely combinatorial proofs of the main equivalences in Towsner's result.
Improved Bounds on the Multicolor Ramsey Numbers of Paths and Even Cycles
Authors: Knierim Charlotte , Su Pascal
Published: January 2020

We study the multicolor Ramsey numbers for paths and even cycles, $R_k(P_n)$ and $R_k(C_n)$, which are the smallest integers $N$ such that every coloring of the complete graph $K_N$ has a monochromatic copy of $P_n$ or $C_n$ respectively. For a long time, $R_k(P_n)$ has only been known to lie between $(k-1+o(1))n$ and $(k + o(1))n$. A recent breakthrough by Sárközy and later improvement by Davies, Jenssen and Roberts give an upper bound of $(k - \frac{1}{4} + o(1))n$. We improve the upper bound to $(k - \frac{1}{2}+ o(1))n$. Our approach uses structural insights in connected graphs without a large matching.
Phase Measurement of Quantum Walks: Application to Structure Theorem of the Positive Support of the Grover Walk
Authors: Konno Norio , Sato Iwao , Segawa Etsuo
Published: January 2020

We obtain a structure theorem of the positive support of the $n$-th power of the Grover walk on $k$-regular graph whose girth is greater than $2(n-1)$. This structure theorem is provided by the parity of the amplitude of another quantum walk on the line which depends only on $k$. The phase pattern of this quantum walk has a curious regularity. We also exactly show how the spectrum of the $n$-th power of the Grover walk is obtained by lifting up that of the adjacency matrix to the complex plain.
Vertex Degree Sums for Perfect Matchings in 3-Uniform Hypergraphs
Authors: Zhang Yi , Zhao Yi , Lu Mei
Published: January 2020

We determine the minimum degree sum of two adjacent vertices that ensures a perfect matching in a 3-uniform hypergraph without an isolated vertex. Suppose that $H$ is a 3-uniform hypergraph whose order $n$ is sufficiently large and divisible by $3$. If $H$ contains no isolated vertex and $\deg(u)+\deg(v) > \frac{2}{3}n^2-\frac{8}{3}n+2$ for any two vertices $u$ and $v$ that are contained in some edge of $H$, then $H$ contains a perfect matching. This bound is tight and the (unique) extremal hyergraph is a different space barrier from the one for the corresponding Dirac problem.
$\lambda$-Euler's Difference Table for Colored Permutations
Authors: Han Bin
Published: January 2020

Motivated by the $\lambda$-Euler's difference table of  Eriksen et al. and colored Euler's difference table of Faliharimalala and Zeng,  we study the $\lambda$-analogue of colored Euler's difference table and generalize their results. We generalize the number of permutations with $k$-excedances studied by Liese and Remmel in colored permutations. We also extend Wang et al.'s recent results about $r$-derangements by relating with the sequences arising from the difference table.
Monops, Monoids and Operads: The Combinatorics of Sheffer Polynomials
Authors: Méndez Miguel A. , Sánchez Lamoneda Rafael
Published: January 2020

We introduce a new algebraic construction, monop, that combines monoids (with respect to the product of species), and operads (monoids with respect to the substitution of species) in the same algebraic structure. By the use of properties of cancellative set-monops we construct a family of partially ordered sets whose prototypical examples are the Dowling lattices. They generalize the enriched partition posets associated to a cancellative operad, and the subset posets associated to a cancellative monoid. Their Whitney numbers of the first and second kind are the connecting coefficients of two umbral inverse Sheffer sequences with the family of powers $\{x^n\}_{n=0}^{\infty}$. Equivalently, the entries of a Riordan matrix and its inverse. This aticle is the first part of a program in progress to develop a theory of Koszul duality for monops.
On Generalized Choice and Coloring Numbers
Authors: Dvořák Zdenēk , Pekárek Jakub , Sereni Jean-Sébastien
Published: January 2020

A well-known result of Alon shows that the coloring number of a graph is bounded by a function of its choosability.  We explore this relationship in a more general setting with relaxed assumptions on color classes, encoded by a graph parameter.
Subdivision Yields Alexander Duality on Independence Complexes
Authors: Csorba Péter
Published: January 2020

We study how the homotopy type of the independence complex of a graph changes if we subdivide edges. We show that the independence complex becomes the Alexander dual if we place one new vertex on each edge of a graph. If we place two new vertices on each edge then the independence complex is the wedge of two spheres. Placing three new vertices on an edge yields the suspension of the independence complex.
Homomesy in Products of Three Chains and Multidimensional Recombination
Authors: Vorland Corey
Published: January 2020

J. Propp and T. Roby isolated a phenomenon in which a statistic on a set has the same average value over any orbit as its global average, naming it homomesy. They proved that the cardinality statistic on order ideals of the product of two chains poset under rowmotion exhibits homomesy. In this paper, we prove an analogous result in the case of the product of three chains where one chain has two elements. In order to prove this result, we generalize from two to n dimensions the recombination technique that D. Einstein and Propp developed to study homomesy. We see that our main homomesy result does not fully generalize to an arbitrary product of three chains, nor to larger products of chains; however, we have a partial generalization to an arbitrary product of three chains. Additional corollaries include refined homomesy results in the product of three chains and a new result on increasing tableaux. We conclude with a generalization of recombination to any ranked poset and a homomesy result for the Type B minuscule poset cross a two element chain.
Non-Fringe Subtrees in Conditioned Galton—Watson Trees
Authors: Cai Xing Shi , Janson Svante
Published: January 2020

We study $S(\mathcal{T}_{n})$, the number of subtrees in a conditioned Galton—Watson tree of size $n$. With two very different methods, we show that $\log(S(\mathcal{T}_{n}))$ has a Central Limit Law and that the moments of $S(\mathcal{T}_{n})$ are of exponential scale.
Limiting Probabilities for Vertices of a Given Rank in 1-2 Trees
Authors: Bóna Miklós , Mező István
Published: January 2020

We consider two varieties of labeled rooted trees, namely non-plane and plane 1-2 trees. In these tree varieties, we study the probability that a vertex chosen from all vertices of all trees of a given size uniformly at random has a given rank. We prove that this probability converges to a limit as the tree size goes to infinity.
Determining Lower Bounds for Packing Densities of Non-layered Patterns Using Weighted Templates
Authors: Presutti Cathleen Battiste
Published: January 2020

The packing density of a permutation pattern $\pi$ is the limiting value, ${n}$ $\rightarrow$ $\infty$, of the maximum proportion of subsequences of $\sigma$ $\in$ ${S_{n}}$ that are order-isomorphic to $\pi$. We generalize methods for obtaining lower bounds for the packing density of any pattern and demonstrate the methods' usefulness when patterns are non-layered.
Using Symbolic Computation to Prove Nonexistence of Distance-Regular Graphs
Authors: Vidali Janoš
Published: January 2020

A package for the Sage computer algebra system is developed for checking feasibility of a given intersection array for a distance-regular graph. We use this tool to show that there is no distance-regular graph with intersection array$$\{(2r+1)(4r+1)(4t-1), 8r(4rt-r+2t), (r+t)(4r+1); 1, (r+t)(4r+1), 4r(2r+1)(4t-1)\}  (r, t \geq 1),$$$\{135,\! 128,\! 16; 1,\! 16,\! 120\}$, $\{234,\! 165,\! 12; 1,\! 30,\! 198\}$ or $\{55,\! 54,\! 50,\! 35,\! 10; 1,\! 5,\! 20,\! 45,\! 55\}$. In all cases, the proofs rely on equality in the Krein condition, from which triple intersection numbers are determined. Further combinatorial arguments are then used to derive nonexistence.
Random Numerical Semigroups and a Simplicial Complex of Irreducible Semigroups
Authors: De Loera Jesus , O'Neill Christopher , Wilburne Dane
Published: January 2020

We examine properties of random numerical semigroups  under a probabilistic model inspired by the Erdos-Renyi model for random graphs. We provide a threshold function for cofiniteness, and bound the expected embedding dimension, genus, and Frobenius number of random semigroups.  Our results follow, surprisingly, from the construction of a very natural shellable simplicial complex whose facets are in bijection with irreducible numerical semigroups of a fixed Frobenius number and whose $h$-vector determines the probability that a particular element lies in the semigroup.
Minimal Multiple Blocking Sets
Authors: Bishnoi Anurag , Mattheus Sam , Schillewaert Jeroen
Published: January 2020

We prove that a minimal $t$-fold blocking set in a finite projective plane of order $n$ has cardinality at most \[\frac{1}{2} n\sqrt{4tn - (3t + 1)(t - 1)} + \frac{1}{2} (t - 1)n + t.\] This is the first general upper bound on the size of minimal $t$-fold blocking sets in finite projective planes and it generalizes the classical result of Bruen and Thas on minimal blocking sets. From the proof it directly follows that if equality occurs in this bound then every line intersects the blocking set $S$ in either $t$ points or $\frac{1}{2}(\sqrt{4tn  - (3t + 1)(t - 1)}  + t - 1) + 1$ points. We use this to show that for $n$ a prime power, equality can occur in our bound in exactly one of the following three cases: (a) $t = 1$, $n$ is a square and $S$ is a unital; (b) $t = n - \sqrt{n}$, $n$ is a square and $S$ is the complement of a Baer subplane; (c) $t = n$ and $S$ is equal to the set of all points except one. For a square prime power $q$ and $t \leq \sqrt{q} + 1$, we give a construction of a minimal $t$-fold blocking set $S$ in $\mathrm{PG}(2,q)$ with $|S| = q\sqrt{q} + 1 + (t - 1)(q - \sqrt{q} + 1)$. Furthermore, we obtain an upper bound on the size of minimal blocking sets in symmetric $2$-designs and use it to give new proofs of other known results regarding tangency sets in higher dimensional finite projective spaces. We also discuss further generalizations of our bound. In our proofs we use an incidence bound on combinatorial designs which follows from applying the expander mixing lemma to the incidence graph of these designs.
On the Rainbow Turán number of paths
Authors: Ergemlidze Beka , Győri Ervin , Methuku Abhishek
Published: January 2020

Let $F$ be a fixed graph. The rainbow Turán number of $F$ is defined as the maximum number of edges in a graph on $n$ vertices that has a proper edge-coloring with no rainbow copy of $F$ (i.e., a copy of $F$ all of whose edges have different colours). The systematic study of such problems was initiated by Keevash, Mubayi, Sudakov and Verstraëte.

 In this paper, we show that the rainbow Turán number of a path with $k+1$ edges is less than $\left(9k/7+2\right) n$, improving an earlier estimate of Johnston,  Palmer and Sarkar.
Structure of Cubic Lehman Matrices
Authors: Mayhew Dillon , Pivotto Irene , Royle Gordon
Published: January 2020

A pair $(A,B)$ of square $(0,1)$-matrices is called a Lehman pair if $AB^T=J+kI$ for some integer $k\in\{-1,1,2,3,\ldots\}$. In this case $A$ and $B$ are called Lehman matrices. This terminology arises because Lehman showed that the rows with the fewest ones in any non-degenerate minimally nonideal (mni) matrix $M$ form a square Lehman submatrix of $M$. Lehman matrices with $k=-1$ are essentially equivalent to partitionable graphs (also known as $(\alpha,\omega)$-graphs), so have been heavily studied as part of attempts to directly classify minimal imperfect graphs. In this paper, we view a Lehman matrix as the bipartite adjacency matrix of a regular bipartite graph, focusing in particular on the case where the graph is cubic. From this perspective, we identify two constructions that generate cubic Lehman graphs from smaller Lehman graphs. The most prolific of these constructions involves repeatedly replacing suitable pairs of edges with a particular $6$-vertex subgraph that we call a $3$-rung ladder segment. Two decades ago, Lütolf & Margot initiated a computational study of mni matrices and constructed a catalogue containing (among other things) a listing of all cubic Lehman matrices with $k =1$ of order up to $17 \times 17$.  We verify their catalogue (which has just one omission), and extend the computational results to $20 \times 20$ matrices. Of the $908$ cubic Lehman matrices (with $k=1$) of order up to $20 \times 20$, only two do not arise from our $3$-rung ladder construction. However these exceptions can be derived from our second construction, and so our two constructions cover all known cubic Lehman matrices with $k=1$.
Spectral and Combinatorial Properties of Some Algebraically Defined Graphs
Authors: Cioabă Sebastian M. , Lazebnik Felix , Sun Shuying
Published: January 2020

Let $k\ge 3$ be an integer, $q$ be a prime power, and $\mathbb{F}_q$ denote the field of $q$ elements. Let $f_i, g_i\in\mathbb{F}_q[X]$, $3\le i\le k$, such that $g_i(-X) = -\, g_i(X)$. We define a graph $S(k,q) = S(k,q;f_3,g_3,\cdots,f_k,g_k)$ as a graph with the vertex set $\mathbb{F}_q^k$ and edges defined as follows: vertices $a = (a_1,a_2,\ldots,a_k)$ and $b = (b_1,b_2,\ldots,b_k)$ are adjacent if $a_1\ne b_1$ and the following $k-2$ relations on their components hold:$$b_i-a_i = g_i(b_1-a_1)f_i\Bigl(\frac{b_2-a_2}{b_1-a_1}\Bigr)\;,\quad 3\le i\le k.$$ We show that the graphs $S(k,q)$ generalize several recently studied examples of regular expanders and can provide many new such examples.
Note on the Multicolour Size-Ramsey Number for Paths,
Authors: Dudek Andrzej , Prałat Paweł
Published: January 2020

The size-Ramsey number $\hat{R}(F,r)$ of a graph $F$ is the smallest integer $m$ such that there exists a graph $G$ on $m$ edges with the property that any colouring of the edges of $G$ with $r$ colours yields a monochromatic copy of $F$. In this short note, we give an alternative proof of the recent result of Krivelevich that $\hat{R}(P_n,r) = O((\log r)r^2 n)$. This upper bound is nearly optimal, since it is also known that $\hat{R}(P_n,r) = \Omega(r^2 n)$.
Combining Extensions of the Hales-Jewett Theorem with Ramsey Theory in Other Structures
Authors: Hindman Neil , Strauss Dona , Zamboni Luca Q.
Published: January 2020

The Hales-Jewett Theorem states that given any finite nonempty set ${\mathbb A}$ and any finite coloring of the free semigroup $S$ over the alphabet ${\mathbb A}$ there is a variable word over ${\mathbb A}$ all of whose instances are the same color. This theorem has some extensions involving several distinct variables occurring in the variable word. We show that, when combined with a sufficiently well behaved homomorphism,  the relevant variable word simultaneously satisfies a Ramsey-Theoretic conclusion in the other structure. As an example we show that if $\tau$ is the homomorphism from the set of variable words into the natural numbers which associates to each variable word $w$ the number of occurrences of the variable in $w$, then given any finite coloring of $S$ and any infinite sequence of natural numbers, there is a variable word $w$ whose instances are monochromatic and $\tau(w)$ is a sum of distinct members of the given sequence.Our methods rely on the algebraic structure of the Stone-Čech compactification of $S$ and the other semigroups that we consider.  We show for example that if $\tau$ is as in the paragraph above, there is a compact subsemigroup $P$ of $\beta{\mathbb N}$ which contains all of the idempotents of $\beta{\mathbb N}$ such that, given any $p\in P$, any $A\in p$, and any finite coloring of $S$, there is a variable word $w$ whose instances are monochromatic and $\tau(w)\in A$.We end with a new short algebraic proof of an infinitary extension of the Graham-Rothschild Parameter Sets Theorem.
Decomposing Graphs into a Spanning Tree, an Even Graph, and a Star Forest
Authors: Lyngsie Kasper Szabo , Merker Martin
Published: January 2020

We prove that every connected graph can be edge-decomposed into a spanning tree, an even graph, and a star forest.
Circular Repetition Thresholds on Some Small Alphabets: Last Cases of Gorbunova's Conjecture
Authors: Currie James D. , Mol Lucas , Rampersad Narad
Published: January 2020

A word is called $\beta$-free if it has no factors of exponent greater than or equal to $\beta$. The repetition threshold $\mbox{RT}(k)$ is the infimum of the set of all $\beta$ such that there are arbitrarily long $k$-ary $\beta$-free words (or equivalently, there are $k$-ary $\beta$-free words of every sufficiently large length, or even every length). These three equivalent definitions of the repetition threshold give rise to three natural definitions of a repetition threshold for circular words. The infimum of the set of all $\beta$ such that

there are arbitrarily long $k$-ary $\beta$-free circular words is called the weak circular repetition threshold, denoted $\mbox{CRT}_\mbox{W}(k)$;
there are $k$-ary $\beta$-free circular words of every sufficiently large length is called the intermediate circular repetition threshold, denoted $\mbox{CRT}_\mbox{I}(k)$;
there are $k$-ary $\beta$-free circular words of every length is called the strong circular repetition threshold, denoted $\mbox{CRT}_\mbox{S}(k)$.

We prove that $\mbox{CRT}_\mbox{S}(4)=\tfrac{3}{2}$ and $\mbox{CRT}_\mbox{S}(5)=\tfrac{4}{3}$, confirming a conjecture of Gorbunova and providing the last unknown values of the strong circular repetition threshold. We also prove that $\mbox{CRT}_\mbox{S}(3)=\mbox{CRT}_\mbox{W}(3)=\mbox{RT}(3)=\tfrac{7}{4}$.
On Walks Avoiding a Quadrant
Authors: Raschel Kilian , Trotignon Amélie
Published: January 2020

Two-dimensional (random) walks in cones are very natural both in combinatorics and probability theory: they are interesting for themselves and also because they are strongly related to other discrete structures. While walks restricted to the first quadrant have been studied a lot, the case of planar, non-convex cones – equivalent to the three-quarter plane after a linear transform – has been approached only recently. In this article we develop an analytic approach to the case of walks in three quadrants. The advantage of this method is to provide uniform treatment in the study of models corresponding to different step sets. After splitting the three quadrants in two symmetric convex cones, the method is composed of three main steps: write a system of functional equations satisfied by the counting generating function, which may be simplified into one single equation under symmetry conditions; transform the functional equation into a boundary value problem; and finally solve this problem, using a concept of anti-Tutte's invariant. The result is a contour-integral expression for the generating function. Such systems of functional equations also appear in queueing theory with the famous Join-the-Shortest-Queue model, which is still an open problem in the non-symmetric case.
$(k,\lambda)$-Anti-Powers and Other Patterns in Words
Authors: Burcroff Amanda
Published: January 2020

Given a word, we are interested in the structure of its contiguous subwords split into $k$ blocks of equal length, especially in the homogeneous and anti-homogeneous cases.  We introduce the notion of $(\mu_1,\dots,\mu_k)$-block-patterns, words of the form $w = w_1\cdots w_k$ where, when $\{w_1,\dots,w_k\}$ is partitioned via equality, there are $\mu_s$ sets of size $s$ for each $s \in \{1,\dots,k\}$.  This is a generalization of the well-studied $k$-powers and the $k$-anti-powers  recently introduced by Fici, Restivo, Silva, and Zamboni, as well as a refinement of the  $(k,\lambda)$-anti-powers introduced by Defant. We generalize the anti-Ramsey-type results of Fici et al. to $(\mu_1,\dots,\mu_k)$-block-patterns and improve their bounds on $N_\alpha(k,k)$, the minimum length such that every word of length $N_\alpha(k,k)$ on an alphabet of size $\alpha$ contains a $k$-power or $k$-anti-power.  We also generalize their results on infinite words avoiding $k$-anti-powers to the case of $(k,\lambda)$-anti-powers.  We provide a few results on the relation between $\alpha$ and  $N_\alpha(k,k)$ and find the expected number of $(\mu_1,\dots,\mu_k)$-block-patterns in a word of length $n$.
Axioms for Shifted Tableau Crystals
Authors: Gillespie Maria , Levinson Jake
Published: January 2020

We give local axioms that uniquely characterize the crystal-like structure on shifted tableaux developed by the authors and Purbhoo. These axioms closely resemble those developed by Stembridge for type A tableau crystals. This axiomatic characterization gives rise to a new method for proving and understanding Schur $Q$-positive expansions in symmetric function theory, just as the Stembridge axiomatic structure provides for ordinary Schur positivity.
Derangement Polynomials and Excedances of Type $B$
Authors: Chen William Y. C. , Tang Robert L. , Zhao Alina F. Y.
Published: January 2020

Based on the notion of excedances of type $B$ introduced by Brenti, we give a type $B$ analogue of the derangement polynomials. The connection between the derangement polynomials and Eulerian polynomials naturally extends to the type $B$ case. Using this relation, we derive some basic properties of the derangement polynomials of type $B$, including the generating function formula, the Sturm sequence property, and the asymptotic normal distribution. We also show that the derangement polynomials are almost symmetric in the sense that the coefficients possess the spiral property.
Generalized Coinvariant Algebras for $G(r,1,n)$ in the Stanley-Reisner setting
Authors: Kroes Daniël
Published: January 2020

Let $r$ and $n$ be positive integers, let $G_n$ be the complex reflection group of $n \times n$ monomial matrices whose entries are $r^{\textrm{th}}$ roots of unity and let $0 \leq k \leq n$ be an integer. Recently, Haglund, Rhoades and Shimozono ($r=1$) and Chan and Rhoades ($r>1$) introduced quotients $R_{n,k}$ (for $r>1$) and $S_{n,k}$ (for $r \geq 1$) of the polynomial ring $\mathbb{C}[x_1,\ldots,x_n]$ in $n$ variables, which for $k=n$ reduce to the classical coinvariant algebra attached to $G_n$. When $n=k$ and $r=1$, Garsia and Stanton exhibited a quotient of $\mathbb{C}[\mathbf{y}_S]$ isomorphic to the coinvariant algebra, where $\mathbb{C}[\mathbf{y}_S]$ is the polynomial ring in $2^n-1$ variables whose variables are indexed by nonempty subsets $S \subseteq [n]$. In this paper, we will define analogous quotients that are isomorphic to $R_{n,k}$ and $S_{n,k}$.
Rainbow Matchings in Properly-Colored Hypergraphs
Authors: Huang Hao , Li Tong , Wang Guanghui
Published: January 2020

A hypergraph $H$ is properly colored if for every vertex $v\in V(H)$, all the edges incident to $v$ have distinct colors. In this paper, we show that if $H_{1}, \ldots, H_{s}$ are properly-colored $k$-uniform hypergraphs on $n$ vertices, where $n\geq3k^{2}s$, and  $e(H_{i})>{{n}\choose {k}}-{{n-s+1}\choose {k}}$, then there exists a rainbow matching of size $s$, containing one edge from each $H_i$. This generalizes some previous results on the Erdős Matching Conjecture.
2-Colorability of r-Uniform Hypergraphs
Authors: Krul Michael , Thoma Luboš
Published: January 2020

A hypergraph is properly 2-colorable if each vertex can be colored by one of two colors and no edge is completely colored by a single color. We present a complete algebraic characterization of the 2-colorability of r-uniform hypergraphs. This generalizes a well known algebraic characterization of k-colorability of graphs due to Alon, Tarsi, Lovasz, de Loera, and Hillar. We also introduce a method for distinguishing proper 2-colorings called coloring schemes, and provide a decomposition of all proper 2-colorings into these schemes. As an application, we present a new example of a 4-uniform non-2-colorable hypergraph on 11 vertices and 24 edges which is not isomorphic to a well-known construction by Seymour (1974) of a minimal non-2-colorable 4-uniform hypergraph. Additionally, we provide a heuristically constructed hypergraph which admits only specific coloring schemes. Further, we give an algebraic characterization of the coloring scheme known as a conflict-free coloring.
Extremal $H$-Free Planar Graphs
Authors: Lan Yongxin , Shi Yongtang , Song Zi-Xia
Published: January 2020

Given a graph $H$, a graph is $H$-free if it does not contain $H$ as a subgraph. We continue to study the topic of "extremal" planar graphs initiated by Dowden [J. Graph Theory  83 (2016) 213–230], that is, how many edges can an $H$-free planar graph on $n$ vertices have? We define $ex_{_\mathcal{P}}(n,H)$ to be the maximum number of edges in an $H$-free planar graph on $n $ vertices. We first obtain several sufficient conditions on $H$ which yield  $ex_{_\mathcal{P}}(n,H)=3n-6$ for all $n\ge |V(H)|$. We discover that the chromatic number of $H$ does not play a role, as in the celebrated Erdős-Stone Theorem.  We then completely determine $ex_{_\mathcal{P}}(n,H)$ when $H$ is a wheel or a star. Finally, we examine the case when $H$ is a $(t, r)$-fan, that is, $H$ is isomorphic to  $K_1+tK_{r-1}$, where $t\ge2$ and $r\ge 3$ are integers. However, determining $ex_{_\mathcal{P}}(n,H)$, when $H$ is a planar subcubic graph, remains wide open.
VC Dimension and a Union Theorem for Set Systems
Authors: Cambie Stijn , Girão António , Kang Ross J.
Published: January 2020

Fix positive integers $k$ and $d$. We show that, as $n\to\infty$, any set system $\mathcal{A} \subset 2^{[n]}$ for which the VC dimension of $\{ \triangle_{i=1}^k S_i \mid S_i \in \mathcal{A}\}$ is at most $d$ has size at most $(2^{d\bmod{k}}+o(1))\binom{n}{\lfloor d/k\rfloor}$. Here $\triangle$ denotes the symmetric difference operator. This is a $k$-fold generalisation of a result of Dvir and Moran, and it settles one of their questions. 

A key insight is that, by a compression method, the problem is equivalent to an extremal set theoretic problem on $k$-wise intersection or union that was originally due to Erdős and Frankl.

We also give an example of a family $\mathcal{A} \subset 2^{[n]}$ such that the VC dimension of $\mathcal{A}\cap \mathcal{A}$ and of $\mathcal{A}\cup \mathcal{A}$ are both at most $d$, while $\lvert \mathcal{A} \rvert = \Omega(n^d)$. This provides a negative answer to another question of Dvir and Moran.
Circular Digraph Walks, $k$-Balanced Strings, Lattice Paths and Chebychev Polynomials
Authors: Georgiadis Evangelos , Callan David , Hou Qing-Hu
Published: January 2020

We count the number of walks of length $n$ on a $k$-node circular digraph that cover all $k$ nodes in two ways. The first way illustrates the transfer-matrix method. The second involves counting various classes of height-restricted lattice paths. We observe that the results also count so-called $k$-balanced strings of length $n$, generalizing a 1996 Putnam problem.
Opportunity Costs in the Game of Best Choice
Authors: Crews Madeline , Jones Brant , Myers Kaitlyn , Taalman Laura , Urbanski Michael , Wilson Breeann
Published: January 2020

The game of best choice, also known as the secretary problem, is a model for sequential decision making with many variations in the literature. Notably, the classical setup assumes that the sequence of candidate rankings is uniformly distributed over time and that there is no expense associated with the candidate interviews. Here, we weight each ranking permutation according to the position of the best candidate in order to model costs incurred from conducting interviews with candidates that are ultimately not hired. We compare our weighted model with the classical (uniform) model via a limiting process. It turns out that imposing even infinitesimal costs on the interviews results in a probability of success that is about 28%, as opposed to 1/e (about 37%) in the classical case.
Factoring $(16, 6, 2)$ Hadamard Difference Sets
Authors: Bhattacharya Chirashree , Smith Ken W.
Published: January 2020

We describe a "factoring" method which constructs all twenty-seven Hadamard $(16,6,2)$ difference sets. The method involves identifying perfect ternary arrays of energy 4 (PTA(4)) in homomorphic images of a group $G$, studying the image of difference sets under such homomorphisms and using the preimages of the PTA(4)s to find the "factors" of difference sets in $G$. This "factoring" technique generalizes to other parameters, offering a general mechanism for creating Hadamard difference sets.
Nearly-Regular Hypergraphs and Saturation of Berge Stars
Authors: Austhof Bethany , English Sean
Published: January 2020

Given a graph $G$, we say a $k$-uniform hypergraph $H$ on the same vertex set contains a Berge-$G$ if there exists an injection $\phi:E(G)\to E(H)$ such that $e\subseteq\phi(e)$ for each edge $e\in E(G)$. A hypergraph $H$ is Berge-$G$-saturated if $H$ does not contain a Berge-$G$, but adding any edge to $H$ creates a Berge-$G$. The saturation number for Berge-$G$, denoted $\mathrm{sat}_k(n,\text{Berge-}G)$ is the least number of edges in a $k$-uniform hypergraph that is Berge-$G$-saturated. We determine exactly the value of the saturation numbers for Berge stars. As a tool for our main result, we also prove the existence of nearly-regular $k$-uniform hypergraphs, or $k$-uniform hypergraphs in which every vertex has degree $r$ or $r-1$ for some $r\in \mathbb{Z}$, and less than $k$ vertices have degree $r-1$.
Incompatible Double Posets and Double Order Polytopes
Authors: Benjes Aenne
Published: January 2020

In 1986 Stanley associated to a poset the order polytope. The close interplay between its combinatorial and geometric properties makes the order polytope an object of tremendous interest. Double posets were introduced in 2011 by Malvenuto and Reutenauer as a generalization of Stanleys labelled posets. A double poset is a finite set equipped with two partial orders. To a double poset Chappell, Friedl and Sanyal (2017) associated the double order polytope. They determined the combinatorial structure for the class of compatible double posets. In this paper we generalize their description to all double posets and we classify the 2-level double order polytopes.
Eigenvalues of the Laplacian on the Goldberg-Coxeter Constructions for 3- and 4-valent Graphs
Authors: Omori Toshiaki , Naito Hisashi , Tate Tatsuya
Published: January 2020

We are concerned with spectral problems of the Goldberg-Coxeter construction for $3$- and $4$-valent finite graphs. The Goldberg-Coxeter constructions $\mathrm{GC}_{k,l}(X)$ of a finite $3$- or $4$-valent graph $X$ are considered as ``subdivisions'' of $X$, whose number of vertices are increasing at order $O(k^2+l^2)$, nevertheless which have bounded girth. It is shown that the first (resp. the last) $o(k^2)$ eigenvalues of the combinatorial Laplacian on $\mathrm{GC}_{k,0}(X)$ tend to $0$ (resp. tend to $6$ or $8$ in the $3$- or $4$-valent case, respectively) as $k$ goes to infinity. A concrete estimate for the first several eigenvalues of $\mathrm{GC}_{k,l}(X)$ by those of $X$ is also obtained for general $k$ and $l$. It is also shown that the specific values always appear as eigenvalues of $\mathrm{GC}_{2k,0}(X)$ with large multiplicities almost independently to the structure of the initial $X$. In contrast, some dependency of the graph structure of $X$ on the multiplicity of the specific values is also studied.
Smirnov Trees
Authors: Konvalinka Matjaž , Tewari Vasu
Published: January 2020

We introduce a generalization of Smirnov words in the context of labeled binary trees, which we call Smirnov trees. We study the generating function for ascent-descent statistics on Smirnov trees and establish that it is $e$-positive, which is akin to the classical case of Smirnov words. Our proof relies on an intricate weight-preserving bijection.
Lattices From Tight Frames and Vertex Transitive Graphs
Authors: Fukshansky Lenny , Needell Deanna , Park Josiah , Xin Yuxin
Published: January 2020

We show that real tight frames that generate lattices must be rational. In the case of irreducible group frames, we show that the corresponding lattice is always strongly eutactic. We use this observation to describe a construction of strongly eutactic lattices from vertex transitive graphs. We show that such lattices exist in arbitrarily large dimensions and discuss some examples arising from complete graphs, product graphs, as well as some other notable examples of graphs. In particular, some well-known root lattices and those related to them can be recovered this way. We discuss various properties of this construction and also mention some potential applications of lattices generated by incoherent systems of vectors.
On the Weight of Berge-$F$-Free Hypergraphs
Authors: English Sean , Gerbner Dániel , Methuku Abhishek , Palmer Cory
Published: January 2020

For a graph $F$, we say a hypergraph is a Berge-$F$ if it can be obtained from $F$ by replacing each edge of $F$ with a hyperedge containing it. A hypergraph is Berge-$F$-free if it does not contain a subhypergraph that is a Berge-$F$. The weight of a non-uniform hypergraph $\mathcal{H}$ is the quantity $\sum_{h \in E(\mathcal{H})} |h|$.

Suppose $\mathcal{H}$ is a Berge-$F$-free hypergraph on $n$ vertices. In this short note, we prove that as long as every edge of $\mathcal{H}$ has size at least the Ramsey number of $F$, the weight of $\mathcal{H}$ is $o(n^2)$. This result is best possible in some sense. Along the way, we study other weight functions, and strengthen results of Gerbner and Palmer; and Grósz, Methuku and Tompkins.
The Spectral Excess Theorem for Distance-Regular Graphs: A Global (Over)view
Authors: Van Dam Edwin R.
Published: January 2020

Distance-regularity of a graph is in general not determined by the spectrum of the graph. The spectral excess theorem states that a connected regular graph is distance-regular if for every vertex, the number of vertices at extremal distance (the excess) equals some given expression in terms of the spectrum of the graph. This result was proved by Fiol and Garriga [From local adjacency polynomials to locally pseudo-distance-regular graphs, J. Combinatorial Th. B 71 (1997), 162-183] using a local approach. This approach has the advantage that more general results can be proven, but the disadvantage that it is quite technical. The aim of the current paper is to give a less technical proof by taking a global approach.
A New Bijection Between RNA Secondary Structures and Plane Trees and its Consequences
Authors: Chen Ricky Xiaofeng
Published: January 2020

In this paper, we first present a new bijection between RNA secondary structures and plane trees. Combined with the Schmitt-Waterman bijection between these objects, we then obtain a bijection on plane trees that relates the horizontal fiber decomposition associated  to internal vertices to the degrees of odd-level vertices while the vertical path decomposition associated to leaves is related to the degrees of even-level vertices.  To the best of our knowledge, only the former relation (i.e., horizontal vs odd-level) due to Deutsch is known. As a consequence,  we obtain enumeration results for various classes of plane trees, e.g., refining the Narayana numbers and the enumeration involving young leaves due to Chen, Deutsch and Elizalde, and counting a newly introduced `vertical' version of $k$-ary trees. The enumeration results can be also formulated in terms of RNA secondary structures with certain parameterized features, which might have some biological significance.
Distribution of Variables in Lambda-Terms with Restrictions on De Bruijn Indices and De Bruijn Levels
Authors: Gittenberger Bernhard , Larcher Isabella
Published: January 2020

We consider two special subclasses of lambda-terms that are restricted by a bound on the number of abstractions between a variable and its binding lambda, the so-called De-Bruijn index, or by a bound on the nesting levels of abstractions, i.e., the number of De Bruijn levels, respectively.

We show that the total number of variables is asymptotically normally distributed for both subclasses of lambda-terms with mean and variance asymptotically equal to $Cn$ and $\tilde{C}n$, respectively, where the constants $C$ and $\tilde{C}$ depend on the bound that has been imposed. For the class of lambda-terms with bounded De Bruijn index we derive closed formulas for the constant. For the other class of lambda-terms that we consider, namely lambda-terms with a bounded number of De Bruijn levels, we show quantitative and distributional results on the number of variables, as well as abstractions and applications, in the different De Bruijn levels and thereby exhibit a so-called "unary profile" that attains a very interesting shape. 

Our results give a combinatorial explanation of an earlier discovered strange phenomenon exhibited by the counting sequence of this particular class of lambda-terms.
Vertex Degree Sums for Matchings in 3-Uniform Hypergraphs
Authors: Zhang Yi , Zhao Yi , Lu Mei
Published: January 2020

Let $n, s$ be positive integers such that $n$ is sufficiently large and $s\le n/3$. Suppose $H$ is a 3-uniform hypergraph of order $n$ without isolated vertices. If $\deg(u)+\deg(v) > 2(s-1)(n-1)$ for any two vertices $u$ and $v$ that are contained in some edge of $H$, then $H$ contains a matching of size $s$. This degree sum condition is best possible and confirms a conjecture of the authors [Electron. J. Combin. 25 (3), 2018], who proved the case when $s= n/3$.
A New Encoding of Permutations by Laguerre Histories
Authors: Yan Sherry H.F. , Zhou Hao , Lin Zhicong
Published: January 2020

We construct a bijection from permutations to some weighted Motzkin paths known as Laguerre histories. As one application of our bijection, a neat $q$-$\gamma$-positivity expansion of the $(\mathrm{inv},\mathrm{exc})$-$q$-Eulerian polynomials is obtained.
Position Sequences and a $q$-Analogue for the Modular Hook Length Formula
Authors: Mendes Anthony , Lindbloom-Airey Sam
Published: January 2020

We prove a $q$-analogue of the modular hook length formula using position sequences. These position sequences, which correspond to moving the beads in a mathematical abacus, provide a new combinatorial interpretation for the characters of the irreducible representations of the symmetric group.
Necklace Bisection with One Cut Less than Needed
Authors: Simonyi Gábor
Published: January 2020

A well-known theorem of Goldberg and West states that two thieves can always split a necklace containing an even number of beads from each of $k$ types fairly by at most $k$ cuts. We prove that if we can use at most $k-1$ cuts and fair splitting is not possible then the thieves still have the following option. Whatever way they specify two disjoint sets $D_1, D_2$ of the types of beads with $D_1\cup D_2\neq\emptyset$, it will always be possible to cut the necklace (with $k-1$ cuts) so that the first thief gets more of those types of beads that are in $D_1$ and the second gets more of those in $D_2$, while the rest is divided equally. The proof combines the simple proof given by Alon and West to the original statement with a variant of the Borsuk-Ulam theorem due to Tucker and Bacon.