bluuebunny/crossref_metadata_2025 huggingface dataset:
Mixed Ehrhart polynomials
Authors: Haase Christian , Juhnke-Kubitzke Martina , Sanyal Raman , Theobald Thorsten
Published: January 2020

For lattice polytopes $P_1,\ldots, P_k \subseteq \mathbb{R}^d$, Bihan (2016) introduced the discrete mixed volume $DMV(P_1,\dots,P_k)$ in analogy to the classical mixed volume.  In this note we study the associated mixed Ehrhart polynomial $ME_{P_1, \dots,P_k}(n) = DMV(nP_1, \dots, nP_k)$.  We provide a characterization of all mixed Ehrhart coefficients in terms of the classical multivariate Ehrhart polynomial. Bihan (2016) showed that the discrete mixed volume is always non-negative. Our investigations yield simpler proofs for certain special cases.We also introduce and study the associated mixed $h^*$-vector. We show that for large enough dilates $r  P_1, \ldots, rP_k$ the corresponding mixed $h^*$-polynomial has only real roots and as a consequence  the mixed $h^*$-vector becomes non-negative.
Minimal Weight in Union-Closed Families
Authors: Falgas-Ravry Victor
Published: January 2020

Let $\Omega$ be a finite set and let $\mathcal{S} \subseteq \mathcal{P}(\Omega)$ be a set system on $\Omega$. For $x\in \Omega$, we denote by $d_{\mathcal{S}}(x)$ the number of members of $\mathcal{S}$ containing $x$. A long-standing conjecture of Frankl states that if $\mathcal{S}$ is union-closed then there is some $x\in \Omega$ with $d_{\mathcal{S}}(x)\geq \frac{1}{2}|\mathcal{S}|$. We consider a related question. Define the weight of a family $\mathcal{S}$ to be $w(\mathcal{S}) := \sum_{A \in \mathcal{S}} |A|$. Suppose $\mathcal{S}$ is union-closed. How small can $w(\mathcal{S})$ be? Reimer showed $$w(\mathcal{S}) \geq \frac{1}{2} |\mathcal{S}| \log_2 |\mathcal{S}|,$$ and that this inequality is tight. In this paper we show how Reimer's bound may be improved if we have some additional information about the domain $\Omega$ of $\mathcal{S}$: if $\mathcal{S}$ separates the points of its domain, then $$w(\mathcal{S})\geq \binom{|\Omega|}{2}.$$ This is stronger than Reimer's Theorem when $\vert \Omega \vert > \sqrt{|\mathcal{S}|\log_2 |\mathcal{S}|}$. In addition we construct a family of examples showing the combined bound on $w(\mathcal{S})$ is tight except in the region $|\Omega|=\Theta (\sqrt{|\mathcal{S}|\log_2 |\mathcal{S}|})$, where it may be off by a multiplicative factor of $2$. Our proof also gives a lower bound on the average degree: if $\mathcal{S}$ is a point-separating union-closed family on $\Omega$, then $$ \frac{1}{|\Omega|} \sum_{x \in \Omega} d_{\mathcal{S}}(x) \geq \frac{1}{2} \sqrt{|\mathcal{S}| \log_2 |\mathcal{S}|}+ O(1),$$ and this is best possible except for a multiplicative factor of $2$.
Enumerating Matroids of Fixed Rank
Authors: Pendavingh Rudi , Van der Pol Jorn
Published: January 2020

It has been conjectured that asymptotically almost all matroids are sparse paving, i.e. that~$s(n) \sim m(n)$, where $m(n)$ denotes the number of matroids on a fixed groundset of size $n$, and $s(n)$ the number of sparse paving matroids. In an earlier paper, we showed that $\log s(n) \sim \log m(n)$. The bounds that we used for that result were dominated by matroids of rank $r\approx n/2$. In this paper we consider the relation between the number of sparse paving matroids $s(n,r)$ and the number of matroids $m(n,r)$ on a fixed groundset of size $n$ of fixed rank $r$. In particular, we show that $\log s(n,r) \sim \log m(n,r)$ whenever $r\ge 3$, by giving asymptotically matching upper and lower bounds.Our upper bound on $m(n,r)$ relies heavily on the theory of matroid erections as developed by Crapo and Knuth, which we use to encode any matroid as a stack of paving matroids. Our best result is obtained by relating to this stack of paving matroids an antichain that completely determines the matroid. We also obtain that the collection of essential flats and their ranks gives a concise description of matroids.
A Generalized Alon-Boppana Bound and Weak Ramanujan Graphs
Authors: Chung Fan
Published: January 2020

A basic eigenvalue bound due to Alon and Boppana holds only for regular graphs. In this paper we give a generalized Alon-Boppana bound for eigenvalues of graphs that are not required to be regular. We show that a graph $G$ with diameter $k$ and vertex set $V$, the smallest nontrivial eigenvalue $\lambda_1$ of the normalized Laplacian $\mathcal L$ satisfies$$ \lambda_1 \leq 1-\sigma \big(1- \frac c {k} \big)$$ for some constant $c$ where $\sigma = 2\sum_v d_v \sqrt{d_v-1}/\sum_v d_v^2 $ and $d_v$ denotes the degree of the vertex $v$.We consider weak Ramanujan graphs defined as graphs satisfying $ \lambda_1 \geq 1-\sigma$. We examine the vertex expansion and edge expansion of weak Ramanujan graphs and then use the expansion properties among other methods to derive the above Alon-Boppana bound. A corrigendum was added on the 3rd of November 2017.
The Cayley Isomorphism Property for Cayley Maps
Authors: Muzychuk Mikhail , Somlai Gábor
Published: January 2020

The Cayley Isomorphism property for combinatorial objects was introduced by L. Babai in 1977. Since then it has been intensively studied for binary relational structures: graphs, digraphs, colored graphs etc. In this paper we study this property for oriented Cayley maps. A Cayley map is a Cayley graph provided by a cyclic rotation of its connection set.  If the underlying graph is connected, then the map is an embedding of a Cayley graph into an oriented surface with the same cyclic rotation around every vertex.Two Cayley maps are called Cayley isomorphic if there exists a map isomorphism between them which is a group isomorphism too. We say that a finite group $H$ is a CIM-group if any two Cayley maps over $H$ are isomorphic if and only if they are Cayley isomorphic.The paper contains two main results regarding CIM-groups. The first one provides necessary conditons for being a CIM-group. It shows that a CIM-group should be one of the following$$\mathbb{Z}_m\times\mathbb{Z}_2^r, \\mathbb{Z}_m\times\mathbb{Z}_{4},\\mathbb{Z}_m\times\mathbb{Z}_{8}, \ \mathbb{Z}_m\times Q_8, \\mathbb{Z}_m\rtimes\mathbb{Z}_{2^e}, e=1,2,3,$$ where $m$ is an odd square-free number and $r$ a non-negative integer. Our second main result shows that the groups $\mathbb{Z}_m\times\mathbb{Z}_2^r$, $\mathbb{Z}_m\times\mathbb{Z}_{4}$, $\mathbb{Z}_m\times Q_8$ contained in the above list are indeed CIM-groups.
A Ternary Square-free Sequence Avoiding Factors Equivalent to $abcacba$
Authors: Currie James
Published: January 2020

We solve a problem of Petrova, finalizing the classification of letter patterns avoidable by ternary square-free words; we show that there is a ternary square-free word avoiding letter pattern $xyzxzyx$. In fact, wecharacterize all the (two-way) infinite ternary square-free words avoiding letter pattern $xyzxzyx$characterize the lexicographically least (one-way) infinite ternary square-free word avoiding letter pattern $xyzxzyx$show that the number of ternary square-free words of length $n$ avoiding letter pattern $xyzxzyx$ grows exponentially with $n$.
Stability Analysis for $k$-wise Intersecting Families
Authors: Kamat Vikram
Published: January 2020

We consider the following generalization of the seminal Erdős–Ko–Rado theorem, due to Frankl. For some $k\geq 2$, let $\mathcal{F}$ be a $k$-wise intersecting family of $r$-subsets of an $n$ element set $X$, i.e. for any $F_1,\ldots,F_k\in \mathcal{F}$, $\cap_{i=1}^k F_i\neq \emptyset$. If $r\leq \dfrac{(k-1)n}{k}$, then $|\mathcal{F}|\leq {n-1 \choose r-1}$. We prove a stability version of this theorem, analogous to similar results of Dinur-Friedgut, Keevash-Mubayi and others for the EKR theorem. The technique we use is a generalization of Katona's circle method, initially employed by Keevash, which uses expansion properties of a particular Cayley graph of the symmetric group.
Enumeration of Chord Diagrams without Loops and Parallel Chords
Authors: Krasko Evgeniy , Omelchenko Alexander
Published: January 2020

We enumerate chord diagrams without loops and without both loops and parallel chords. For labelled diagrams we obtain generating functions, for unlabelled ones we derive recurrence relations.
Chromatic Index, Treewidth and Maximum Degree
Authors: Bruhn Henning , Gellert Laura , Lang Richard
Published: January 2020

We conjecture that any graph $G$ with treewidth $k$ and maximum degree $\Delta(G)\geq k + \sqrt{k}$ satisfies $\chi'(G)=\Delta(G)$. In support of the conjecture we prove its fractional version. We also show that any graph $G$ with treewidth $k\geq 4$ and maximum degree $2k-1$ satisfies $\chi'(G)=\Delta(G)$, extending an old result of Vizing.
Symmetric Isostatic Frameworks with $\ell^1$ or $\ell^\infty$ Distance Constraints
Authors: Kitson Derek , Schulze Bernd
Published: January 2020

Combinatorial characterisations of minimal rigidity are obtained for symmetric $2$-dimensional bar-joint frameworks with either $\ell^1$ or $\ell^\infty$ distance constraints. The characterisations are expressed in terms of symmetric tree packings and the number of edges fixed by the symmetry operations. The proof uses new Henneberg-type inductive construction schemes.
Periods of Ehrhart Coefficients of Rational Polytopes
Authors: McAllister Tyrrell B. , Rochais Hélène O.
Published: January 2020

Let $\mathcal{P} \subset \mathbb{R}^{n}$ be a polytope whose vertices have rational coordinates. By a seminal result of E. Ehrhart, the number of integer lattice points in the $k$th dilate of $\mathcal{P}$ ($k$ a positive integer) is a quasi-polynomial function of $k$ — that is, a "polynomial" in which the coefficients are themselves periodic functions of $k$. It is an open problem to determine which quasi-polynomials are the Ehrhart quasi-polynomials of rational polytopes. As partial progress on this problem, we construct families of polytopes in which the periods of the coefficient functions take on various prescribed values.
Gröbner Bases Techniques for an $S$-Packing $k$-Coloring of a Graph
Authors: Maarouf Hamid
Published: January 2020

In this paper, polynomial ideal theory is used to deal with the problem of the $S$-packing coloring of a finite undirected and unweighted graph by introducing a family of polynomials encoding the problem. A method to find the $S$-packing colorings of the graph is presented and illustrated by examples.
Anagram-Free Graph Colouring
Authors: Wilson Tim E. , Wood David R.
Published: January 2020

An anagram is a word of the form $WP$ where $W$ is a non-empty word and $P$ is a permutation of $W$. We study anagram-free graph colouring and give bounds on the chromatic number. Alon et al.[Random Structures & Algorithms 2002] asked whether anagram-free chromatic number is bounded by a function of the maximum degree. We answer  this question in the negative by constructing graphs with maximum degree 3 and unbounded anagram-free chromatic number. We also prove upper and lower bounds on the anagram-free chromatic number of trees in terms of their radius and pathwidth. Finally, we explore extensions to edge colouring and $k$-anagram-free colouring.
Local Resilience for Squares of Almost Spanning Cycles in Sparse Random Graphs
Authors: Noever Andreas , Steger Angelika
Published: January 2020

In 1962, Pósa conjectured that a graph $G=(V, E)$ contains a square of a Hamiltonian cycle if $\delta(G)\ge 2n/3$. Only more than thirty years later Komlós, Sárkőzy, and Szemerédi proved this conjecture using the so-called Blow-Up Lemma. Here we extend their result to a random graph setting. We show that for every $\epsilon > 0$ and $p=n^{-1/2+\epsilon}$ a.a.s. every subgraph of $G_{n,p}$ with minimum degree at least $(2/3+\epsilon)np$ contains the square of a cycle on $(1-o(1))n$ vertices. This is almost best possible in three ways: (1) for $p\ll n^{-1/2}$ the random graph will not contain any square of a long cycle (2) one cannot hope for a resilience version for the square of a spanning cycle (as deleting all edges in the neighborhood of single vertex destroys this property) and (3) for $c<2/3$ a.a.s. $G_{n,p}$ contains a subgraph with minimum degree at least $cnp$ which does not contain the square of a path on $(1/3+c)n$ vertices.
A Step Towards Yuzvinsky's Conjecture
Authors: Gitler Isidoro , Reyes Enrique , Zaragoza Martínez Francisco Javier
Published: January 2020

An intercalate matrix $M$ of type $[r,s,n]$ is an $r\times s$ matrix with entries in $\{1,2,\dotsc,n\}$ such that all entries in each row are distinct, all entries in each column are distinct, and all $2 \times 2$ submatrices of $M$ have either $2$ or $4$ distinct entries. Yuzvinsky's Conjecture on intercalate matrices claims that the smallest $n$ for which there is an intercalate matrix of type $[r,s,n]$ is the Hopf-Stiefel function $r \circ s$. In this paper we prove that Yuzvinsky's Conjecture is asimptotically true for $\frac{5}{6}$ of integer pairs $(r,s)$. We prove the Conjecture for $r\le 8$, and we study it in the range $r,s\le 32$.
Counting racks of order $n$
Authors: Ashford Matthew , Riordan Oliver
Published: January 2020

A rack on $[n]$ can be thought of as a set of maps $(f_x)_{x \in [n]}$, where each $f_x$ is a permutation of $[n]$ such that $f_{(x)f_y} = f_y^{-1}f_xf_y$ for all $x$ and $y$. In 2013, Blackburn showed that the number of isomorphism classes of racks on $[n]$ is at least $2^{(1/4 - o(1))n^2}$ and at most $2^{(c + o(1))n^2}$, where $c \approx 1.557$; in this paper we improve the upper bound to $2^{(1/4 + o(1))n^2}$, matching the lower bound. The proof involves considering racks as loopless, edge-coloured directed multigraphs on $[n]$, where we have an edge of colour $y$ between $x$ and $z$ if and only if $(x)f_y = z$, and applying various combinatorial tools.
Quasi-Eulerian Hypergraphs
Authors: Bahmanian Amin , Šajna Mateja
Published: January 2020

We generalize the notion of an Euler tour in a graph in the following way. An Euler family in a hypergraph is a family of closed walks that jointly traverse each edge of the hypergraph exactly once. An Euler tourthus corresponds to an Euler family with a single component. We provide necessary and sufficient conditions for the existence of an Euler family in an arbitrary hypergraph, and in particular, we show that every 3-uniform hypergraph without cut edges admits an Euler family. Finally, we show that the problem of existence of an Euler family is polynomial on the class of all hypergraphs.This work complements existing results on rank-1 universal cycles and 1-overlap cycles in triple systems, as well as recent results by Lonc and Naroski, who showed that the problem of existence of an Euler tour in a hypergraph is NP-complete.
Multivariate Normal Limit Laws for the Numbers of Fringe Subtrees in $m$-ary Search Trees and Preferential Attachment Trees
Authors: Holmgren Cecilia , Janson Svante , Sileikis Matas
Published: January 2020

We study fringe subtrees of random $m$-ary search trees and of preferential attachment trees, by putting them in the context of generalised Pólya urns. In particular we show that for the random $m$-ary search trees with $ m\leq 26 $ and for the linear preferential attachment trees, the number of fringe subtrees that are isomorphic to an arbitrary fixed tree $ T $ converges to a normal distribution; more generally, we also prove multivariate normal distribution results for random vectors of such numbers for different fringe subtrees. Furthermore, we show that the number of protected nodes in random $m$-ary search trees for $m\leq 26$ has asymptotically a normal distribution.
An Inertial Lower Bound for the Chromatic Number of a Graph
Authors: Elphick Clive , Wocjan Pawel
Published: January 2020

Let $\chi(G$) and $\chi_f(G)$ denote the chromatic and fractional chromatic numbers of a graph $G$, and let $(n^+ , n^0 , n^-)$ denote the inertia of $G$. We prove that:\[1 + \max\left(\frac{n^+}{n^-} , \frac{n^-}{n^+}\right) \le \chi(G)\] and conjecture that \[ 1 + \max\left(\frac{n^+}{n^-} , \frac{n^-}{n^+}\right) \le \chi_f(G).\] We investigate extremal graphs for these bounds and demonstrate that this inertial bound is not a lower bound for the vector chromatic number. We conclude with a discussion of asymmetry between $n^+$ and $n^-$, including some Nordhaus-Gaddum bounds for inertia.
Coloring Chains for Compression with Uncertain Priors
Authors: Golowich Noah
Published: January 2020

Haramaty and Sudan considered the problem of transmitting a message between two people, Alice and Bob, when Alice's and Bob's priors on the message are allowed to differ by at most a given factor. To find a deterministic compression scheme for this problem, they showed that it is sufficient to obtain an upper bound on the chromatic number of a graph, denoted $U(N,s,k)$ for parameters $N,s,k$, whose vertices are nested sequences of subsets and whose edges are between vertices that have similar sequences of sets. In turn, there is a close relationship between the problem of determining the chromatic number of $U(N,s,k)$ and a local graph coloring problem considered by Erdős et al. We generalize the results of Erdős et al. by finding bounds on the chromatic numbers of graphs $H$ and $G$ when there is a homomorphism $\phi :H\rightarrow G$ that satisfies a nice property. We then use these results to improve upper and lower bounds on $\chi(U(N,s,k))$.
Circulant Homogeneous Factorisations of Complete Digraphs $\rm\bf K_{p^d}$ with $p$ an Odd Prime
Authors: Xu Jing
Published: January 2020

Let $\mathcal F=(\rm\bf K_{n},\mathcal P)$ be a circulant homogeneous factorisation of index $k$, that means $\mathcal P$ is a partition of the arc set of the complete digraph $\rm\bf K_n$ into $k$ circulant factor digraphs such that there exists $\sigma\in S_n$ permuting the factor circulants transitively amongst themselves. Suppose further such an element $\sigma$ normalises the cyclic regular automorphism group of these circulant factor digraphs, we say $\mathcal F$ is normal. Let $\mathcal F=(\rm\bf K_{p^d},\mathcal P)$ be a circulant homogeneous factorisation of index $k$ where $p^d$,  ($d\ge 1$) is an odd prime power. It is shown in this paper that either $\mathcal F$ is normal or $\mathcal F$ is a lexicographic product of two smaller circulant homogeneous factorisations.
Latin Squares with No Transversals
Authors: Cavenagh Nicholas J. , Wanless Ian M.
Published: January 2020

A $k$-plex in a latin square of order $n$ is a selection of $kn$ entries that includes $k$ representatives from each row and column and $k$ occurrences of each symbol. A $1$-plex is also known as a transversal.It is well known that if $n$ is even then $B_n$, the addition table for the integers modulo $n$, possesses no transversals. We show that there are a great many latin squares that are similar to $B_n$ and have no transversal. As a consequence, the number of species of transversal-free latin squares is shown to be at least $n^{n^{3/2}(1/2-o(1))}$ for even $n\rightarrow\infty$.We also produce various constructions for latin squares that have no transversal but do have a $k$-plex for some odd $k>1$. We prove a 2002 conjecture of the second author that for all even orders $n>4$ there is a latin square of order $n$ that contains a $3$-plex but no transversal. We also show that for odd $k$ and $m\geq 2$, there exists a latin square of order $2km$ with a $k$-plex but no $k'$-plex for odd $k'<k$.
Independent Sets in the Union of Two Hamiltonian Cycles
Authors: Aharoni Ron , Soltész Daniel
Published: January 2020

Motivated by a question on the maximal number of vertex disjoint Schrijver graphs in the Kneser graph, we investigate the following function, denoted by $f(n,k)$: the maximal number of Hamiltonian cycles on an $n$ element set, such that no two cycles share a common independent set of size more than $k$. We shall mainly be interested in the behavior of $f(n,k)$ when $k$ is a linear function of $n$, namely $k=cn$. We show a threshold phenomenon: there exists a constant $c_t$ such that for $c<c_t$, $f(n,cn)$ is bounded by a constant depending only on $c$ and not on $n$, and for $c_t <c$, $f(n,cn)$ is exponentially large in $n ~(n \to \infty)$. We prove that $0.26 < c_t < 0.36$, but the exact value of $c_t$ is not determined. For the lower bound we prove a technical lemma, which for graphs that are the union of two Hamiltonian cycles establishes a relation between the independence number and the number of $K_4$ subgraphs. A corollary of this lemma is that if a graph $G$ on $n>12$ vertices is the union of  two Hamiltonian cycles and $\alpha(G)=n/4$, then $V(G)$ can be covered by vertex-disjoint $K_4$ subgraphs.
Some New Groups which are not CI-groups with Respect to Graphs
Authors: Dobson Ted
Published: January 2020

A group $G$ is a CI-group with respect to graphs if two Cayley graphs of $G$ are isomorphic if and only if they are isomorphic by a group automorphism of $G$.  We show that an infinite family of groups which include $D_n\times F_{3p}$ are not CI-groups with respect to graphs, where $p$ is prime, $n\not = 10$ is relatively prime to $3p$, $D_n$ is the dihedral group of order $n$, and $F_{3p}$ is the nonabelian group of order $3p$.
Coincidences between Characters to Hook Partitions and 2-Part Partitions on Families arising from 2-Regular Classes
Authors: Bessenrodt Christine
Published: January 2020

Strongly refining results by Regev, Regev and Zeilberger, we prove surprising coincidences between characters to 2-part partitions of size $n$ and characters to hook partitions of size $n+2$ on two related families obtained by extending 2-regular conjugacy classes.
The Complete cd-Index of Dihedral and Universal Coxeter Groups
Authors: Blanco Saúl A.
Published: January 2020

We present a description, including a characterization, of the complete cd-index of dihedral intervals. Furthermore, we describe a method to compute the complete cd-index of intervals in universal Coxeter groups. To obtain such descriptions, we consider Bruhat intervals for which Björner and Wachs's CL-labeling can be extended to paths of different lengths in the Bruhat graph. While such an extension cannot be defined for all Bruhat intervals, it can be in dihedral and universal Coxeter systems.
Classical Sequences Revisited with Permutations Avoiding Dotted Pattern
Authors: Baril Jean-Luc
Published: January 2020

Inspired by the definition of the barred pattern-avoiding permutation, we introduce the new concept of dotted pattern for permutations. We investigate permutations classes avoiding dotted patterns of length at most 3, possibly along with other classical patterns. We deduce some enumerating results which allow us to exhibit new families of permutations counted by the classical sequences: $2^{n}$, Catalan, Motzkin, Pell, Fibonacci, Fine, Riordan, Padovan, Eulerian.
Neighborhood Reconstruction and Cancellation of Graphs
Authors: Hammack Richard H. , Mullican Cristina
Published: January 2020

We connect two seemingly unrelated problems in graph theory.Any graph $G$ has a neighborhood multiset $\mathscr{N}(G)= \{N(x) \mid x\in V(G)\}$ whose elements are precisely the open vertex-neighborhoods of $G$. In general there exist non-isomorphic graphs $G$ and $H$ for which $\mathscr{N}(G)=\mathscr{N}(H)$. The neighborhood reconstruction problem asks the conditions under which $G$ is uniquely reconstructible from its neighborhood multiset, that is, the conditions under which $\mathscr{N}(G)=\mathscr{N}(H)$ implies $G\cong H$. Such a graph is said to be neighborhood-reconstructible.The cancellation problem for the direct product of graphs seeks the conditions under which $G\times K\cong H\times K$ implies $G\cong H$. Lovász proved that this is indeed the case if $K$ is not bipartite. A second instance of the cancellation problem asks for conditions on $G$ that assure $G\times K\cong H\times K$ implies $G\cong H$ for any bipartite~$K$ with $E(K)\neq \emptyset$. A graph $G$ for which this is true is called a cancellation graph.We prove that the neighborhood-reconstructible graphs are precisely the cancellation graphs. We also present some new results on cancellation graphs, which have corresponding implications for neighborhood reconstruction. We are particularly interested in the (yet-unsolved) problem of finding a simple structural characterization of cancellation graphs (equivalently, neighborhood-reconstructible graphs).
On 1212-Avoiding Restricted Growth Functions
Authors: Lin Zhicong , Fu Shishuo
Published: January 2020

Restricted growth functions (RGFs) avoiding the pattern $1212$ are in natural bijection with noncrossing partitions. Motivated by recent work of Campbell et al., we study five classical statistics bk, ls, lb, rs and rb on $1212$-avoiding RGFs. We show the equidistribution of (ls, rb, lb, bk) and (rb, ls, lb, bk) on $1212$-avoiding RGFs by constructing a simple involution. To our surprise, this result was already proved by Simion 22 years ago via an involution on noncrossing partitions. Our involution, though turns out essentially the same as Simion's, is defined quite differently and has the advantage that makes the discussion more transparent. Consequently, a multiset-valued extension of Simion's result is discovered. Furthermore, similar approach enables us to prove the equidistribution of (mak, rb, rs, bk) and (rb, mak, rs, bk) on $1212$-avoiding RGFs, where "mak" is a set partition statistic introduced by Steingrímsson.Through two bijections to Motzkin paths, we also prove that the triple of classical permutation statistics (exc+1, den, inv — exc) on $321$-avoiding permutations is equidistributed with the triple (bk, rb, rs) on $1212$-avoiding RGFs, which generalizes another result of Simion. In the course, an interesting $q$-analog of the $\gamma$-positivity of Narayana polynomials is found.
On the Schur Expansion of Hall-Littlewood and Related Polynomials via Yamanouchi Words
Authors: Roberts Austin
Published: January 2020

This paper uses the theory of dual equivalence graphs to give explicit Schur expansions for several families of symmetric functions. We begin by giving a combinatorial definition of the modified Macdonald polynomials and modified Hall-Littlewood polynomials indexed by any diagram $\delta \subset {\mathbb Z} \times {\mathbb Z}$, written as $\widetilde H_{\delta}(X;q,t)$ and $\widetilde H_{\delta}(X;0,t)$, respectively. We then give an explicit Schur expansion of $\widetilde H_{\delta}(X;0,t)$ as a sum over a subset of the Yamanouchi words, as opposed to the expansion using the charge statistic given in 1978 by Lascoux and Schüztenberger. We further define the symmetric function $R_{\gamma,\delta}(X)$ as a refinement of $\widetilde H_{\delta}(X;0,t)$ and similarly describe its Schur expansion. We then analyze $R_{\gamma,\delta}(X)$ to determine the leading term of its Schur expansion. We also provide a conjecture towards the Schur expansion of $\widetilde H_{\delta}(X;q,t)$. To gain these results, we use a construction from the 2007 work of Sami Assaf to associate each Macdonald polynomial with a signed colored graph $\mathcal{H}_\delta$. In the case where a subgraph of $\mathcal{H}_\delta$ is a dual equivalence graph, we provide the Schur expansion of its associated symmetric function, yielding several corollaries.
Bounds on Parameters of Minimally Nonlinear Patterns
Authors: CrowdMath P. A.
Published: January 2020

Let $ex(n, P)$ be the maximum possible number of ones in any 0-1 matrix of dimensions $n \times n$ that avoids $P$. Matrix $P$ is called minimally non-linear if $ex(n, P) \neq O(n)$ but $ex(n, P') = O(n)$ for every proper subpattern $P'$ of $P$. We prove that the ratio between the length and width of any minimally non-linear 0-1 matrix is at most $4$, and that a minimally non-linear 0-1 matrix with $k$ rows has at most $5k-3$ ones. We also obtain an upper bound on the number of minimally non-linear 0-1 matrices with $k$ rows.In addition, we prove corresponding bounds for minimally non-linear ordered graphs. The minimal non-linearity that we investigate for ordered graphs is for the extremal function $ex_{<}(n, G)$, which is the maximum possible number of edges in any ordered graph on $n$ vertices with no ordered subgraph isomorphic to $G$.
A Note on the Rainbow Connection of Random Regular Graphs
Authors: Molloy Michael
Published: January 2020

We prove that a random 3-regular graph has rainbow connection number $O(\log n)$. This completes the remaining open case from Rainbow connection of random regular graphs, by Dudek, Frieze and Tsourakakis.
On the Connectivity of Graphs in Association Schemes
Authors: Kodalen Brian G. , Martin William J.
Published: January 2020

Let $(X,\mathcal{R})$ be a commutative association scheme and let $\Gamma=(X,R\cup R^\top)$ be a connected undirected  graph where $R\in \mathcal{R}$. Godsil (resp., Brouwer) conjectured that the edge connectivity (resp., vertex connectivity) of $\Gamma$ is equal to its valency. In this paper, we prove that the deletion of the neighborhood of any vertex leaves behind at most one non-singleton component. Two vertices $a,b\in X$  are called "twins" in $\Gamma$ if they have identical neighborhoods: $\Gamma(a)=\Gamma(b)$. We characterize twins in polynomial association schemes and show that, in the absence of twins, the deletion of any vertex and its neighbors in $\Gamma$ results in a connected graph. Using this and other tools, we find lower bounds on the connectivity of $\Gamma$, especially in the case where $\Gamma$ has diameter two.
On the Diameter of Dual Graphs of Stanley-Reisner Rings and Hirsch Type Bounds on Abstractions of Polytopes
Authors: Holmes Brent
Published: January 2020

Let $R$ be an equidimensional commutative Noetherian ring of positive dimension. The dual graph $\mathcal{G} (R)$ of $R$ is defined as follows: the vertices are the minimal prime ideals of $R$, and the edges are the pairs of prime ideals $(P_1,P_2)$ with height$(P_1 + P_2) = 1$. If $R$ satisfies Serre's property $(S_2)$, then $\mathcal{G} (R)$ is connected. In this note, we provide lower and upper bounds for the maximum diameter of dual graphs of Stanley-Reisner rings satisfying $(S_2)$. These bounds depend on the number of variables and the dimension. Dual graphs of $(S_2)$ Stanley-Reisner rings are a natural abstraction of the $1$-skeletons of polyhedra. We discuss how our bounds imply new Hirsch-type bounds on $1$-skeletons of polyhedra.
Promotion of Increasing Tableaux: Frames and Homomesies
Authors: Pechenik Oliver
Published: January 2020

A key fact about M.-P. Schützenberger's (1972) promotion operator on rectangular standard Young tableaux is that iterating promotion once per entry recovers the original tableau. For tableaux with strictly increasing rows and columns, H. Thomas and A. Yong (2009) introduced a theory of $K$-jeu de taquin with applications to $K$-theoretic Schubert calculus. The author (2014) studied a $K$-promotion operator $\mathcal{P}$ derived from this theory, but observed that this key fact does not generally extend to $K$-promotion of such increasing tableaux. Here, we show that the key fact holds for labels on the boundary of the rectangle. That is, for $T$ a rectangular increasing tableau with entries bounded by $q$, we have $\mathsf{Frame}(\mathcal{P}^q(T)) = \mathsf{Frame}(T)$, where $\mathsf{Frame}(U)$ denotes the restriction of $U$ to its first and last row and column. Using this fact, we obtain a family of homomesy results on the average value of certain statistics over $K$-promotion orbits, extending a $2$-row theorem of J. Bloom, D. Saracino, and the author (2016) to arbitrary rectangular shapes.
A Dual Ramsey Theorem for Permutations
Authors: Mašulović Dragan
Published: January 2020

In 2012 M. Sokić proved that the that the class of all finite permutations has the Ramsey property. Using different strategies the same result was then reproved in 2013 by J. Böttcher and J. Foniok, in 2014 by M. Bodirsky and in 2015 yet another proof was provided by M. Sokić.Using the categorical reinterpretation of the Ramsey property in this paper we prove that the class of all finite permutations has the dual Ramsey property as well. It was Leeb who pointed out in 1970 that the use of category theory can be quite helpful both in the formulation and in the proofs of results pertaining to structural Ramsey theory. In this paper we argue that this is even more the case when dealing with the dual Ramsey property.
On the Poset and Asymptotics of Tesler Matrices
Authors: O'Neill Jason
Published: January 2020

Tesler matrices are certain integral matrices counted by the Kostant partition function and have appeared recently in Haglund's study of diagonal harmonics. In 2014, Drew Armstrong defined a poset on such matrices and conjectured that the characteristic polynomial of this poset is a power of $q-1$. We use a method of Hallam and Sagan to prove a stronger version of this conjecture for posets of a certain class of generalized Tesler matrices. We also study bounds for the number of Tesler matrices and how they compare to the number of parking functions, the dimension of the space of diagonal harmonics.
On the Orchard Crossing Number of the Complete Bipartite Graphs $K_{n,n}$
Authors: Feder Elie , Garber David
Published: January 2020

We compute the Orchard crossing number, which is defined in a similar way to the rectilinear crossing number, for the complete bipartite graphs $K_{n,n}$.
The Orthomorphism Graph $\mathcal{L}_3(q)$
Authors: Evans Anthony B.
Published: January 2020

Orthomorphisms of groups and pairwise orthogonal orthomorphisms have been used in several constructions of combinatorial designs, in particular in the construction of mutually orthogonal sets of latin squares based on  groups. In this paper we will use difference equations to construct orthomorphisms in $\mathcal{L}_3(q)$, an orthomorphism graph of $GF(q)^{+}\times GF(3)^+$, and to establish lower bounds for the number of pairwise orthogonal orthomorphisms in $\mathcal{L}_3(q)$.
Maximum Size of a Family of Pairwise Graph-Different Permutations
Authors: Golowich Louis , Kim Chiheon , Zhou Richard
Published: January 2020

Two permutations of the vertices of a graph $G$ are called $G$-different if there exists an index $i$ such that $i$-th entry of the two permutations form an edge in $G$. We bound or determine the maximum size of a family of pairwise $G$-different permutations for various graphs $G$. We show that for all balanced bipartite graphs $G$ of order $n$ with minimum degree $n/2 - o(n)$, the maximum number of pairwise $G$-different permutations of the vertices of $G$ is $2^{(1-o(1))n}$. We also present examples of bipartite graphs $G$ with maximum degree $O(\log n)$ that have this property. We explore the problem of bounding the maximum size of a family of pairwise graph-different permutations when an unlimited number of disjoint vertices is added to a given graph. We determine this exact value for the graph of 2 disjoint edges, and present some asymptotic bounds relating to this value for graphs consisting of the union of $n/2$ disjoint edges.
Counting Lyndon Factors
Authors: Glen Amy , Simpson Jamie , Smyth W. F.
Published: January 2020

In this paper, we determine the maximum number of distinct Lyndon factors that a word of length $n$ can contain. We also derive formulas for the expected total number of Lyndon factors in a word of length $n$ on an alphabet of size $\sigma$, as well as the expected number of distinct Lyndon factors in such a word. The minimum number of distinct Lyndon factors in a word of length $n$ is $1$ and the minimum total number is $n$, with both bounds being achieved by $x^n$ where $x$ is a letter. A more interesting question to ask is what is the minimum number of distinct Lyndon factors in a Lyndon word of length $n$? In this direction, it is known (Saari, 2014) that a lower bound for the number of distinct Lyndon factors in a Lyndon word of length $n$ is $\lceil\log_{\phi}(n) + 1\rceil$, where $\phi$ denotes the golden ratio $(1 + \sqrt{5})/2$. Moreover, this lower bound is sharp when $n$ is a Fibonacci number and is attained by the so-called finite Fibonacci Lyndon words, which are precisely the Lyndon factors of the well-known infinite Fibonacci word $\boldsymbol{f}$ (a special example of an infinite Sturmian word). Saari (2014) conjectured that if $w$ is Lyndon word of length $n$, $n\ne 6$, containing the least number of distinct Lyndon factors over all Lyndon words of the same length, then $w$ is a Christoffel word (i.e., a Lyndon factor of an infinite Sturmian word). We give a counterexample to this conjecture. Furthermore, we generalise Saari's result on the number of distinct Lyndon factors of a Fibonacci Lyndon word by determining the number of distinct Lyndon factors of a given Christoffel word. We end with two open problems.
Relaxations of GF(4)-Representable Matroids
Authors: Clark Ben , Oxley James , Van Zwam Stefan H.M.
Published: January 2020

We consider the $\mathrm{GF}(4)$-representable matroids with a circuit-hyperplane such that the matroid obtained by relaxing the circuit-hyperplane is also $\mathrm{GF}(4)$-representable. We characterize the structure of these matroids as an application of structure theorems for the classes of $U_{2,4}$-fragile and $\{U_{2,5},U_{3,5}\}$-fragile matroids. In addition, we characterize the forbidden submatrices in $\mathrm{GF}(4)$-representations of these matroids.
Cohomology Classes of Interval Positroid Varieties and a Conjecture of Liu
Authors: Pawlowski Brendan
Published: January 2020

To each finite subset of $\mathbb{Z}^2$ (a diagram), one can associate a subvariety of a complex Grassmannian (a diagram variety), and a representation of a symmetric group (a Specht module). Liu has conjectured that the cohomology class of a diagram variety is represented by the Frobenius characteristic of the corresponding Specht module. We give a counterexample to this conjecture.However, we show that for the diagram variety of a permutation diagram, Liu's conjectured cohomology class $\sigma$ is at least an upper bound on the actual class $\tau$, in the sense that $\sigma - \tau$ is a nonnegative linear combination of Schubert classes. To do this, we exhibit the appropriate diagram variety as a component in a degeneration of one of Knutson's interval positroid varieties (up to Grassmann duality). A priori, the cohomology classes of these interval positroid varieties are represented by affine Stanley symmetric functions. We give a different formula for these classes as ordinary Stanley symmetric functions, one with the advantage of being Schur-positive and compatible with inclusions between Grassmannians.
Non-Flat Regular Polytopes and Restrictions on Chiral Polytopes
Authors: Cunningham Gabe
Published: January 2020

An abstract polytope is flat if every facet is incident on every vertex. In this paper, we prove that no chiral polytope has flat finite regular facets and finite regular vertex-figures. We then determine the three smallest non-flat regular polytopes in each rank, and use this to show that for $n \geq 8$, a chiral $n$-polytope has at least $48(n-2)(n-2)!$ flags.
Fair Splitting of Colored Paths
Authors: Alishahi Meysam , Meunier Frédéric
Published: January 2020

This paper deals with two problems about splitting fairly a path with colored vertices, where "fairly" means that each part contains almost the same amount of vertices in each color.Our first result states that it is possible to remove one vertex per color from a path with colored vertices so that the remaining vertices can be fairly split into two independent sets of the path. It implies in particular a conjecture of Ron Aharoni and coauthors. The proof uses the octahedral Tucker lemma.Our second result is the proof of a particular case of a conjecture of Dömötör Pálvölgyi about fair splittings of necklaces for which one can decide which thieves are advantaged. The proof is based on a rounding technique introduced by Noga Alon and coauthors to prove the discrete splitting necklace theorem from the continuous one.
A Classification of Motzkin Numbers Modulo 8
Authors: Wang Ying , Xin Guoce
Published: January 2020

The well-known Motzkin numbers were conjectured by Deutsch and Sagan to be nonzero when modulo $8$. The conjecture was first proved by Sen-Peng Eu, Shu-chung Liu and Yeong-Nan Yeh by using the factorial representation of the Catalan numbers. We present a short proof by finding a recursive formula for Motzkin numbers modulo $8$. Moreover, such a recursion leads to a full classification of Motzkin numbers modulo $8$. An addendum was added on April 3 2018.
Clique Colourings of Geometric Graphs
Authors: McDiarmid Colin , Mitsche Dieter , Prałat Pawel
Published: January 2020

A clique colouring of a graph is a colouring of the vertices such that no maximal clique is monochromatic (ignoring isolated vertices). The least number of colours in such a colouring is the clique chromatic number.  Given $n$ points $\mathbf{x}_1, \ldots,\mathbf{x}_n$ in the plane, and a threshold $r>0$, the corresponding geometric graph has vertex set $\{v_1,\ldots,v_n\}$, and distinct $v_i$ and $v_j$ are adjacent when the Euclidean distance between $\mathbf{x}_i$ and $\mathbf{x}_j$ is at most $r$. We investigate the clique chromatic number of such graphs.We first show that the clique chromatic number is at most 9 for any geometric graph in the plane, and briefly consider geometric graphs in higher dimensions. Then we study the asymptotic behaviour of the clique chromatic number for the random geometric graph $\mathcal{G}$ in the plane, where $n$ random points are independently and uniformly distributed in a suitable square. We see that as $r$ increases from 0, with high probability the clique chromatic number is 1 for very small $r$, then 2 for small $r$, then at least 3 for larger $r$, and finally drops back to 2.
Coloring Cross-Intersecting Families
Authors: Cherkashin Danila
Published: January 2020

Intersecting and cross-intersecting families usually appear in extremal combinatorics in the vein of the Erdős-Ko-Rado theorem. On the other hand, P. Erdős and L. Lovász in their noted 1975 paper posed problems on coloring intersecting families as a restriction of classical hypergraph coloring problems to a special class of hypergraphs. This note deals with the mentioned coloring problems stated for cross-intersecting families.
The $r$-Matching Sequencibility of Complete Graphs
Authors: Mammoliti Adam
Published: January 2020

Alspach [ Bull. Inst. Combin. Appl., 52 (2008), pp. 7--20] defined the maximal matching sequencibility of a graph $G$, denoted $ms(G)$, to be the largest integer $s$ for which there is an ordering of the edges of $G$ such that every $s$ consecutive edges form a matching. Alspach also proved that $ms(K_n) = \bigl\lfloor\frac{n-1}{2}\bigr\rfloor$. Brualdi et al. [Australas. J. Combin., 53 (2012), pp. 245--256] extended the definition to cyclic matching sequencibility of a graph $G$, denoted $cms(G)$, which allows cyclical orderings and proved that $cms(K_n) = \bigl\lfloor\frac{n-2}{2}\bigr\rfloor$.In this paper, we generalise these definitions to require that every $s$ consecutive edges form a subgraph where every vertex has degree at most $r\geq 1$, and we denote the maximum such number for a graph $G$ by $ms_r(G)$ and $cms_r(G)$ for the non-cyclic and cyclic cases, respectively. We conjecture that $ms_r(K_n) = \bigl\lfloor\frac{rn-1}{2}\bigr\rfloor$ and ${\bigl\lfloor\frac{rn-1}{2}\bigr\rfloor-1}\leq cms_r(K_n)  \leq  \bigl\lfloor\frac{rn-1}{2}\bigr\rfloor$ and that both bounds are attained for some $r$ and $n$. We prove these conjectured identities for the majority of cases, by defining and characterising selected decompositions of $K_n$. We also provide bounds on $ms_r(G)$ and $cms_r(G)$ as well as results on hypergraph analogues of $ms_r(G)$ and $cms_r(G)$.
Lecture Hall Partitions and the Affine Hyperoctahedral Group
Authors: Hanusa Christopher R. H. , Savage Carla D.
Published: January 2020

In 1997 Bousquet-Mélou and Eriksson introduced lecture hall partitions as the inversion vectors of elements of the parabolic quotient $\widetilde{C}/C$.  We provide a new view of their correspondence that allows results in one domain to be translated into the other.  We determine the equivalence between combinatorial statistics in each domain and use this correspondence to translate certain generating function formulas on lecture hall partitions to new observations about $\widetilde{C}/C$.
Cubic Graphs with Small Independence Ratio
Authors: Balogh József , Kostochka Alexandr , Liu Xujun
Published: January 2020

Let $i(r,g)$ denote the infimum of the ratio $\frac{\alpha(G)}{|V(G)|}$ over the $r$-regular graphs of girth at least $g$, where $\alpha(G)$ is the independence number of $G$, and  let $i(r,\infty) := \lim\limits_{g \to \infty} i(r,g)$. Recently, several new lower bounds of $i(3,\infty)$ were obtained. In particular, Hoppen and Wormald showed in 2015 that $i(3, \infty) \geqslant 0.4375,$ and Csóka improved it to $i(3,\infty) \geqslant 0.44533$ in 2016. Bollobás proved the upper bound  $i(3,\infty) < \frac{6}{13}$  in 1981, and McKay improved it to $i(3,\infty) < 0.45537$in 1987. There were no improvements since then. In this paper, we improve the upper bound to $i(3,\infty) \leqslant 0.454.$
Distinguishing Graphs of Maximum Valence 3
Authors: Hüning Svenja , Imrich Wilfried , Kloas Judith , Schreber Hannah , Tucker Thomas W.
Published: January 2020

The distinguishing number $D(G)$ of a graph $G$ is the smallest number of colors that is needed to color the vertices such that the only color-preserving automorphism fixes all vertices. We give a complete classification for all connected graphs $G$ of maximum valence $\Delta(G) = 3$ and distinguishing number $D(G) = 3$. As one of the consequences we show that all infinite connected graphs with $\Delta(G) = 3$ are $2$-distinguishable.
Transversals, Plexes, and Multiplexes in Iterated Quasigroups
Authors: Taranenko Anna
Published: January 2020

A $d$-ary quasigroup of order $n$ is a $d$-ary operation over a set of cardinality $n$ such that the Cayley table of the operation is a $d$-dimensional latin hypercube of the same order. Given a binary quasigroup $G$, the $d$-iterated quasigroup $G^{\left[d\right]}$ is a $d$-ary quasigroup that is a $d$-time composition of $G$ with itself. A $k$-multiplex (a $k$-plex) $K$ in a $d$-dimensional latin hypercube $Q$ of order $n$ or in the corresponding $d$-ary quasigroup is a multiset (a set) of $kn$ entries such that each hyperplane and each symbol of $Q$ is covered by exactly $k$ elements of $K$. It is common to call 1-plexes transversals. In this paper we prove that there exists a constant $c(G,k)$ such that if a $d$-iterated quasigroup $G$ of order $n$ has a $k$-multiplex then for large $d$ the number of its $k$-multiplexes is asymptotically equal to $c(G,k) \left(\frac{(kn)!}{k!^n}\right)^{d-1}$. As a corollary we obtain that if the number of transversals in the Cayley table of a $d$-iterated quasigroup $G$ of order $n$ is nonzero then asymptotically it is $c(G,1)  n!^{d-1}$.  In addition, we  provide limit constants and recurrence formulas for the numbers of transversals in two iterated quasigroups of order $5$, characterize a typical $k$-multiplex and estimate numbers of partial $k$-multiplexes and transversals in $d$-iterated quasigroups.
On the Smallest Snarks with Oddness 4 and Connectivity 2
Authors: Goedgebeur Jan
Published: January 2020

A snark is a bridgeless cubic graph which is not 3-edge-colourable. The oddness of a bridgeless cubic graph is the minimum number of odd components in any 2-factor of the graph.Lukot'ka, Máčajová, Mazák and Škoviera showed in [Electron. J. Combin. 22 (2015)] that the smallest snark with oddness 4 has 28 vertices and remarked that there are exactly two such graphs of that order. However, this remark is incorrect as — using an exhaustive computer search — we show that there are in fact three snarks with oddness 4 on 28 vertices. In this note we present the missing snark and also determine all snarks with oddness 4 up to 34 vertices.
On Bipartite $Q$-Polynomial Distance-Regular Graphs with Diameter 9, 10, or 11
Authors: Miklavič Štefko
Published: January 2020

Let $\Gamma$ denote a bipartite distance-regular graph with diameter $D$. In [Caughman (2004)], Caughman showed that if $D \ge 12$, then $\Gamma$ is $Q$-polynomial if and only if one of the following (i)-(iv) holds: (i) $\Gamma$ is the ordinary $2D$-cycle, (ii) $\Gamma$ is the Hamming cube $H(D,2)$, (iii) $\Gamma$ is the antipodal quotient of the Hamming cube $H(2D,2)$, (iv) the intersection numbers of $\Gamma$ satisfy $c_i = (q^i - 1)/(q-1)$, $b_i = (q^D-q^i)/(q-1)$ $(0 \le i \le D)$, where $q$ is an integer at least $2$. In this paper we show that the above result is true also for bipartite distance-regular graphs with $D \in \{9,10,11\}$.