bluuebunny/crossref_metadata_2025 huggingface dataset:
Orphans in Forests of Linear Fractional Transformations
Authors: Han Sandie , Masuda Ariane M. , Singh Satyanand , Thiel Johann
Published: January 2020

A positive linear fractional transformation (PLFT) is a function of the form $f(z)=\frac{az+b}{cz+d}$ where $a,b,c$ and $d$ are nonnegative integers with determinant $ad-bc\neq 0$. Nathanson generalized the notion of the Calkin-Wilf tree to PLFTs and used it to partition the set of PLFTs into an infinite forest of rooted trees. The roots of these PLFT Calkin-Wilf trees are called orphans. In this paper, we provide a combinatorial formula for the number of orphans with fixed determinant $D$. In addition, we derive a method for determining the orphan ancestor of a given PLFT. Lastly, taking $z$ to be a complex number, we show that every positive complex number has finitely many ancestors in the forest of complex $(u,v)$-Calkin-Wilf trees.
Chip Games and Paintability
Authors: Duraj Lech , Gutowski Grzegorz , Kozik Jakub
Published: January 2020

We prove that the paint number of the complete bipartite graph $K_{N,N}$ is $\log N + O(1)$. As a consequence, we get that the difference between the paint number and the choice number of $K_{N,N}$ is $\Theta(\log \log N)$. This answers in the negative the question of Zhu (2009) whether this difference, for all graphs, can be bounded by a common constant. By a classical correspondence, our result translates to the framework of on-line coloring of uniform hypergraphs. This way we obtain that for every on-line two coloring algorithm there exists a $k$-uniform hypergraph with $\Theta(2^k)$ edges on which the strategy fails. The results are derived through an analysis of a natural family of chip games.
New Results on $k$-Independence of Graphs
Authors: Kogan Shimon
Published: January 2020

Let $G = (V, E)$ be a graph and $k \geq 0$ an integer. A $k$-independent set $S \subseteq G$ is a set of vertices such that the maximum degree in the graph induced by $S$ is at most $k$. Denote by $\alpha_{k}(G)$ the maximum cardinality of a $k$-independent set of $G$. For a graph $G$ on $n$ vertices and average degree $d$, Turán's theorem asserts that $\alpha_{0}(G) \geq \frac{n}{d+1}$, where the equality holds if and only if $G$ is a union of cliques of equal size. For general $k$ we prove that $\alpha_{k}(G) \geq \dfrac{(k+1)n}{d+k+1}$, improving on the previous best bound $\alpha_{k}(G) \geq \dfrac{(k+1)n}{ \lceil d \rceil+k+1}$ of Caro and Hansberg [E-JC, 2013]. For $1$-independence we prove that equality holds if and only if $G$ is either an independent set or a union of almost-cliques of equal size (an almost-clique is a clique on an even number of vertices minus a $1$-factor). For $2$-independence, we prove that equality holds if and only if $G$ is an independent set. Furthermore when $d>0$ is an integer divisible by 3 we prove that $\alpha_2(G) \geq \dfrac{3n}{d+3} \left( 1 + \dfrac{12}{5d^2 + 25d + 18} \right)$.
Lattice Points and Simultaneous Core Partitions
Authors: Johnson Paul
Published: January 2020

We apply lattice point techniques to the study of simultaneous core partitions. Our central observation is that for $a$ and $b$ relatively prime, the abacus construction identifies the set of simultaneous $(a,b)$-core partitions with lattice points in a rational simplex. We apply this result in two main ways: using Ehrhart theory, we reprove Anderson's theorem that there are $(a+b-1)!/a!b!$ simultaneous $(a,b)$-cores; and using Euler-Maclaurin theory we prove Armstrong's conjecture that the average size of an $(a,b)$-core is $(a+b+1)(a-1)(b-1)/24$. Our methods also give new derivations of analogous formulas for the number and average size of self-conjugate $(a,b)$-cores.
A Census of Vertices by Generations in Regular Tessellations of the Plane
Authors: Paul Alice , Pippenger Nicholas
Published: January 2020

We consider regular tessellations of the plane as infinite graphs in which $q$ edges and $q$ faces meet at each vertex, and in which $p$ edges and $p$ vertices surround each face. For ${1/p + 1/q = 1/2}$, these are tilings of the Euclidean plane; for ${1/p + 1/q < 1/2}$, they are tilings of the hyperbolic plane. We choose a vertex as the origin, and classify vertices into generations according to their distance (as measured by the number of edges in a shortest path) from the origin. For all $p\ge 3$ and $q \ge 3$ with ${1/p + 1/q\le1/2}$, we give simple combinatorial derivations of the rational generating functions for the number of vertices in each generation.
Application of Smirnov Words to Waiting Time Distributions of Runs
Authors: Freiberg Uta , Heuberger Clemens , Prodinger Helmut
Published: January 2020

Consider infinite random words over a finite alphabet where the letters occur as an i.i.d. sequence according to some arbitrary distribution on the alphabet. The expectation and the variance of the waiting time for the first completed $h$-run of any letter (i.e., first occurrence of $h$ subsequential equal letters) is computed. The expected waiting time for the completion of $h$-runs of $j$ arbitrary distinct letters is also given.
Deferred On-Line Bipartite Matching
Authors: Kozik Jakub , Matecki Grzegorz
Published: January 2020

We present a new model for the problem of on-line matching on bipartite graphs. Suppose that one part of a graph is given, but the vertices of the other part are presented in an on-line fashion. In the classical version, each incoming vertex is either irrevocably matched to a vertex from the other part or stays unmatched forever. In our version, an algorithm is allowed to match the new vertex to a group of elements (possibly empty). Later on, the algorithm can decide to remove some vertices from the group and assign them to another (just presented) vertex, with the restriction that each element belongs to at most one group. We present an optimal (deterministic) algorithm for this problem and prove that its competitive ratio equals $1-\pi/\cosh(\frac{\sqrt{3}}{2}\pi)\approx 0.588$.
Mixed Volumes of Hypersimplices
Authors: Liu Gaku
Published: January 2020

In this paper we consider mixed volumes of combinations of hypersimplices. These numbers, called "mixed Eulerian numbers", were first considered by A. Postnikov and were shown to satisfy many properties related to Eulerian numbers, Catalan numbers, binomial coefficients, etc. We give a general combinatorial interpretation for mixed Eulerian numbers and prove the above properties combinatorially. In particular, we show that each mixed Eulerian number enumerates a certain set of permutations in $S_n$. We also prove several new properties of mixed Eulerian numbers using our methods. Finally, we consider a type B analogue of mixed Eulerian numbers and give an analogous combinatorial interpretation for these numbers.
Extremal Graph for Intersecting Odd Cycles
Authors: Hou Xinmin , Qiu Yu , Liu Boyuan
Published: January 2020

An extremal graph for a graph $H$ on $n$ vertices is a graph on $n$ vertices with maximum number of edges that does not contain $H$ as a subgraph. Let $T_{n,r}$ be the Turán graph, which is the complete $r$-partite graph on $n$ vertices with part sizes that differ by at most one. The well-known Turán Theorem states that $T_{n,r}$ is the only extremal graph for complete graph $K_{r+1}$. Erdős et al. (1995) determined the extremal graphs for intersecting triangles and Chen et al. (2003) determined the maximum number of edges of the extremal graphs for intersecting cliques. In this paper, we determine the extremal graphs for intersecting odd cycles.
Combinatorics Meets Potential Theory
Authors: D'Arco Philippe , Lacivita Valentina , Mustapha Sami
Published: January 2020

Using potential theoretic techniques, we show how it is possible to determine the dominant asymptotics for the number of walks of length $n$, restricted to the positive quadrant and taking unit steps in a balanced set $\Gamma$. The approach is illustrated through an example of inhomogeneous space walk. This walk takes its steps in $\{ \leftarrow, \uparrow, \rightarrow, \downarrow \}$ or $\{ \swarrow, \leftarrow, \nwarrow, \uparrow,\nearrow, \rightarrow, \searrow, \downarrow \}$, depending on the parity of the coordinates of its positions. The exponential growth of our model is $(4\phi)^n$, where $\phi= \frac{1+\sqrt 5}{2}$denotes the Golden ratio, while the subexponential growth is like $1/n$.As an application of our approach we prove the non-D-finiteness in two dimensions of the length generating functions corresponding to nonsingular small step sets with an infinite group and zero-drift.
The Weighted Hook Length Formula III: Shifted Tableaux
Authors: Konvalinka Matjaž
Published: January 2020

Recently, a simple proof of the hook length formula was given via the branching rule. In this paper, we extend the results to shifted tableaux. We give a bijective proof of the branching rule for the hook lengths for shifted tableaux; present variants of this rule, including weighted versions; and make the first tentative steps toward a bijective proof of the hook length formula for $d$-complete posets.
Minimal Orbits of Promotion
Authors: Purbhoo Kevin , Rhee Donguk
Published: January 2020

We give a bijection between the symmetric group $S_n$, and the set of standard Young tableaux of rectangular shape $m^n$, $m \geq n$, that have order $n$ under jeu de taquin promotion.
Guessing Numbers of Odd Cycles
Authors: Atkins Ross , Rombach Puck , Skerman Fiona
Published: January 2020

For a given number of colours, $s$, the guessing number of a graph is the base $s$ logarithm of the size of the largest family of colourings of the vertex set of the graph such that the colour of each vertex can be determined from the colours of the vertices in its neighbourhood. An upper bound for the guessing number of the $n$-vertex cycle graph $C_n$ is $n/2$. It is known that the guessing number equals $n/2$ whenever $n$ is even or $s$ is a perfect square. We show that, for any given integer $s \geq 2$, if $a$ is the largest factor of $s$ less than or equal to $\sqrt{s}$, for sufficiently large odd $n$, the guessing number of $C_n$ with $s$ colours is $(n-1)/2 + \log_s(a)$. This answers a question posed by Christofides and Markström in 2011.We also present an explicit protocol which achieves this bound for every $n$. Linking this to index coding with side information, we deduce that the information defect of $C_n$ with $s$ colours is $(n+1)/2 - \log_s(a)$ for sufficiently large odd $n$.
Generating Asymptotics for Factorially Divergent Sequences
Authors: Borinsky Michael
Published: January 2020

The algebraic properties of formal power series, whose coefficients show factorial growth and admit a certain well-behaved asymptotic expansion, are discussed. It is shown that these series form a subring of $\mathbb{R}[[x]]$. This subring is also closed under composition and inversion of power series. An `asymptotic derivation' is defined which maps a power series to the asymptotic expansion of its coefficients. Product and chain rules for this derivation are deduced. With these rules asymptotic expansions of the coefficients of implicitly defined power series can be obtained. The full asymptotic expansions of the number of connected chord diagrams and the number of simple permutations are given as examples.
Preserving the Number of Cycles of Length $k$ in a Growing Uniform Permutation
Authors: Duchon Philippe , Duvignau Romaric
Published: January 2020

The goal of this work is to describe a uniform generation tree for permutations which preserves the number of $k$-cycles between any permutation (except for a small unavoidable subset of optimal size) of the tree and its direct children. Moreover, the tree we describe has the property that if the number of $k$-cycles does not change during any $k$ consecutive levels, then any further random descent will always yield permutations with that same number of $k$-cycles. This specific additional property yields interesting applications for exact sampling. We describe a new random generation algorithm for permutations with a fixed number of $k$-cycles in $n+\mathcal{O}(1)$ expected calls to a random integer sampler. Another application is a combinatorial algorithm for exact sampling from the Poisson distribution with parameter $1/k$.
Counting Trees in Graphs
Authors: Verstraete Jacques , Mubayi Dhruv
Published: January 2020

Erdős and Simonovits proved that the number of paths of length $t$ in an $n$-vertex graph of average degree $d$ is at least $(1 - \delta) nd(d - 1) \cdots (d - t + 1)$, where $\delta = (\log d)^{-1/2 + o(1)}$ as $d \rightarrow \infty$. In this paper, we strengthen and generalize this result as follows. Let $T$ be a tree with $t$ edges. We prove that for any $n$-vertex graph $G$ of average degree $d$ and minimum degree greater than $t$, the number of labelled copies of $T$ in $G$ is at least \[(1 - \varepsilon) n d(d - 1) \cdots (d - t + 1)\] where $\varepsilon = O(d^{-2})$ as $d \rightarrow \infty$. This bound is tight except for the term $1 - \varepsilon$, as shown by a disjoint union of cliques. Our proof is obtained by first showing a lower bound that is a convex function of the degree sequence of $G$, and this answers a question of Dellamonica et. al.
Anti-van der Waerden Numbers of 3-Term Arithmetic Progression
Authors: Berikkyzy Zhanar , Shulte Alex , Young Michael
Published: January 2020

The anti-van der Waerden number, denoted by $aw([n],k)$, is the smallest $r$ such that every exact $r$-coloring of $[n]$ contains a rainbow $k$-term arithmetic progression. Butler et. al. showed that $\lceil \log_3 n \rceil + 2 \le aw([n],3) \le \lceil \log_2 n \rceil + 1$, and conjectured that there exists a constant $C$ such that $aw([n],3) \le \lceil \log_3 n \rceil + C$. In this paper, we show this conjecture is true by determining $aw([n],3)$ for all $n$. We prove that for $7\cdot 3^{m-2}+1 \leq n \leq 21 \cdot 3^{m-2}$,         \begin{equation*}            aw([n],3)=\left\{\begin{array}{ll}                m+2, & \mbox{if $n=3^m$} \\                m+3, & \mbox{otherwise}.            \end{array}\right.        \end{equation*}
Unsplittable Classes of Separable Permutations
Authors: Albert Michael , Jelínek Vít
Published: January 2020

A permutation class is splittable if it is contained in the merge of two of its proper subclasses. We characterise the unsplittable subclasses of the class of separable permutations both structurally and in terms of their bases.
A Flag Whitney Number Formula for Matroid Kazhdan-Lusztig Polynomials
Authors: Wakefield Max
Published: January 2020

For a representation of a matroid the combinatorially defined Kazhdan-Lusztig polynomial computes the intersection cohomology of the associated reciprocal plane. However, these polynomials are difficult to compute and there are numerous open conjectures about their structure. For example, it is unknown whether or not the coefficients are non-negative for non-representable matroids. The main result in this note is a combinatorial formula for the coefficients of these matroid Kazhdan-Lusztig polynomials in terms of flag Whitney numbers. This formula gives insight into some vanishing behavior of the matroid Kazhdan-Lusztig polynomials.
A Short Conceptual Proof of Narayana's Path-Counting Formula
Authors: Ciucu Mihai
Published: January 2020

We deduce Narayana's formula for the number of lattice paths that fit in a Young diagram as a direct consequence of the Gessel-Viennot theorem on non-intersecting lattice paths.
Binary Covering Arrays on Tournaments
Authors: Maltais Elizabeth , Moura Lucia , Newman Mike
Published: January 2020

We introduce graph-dependent covering arrays which generalize covering arrays on graphs, introduced by Meagher and Stevens (2005), and graph-dependent partition systems, studied by Gargano, Körner, and Vaccaro (1994). A covering array $\hbox{CA}(n; 2, G, H)$ (of strength 2) on column graph $G$ and alphabet graph $H$ is an $n\times |V(G)|$ array with symbols $V(H)$ such that for every arc $ij \in E(G)$ and for every arc $ab\in E(H)$, there exists a  row $\vec{r} = (r_{1},\dots, r_{|V(G)|})$   such that $(r_{i}, r_{j}) = (a,b)$.  We prove bounds on $n$ when $G$ is a tournament graph and $E(H)$ consists of the edge $(0,1)$, which corresponds to a directed version of Sperner's 1928 theorem. For two infinite families of column graphs, transitive and so-called circular tournaments, we give constructions of covering arrays which are optimal infinitely often.
Minimum Cuts of Distance-Regular Digraphs
Authors: Ashkboos Saleh , Omidi Gholamreza , Shafiei Fateme , Tajbakhsh Khosro
Published: January 2020

In this paper, we investigate the structure of minimum vertex and edge cuts of distance-regular digraphs. We show that each distance-regular digraph $\Gamma$, different from an undirected cycle, is super edge-connected, that is, any minimum edge cut of $\Gamma$ is the set of all edges going into (or coming out of) a single vertex. Moreover, we will show that except for undirected cycles, any distance regular-digraph $\Gamma$ with diameter $D=2$, degree $k\leq 3$ or $\lambda=0$ ($\lambda$ is the number of 2-paths from $u$ to $v$ for an edge $uv$ of $\Gamma$) is super vertex-connected, that is, any minimum vertex cut of $\Gamma$ is the set of all out-neighbors (or in-neighbors) of a single vertex in $\Gamma$. These results extend the same known results for the undirected case with quite different proofs.
Cycles in the Graph of Overlapping Permutations Avoiding Barred Patterns
Authors: Qin Guizhi , Yan Sherry  H.F.
Published: January 2020

As a variation of De Bruijn graphs on strings of symbols, the graph of overlapping permutations has a directed edge $\pi(1)\pi(2)\ldots \pi(n+1)$ from the standardization of $\pi(1)\pi(2)\ldots \pi(n)$ to the standardization of $\pi(2)\pi(3)\ldots \pi(n+1)$. In this paper, we consider the enumeration of $d$-cycles in the subgraph of overlapping $(231, 4\bar{1}32)$-avoiding permutations. To this end, we introduce the notions of marked Motzkin paths and marked Riordan paths, where a marked Motzkin (resp. Riordan) path is a Motzkin (resp. Riordan) path in which exactly one step before the leftmost return point is marked. We show that the number of closed walks of length $d$ in the subgraph of overlapping $(231, 4\bar{1}32)$-avoiding permutations are closely related to the number of marked Motzkin paths and that of marked Riordan paths.  By establishing bijections, we get the enumerations of marked Motzkin paths and marked Riordan paths. As a corollary, we provide bijective proofs of two identities involving Catalan numbers in answer to the problem posed by Ehrenborg, Kitaev and Steingrímsson. Moreover, we get the enumerations of $(231, 4\bar{1}32)$-avoiding affine permutations and $(312, 32\bar{4}1)$-avoiding affine permutations.
On Stacked Triangulated Manifolds
Authors: Datta Basudeb , Murai Satoshi
Published: January 2020

We prove two results on stacked triangulated manifolds in this paper: (a) every stacked triangulation of a connected manifold with or without boundary is obtained from a simplex or the boundary of a simplex by certain combinatorial operations; (b) in dimension $d \geq 4$, if $\Delta$ is a tight connected closed homology $d$-manifold whose $i$th homology vanishes for $1 < i < d-1$, then $\Delta$ is a stacked triangulation of a manifold. These results give affirmative answers to questions posed by Novik and Swartz and by Effenberger.
Pieri Rules for Classical Groups and Equinumeration between Generalized Oscillating Tableaux and Semistandard Tableaux
Authors: Okada Soichi
Published: January 2020

We present several equinumerous results between generalized oscillating tableaux and semistandard tableaux and give a representation-theoretic proof to them. As one of the key ingredients of the proof, we provide Pieri rules for the symplectic and orthogonal groups.
Cluster Automorphisms and the Marked Exchange Graphs of Skew-Symmetrizable Cluster Algebras
Authors: Lawson John W
Published: January 2020

Cluster automorphisms have been shown to have links to the mapping class groups of surfaces, maximal green sequences and to exchange graph automorphisms for skew-symmetric cluster algebras. In this paper we generalise these results to the skew-symmetrizable case by introducing a marking on the exchange graph. Many skew-symmetrizable matrices unfold to skew-symmetric matrices and we consider how cluster automorphisms behave under this unfolding with applications to coverings of orbifolds by surfaces.
Combinatorics of Exceptional Sequences in Type A
Authors: Garver Alexander , Igusa Kiyoshi , Matherne Jacob P. , Ostroff Jonah
Published: January 2020

Exceptional sequences are certain sequences of quiver representations.  We introduce a class of objects called strand diagrams and use these to classify exceptional sequences of representations of a quiver whose underlying graph is a type $\mathbb{A}_n$ Dynkin diagram. We also use variations of these objects to classify $c$-matrices of such quivers, to interpret exceptional sequences as linear extensions of explicitly constructed posets, and to give a simple bijection between exceptional sequences and certain saturated chains in the lattice of noncrossing partitions.
The Extremal Function for Cycles of Length $\ell$ mod $k$
Authors: Sudakov Benny , Verstraete Jacques
Published: January 2020

Burr and Erdős conjectured that for each $k,\ell \in \mathbb Z^+$ such that $k \mathbb Z + \ell$ contains even integers, there exists $c_k(\ell)$ such that any graph of average degree at least $c_k(\ell)$ contains a cycle of length $\ell$ mod $k$. This conjecture was proved by Bollobás, and many successive improvements of upper bounds on $c_k(\ell)$ appear in the literature. In this short note, for $1 \leq \ell \leq k$, we show that $c_k(\ell)$ is proportional to the largest average degree of a $C_{\ell}$-free graph on $k$ vertices, which determines $c_k(\ell)$ up to an absolute constant. In particular, using known results on Turán numbers for even cycles, we obtain $c_k(\ell) = O(\ell k^{2/\ell})$ for all even $\ell$, which is tight for $\ell \in \{4,6,10\}$. Since the complete bipartite graph $K_{\ell - 1,n - \ell + 1}$ has no cycle of length $2\ell$ mod $k$, it also shows $c_k(\ell) = \Theta(\ell)$ for $\ell = \Omega(\log k)$.
Dominating Sequences in Grid-Like and Toroidal Graphs
Authors: Brešar Boštjan , Bujtás Csilla , Gologranc Tanja , Klavžar Sandi , Košmrlj Gašper , Patkós Balázs , Tuza Zsolt , Vizer Máté
Published: January 2020

A longest sequence $S$ of distinct vertices of a graph $G$ such that each vertex of $S$ dominates some vertex that is not dominated by its preceding vertices, is called a Grundy dominating sequence; the length of $S$ is the Grundy domination number of $G$. In this paper we study the Grundy domination number in the four standard graph products: the Cartesian, the lexicographic, the direct, and the strong product. For each of the products we present a lower bound for the Grundy domination number which turns out to be exact for the lexicographic product and is conjectured to be exact for the strong product. In most of the cases exact Grundy domination numbers are determined for products of paths and/or cycles.
Toughness of $K_{a,t}$-Minor-free Graphs
Authors: Chen Guantao , Egawa Yoshimi , Kawarabayashi Ken-ichi , Mohar Bojan , Ota Katsuhiro
Published: January 2020

The toughness of a non-complete graph $G$ is the minimum value of $\frac{|S|}{\omega(G-S)}$ among all separating vertex sets $S\subset V(G)$, where $\omega(G-S)\ge 2$ is the number of components of $G-S$. It is well-known that every $3$-connected planar graph has toughness greater than $1/2$. Related to this property, every $3$-connected planar graph has many good substructures, such as a spanning tree with maximum degree three, a $2$-walk, etc. Realizing that 3-connected planar graphs are essentially the same as 3-connected $K_{3,3}$-minor-free graphs, we consider a generalization to $a$-connected $K_{a,t}$-minor-free graphs, where $3\le a\le t$. We prove that there exists a positive constant $h(a,t)$ such that every $a$-connected $K_{a,t}$-minor-free graph $G$ has toughness at least $h(a,t)$. For the case where $a=3$ and $t$ is odd, we obtain the best possible value for $h(3,t)$. As a corollary it is proved that every such graph of order $n$ contains a cycle of length $\Omega(\log_{h(a,t)} n)$.
On $q$-Quasiadditive and $q$-Quasimultiplicative Functions
Authors: Kropf Sara , Wagner Stephan
Published: January 2020

In this paper, we introduce the notion of $q$-quasiadditivity of arithmetic functions, as well as the related concept of $q$-quasimultiplicativity, which generalise strong $q$-additivity and -multiplicativity, respectively. We show that there are many natural examples for these concepts, which are characterised by functional equations of the form $f(q^{k+r}a + b) = f(a) + f(b)$ or $f(q^{k+r}a + b) = f(a) f(b)$ for all $b < q^k$ and a fixed parameter $r$. In addition to some elementary properties of $q$-quasiadditive and $q$-quasimultiplicative functions, we prove characterisations of $q$-quasiadditivity and $q$-quasimultiplicativity for the special class of $q$-regular functions. The final main result provides a general central limit theorem that includes both classical and new examples as corollaries.
Permutations that Destroy Arithmetic Progressions in Elementary $p$-Groups
Authors: Elkies Noam D. , Swaminathan Ashvin A.
Published: January 2020

Given an abelian group $G$, it is natural to ask whether there exists a permutation $\pi$ of $G$ that "destroys" all nontrivial 3-term arithmetic progressions (APs), in the sense that $\pi(b) - \pi(a) \neq \pi(c) - \pi(b)$ for every ordered triple $(a,b,c) \in G^3$ satisfying $b-a = c-b \neq 0$. This question was resolved for infinite groups $G$ by Hegarty, who showed that there exists an AP-destroying permutation of $G$ if and only if $G/\Omega_2(G)$ has the same cardinality as $G$, where $\Omega_2(G)$ denotes the subgroup of all elements in $G$ whose order divides $2$. In the case when $G$ is finite, however, only partial results have been obtained thus far. Hegarty has conjectured that an AP-destroying permutation of $G$ exists if $G = \mathbb{Z}/n\mathbb{Z}$ for all $n \neq 2,3,5,7$, and together with Martinsson, he has proven the conjecture for all $n > 1.4 \times 10^{14}$. In this paper, we show that if $p$ is a prime and $k$ is a positive integer, then there is an AP-destroying permutation of the elementary $p$-group $(\mathbb{Z}/p\mathbb{Z})^k$ if and only if $p$ is odd and $(p,k) \not\in \{(3,1),(5,1), (7,1)\}$.
On the Minimum Length of Linear Codes over the Field of 9 Elements
Authors: Kumegawa Kazuki , Okazaki Ysukasa , Maruta Tatsuya
Published: January 2020

We construct a lot of new $[n,4,d]_9$ codes whose lengths are close to the Griesmer bound and prove the nonexistence of some linear codes attaining the Griesmer bound using some geometric techniques through projective geometries to determine the exact value of $n_9(4,d)$ or to improve the known bound on $n_9(4,d)$ for given values of $d$, where $n_q(k,d)$ is the minimum length $n$ for which an $[n,k,d]_q$ code exists. We also give the updated table for $n_9(4,d)$ for all $d$ except some known cases.
On the Queue-Number of Graphs with Bounded Tree-Width
Authors: Wiechert Veit
Published: January 2020

A queue layout of a graph consists of a linear order on the vertices and an assignment of the edges to queues, such that no two edges in a single queue are nested. The minimum number of queues needed in a queue layout of a graph is called its queue-number. We show that for each $k\geq0$, graphs with tree-width at most $k$ have queue-number at most $2^k-1$. This improves upon double exponential upper bounds due to Dujmović et al. and Giacomo et al. As a consequence we obtain that these graphs have track-number at most $2^{O(k^2)}$. We complement these results by a construction of $k$-trees that have queue-number at least $k+1$. Already in the case $k=2$ this is an improvement to existing results and solves a problem of Rengarajan and Veni Madhavan, namely, that the maximal queue-number of $2$-trees is equal to $3$.
Perfect Matchings of Trimmed Aztec Rectangles
Authors: Lai Tri
Published: January 2020

We consider several new families of subgraphs of the square grid whose matchings are enumerated by powers of several small prime numbers: $2$, $3$, $5$, and $11$.  Our graphs are obtained by trimming two opposite corners of an Aztec rectangle. The result yields a proof of a conjecture posed by Ciucu. In addition, we reveal a hidden connection between our graphs and the hexagonal dungeons introduced by Blum.
New Combinatorial Formulas for Cluster Monomials of Type $A$ Quivers
Authors: Lee Kyungyong , Li Li , Nguyen Ba
Published: January 2020

Lots of research focuses on the combinatorics behind various bases of cluster algebras. This paper studies the natural basis of a type $A$ cluster algebra, which consists of all cluster monomials. We introduce a new kind of combinatorial formula for the cluster monomials in terms of the so-called globally compatible collections. We give bijective proofs of these formulas by comparing with the well-known combinatorial models of the $T$-paths and of the perfect matchings in a snake diagram. For cluster variables of a type $A$ cluster algebra, we give a bijection that relates our new formula with the theta functions constructed by Gross, Hacking, Keel and Kontsevich.
Countable Menger's Theorem with Finitary Matroid Constraints on the Ingoing Edges
Authors: Joó Attila
Published: January 2020

We present a strengthening of the countable Menger's theorem of R. Aharoni. Let $ D=(V,A) $ be a countable digraph with $ s\neq t\in V $ and let $\mathcal{M}=\bigoplus_{v\in V}\mathcal{M}_v $ be a matroid on $ A $ where $ \mathcal{M}_v $ is a finitary matroid on the ingoing edges of $ v $. We show that there is a system of edge-disjoint $ s \rightarrow t $ paths $ \mathcal{P} $ such that the united edge set of these paths is $ \mathcal{M} $-independent, and there is a $ C \subseteq A $ consisting of one edge from each element of $\mathcal{P} $ for which $ \mathsf{span}_{\mathcal{M}}(C) $ covers all the $ s\rightarrow t $ paths in $ D $.
Omittable Planes
Authors: Grünbaum Branko , Lenchner Jonathan
Published: January 2020

In analogy to omittable lines in the plane, we initiate the study of omittable planes in $3$-space. Given a collection of $n$ planes in real projective $3$-space, a plane $\Pi$ is said to be omittable if $\Pi$ is free of ordinary lines of intersection – in other words, if all the lines of intersection of $\Pi$ with other planes from the collection come at the intersection of three or more planes. We provide two infinite families of planes yielding omittable planes in either a pencil or near-pencil, together with examples having between three and seven omittable planes, examples that we call "sporadic," which do not fit into either of the two infinite families.
Double Posets and the Antipode of QSym
Authors: Grinberg Darij
Published: January 2020

A quasisymmetric function is assigned to every double poset (that is, every finite set endowed with two partial orders) and any weight function on its ground set. This generalizes well-known objects such as monomial and fundamental quasisymmetric functions, (skew) Schur functions, dual immaculate functions, and quasisymmetric $\left(P, \omega\right)$-partition enumerators. We prove a formula for the antipode of this function that holds under certain conditions (which are satisfied when the second order of the double poset is total, but also in some other cases); this restates (in a way that to us seems more natural) a result by Malvenuto and Reutenauer, but our proof is new and self-contained. We generalize it further to an even more comprehensive setting, where a group acts on the double poset by automorphisms.
Avoiding Fractional Powers over the Natural Numbers
Authors: Pudwell Lara , Rowland Eric
Published: January 2020

We study the lexicographically least infinite $a/b$-power-free word on the alphabet of non-negative integers. Frequently this word is a fixed point of a uniform morphism, or closely related to one. For example, the lexicographically least $7/4$-power-free word is a fixed point of a $50847$-uniform morphism. We identify the structure of the lexicographically least $a/b$-power-free word for three infinite families of rationals $a/b$ as well many "sporadic" rationals that do not seem to belong to general families. To accomplish this, we develop an automated procedure for proving $a/b$-power-freeness for morphisms of a certain form, both for explicit and symbolic rational numbers $a/b$. Finally, we establish a connection to words on a finite alphabet. Namely, the lexicographically least $27/23$-power-free word is in fact a word on the finite alphabet $\{0, 1, 2\}$, and its sequence of letters is $353$-automatic.
The Signless Laplacian Spectral Radius of Unicyclic and Bicyclic Graphs with a Given Girth
Authors: Li Ke , Wang Ligong , Zhao Guopeng
Published: January 2020

Let $\mathcal{U}(n,g)$ and $\mathcal{B}(n,g)$ be the set of unicyclic graphs and bicyclic graphs on $n$ vertices with girth $g$, respectively. Let $\mathcal{B}_{1}(n,g)$ be the subclass of $\mathcal{B}(n,g)$ consisting of all bicyclic graphs with two edge-disjoint cycles and $\mathcal{B}_{2}(n,g)=\mathcal{B}(n,g)\backslash\mathcal{B}_{1}(n,g)$. This paper determines the unique graph with the maximal signless Laplacian spectral radius among all graphs in $\mathcal{U}(n,g)$ and $\mathcal{B}(n,g)$, respectively. Furthermore, an upper bound of the signless Laplacian spectral radius and the extremal graph for $\mathcal{B}(n,g)$ are also given.
On some Euler-Mahonian Distributions
Authors: Carnevale Angela
Published: January 2020

We prove that the pair of statistics (des,maj) on multiset permutations is equidistributed with the pair (stc,inv) on certain quotients of the symmetric group. We define an analogue of the statistic stc on multiset permutations whose joint distribution with the inversions equals that of (des,maj). We extend the definition of the statistic stc to hyperoctahedral and even hyperoctahedral groups. These functions, together with the Coxeter length, are equidistributed with (ndes,nmaj) and (ddes,dmaj), respectively.
Enumeration of Fuss-Schröder paths
Authors: An Suhyung , Jung JiYoon , Kim Sangwook
Published: January 2020

In this paper we enumerate the number of $(k, r)$-Fuss-Schröder paths of type $\lambda$. Y. Park and S. Kim studied small Schröder paths with type $\lambda$. Generalizing the results to small $(k, r)$-Fuss-Schröder paths with type $\lambda$, we give a combinatorial interpretation for the number of small $(k, r)$-Fuss-Schröder paths of type $\lambda$ by using Chung-Feller style. We also give two sets of sparse noncrossing partitions of $[2(k + 1)n + 1]$ and $[2(k + 1)n + 2]$ which are in bijection with the set of all small and large, respectively, $(k, r)$-Fuss-Schröder paths of type $\lambda$.
The Guessing Number of Undirected Graphs
Authors: Christofides Demetres , Markström Klas
Published: January 2020

Riis [Electron. J. Combin., 14(1):R44, 2007] introduced a guessing game for graphs which is equivalent to finding protocols for network coding. In this paper we prove upper and lower bounds for the winning probability of the guessing game on undirected graphs. We find optimal bounds for perfect graphs and minimally imperfect graphs, and present a conjecture relating the exact value for all graphs to the fractional chromatic number.
On Repetition Thresholds of Caterpillars and Trees of Bounded Degree
Authors: Lužar Borut , Ochem Pascal , Pinlou Alexandre
Published: January 2020

The repetition threshold is the smallest real number $\alpha$ such that there exists an infinite word over a $k$-letter alphabet that avoids repetition of exponent strictly greater than $\alpha$. This notion can be generalized to graph classes. In this paper, we completely determine the repetition thresholds for caterpillars and caterpillars of maximum degree $3$. Additionally, we present bounds for the repetition thresholds of trees with bounded maximum degrees.
Algebraic Properties of Edge Ideals via Combinatorial Topology
Authors: Dochtermann Anton , Engström Alexander
Published: January 2020

We apply some basic notions from combinatorial topology to establish various algebraic properties of edge ideals of graphs and more general Stanley-Reisner rings. In this way we provide new short proofs of some theorems from the literature regarding linearity, Betti numbers, and (sequentially) Cohen-Macaulay properties of edge ideals associated to chordal, complements of chordal, and Ferrers graphs, as well as trees and forests. Our approach unifies (and in many cases strengthens) these results and also provides combinatorial/enumerative interpretations of certain algebraic properties. We apply our setup to obtain new results regarding algebraic properties of edge ideals in the context of local changes to a graph (adding whiskers and ears) as well as bounded vertex degree. These methods also lead to recursive relations among certain generating functions of Betti numbers which we use to establish new formulas for the projective dimension of edge ideals. We use only well-known tools from combinatorial topology along the lines of independence complexes of graphs, (not necessarily pure) vertex decomposability, shellability, etc.
Kirillov's Unimodality Conjecture for the Rectangular Narayana Polynomials
Authors: Chen Herman Z. Q. , Yang Arthur L. B. , Zhang Philip B.
Published: January 2020

In the study of Kostka numbers and Catalan numbers, Kirillov posed a unimodality conjecture for the rectangular Narayana polynomials. We prove that the rectangular Narayana polynomials have only real zeros, and thereby confirm Kirillov's unimodality conjecture. By using an equidistribution property between descent numbers and ascent numbers on ballot paths due to Sulanke and a bijection between lattice words and standard Young tableaux, we show that the rectangular Narayana polynomial is equal to the descent generating function on standard Young tableaux of certain rectangular shape, up to a power of the indeterminate. Then we obtain the real-rootedness of the rectangular Narayana polynomial based on a result of Brenti which implies that the descent generating function of standard Young tableaux has only real zeros.
Identities in Plactic, Hypoplactic, Sylvester, Baxter, and Related Monoids
Authors: Cain Alan J. , Malheiro António
Published: January 2020

This paper considers whether non-trivial identities are satisfied by certain `plactic-like' monoids that, like the plactic monoid, are closely connected to combinatorics. New results show that the hypoplactic, sylvester, Baxter, stalactic, and taiga monoids satisfy identities, and indeed give shortest identities satisfied by these monoids. The existing state of knowledge is discussed for the plactic monoid and left and right patience sorting monoids.
Rook Placements and Jordan Forms of Upper-Triangular Nilpotent Matrices
Authors: Yip Martha
Published: January 2020

The set of $n$ by $n$ upper-triangular nilpotent matrices with entries in a finite field $\mathbb{F}_q$ has Jordan canonical forms indexed by partitions $\lambda \vdash n$. We present a combinatorial formula for computing the number $F_\lambda(q)$ of matrices of Jordan type $\lambda$ as a weighted sum over standard Young tableaux. We construct a bijection between paths in a modified version of Young's lattice and non-attacking rook placements, which leads to a refinement of the formula for $F_\lambda(q)$.
Perfect Fractional Matchings in $k$-Out Hypergraphs
Authors: Devlin Pat , Kahn Jeff
Published: January 2020

Extending the notion of (random) $k$-out graphs, we consider when the $k$-out hypergraph is likely to have a perfect fractional matching. In particular, we show that for each $r$ there is a $k=k(r)$ such that the $k$-out $r$-uniform hypergraph on $n$ vertices has a perfect fractional matching with high probability (i.e., with probability tending to $1$ as $n\to\infty$) and prove an analogous result for $r$-uniform $r$-partite hypergraphs. This is based on a new notion of hypergraph expansion and the observation that sufficiently expansive hypergraphs admit perfect fractional matchings. As a further application, we give a short proof of a stopping-time result originally due to Krivelevich.
Zero Sum Partition of Abelian Groups into Sets of the Same Order and its Applications
Authors: Cichacz Sylwia
Published: January 2020

We will say that an Abelian group $\Gamma$ of order $n$ has the $m$-zero-sum-partition property ($m$-ZSP-property) if $m$ divides $n$, $m\geq 2$ and there is a partition of $\Gamma$ into pairwise disjoint subsets $A_1, A_2,\ldots , A_t$, such that $|A_i| = m$ and $\sum_{a\in A_i}a = g_0$ for $1 \leq i \leq t$, where $g_0$ is the identity element of $\Gamma$.In this paper we study the $m$-ZSP property of $\Gamma$. We show that $\Gamma$ has the $m$-ZSP property if and only if $m\geq 3$ and $|\Gamma|$ is odd or $\Gamma$ has more than one involution. We will apply the results to the study of group distance magic graphs as well as to generalized Kotzig arrays.
Note on the Union-Closed Sets Conjecture
Authors: Raz Abigail
Published: January 2020

The union-closed sets conjecture states that if a finite family of sets $\mathcal{A} \neq \{\varnothing\}$ is union-closed, then there is an element which belongs to at least half the sets in $\mathcal{A}$. In 2001, D. Reimer showed that the average set size of a union-closed family, $\mathcal{A}$, is at least $\frac{1}{2} \log_2 |\mathcal{A}|$. In order to do so, he showed that all union-closed families satisfy a particular condition, which in turn implies the preceding bound. Here, answering a question raised in the context of T. Gowers' polymath project on the union-closed sets conjecture, we show that Reimer's condition alone is not enough to imply that there is an element in at least half the sets.
The $Z$-Polynomial of a Matroid
Authors: Proudfoot Nicholas , Xu Yuan , Young Ben
Published: January 2020

We introduce the $Z$-polynomial of a matroid, which we define in terms of the Kazhdan-Lusztig polynomial. We then exploit a symmetry of the $Z$-polynomial to derive a new recursion for Kazhdan-Lusztig coefficients. We solve this recursion, obtaining a closed formula for Kazhdan-Lusztig coefficients as alternating sums of multi-indexed Whitney numbers. For realizable matroids, we give a cohomological interpretation of the $Z$-polynomial in which the symmetry is a manifestation of Poincaré duality.
A New Approach for Examining $q$-Steiner Systems
Authors: Etzion Tuvi
Published: January 2020

One of the most intriguing problems in $q$-analogs of designs and codes is the existence question of an infinite family of $q$-analog of Steiner systems (spreads not included) in general, and the existence question for the $q$-analog of the Fano plane in particular.We exhibit a completely new method to attack this problem. In the process we define a new family of designs whose existence is implied by the existence of $q$-Steiner systems, but could exist even if the related $q$-Steiner systems do not exist.The method is based on a possible system obtained by puncturing all the subspaces of the $q$-Steiner system several times. We define  the punctured system as a new type of design and enumerate the number of subspaces of various types that it might have. It will be evident that its existence does not imply the existence of the related $q$-Steiner system. On the other hand, this type of design demonstrates how close can we get to the related $q$-Steiner system.Necessary conditions for the existence of such designs are presented. These necessary conditions will be also necessary conditions for the existence of the related $q$-Steiner system. Trivial and nontrivial direct constructions and a nontrivial recursive construction for such designs are given. Some of the designs have a symmetric structure, which is uniform in the dimensions of the existing subspaces in the system. Most constructions are based on this uniform structure of the design or its punctured designs.
Pattern Avoidance in Ascent Sequences
Authors: Duncan Paul , Steingrímsson Einar
Published: January 2020

Ascent sequences are sequences of nonnegative integers with restrictions on the size of each letter, depending on the number of ascents preceding it in the sequence. Ascent sequences have recently been related to $(2+2)$-free posets and various other combinatorial structures. We study pattern avoidance in ascent sequences, giving several results for patterns of lengths up to 4, for Wilf equivalence and for growth rates. We establish bijective connections between pattern avoiding ascent sequences and various other combinatorial objects, in particular with set partitions. We also make a number of conjectures related to all of these aspects.
Extensions of Partial Cyclic Orders, Euler Numbers and Multidimensional Boustrophedons
Authors: Ramassamy Sanjay
Published: January 2020

We enumerate total cyclic orders on $\left\{x_1,\ldots,x_n\right\}$ where we prescribe the relative cyclic order of consecutive triples $(x_i,x_{i+1},x_{i+2})$, with indices taken modulo $n$. In some cases, the problem reduces to the enumeration of descent classes of permutations, which is done via the boustrophedon construction. In other cases, we solve the question by introducing multidimensional versions of the boustrophedon. In particular we find new interpretations for the Euler up/down numbers and the Entringer numbers.
A Cycle of Maximum Order in a Graph of High Minimum Degree has a Chord
Authors: Harvey Daniel J.
Published: January 2020

A well-known conjecture of Thomassen states that every cycle of maximum order in a $3$-connected graph contains a chord. While many partial results towards this conjecture have been obtained, the conjecture itself remains unsolved. In this paper, we prove a stronger result without a connectivity assumption for graphs of high minimum degree, which shows Thomassen's conjecture holds in that case. This result is within a constant factor of best possible. In the process of proving this, we prove a more general result showing that large minimum degree forces a large difference between the order of the largest cycle and the order of the largest chordless cycle.
Proper Distinguishing Colorings with Few Colors for Graphs with Girth at Least 5
Authors: Cranston Daniel W.
Published: January 2020

The distinguishing chromatic number, $\chi_D(G)$, of a graph $G$ is the smallest number of colors in a proper coloring, $\varphi$, of $G$, such that the only automorphism of $G$ that preserves all colors of $\varphi$ is the identity map.  Collins and Trenk conjectured that if $G$ is connected with girth at least 5 and $G\ne C_6$, then $\chi_D(G)\leqslant \Delta+1$. We prove this conjecture.
How to Draw Tropical Planes
Authors: Herrmann Sven , Jensen Anders , Joswig Michael , Sturmfels Bernd
Published: January 2020

The tropical Grassmannian parameterizes tropicalizations of ordinary linear spaces, while the Dressian parameterizes all tropical linear spaces in ${\Bbb T}{\Bbb P}^{n-1}$. We study these parameter spaces and we compute them explicitly for $n \leq 7$. Planes are identified with matroid subdivisions and with arrangements of trees. These representations are then used to draw pictures.
Monochromatic Cycle Partitions of $2$-Coloured Graphs with Minimum Degree $3n/4$
Authors: Letzter Shoham
Published: January 2020

Balogh, Barát, Gerbner, Gyárfás, and Sárközy made the following conjecture. Let $G$ be a graph on $n$ vertices with minimum degree at least $3n/4$. Then for every $2$-edge-colouring of $G$, the vertex set $V(G)$ may be partitioned into two vertex-disjoint cycles, one of each colour.

We prove this conjecture for large $n$, improving approximate results by the aforementioned authors and by DeBiasio and Nelsen.
On the Maximum Degree of Path-Pairable Planar Graphs
Authors: Girão António , Mészáros Gábor , Popielarz Kamil , Snyder Richard
Published: January 2020

A graph is path-pairable if for any pairing of its vertices there exist edge-disjoint paths joining the vertices in each pair. We investigate the behaviour of the maximum degree in path-pairable planar graphs. We show that any $n$-vertex path-pairable planar graph must contain a vertex of degree linear in $n$. Our result generalizes to graphs embeddable on a surface of finite genus.