bluuebunny/crossref_metadata_2025 huggingface dataset:
Ramsey Numbers of Trees Versus Odd Cycles
Authors: Brennan Matthew
Published: January 2020

Burr, Erdős, Faudree, Rousseau and Schelp initiated the study of Ramsey numbers of trees versus odd cycles, proving that $R(T_n, C_m) = 2n - 1$ for all odd $m \ge 3$ and $n \ge 756m^{10}$, where $T_n$ is a tree with $n$ vertices and $C_m$ is an odd cycle of length $m$. They proposed to study the minimum positive integer $n_0(m)$ such that this result holds for all $n \ge n_0(m)$, as a function of $m$. In this paper, we show that $n_0(m)$ is at most linear. In particular, we prove that $R(T_n, C_m) = 2n - 1$ for all odd $m \ge 3$ and $n \ge 25m$. Combining this with a result of Faudree, Lawrence, Parsons and Schelp yields $n_0(m)$ is bounded between two linear functions, thus identifying $n_0(m)$ up to a constant factor.
Pathwidth and Nonrepetitive List Coloring
Authors: Gągol Adam , Joret Gwenaël , Kozik Jakub , Micek Piotr
Published: January 2020

A vertex coloring of a graph is nonrepetitive if there is no path in the graph whose first half receives the same sequence of colors as the second half. While every tree can be nonrepetitively colored with a bounded number of colors (4 colors is enough), Fiorenzi, Ochem, Ossona de Mendez, and Zhu recently showed that this does not extend to the list version of the problem, that is, for every $\ell \geq 1$ there is a tree that is not nonrepetitively $\ell$-choosable. In this paper we prove the following positive result, which complements the result of Fiorenzi et al.: There exists a function $f$ such that every tree of pathwidth $k$ is nonrepetitively $f(k)$-choosable. We also show that such a property is specific to trees by constructing a family of pathwidth-2 graphs that are not nonrepetitively $\ell$-choosable for any fixed $\ell$.
The Peak Statistics on Simsun Permutations
Authors: Ma Shi-Mei , Yeh Yeong-Nan
Published: January 2020

In this paper, we study the relationship among left peaks, interior peaks and up-down runs of simsun permutations. Properties of the generating polynomials, including the recurrence relation, generating function and real-rootedness are studied. Moreover, we introduce and study simsun permutations of the second kind.
The Universal Gröbner Basis of a Binomial Edge Ideal
Authors: Badiane Mourtadha , Burke Isaac , Sköldberg Emil
Published: January 2020

We show that the universal Gröbner basis and the Graver basis of a binomial edge ideal coincide. We provide a description for this basis set in terms of certain paths in the underlying graph. We conjecture a similar result for a parity binomial edge ideal and prove this conjecture for the case when the underlying graph is the complete graph.
Isotropic Matroids III: Connectivity
Authors: Brijder Robert , Traldi Lorenzo
Published: January 2020

The isotropic matroid $M[IAS(G)]$ of a graph $G$ is a binary matroid, which is equivalent to the isotropic system introduced by Bouchet. In this paper we discuss four notions of connectivity related to isotropic matroids and isotropic systems. We show that the isotropic system connectivity defined by Bouchet is equivalent to vertical connectivity of $M[IAS(G)]$, and if $G$ has at least four vertices, then $M[IAS(G)]$ is vertically 5-connected if and only if $G$ is prime (in the sense of Cunningham's split decomposition). We also show that $M[IAS(G)]$ is $3$-connected if and only if $G$ is connected and has neither a pendant vertex nor a pair of twin vertices. Our most interesting theorem is that if $G$ has $n\geq7$ vertices then $M[IAS(G)]$ is not vertically $n$-connected. This abstract-seeming result is equivalent to the more concrete assertion that $G$ is locally equivalent to a graph with a vertex of degree $<\frac{n-1}{2}$.
On the Caccetta-Häggkvist Conjecture with a Forbidden Transitive Tournament
Authors: Grzesik Andrzej
Published: January 2020

The Caccetta-Häggkvist Conjecture asserts that every oriented graph on $n$ vertices without directed cycles of length less than or equal to $l$ has minimum outdegree at most $(n-1)/l$. In this paper we state a conjecture for graphs missing a transitive tournament on $2^k+1$ vertices, with a weaker assumption on minimum outdegree. We prove that the Caccetta-Häggkvist Conjecture follows from the presented conjecture and show matching constructions for all $k$ and $l$. The main advantage of considering this generalized conjecture is that it reduces the set of the extremal graphs and allows using an induction.We also prove the triangle case of the conjecture for $k=1$ and $2$ by using the Razborov's flag algebras. In particular, it proves the most interesting and studied case of the Caccetta-Häggkvist Conjecture in the class of graphs without the transitive tournament on 5 vertices. It is also shown that the extremal graph for the case $k=2$ has to be a blow-up of a directed cycle on 4 vertices having in each blob an extremal graph for the case $k=1$ (complete regular bipartite graph), which confirms the conjectured structure of the extremal examples.
On a Vertex-Minimal Triangulation of $\mathbb R \mathrm P ^4$
Authors: Balagopalan Sonia
Published: January 2020

We give three constructions of a vertex-minimal triangulation of $4$-dimensional real projective space $\mathbb{R}\mathrm{P}^4$. The first construction describes a $4$-dimensional sphere on $32$ vertices, which is a double cover of a triangulated $\mathbb{R}\mathrm{P}^4$ and has a large amount of symmetry. The second and third constructions illustrate approaches to improving the known number of vertices needed to triangulate $n$-dimensional real projective space. All three constructions deliver the same combinatorial manifold, which is also the same as the only known $16$-vertex triangulation of $\mathbb{R}\mathrm{P}^4$. We also give a short, simple construction of the $22$-point Witt design, which is closely related to the complex we construct.
Two Partial Orders for Standard Young Tableaux
Authors: Kosakowska Justyna , Schmidmeier Markus , Thomas Hugh
Published: January 2020

In this manuscript we show that two partial orders defined on the set of standard Young tableaux of shape $\alpha$ are equivalent. In fact, we give two proofs for the equivalence of  the box order and the dominance order for tableaux. Both are algorithmic. The first of these proofs emphasizes links to the Bruhat order for the symmetric group and the second provides a more straightforward construction of the cover relations. This work is motivated by the known result that the equivalence of the two combinatorial orders leads to a description of the geometry of the representation space of invariant subspaces of nilpotent linear operators.
A Better Lower Bound on Average Degree of 4-List-Critical Graphs
Authors: Rabern Landon
Published: January 2020

This short note proves that every non-complete $k$-list-critical graph has average degree at least $k-1 + \frac{k-3}{k^2-2k+2}$. This improves the best known bound for $k = 4,5,6$. The same bound holds for online $k$-list-critical graphs.
The Lattice of Definable Equivalence Relations in Homogeneous $n$-Dimensional Permutation Structures
Authors: Braunfeld Samuel
Published: January 2020

In Homogeneous permutations, Peter Cameron [Electronic Journal of Combinatorics 2002] classified the homogeneous permutations (homogeneous structures with 2 linear orders), and posed the problem of classifying the homogeneous $n$-dimensional permutation structures (homogeneous structures with $n$ linear orders) for all finite $n$. We prove here that the lattice of $\emptyset$-definable equivalence relations in such a structure can be any finite distributive lattice, providing many new imprimitive examples of homogeneous finite dimensional permutation structures. We conjecture that the distributivity of the lattice of $\emptyset$-definable equivalence relations is necessary, and prove this under the assumption that the reduct of the structure to the language of $\emptyset$-definable equivalence relations is homogeneous. Finally, we conjecture a classification of the primitive examples, and confirm this in the special case where all minimal forbidden structures have order 2.
On Symmetries in Phylogenetic Trees
Authors: Fusy Éric
Published: January 2020

Billey et al. [arXiv:1507.04976] have recently discovered a surprisingly simple formula for the number $a_n(\sigma)$ of leaf-labelled rooted non-embedded binary trees (also known as phylogenetic trees) with $n\geq 1$ leaves, fixed (for the relabelling action) by a given permutation $\sigma\in\frak{S}_n$. Denoting by $\lambda\vdash n$ the integer partition giving the sizes of the cycles of $\sigma$ in non-increasing order, they show by a guessing/checking approach that if $\lambda$ is a binary partition (it is known that $a_n(\sigma)=0$ otherwise), then$$a_n(\sigma)=\prod_{i=2}^{\ell(\lambda)}(2(\lambda_i+\cdots+\lambda_{\ell(\lambda)})-1),$$and they derive from it a formula and random generation procedure for tanglegrams (and more generally for tangled chains). Our main result is a combinatorial proof of the formula for $a_n(\sigma)$, which yields a simplification of the random sampler for tangled chains.
Majority Bootstrap Percolation on $G(n,p)$
Authors: Holmgren Cecilia , Juškevičius Tomas , Kettle Nathan
Published: January 2020

Majority bootstrap percolation on a graph $G$ is an epidemic process defined in the following manner. Firstly, an initially infected set of vertices is selected. Then step by step the vertices that have at least half of its neighbours infected become infected. We say that percolation occurs if eventually all vertices in $G$ become infected.In this paper we  provide sharp bounds for the critical size of the initially infected set in majority bootstrap percolation on the Erdős-Rényi random graph $G(n,p)$. This answers an open question by Janson, Luczak, Turova and Vallier (2012). Our results obtained for $p=c\log(n)/n$ are close to the results obtained by Balogh, Bollobás and Morris (2009) for majority bootstrap percolation on the hypercube. We conjecture that similar results will be true for all regular-like graphs with the same density and sufficiently strong expansion properties.
The Wildcard Set's Size in the Density Hales-Jewett Theorem
Authors: McCutcheon Randall
Published: January 2020

In this paper prove results concerning restrictions on the cardinality of the wildcard set in the density Hales-Jewett theorem, establishing in particular that for general $k$ one may choose this cardinality from any IP set and that for $k=2$ it may be chosen to be a square, thus providing an abstract extension of Sárközy's theorem on square differences in sets of positive upper density.
Improved Lower Bounds for the Orders of Even Girth Cages
Authors: Jajcayová Tatiana Baginová , Filipovski Slobodan , Jajcay Robert
Published: January 2020

The well-known Moore bound $M(k,g)$ serves as a universal lower bound for the order of $k$-regular graphs of girth $g$. The excess $e$ of a $k$-regular graph $G$ of girth $g$ and order $n$ is the difference between its order $n$ and the corresponding Moore bound, $e=n - M(k,g) $. We find infinite families of parameters $(k,g)$, $g$ even, for which we show that the excess of any $k$-regular graph of girth $g$ is larger than $4$. This yields new improved lower bounds on the order of $k$-regular graphs of girth $g$ of smallest possible order; the so-called $(k,g)$-cages. We also show that the excess of the smallest $k$-regular graphs of girth $g$ can be arbitrarily large for a restricted family of $(k,g)$-graphs satisfying a very natural additional structural property.
On the Size of Dissociated Bases
Authors: Lev Vsevolod F. , Yuster Raphael
Published: January 2020

We prove that the sizes of the maximal dissociated subsets of a given finite subset of an abelian group differ by a logarithmic factor at most. On the other hand, we show that the set $\{0,1\}^n\subseteq\mathbb{Z}^n$ possesses a dissociated subset of size $\Omega(n\log n)$; since the standard basis of $\mathbb{Z}^n$ is a maximal dissociated subset of $\{0,1\}^n$ of size $n$, the result just mentioned is essentially sharp.
Refining the Hierarchies of Classes of Geometric Intersection Graphs
Authors: Cabello Sergio , Jejčič Miha
Published: January 2020

We analyse properties of geometric intersection graphs to show the strict containment between some natural classes of geometric intersection graphs. In particular, we show the following properties:A graph $G$ is outerplanar if and only if the 1-subdivision of $G$ is outer-segment.For each integer $k\ge 1$, the class of intersection graphs of segments with $k$ different lengths is a strict subclass of the class of intersection graphs of segments with $k+1$ different lengths.For each integer $k\ge 1$, the class of intersection graphs of disks with $k$ different sizes is a strict subclass of the class of intersection graphs of disks with $k+1$ different sizes.The class of outer-segment graphs is a strict subclass of the class of outer-string graphs.
A Brooks Type Theorem for the Maximum Local Edge Connectivity
Authors: Stiebitz Michael , Toft Bjarne
Published: January 2020

For a graph $G$, let $\chi(G)$ and $\lambda(G)$ denote the chromatic number of $G$ and the maximum local edge connectivity of $G$, respectively. A result of Dirac implies that every graph $G$ satisfies $\chi(G)\leq \lambda(G)+1$. In this paper we characterize the graphs $G$ for which $\chi(G)=\lambda(G)+1$. The case $\lambda(G)=3$ was already solved by Aboulker, Brettell, Havet, Marx, and Trotignon. We show that a graph $G$ with $\lambda(G)=k\geq 4$ satisfies $\chi(G)=k+1$ if and only if $G$ contains a block which can be obtained from copies of $K_{k+1}$ by repeated applications of the Hajós join.
A Simple Existence Criterion for Normal Spanning Trees
Authors: Diestel Reinhard
Published: January 2020

Halin proved in 1978 that there exists a normal spanning tree in every connected graph $G$ that satisfies the following two conditions: (i) $G$ contains no subdivision of a `fat' $K_{\aleph_0}$, one in which every edge has been replaced by uncountably many parallel edges; and (ii) $G$ has no $K_{\aleph_0}$ subgraph. We show that the second condition is unnecessary.
A Square Root Map on Sturmian Words
Authors: Peltomäki Jarkko , Whiteland Markus A.
Published: January 2020

We introduce a square root map on Sturmian words and study its properties. Given a Sturmian word of slope $\alpha$, there exists exactly six minimal squares in its language (a minimal square does not have a square as a proper prefix). A Sturmian word $s$ of slope $\alpha$ can be written as a product of these six minimal squares: $s = X_1^2 X_2^2 X_3^2 \cdots$. The square root of $s$ is defined to be the word $\sqrt{s} = X_1 X_2 X_3 \cdots$. The main result of this paper is that $\sqrt{s}$ is also a Sturmian word of slope $\alpha$. Further, we characterize the Sturmian fixed points of the square root map, and we describe how to find the intercept of $\sqrt{s}$ and an occurrence of any prefix of $\sqrt{s}$ in $s$. Related to the square root map, we characterize the solutions of the word equation $X_1^2 X_2^2 \cdots X_n^2 = (X_1 X_2 \cdots X_n)^2$ in the language of Sturmian words of slope $\alpha$ where the words $X_i^2$ are minimal squares of slope $\alpha$.We also study the square root map in a more general setting. We explicitly construct an infinite set of non-Sturmian fixed points of the square root map. We show that the subshifts $\Omega$ generated by these words have a curious property: for all $w \in \Omega$ either $\sqrt{w} \in \Omega$ or $\sqrt{w}$ is periodic. In particular, the square root map can map an aperiodic word to a periodic word.
Acyclic Sets in $k$-Majority Tournaments
Authors: Milans Kevin G. , Schreiber Daniel H. , West Douglas B.
Published: January 2020

When $\Pi$ is a set of $k$ linear orders on a ground set $X$, and $k$ is odd, the $k$-majority tournament generated by $\Pi$ has vertex set $X$ and has an edge from $u$ to $v$ if and only if a majority of the orders in $\Pi$ rank $u$ before $v$. Let $f_k(n)$ be the minimum, over all $k$-majority tournaments with $n$ vertices, of the maximum order of an induced transitive subtournament. We prove that $f_3(n)\ge\sqrt{n}$ always and that $f_3(n)\le 2\sqrt{n}-1$ when $n$ is a perfect square. We also prove that $f_5(n) \ge n^{1/4}$. For general $k$, we prove that $n^{c_k} \le f_k(n) \le n^{d_k(n)}$, where $c_k = 3^{-(k-1)/2}$ and $d_k(n)\to \frac{1+\lg\lg k}{-1+\lg k}$ as $n\to \infty$.
The Threshold for Jigsaw Percolation on Random Graphs
Authors: Bollobás Béla , Riordan Oliver , Slivken Erik , Smith Paul
Published: January 2020

Jigsaw percolation is a model for the process of solving puzzles within a social network, which was recently proposed by Brummitt, Chatterjee, Dey and Sivakoff. In the model there are two graphs on a single vertex set (the `people' graph and the `puzzle' graph), and vertices merge to form components if they are joined by an edge of each graph. These components then merge to form larger components if again there is an edge of each graph joining them, and so on. Percolation is said to occur if the process terminates with a single component containing every vertex. In this note we determine the threshold for percolation up to a constant factor, in the case where both graphs are Erdős-Rényi random graphs.
Partition Statistics for Cubic Partition Pairs
Authors: Kim Byungchan
Published: January 2020

In this brief note, we give two partition statistics which explain the following partition congruences: \begin{align*} b(5n+4) &\equiv 0 \pmod{5}, \\ b(7n+a) &\equiv 0 \pmod{7}, \text{if $a=2$, $3$, $4$, or $6$}. \end{align*} Here, $b(n)$ is the number of $4$-color partitions of $n$ with colors $r$, $y$, $o$, and $b$ subject to the restriction that the colors $o$ and $b$ appear only in even parts.
Symmetries of Unlabelled Planar Triangulations
Authors: Kang Mihyun , Sprüssel Philipp
Published: January 2020

We derive a decomposition scheme of unlabelled triangulations rooted at a single cell, where the decomposition depends on whether the automorphism group of the triangulation contains reflections, rotations, or both. Furthermore, the decomposition scheme is constructive in the sense that for each of the three cases, there is a $k\in\mathbb{N}$ such that the scheme defines a one-to-$k$ correspondence between the respective triangulations and their decompositions.
Matching and Independence Complexes Related to Small Grids
Authors: Braun Benjamin , Hough Wesley K.
Published: January 2020

The topology of the matching complex for the $2\times n$ grid graph is mysterious. We describe a discrete Morse matching for a family of independence complexes $\mathrm{Ind}(\Delta_n^m)$ that include these matching complexes. Using this matching, we determine the dimensions of the chain spaces for the resulting Morse complexes and derive bounds on the location of non-trivial homology groups for certain $\mathrm{Ind}(\Delta_n^m)$. Further, we determine the Euler characteristic of $\mathrm{Ind}(\Delta_n^m)$ and prove that several homology groups of $\mathrm{Ind}(\Delta_n^m)$ are non-zero.
Frankl's Conjecture for Subgroup Lattices
Authors: Abdollahi Alireza , Woodroofe Russ , Zaimi Gjergji
Published: January 2020

We show that the subgroup lattice of any finite group satisfies Frankl’s Union-Closed Conjecture. We show the same for all lattices with a modular coatom, a family which includes all supersolvable and dually semimodular lattices. A common technical result used to prove both may be of some independent interest.
On Total Positivity of Catalan-Stieltjes Matrices
Authors: Pan Qiongqiong , Zeng Jiang
Published: January 2020

Recently Chen-Liang-Wang (Linear Algerbra Appl. 471 (2015) 383—393) proved some sufficient conditions for the total positivity of Catalan-Stieltjes matrices. Our aim is to provide a combinatorial interpretation of their sufficiant conditions. More precisely, for any Catalan-Stieltjes matrix $A$ we construct a digraph with a weight, which is positive under their sufficient conditions, such that every minor of $A$ is equal to the sum of weights of families of nonintersecting paths of the digraph. We have also an analogue result for the minors of Hankel matrix associated to the first column of Catalan-Stieltjes matrix $A$.
Ramsey Numbers of Connected Clique Matchings
Authors: Roberts Barnaby
Published: January 2020

We determine the Ramsey number of a connected clique matching. That is, we show that if $G$ is a $2$-edge-coloured complete graph on $(r^2-r-1)n-r+1$ vertices, then there is a monochromatic connected subgraph containing $n$ disjoint copies of $K_r$, and that this number of vertices cannot be reduced.
Waiter–Client and Client–Waiter Colourability and $k$–SAT Games
Authors: Tan Wei En
Published: January 2020

Waiter–Client and Client–Waiter games are two–player, perfect information games, with no chance moves, played on a finite set (board) with special subsets known as the winning sets. Each round of the biased $(1:q)$ Waiter–Client game begins with Waiter offering $q+1$ previously unclaimed elements of the board to Client, who claims one and leaves the remaining $q$ elements to be claimed by Waiter immediately afterwards. In a $(1:q)$ Client–Waiter game, play occurs in the same way except in each round, Waiter offers $t$ elements for any $t$ in the range $1\leqslant t\leqslant q+1$. If Client fully claims a winning set by the time all board elements have been offered, he wins in the Client–Waiter game and loses in the Waiter–Client game. We give an estimate for the threshold bias (i.e. the unique value of $q$ at which the winner of a $(1:q)$ game changes) of the $(1:q)$ Waiter–Client and Client–Waiter versions of two different games: the non–2–colourability game, played on the edge set of a complete $k$–uniform hypergraph, and the $k$–SAT game. More precisely, we show that the threshold bias for the Waiter–Client and Client–Waiter versions of the non–2–colourability game is $\frac{1}{n}\binom{n}{k}2^{\mathcal{O}_k(k)}$ and $\frac{1}{n}\binom{n}{k}2^{-k(1+o_k(1))}$ respectively. Additionally, we show that the threshold bias for the Waiter–Client and Client–Waiter versions of the $k$–SAT game is $\frac{1}{n}\binom{n}{k}$ up to a factor that is exponential and polynomial in $k$ respectively. This shows that these games exhibit the probabilistic intuition.
$T$-Joins in Infinite Graphs
Authors: Joó Attila
Published: January 2020

We characterize the class of infinite graphs $G$ for which there exists a $T$-join for any choice of an infinite $T \subseteq V(G)$. We also show that the following well-known fact remains true in the infinite case. If $G$ is connected and does not contain a $T$-join, then it will if we either remove an arbitrary vertex from $T$ or add any new vertex to $T$.
Anti-Power Prefixes of the Thue-Morse Word
Authors: Defant Colin
Published: January 2020

Recently, Fici, Restivo, Silva, and Zamboni defined a $k$-anti-power to be a word of the form $w_1w_2\cdots w_k$, where $w_1,w_2,\ldots,w_k$ are distinct words of the same length. They defined $AP(x,k)$ to be the set of all positive integers $m$ such that the prefix of length $km$ of the word $x$ is a $k$-anti-power. Let ${\bf t}$ denote the Thue-Morse word, and let $\mathcal F(k)=AP({\bf t},k)\cap(2\mathbb Z^+-1)$. For $k\geq 3$, $\gamma(k)=\min(\mathcal F(k))$ and $\Gamma(k)=\max((2\mathbb Z^+-1)\setminus\mathcal F(k))$ are well-defined odd positive integers. Fici et al. speculated that $\gamma(k)$ grows linearly in $k$. We prove that this is indeed the case by showing that $1/2\leq\displaystyle{\liminf_{k\to\infty}}(\gamma(k)/k)\leq 9/10$ and $1\leq\displaystyle{\limsup_{k\to\infty}}(\gamma(k)/k)\leq 3/2$. In addition, we prove that $\displaystyle{\liminf_{k\to\infty}}(\Gamma(k)/k)=3/2$ and $\displaystyle{\limsup_{k\to\infty}}(\Gamma(k)/k)=3$.
Generating Functions for Inverted Semistandard Young Tableaux and Generalized Ballot Numbers
Authors: Drube Paul
Published: January 2020

An inverted semistandard Young tableau is a row-standard tableau along with a collection of inversion pairs that quantify how far the tableau is from being column semistandard. Such a tableau with precisely $k$ inversion pairs is said to be a $k$-inverted semistandard Young tableau. Building upon earlier work by Fresse and the author, this paper develops generating functions for the numbers of $k$-inverted semistandard Young tableaux of various shapes $\lambda$ and contents $\mu$. An easily-calculable generating function is given for the number of $k$-inverted semistandard Young tableaux that "standardize" to a fixed semistandard Young tableau. For $m$-row shapes $\lambda$ and standard content $\mu$, the total number of $k$-inverted standard Young tableaux of shape $\lambda$ is then enumerated by relating such tableaux to $m$-dimensional generalizations of Dyck paths and counting the numbers of "returns to ground" in those paths. In the rectangular specialization of $\lambda = n^m$ this yields a generating function that involves $m$-dimensional analogues of the famed Ballot numbers. Our various results are then used to directly enumerate all $k$-inverted semistandard Young tableaux with arbitrary content and two-row shape $\lambda = a^1 b^1$, as well as all $k$-inverted standard Young tableaux with two-column shape $\lambda=2^n$.
Pretty Good State Transfer on Circulant Graphs
Authors: Pal Hiranmoy , Bhattacharjya Bikash
Published: January 2020

Let $G$ be a graph with adjacency matrix $A$. The transition matrix of $G$ relative to $A$ is defined by $H(t):=\exp{\left(-itA\right)}$, where $t\in {\mathbb R}$. The graph $G$ is said to admit pretty good state transfer between a pair of vertices $u$ and $v$ if there exists a sequence of real numbers $\{t_k\}$ and a complex number $\gamma$ of unit modulus such that $\lim\limits_{k\rightarrow\infty} H(t_k) e_u=\gamma e_v.$ We find that the cycle $C_n$ as well as its complement $\overline{C}_n$ admit pretty good state transfer if and only if $n$ is a power of two, and it occurs between every pair of antipodal vertices. In addition, we look for pretty good state transfer in more general circulant graphs. We prove that union (edge disjoint) of an integral circulant graph with a cycle, each on $2^k$ $(k\geq 3)$ vertices, admits pretty good state transfer. The complement of such union also admits pretty good state transfer. Using Cartesian products, we find some non-circulant graphs admitting pretty good state transfer.
Excluding Hooks and their Complements
Authors: Choromanski Krzysztof , Falik Dvir , Liebenau Anita , Patel Viresh , Pilipczuk Marcin
Published: January 2020

The long-standing Erdős-Hajnal conjecture states that for every $n$-vertex undirected graph $H$ there exists $\epsilon(H)>0$ such that every graph $G$ that does not contain $H$ as an induced subgraph contains a clique or an independent set of size at least $n^{\epsilon(H)}$. A natural weakening of the conjecture states that the polynomial-size clique/independent set phenomenon occurs if one excludes both $H$ and its complement $H^\mathrm{c}$. These conjectures have been shown to hold for only a handful of graphs: it is not even known if they hold for all graphs on $5$ vertices.In a recent breakthrough, the symmetrized version of the Erdős-Hajnal conjecture was shown to hold for all paths. The goal of this paper is to show that the symmetrized conjecture holds for all trees on $6$ (or fewer) vertices. In fact this is a consequence of showing that the symmetrized conjecture holds for any path with a pendant edge at its third vertex; thus we also give a new infinite family of graphs for which the symmetrized conjecture holds.
Neighborhood Growth Dynamics on the Hamming Plane
Authors: Gravner Janko , Sivakoff David , Slivken Erik
Published: January 2020

We initiate the study of general neighborhood growth dynamics on two-dimensional Hamming graphs. The decision to add a point is made by counting the currently occupied points on the horizontal and the vertical line through it, and checking whether the pair of counts lies outside a fixed Young diagram.  We focus on two related extremal quantities. The first is the size of the smallest set that eventually occupies the entire plane. The second is the minimum of an energy-entropy functional that comes from the scaling of the probability of eventual full occupation versus the density of the initial product measure within a rectangle. We demonstrate the existence of this scaling and study these quantities for large Young diagrams.
On Different "Middle Parts" of a Tree
Authors: Smith Heather , Székely László , Wang Hua , Yuan Shuai
Published: January 2020

We determine the maximum distance between any two of the center, centroid, and subtree core among trees with a given order. Corresponding results are obtained for trees with given maximum degree and also for trees with given diameter. The problem of the maximum distance between the centroid and the subtree core among trees with given order and diameter becomes difficult. It can be solved in terms of the problem of minimizing the number of root-containing subtrees in a rooted tree of given order and height. While the latter problem remains unsolved, we provide a partial characterization of the extremal structure.
A New Bijective Proof of Babson and Steingrímsson's Conjecture
Authors: Chen Joanna N. , Li Shouxiao
Published: January 2020

Babson and Steingrímsson introduced generalized permutation patterns and showed that most of the Mahonian statistics in the literature can be expressed by the combination of generalized pattern functions. Particularly, they defined a new Mahonian statistic in terms of generalized pattern functions, which is denoted $stat$. Given a permutation $\pi$, let $des(\pi)$ denote the descent number of $\pi$ and $maj(\pi)$ denote the major index of $\pi$. Babson and Steingrímsson conjectured that $(des,stat)$ and $(des,maj)$ are equidistributed on $S_n$. Foata and Zeilberger settled this conjecture using q-enumeration, generating functions and Maple packages ROTA and PERCY. Later, Burstein provided a bijective proof of a refinement of this conjecture. In this paper, we give a new bijective proof of this conjecture.
Linear Polychromatic Colorings of Hypercube Faces
Authors: Chen Evan
Published: January 2020

A coloring of the $\ell$-dimensional faces of $Q_n$ is called $d$-polychromatic if every embedded $Q_d$ has every color on at least one face. Denote by $p^\ell(d)$ the maximum number of colors such that any $Q_n$ can be colored in this way. We provide a new lower bound on $p^\ell(d)$ for $\ell > 1$.
A Note on Intersecting Hypergraphs with Large Cover Number
Authors: Haxell P. E. , Scott A. D.
Published: January 2020

We give a construction of $r$-partite $r$-uniform intersecting hypergraphs with cover number at least $r-4$ for all but finitely many $r$. This answers a question of Abu-Khazneh, Barát, Pokrovskiy and Szabó, and shows that a long-standing unsolved conjecture due to Ryser is close to being best possible for every value of $r$.
Connected Order Ideals and $P$-Partitions
Authors: Zhou Ben P.
Published: January 2020

Given a finite poset $P$, we associate a simple graph denoted by $G_P$ with all connected order ideals of $P$ as vertices, and two vertices are adjacent if and only if they have nonempty intersection and are incomparable with respect to set inclusion. We establish a bijection between the set of maximum independent sets of $G_P$ and the set of $P$-forests, introduced by Feray and Reiner in their study of the fundamental generating function $F_P(\textbf{x})$ associated with $P$-partitions. Based on this bijection, in the cases when $P$ is naturally labeled we show that $F_P(\textbf{x})$ can factorise, such that each factor is a summation of rational functions determined by maximum independent sets of a connected component of $G_P$. This approach enables us to give an alternative proof for Feray and Reiner's nice formula of $F_P(\textbf{x})$ for the case of $P$ being a naturally labeled forest with duplications. Another consequence of our result is a product formula to compute the number of linear extensions of $P$.
On Robust Colorings of Hamming-Distance Graphs
Authors: Harney Isaiah , Gluesing-Luerssen Heide
Published: January 2020

$H_q(n,d)$ is defined as the graph with vertex set $\mathbb{Z}_q^n$ and where two vertices are adjacent if their Hamming distance is at least $d$. The chromatic number of these graphs is presented for various sets of parameters $(q,n,d)$. For the $4$-colorings of the graphs $H_2(n,n-1)$ a notion of robustness is introduced. It is based on the tolerance of swapping colors along an edge without destroying properness of the coloring. An explicit description of the maximally robust $4$-colorings of $H_2(n,n-1)$ is presented.
Dinv and Area
Authors: Garsia Adriano , Xin Guoce
Published: January 2020

We give a new combinatorial proof of the well known result that the dinv of an $(m,n)$-Dyck path is equal to the area of its sweep map image. The first proof of this remarkable identity for co-prime $(m,n)$ is due to Loehr and Warrington. There is also a second proof (in the co-prime case) due to Gorsky and Mazin and a third proof due to Mazin. A corrigendum was added to this paper on the 9th of June 2017.
Extremal Numbers for Directed Hypergraphs with Two Edges
Authors: Cameron Alex
Published: January 2020

Let a $2 \rightarrow 1$ directed hypergraph be a 3-uniform hypergraph where every edge has two tail vertices and one head vertex. For any such directed hypergraph $F$, let the $n$th extremal number of $F$ be the maximum number of edges that any directed hypergraph on $n$ vertices can have without containing a copy of $F$. In 2007, Langlois, Mubayi, Sloan, and Turán determined the exact extremal number for a particular directed hypergraph and found the extremal number up to asymptotic equivalence for a second directed hypergraph. Each of these forbidden graphs had exactly two edges. In this paper, we determine the exact extremal numbers for every $2 \rightarrow 1$ directed hypergraph that has exactly two edges.
Isoperimetric Numbers of Regular Graphs of High Degree with Applications to Arithmetic Riemann Surfaces
Authors: Lanphier Dominic , Rosenhouse Jason
Published: January 2020

We derive upper and lower bounds on the isoperimetric numbers and bisection widths of a large class of regular graphs of high degree. Our methods are combinatorial and do not require a knowledge of the eigenvalue spectrum. We apply these bounds to random regular graphs of high degree and the Platonic graphs over the rings $\mathbb{Z}_n$. In the latter case we show that these graphs are generally non-Ramanujan for composite $n$ and we also give sharp asymptotic bounds for the isoperimetric numbers. We conclude by giving bounds on the Cheeger constants of arithmetic Riemann surfaces. For a large class of these surfaces these bounds are an improvement over the known asymptotic bounds.
Avoidability of Formulas with Two Variables
Authors: Ochem Pascal , Rosenfeld Matthieu
Published: January 2020

In combinatorics on words, a word $w$ over an alphabet $\Sigma$ is said to avoid a pattern $p$ over an alphabet $\Delta$ of variables if there is no factor $f$ of $w$ such that $f=h(p)$ where $h:\Delta^*\to\Sigma^*$ is a non-erasing morphism. A pattern $p$ is said to be $k$-avoidable if there exists an infinite word over a $k$-letter alphabet that avoids $p$. We consider the patterns such that at most two variables appear at least twice,  or equivalently, the formulas with at most two variables. For each such formula, we determine whether it is $2$-avoidable, and if it is $2$-avoidable, we determine whether it is avoided by exponentially many binary words.
Vertex Subsets with Minimal Width and Dual Width in $Q$-Polynomial Distance-Regular Graphs
Authors: Tanaka Hajime
Published: January 2020

We study $Q$-polynomial distance-regular graphs from the point of view of what we call descendents, that is to say, those vertex subsets with the property that the width $w$ and dual width $w^*$ satisfy $w+w^*=d$, where $d$ is the diameter of the graph. We show among other results that a nontrivial descendent with $w\geq 2$ is convex precisely when the graph has classical parameters. The classification of descendents has been done for the $5$ classical families of graphs associated with short regular semilattices. We revisit and characterize these families in terms of posets consisting of descendents, and extend the classification to all of the $15$ known infinite families with classical parameters and with unbounded diameter.
Erdős-Ko-Rado Type Theorems for Simplicial Complexes
Authors: Seyed Fakhari Seyed Amin
Published: January 2020

It is shown that every shifted simplicial complex $\Delta$ is EKR of type $(r,s)$, provided that the size of every facet of $\Delta$ is at least $(2s+1)r-s$. It is moreover proven that every $i$-near-cone simplicial complex is EKR of type $(r,i)$ if ${\rm depth}_{\mathbb{K}}\Delta\geq (2i+1)r-i-1$, for some field $\mathbb{K}$. Furthermore, we prove that if $G$ is a graph having at least $(2i+1)r-i$ connected components, including $i$ isolated vertices, then its independence simplicial complex $\Delta_G$ is EKR of type $(r,i)$. The results of this paper, generalize the main result of Frankl (2013).
The Turán Polytope
Authors: Raymond Annie
Published: January 2020

The Turán hypergraph problem asks to find the maximum number of $r$-edges in a $r$-uniform hypergraph on $n$ vertices that does not contain a clique of size $a$. When $r=2$, i.e., for graphs, the answer is well-known and can be found in Turán's theorem. However, when $r\ge 3$, the problem remains open. We model the problem as an integer program and call the underlying polytope the Turán polytope. We draw parallels between the latter and the stable set polytope: we show that generalized and transformed versions of the web and wheel inequalities are also facet-defining for the Turán polytope. We also show that clique inequalities and what we call doubling inequalities are facet-defining when $r=2$. These facets lead to a simple new polyhedral proof of Turán's theorem.
Linear Recurrence Relations for Sums of Products of Two Terms
Authors: Mu Yan-Ping
Published: January 2020

For a sum of the form $\sum_k F({\boldsymbol n},k)G({\boldsymbol n},k)$, we set up two systems of equations involving shifts of $F({\boldsymbol n},k)$ and $G({\boldsymbol n},k)$. Then we solve the systems by utilizing the recursion of $F({\boldsymbol n},k)$ and the method of undetermined coefficients. From the solutions, we derive linear recurrence relations for the sum. With this method, we prove many identities involving Bernoulli numbers and Stirling numbers.
Self-Avoiding Walks and Amenability
Authors: Grimmett Geoffrey , Li Zhongyang
Published: January 2020

The connective constant $\mu(G)$ of an infinite transitive graph $G$ is the exponential growth rate of the number of self-avoiding walks from a given origin. The relationship between connective constants and amenability is explored in the current work.Various properties of connective constants depend on the existence of so-called 'unimodular graph height functions', namely: (i) whether $\mu(G)$ is a local function on certain graphs derived from $G$, (ii) the equality of $\mu(G)$ and the asymptotic growth rate of bridges, and (iii) whether there exists a terminating algorithm for approximating $\mu(G)$ to a given degree of accuracy.In the context of amenable groups, it is proved that the Cayley graphs of infinite, finitely generated, elementary amenable (and, more generally, virtually indicable) groups support unimodular graph height functions, which are in addition harmonic. In contrast, the Cayley graph of the Grigorchuk group, which is amenable but not elementary amenable, does not have a graph height function.In the context of non-amenable, transitive graphs, a lower bound is presented for the connective constant in terms of the spectral bottom of the graph. This is a strengthening of an earlier result of the same authors. Secondly, using a percolation inequality of Benjamini, Nachmias, and Peres, it is explained that the connective constant of a non-amenable, transitive graph with large girth is close to that of a regular tree. Examples are given of non-amenable groups without graph height functions, of which one is the Higman group.The emphasis of the work is upon the structure of Cayley graphs, rather than upon the algebraic properties of the underlying groups. New methods are needed since a Cayley graph generally possesses automorphisms beyond those arising through the action of the group.
Algebraic Properties of Chromatic Roots
Authors: Cameron Peter J. , Morgan Kerri
Published: January 2020

A chromatic root is a root of the chromatic polynomial of a graph.  Any chromatic root is an algebraic integer. Much is known about the location of chromatic roots in the real and complex numbers, but rather less about their properties as algebraic numbers. This question was the subject of a seminar at the Isaac Newton Institute in late 2008.  The purpose of this paper is to report on the seminar and subsequent developments.We conjecture that, for every algebraic integer $\alpha$, there is a natural number n such that $\alpha+n$ is a chromatic root. This is proved for quadratic integers; an extension to cubic integers has been found by Adam Bohn. The idea is to consider certain special classes of graphs for which the chromatic polynomial is a product of linear factors and one "interesting" factor of larger degree. We also report computational results on the Galois groups of irreducible factors of the chromatic polynomial for some special graphs. Finally, extensions to the Tutte polynomial are mentioned briefly.
Almost Tiling of the Boolean Lattice with Copies of a Poset
Authors: Tomon István
Published: January 2020

Let $P$ be a partially ordered set. If the Boolean lattice $(2^{[n]},\subset)$ can be partitioned into copies of $P$ for some positive integer $n$, then $P$ must satisfy the following two trivial conditions:(1) the size of $P$ is a power of $2$,(2) $P$ has a unique maximal and minimal element.Resolving a conjecture of Lonc, it was shown by Gruslys, Leader and Tomon that these conditions are sufficient as well.In this paper, we show that if $P$ only satisfies condition (2), we can still almost partition $2^{[n]}$ into copies of $P$. We prove that if $P$ has a unique maximal and minimal element, then there exists a constant $c=c(P)$ such that all but at most $c$ elements of $2^{[n]}$ can be covered by disjoint copies of $P$.
$\delta$-Connectivity in Random Lifts of Graphs
Authors: Silas Shashwat
Published: January 2020

Amit and Linial have shown that a random lift of a connected graph with minimum degree $\delta\ge3$ is asymptotically almost surely (a.a.s.) $\delta$-connected and mentioned the problem of estimating this probability as a function of the degree of the lift. Using a connection between a random $n$-lift of a graph and a randomly generated subgroup of the symmetric group on $n$-elements, we show that this probability is at least  $1 - O\left(\frac{1}{n^{\gamma(\delta)}}\right)$ where $\gamma(\delta)>0$ for $\delta\ge 5$ and it is strictly increasing with $\delta$. We extend this to show that one may allow $\delta$ to grow slowly as a function of the degree of the lift and the number of vertices and still obtain that random lifts are a.a.s. $\delta$-connected. We also simplify a later result showing a lower bound on the edge expansion of random lifts. On a related note, we calculate the probability that a subgroup of a wreath product of symmetric groups generated by random generators is transitive, extending a well known result of Dixon which covers the case for subgroups of the symmetric group.
Sharp Lower Bounds on the Spectral Radius of Uniform Hypergraphs Concerning Degrees
Authors: Kang Liying , Liu Lele , Shan Erfang
Published: January 2020

Let $\mathcal{A}(H)$ and $\mathcal{Q}(H)$ be the adjacency tensor and signless Laplacian tensor of an $r$-uniform hypergraph $H$. Denote by $\rho(H)$ and $\rho(\mathcal{Q}(H))$ the spectral radii of $\mathcal{A}(H)$ and $\mathcal{Q}(H)$, respectively. In this paper we present a  lower bound on $\rho(H)$ in terms of vertex degrees and we characterize the extremal hypergraphs attaining the bound, which solves a problem posed by Nikiforov [Analytic methods for uniform hypergraphs, Linear Algebra Appl. 457 (2014) 455–535]. Also, we prove a lower bound on $\rho(\mathcal{Q}(H))$ concerning degrees and give a characterization of the extremal hypergraphs attaining the bound.
Ideals and Quotients of Diagonally Quasi-Symmetric Functions
Authors: Li Shu Xiao
Published: January 2020

In 2004, J.-C. Aval, F. Bergeron and N. Bergeron studied the algebra of diagonally quasi-symmetric functions $\operatorname{\mathsf{DQSym}}$ in the ring $\mathbb{Q}[\mathbf{x},\mathbf{y}]$ with two sets of variables. They made conjectures on the structure of the quotient $\mathbb{Q}[\mathbf{x},\mathbf{y}]/\langle\operatorname{\mathsf{DQSym}}^+\rangle$, which is a quasi-symmetric analogue of the diagonal harmonic polynomials. In this paper, we construct a Hilbert basis for this quotient when there are infinitely many variables i.e. $\mathbf{x}=x_1,x_2,\dots$ and $\mathbf{y}=y_1,y_2,\dots$. Then we apply this construction to the case where there are finitely many variables, and compute the second column of its Hilbert matrix.
A Rational Catalan Formula for $(m,3)$-Hikita Polynomials
Authors: Kaliszewski Ryan , Karmakar Debdut
Published: January 2020

Hikita polynomials are the combinatorial side of the rational shuffle theorem. Building upon a recent formula for $(m,3)$-Catalan polynomials, we prove a formula for $(m,3)$-Hikita polynomials in terms of Catalan polynomials. This formula shows a surprising relation among coefficients of Hikita polynomials and implies deeper recursive relations and proves the $q,t$-symmetry of $(m,3)$-Hikita polynomials.
On the Number of $r$-Matchings in a Tree
Authors: Kang Dong Yeap , Kim Jaehoon , Kim Younjin , Law Hiu-Fai
Published: January 2020

An $r$-matching in a graph $G$ is a collection of edges in $G$ such that the distance between any two edges is at least $r$. This generalizes both matchings and induced matchings as matchings are $1$-matchings and induced matchings are $2$-matchings. In this paper, we study the minimum and maximum number of $r$-matchings in a tree with fixed order.
A Note on the Weak Dirac Conjecture
Authors: Han Zeye
Published: January 2020

We show that every set $\mathcal{P}$ of $n$ non-collinear points in the plane contains a point incident to at least $\lceil\frac{n}{3}\rceil+1$ of the lines determined by $\mathcal{P}$.
On Bipartite Cages of Excess 4
Authors: Filipovski Slobodan
Published: January 2020

The Moore bound $M(k,g)$ is a lower bound on the order of $k$-regular graphs of girth $g$ (denoted $(k,g)$-graphs). The excess $e$ of a $(k,g)$-graph of order $n$ is the difference $ n-M(k,g) $. In this paper we consider the existence of $(k,g)$-bipartite graphs of excess $4$ by studying spectral properties of their adjacency matrices. For a given graph $G$ and for the integers $i$ with $0\leq i\leq diam(G)$, the $i$-distance matrix $A_i$ of $G$ is an $n\times n$ matrix such that the entry in position $(u,v)$ is $1$ if the distance between the vertices $u$ and $v$ is $i$, and zero otherwise. We prove that the $(k,g)$-bipartite graphs of excess $4$ satisfy the equation $kJ=(A+kI)(H_{d-1}(A)+E)$, where $A=A_{1}$ denotes the adjacency matrix of the graph in question, $J$ the $n \times n$ all-ones matrix, $E=A_{d+1}$ the adjacency matrix of a union of vertex-disjoint cycles, and $H_{d-1}(x)$ is the Dickson polynomial of the second kind with parameter $k-1$ and degree $d-1$. We observe that the eigenvalues other than $\pm k$ of these graphs are roots of the polynomials $H_{d-1}(x)+\lambda$, where $\lambda$ is an eigenvalue of $E$. Based on the irreducibility of $H_{d-1}(x)\pm2$, we give necessary conditions for the existence of these graphs. If $E$ is the adjacency matrix of a cycle of order $n$, we call the corresponding graphs graphs with cyclic excess; if $E$ is the adjacency matrix of a disjoint union of two cycles, we call the corresponding graphs graphs with bicyclic excess. In this paper we prove the non-existence of $(k,g)$-graphs with cyclic excess $4$ if $k\geq6$ and $k \equiv1 \!\! \pmod {3}$, $g=8, 12, 16$ or $k \equiv2 \!\! \pmod {3}$, $g=8;$ and the non-existence of $(k,g)$-graphs with bicyclic excess $4$ if $k\geq7$ is an odd number and $g=2d$ such that $d\geq4$ is even.