bluuebunny/crossref_metadata_2025 huggingface dataset:
Local Fusion Graphs and Sporadic Simple Groups
Authors: Ballantyne John , Rowley Peter
Published: January 2020

For a group $G$ with $G$-conjugacy class of involutions $X$, the local fusion graph $\mathcal{F}(G,X)$ has $X$ as its vertex set, with distinct vertices $x$ and $y$ joined by an edge if, and only if, the product $xy$ has odd order. Here we show that, with only three possible exceptions, for all pairs $(G,X)$ with $G$ a sporadic simple group or the automorphism group of a sporadic simple group, $\mathcal{F}(G,X)$ has diameter $2$.
Building Graphs from Colored Trees
Authors: Esselstein Rachel M. , Winkler Peter
Published: January 2020

We will explore the computational complexity of satisfying certain sets of neighborhood conditions in graphs with various properties. More precisely, fix a radius $\rho$ and let $N(G)$ be the set of isomorphism classes of $\rho$-neighborhoods of vertices of $G$ where $G$ is a graph whose vertices are colored (not necessarily properly) by colors from a fixed finite palette. The root of the neighborhood will be the unique vertex at the "center" of the graph. Given a set $\mathcal{S}$ of colored graphs with a unique root, when is there a graph $G$ with $N(G)=\mathcal{S}$? Or $N(G) \subset \mathcal{S}$? What if $G$ is forced to be infinite, or connected, or both? If the neighborhoods are unrestricted, all these problems are recursively unsolvable; this follows from the work of Bulitko [Graphs with prescribed environments of the vertices. Trudy Mat. Inst. Steklov., 133:78–94, 274, 1973]. In contrast, when the neighborhoods are cycle free, all the problems are in the class $\mathtt{P}$. Surprisingly, if $G$ is required to be a regular (and thus infinite) tree, we show the realization problem is NP-complete (for degree 3 and higher); whereas, if $G$ is allowed to be any finite graph, the realization problem is in P.
Iterative Properties of Birational Rowmotion II: Rectangles and Triangles
Authors: Grinberg Darij , Roby Tom
Published: January 2020

Birational rowmotion — a birational map associated to any finite poset $P$ — has been introduced by Einstein and Propp as a far-reaching generalization of the (well-studied) classical rowmotion map on the set of order ideals of $P$. Continuing our exploration of this birational rowmotion, we prove that it has order $p+q$ on the $\left(  p, q\right)  $-rectangle poset (i.e., on the product of a $p$-element chain with a $q$-element chain); we also compute its orders on some triangle-shaped posets. In all cases mentioned, it turns out to have finite (and explicitly computable) order, a property it does not exhibit for general finite posets (unlike classical rowmotion, which is a permutation of a finite set). Our proof in the case of the rectangle poset uses an idea introduced by Volkov (arXiv:hep-th/0606094) to prove the $AA$ case of the Zamolodchikov periodicity conjecture; in fact, the finite order of birational rowmotion on many posets can be considered an analogue to Zamolodchikov periodicity. We comment on suspected, but so far enigmatic, connections to the theory of root posets.
Thin Lehman Matrices and Their Graphs
Authors: Wang Jonathan
Published: January 2020

Two square $0,1$ matrices $A,B$ are a pair of Lehman matrices if $AB^T = J+dI$, where $J$ is the matrix of all $1$s and $d$ is a positive integer. It is known that there are infinitely many such matrices when $d=1$, and these matrices are called thin Lehman matrices. An induced subgraph of the Johnson graph may be defined given any Lehman matrix, where the vertices of the graph correspond to rows of the matrix. These graphs are used to study thin Lehman matrices. We show that any connected component of such a graph determines the corresponding rows of the matrix up to permutations of the columns. We also provide a sharp bound on the maximum clique size of such graphs and give a complete classification of Lehman matrices whose graphs have at most two connected components. Some constraints on when a circulant matrix can be Lehman are also provided. Many general classes of thin Lehman matrices are constructed in the paper.
Invariant and Coinvariant Spaces for the Algebra of Symmetric Polynomials in Non-Commuting Variables
Authors: Bergeron François , Lauve Aaron
Published: January 2020

We analyze the structure of the algebra $\mathbb{K}\langle\mathbf{x}\rangle^{\mathfrak{S}_n}$ of symmetric polynomials in non-commuting variables in so far as it relates to $\mathbb{K}[\mathbf{x}]^{\mathfrak{S}_n}$, its commutative counterpart. Using the "place-action" of the symmetric group, we are able to realize the latter as the invariant polynomials inside the former. We discover a tensor product decomposition of $\mathbb{K}\langle\mathbf{x}\rangle^{\mathfrak{S}_n}$ analogous to the classical theorems of Chevalley, Shephard-Todd on finite reflection groups. Résumé. Nous analysons la structure de l'algèbre $\mathbb{K}\langle\mathbf{x}\rangle^{\mathfrak{S}_n}$ des polynômes symétriques en des variables non-commutatives pour obtenir des analogues des résultats classiques concernant la structure de l'anneau $\mathbb{K}[\mathbf{x}]^{\mathfrak{S}_n}$ des polynômes symétriques en des variables commutatives. Plus précisément, au moyen de "l'action par positions", on réalise $\mathbb{K}[\mathbf{x}]^{\mathfrak{S}_n}$ comme sous-module de $\mathbb{K}\langle\mathbf{x}\rangle^{\mathfrak{S}_n}$. On découvre alors une nouvelle décomposition de $\mathbb{K}\langle\mathbf{x}\rangle^{\mathfrak{S}_n}$ comme produit tensorial, obtenant ainsi un analogues des théorèmes classiques de Chevalley et Shephard-Todd.
Limits of Boolean Functions on $\mathbb{F}_p^n$
Authors: Hatami Hamed , Hatami Pooya , Hirst James
Published: January 2020

We study sequences of functions of the form $\mathbb{F}_p^n \to \{0,1\}$ for varying $n$, and define a notion of convergence based on the induced distributions from restricting the functions to a random affine subspace. Using a decomposition theorem   and a recently proven equi-distribution theorem from higher order Fourier analysis, we prove that the limits of such convergent sequences can be represented by certain measurable functions.  We also show that every such limit object arises as the limit of some sequence of functions. These results are in the spirit of similar results which have been developed for limits of graph sequences. A more general, albeit substantially more sophisticated, limit object was recently constructed by Balázs Szegedy [Gowers norms, regularization and limits of functions on abelian groups. 2010. arXiv:1010.6211].
Enumerating Hamiltonian Cycles
Authors: Pettersson Ville H.
Published: January 2020

A dynamic programming method for enumerating hamiltonian cycles in arbitrary graphs is presented. The method is applied to grid graphs, king's graphs, triangular grids, and three-dimensional grid graphs, and results are obtained for larger cases than previously published. The approach can easily be modified to enumerate hamiltonian paths and other similar structures.
Generalizing the Divisibility Property of Rectangle Domino Tilings
Authors: Tong Forest
Published: January 2020

We introduce a class of graphs called compound graphs, which are constructed out of copies of a planar bipartite base graph, and explore the number of perfect matchings of compound graphs. The main result is that the number of matchings of every compound graph is divisible by the number of matchings of its base graph. Our approach is to use Kasteleyn's theorem to prove a key lemma, from which the divisibility theorem follows combinatorially. This theorem is then applied to provide a proof of Problem 21 of Propp's Enumeration of Matchings, a divisibility property of rectangles. Finally, we present a new proof, in the same spirit, of Ciucu's factorization theorem.
Words with Intervening Neighbours in Infinite Coxeter Groups are Reduced
Authors: Eriksson Henrik , Eriksson Kimmo
Published: January 2020

Consider a graph with vertex set $S$. A word in the alphabet $S$ has the intervening neighbours property if any two occurrences of the same letter are separated by all its graph neighbours. For a Coxeter graph, words represent group elements. Speyer recently proved that words with the intervening neighbours property are reduced if the group is infinite and irreducible. We present a new and shorter proof using the root automaton for recognition of reduced words.
Decompositions of Complete Graphs into Bipartite 2-Regular Subgraphs
Authors: Bryant Darryn , Burgess Andrea , Danziger Peter
Published: January 2020

It is shown that if $G$ is any bipartite 2-regular graph of order at most $n/2$ or at least $n-2$, then the obvious necessary conditions are sufficient for the existence of a decomposition of the complete graph of order $n$ into a perfect matching and edge-disjoint copies of $G$.
Wilf-Classification of Mesh Patterns of Short Length
Authors: Hilmarsson Ísak , Jónsdóttir Ingibjörg , Sigurðardóttir Steinunn , Viðarsdóttir Lína , Ulfarsson Henning
Published: January 2020

This paper starts the Wilf-classification of mesh patterns of length 2. Although there are initially 1024 patterns to consider we introduce automatic methods to reduce the number of potentially different Wilf-classes to at most 65. By enumerating some of the remaining classes we bring that upper-bound further down to 56. Finally, we conjecture that the actual number of Wilf-classes of mesh patterns of length 2 is 46.
Maximal Partial Latin Cubes
Authors: Britz Thomas , Cavenagh Nicholas J. , Sørensen Henrik Kragh
Published: January 2020

We prove that each maximal partial Latin cube must have more than $29.289\%$ of its cells filled and show by construction that this is a nearly tight bound. We also prove upper and lower bounds on the number of cells containing a fixed symbol in maximal partial Latin cubes and hypercubes, and we use these bounds to determine for small orders $n$ the numbers $k$ for which there exists a maximal partial Latin cube of order $n$ with exactly $k$ entries. Finally, we prove that maximal partial Latin cubes of order $n$ exist of each size from approximately half-full ($n^3/2$ for even $n\geq 10$ and $(n^3+n)/2$ for odd $n\geq 21$) to completely full, except for when either precisely $1$ or $2$ cells are empty.
Cross-Intersecting Erdős-Ko-Rado Sets in Finite Classical Polar Spaces
Authors: Ihringer Ferdinand
Published: January 2020

A cross-intersecting Erdős-Ko-Rado set of generators of a finite classical polar space is a pair $(Y, Z)$ of sets of generators such that all $y \in Y$ and $z \in Z$ intersect in at least a point. We provide upper bounds on $|Y| \cdot |Z|$ and classify the cross-intersecting Erdős-Ko-Rado sets of maximum size with respect to $|Y| \cdot |Z|$ for all polar spaces except some Hermitian polar spaces.
Weight of 3-Paths in Sparse Plane Graphs
Authors: Aksenov V. A. , Borodin O. V. , Ivanova A. O.
Published: January 2020

We prove precise upper bounds for the minimum weight of a path on three vertices in several natural classes of plane graphs with minimum degree 2 and girth $g$ from 5 to 7. In particular, we disprove a conjecture by S. Jendrol' and M. Maceková concerning the case $g=5$ and prove the tightness of their upper bound for $g=5$ when no vertex is adjacent to more than one vertex of degree 2. For $g\ge8$, the upper bound recently found by Jendrol' and Maceková is tight.
A New Approach to the Dyson Coefficients
Authors: Pang Sabrina X.M. , Lv Lun
Published: January 2020

In this paper, we introduce a direct method to evaluate the Dyson coefficients.
Even More Infinite Ball Packings from Lorentzian Root Systems
Authors: Chen Hao
Published: January 2020

Boyd (1974) proposed a class of infinite ball packings that are generated by inversions. Later, Maxwell (1983) interpreted Boyd's construction in terms of root systems in Lorentz spaces. In particular, he showed that the space-like weight vectors correspond to a ball packing if and only if the associated Coxeter graph is of "level 2"'. In Maxwell's work, the simple roots form a basis of the representations space of the Coxeter group. In several recent studies, the more general based root system is considered, where the simple roots are only required to be positively independent. In this paper, we propose a geometric version of "level'' for root systems to replace Maxwell's graph theoretical "level''. Then we show that Maxwell's results naturally extend to the more general root systems with positively independent simple roots. In particular, the space-like extreme rays of the Tits cone correspond to a ball packing if and only if the root system is of level $2$. We also present a partial classification of level-$2$ root systems, namely the Coxeter $d$-polytopes of level-$2$ with $d+2$ facets.
On-line List Colouring of Random Graphs
Authors: Frieze Alan , Mitsche Dieter , Pérez-Giménez Xavier , Prałat Paweł
Published: January 2020

In this paper, the on-line list colouring of binomial random graphs $\mathcal{G}(n,p)$ is studied. We show that the on-line choice number of $\mathcal{G}(n,p)$ is asymptotically almost surely asymptotic to the chromatic number of $\mathcal{G}(n,p)$, provided that the average degree $d=p(n-1)$ tends to infinity faster than $(\log \log n)^{1/3} (\log n)^2 n^{2/3}$. For sparser graphs, we are slightly less successful; we show that if $d \ge (\log n)^{2+\epsilon}$ for some $\epsilon>0$, then the on-line choice number is larger than the chromatic number by at most a multiplicative factor of $C$, where $C \in [2,4]$, depending on the range of $d$. Also, for $d=O(1)$, the on-line choice number is by at most a multiplicative constant factor larger than the chromatic number.
Closing the Gap on Path-Kipas Ramsey Numbers
Authors: Li Binlong , Zhang Yanbo , Bielak Halina , Broersma Hajo , Holub Premek
Published: January 2020

Given two graphs $G_1$ and $G_2$, the Ramsey number $R(G_1, G_2)$ is the smallest integer $N$ such that, for any graph $G$ of order $N$, either $G_1$ is a subgraph of $G$, or $G_2$ is a subgraph of the complement of $G$. Let $P_n$ denote a path of order $n$ and $\widehat{K}_m$ a kipas of order $m+1$, i.e., the graph obtained from a $P_m$ by adding one new vertex $v$ and edges from $v$ to all vertices of the $P_m$.We close the gap in existing knowledge on exact values of the Ramsey numbers $R(P_n,\widehat{K}_m)$ by determining the exact values for the remaining open cases.
Note on Highly Connected Monochromatic Subgraphs in $2$-Colored Complete Graphs
Authors: Fujita Shinya , Magnant Colton
Published: January 2020

In this note, we improve upon some recent results concerning the existence of large monochromatic, highly connected subgraphs in a $2$-coloring of a complete graph. In particular, we show that if $n\ge 6.5(k - 1)$, then in any $2$-coloring of the edges of $K_{n}$, there exists a monochromatic $k$-connected subgraph of order at least $n - 2(k - 1)$. Our result improves upon several recent results by a variety of authors.
Closing Gaps in Problems related to Hamilton Cycles in Random Graphs and Hypergraphs
Authors: Ferber Asaf
Published: January 2020

We show how to adjust a very nice coupling argument due to McDiarmid in order to prove/reprove in a novel way results concerning Hamilton cycles in various models of random graph and hypergraphs. In particular, we firstly show that for $k\geq 3$, if $pn^{k-1}/\log n$ tends to infinity, then a random $k$-uniform hypergraph on $n$ vertices, with edge probability $p$, with high probability (w.h.p.) contains a loose Hamilton cycle, provided that $(k-1)|n$. This generalizes results of Frieze, Dudek and Frieze, and reproves a result of Dudek, Frieze, Loh and Speiss. Secondly, we show that there exists $K>0$ such for every $p\geq (K\log n)/n$ the following holds: Let $G_{n,p}$ be a random graph on $n$ vertices with edge probability $p$, and suppose that its edges are being colored with $n$ colors uniformly at random. Then, w.h.p. the resulting graph contains a Hamilton cycle with for which all the colors appear (a rainbow Hamilton cycle). Bal and Frieze proved the latter statement for graphs on an even number of vertices, where for odd $n$ their $p$ was $\omega((\log n)/n)$. Lastly, we show that for $p=(1+o(1))(\log n)/n$, if we randomly color the edge set of a random directed graph $D_{n,p}$ with $(1+o(1))n$ colors, then w.h.p. one can find a rainbow Hamilton cycle where all the edges are directed in the same way.
Increasing Paths in Edge-Ordered Graphs: The Hypercube and Random Graph
Authors: De Silva Jessica , Molla Theodore , Pfender Florian , Retter Troy , Tait Michael
Published: January 2020

An edge-ordering of a graph $G=(V,E)$ is a bijection $\phi:E\to\{1,2,\ldots,|E|\}$. Given an edge-ordering, a sequence of edges $P=e_1,e_2,\ldots,e_k$ is an increasing path if it is a path in $G$ which satisfies $\phi(e_i)<\phi(e_j)$ for all $i<j$. For a graph $G$, let $f(G)$ be the largest integer $\ell$ such that every edge-ordering of $G$ contains an increasing path of length $\ell$. The parameter $f(G)$ was first studied for $G=K_n$ and has subsequently been studied for other families of graphs. This paper gives bounds on $f$ for the hypercube and the random graph $G(n,p)$.
Universal and Near-Universal Cycles of Set Partitions
Authors: Higgins Zach , Kelley Elizabeth , Sieben Bertilla , Godbole Anant
Published: January 2020

We study universal cycles of the set $\mathcal{P}(n,k)$ of $k$-partitions of the set $[n]:=\{1,2,\ldots,n\}$ and prove that the transition digraph associated with $\mathcal{P}(n,k)$ is Eulerian. But this does not imply that universal cycles (or ucycles) exist, since vertices represent equivalence classes of partitions. We use this result to prove, however, that ucycles of $\mathcal{P}(n,k)$ exist for all $n \geq 3$ when $k=2$. We reprove that they exist for odd $n$ when $k = n-1$ and that they do not exist for even $n$ when $k = n-1$. An infinite family of $(n,k)$ for which ucycles do not exist is shown to be those pairs for which ${{n-2}\brace{k-2}}$ is odd ($3 \leq k < n-1$). We also show that there exist universal cycles of partitions of $[n]$ into $k$ subsets of distinct sizes when $k$ is sufficiently smaller than $n$, and therefore that there exist universal packings of the partitions in $\mathcal{P}(n,k)$. An analogous result for coverings completes the investigation.
Abelian Cayley Digraphs with Asymptotically Large Order for Any Given Degree
Authors: Aguiló Francesc , Fiol Miquel Àngel , Pérez Sonia
Published: January 2020

Abelian Cayley digraphs can be constructed by using a generalization to $\mathbb{Z}^n$ of the concept of congruence in $\mathbb{Z}$. Here we use this approach to present a family of such digraphs, which, for every fixed value of the degree, have asymptotically large number of vertices as the diameter increases. Up to now, the best known large dense results were all non-constructive.
2-Walk-Regular Dihedrants from Group-Divisible Designs
Authors: Qiao Zhi , Du Shao Fei , Koolen Jack H
Published: January 2020

In this note, we construct bipartite $2$-walk-regular graphs with exactly 6 distinct eigenvalues as the point-block incidence graphs of group divisible designs with the dual property. For many of them, we show that they are 2-arc-transitive dihedrants. We note that some of these graphs are not described in Du et al. (2008), in which they classified the connected 2-arc transitive dihedrants.
Locally Oriented Noncrossing Trees
Authors: Okoth Isaac Owino , Wagner Stephan
Published: January 2020

We define an orientation on the edges of a noncrossing tree induced by the labels: for a noncrossing tree (i.e., the edges do not cross) with vertices $1,2,\ldots,n$ arranged on a circle in this order, all edges are oriented towards the vertex whose label is higher. The main purpose of this paper is to study the distribution of noncrossing trees with respect to the indegree and outdegree sequence determined by this orientation. In particular, an explicit formula for the number of noncrossing trees with given indegree and outdegree sequence is proved and several corollaries are deduced from it. Sources (vertices of indegree $0$) and sinks (vertices of outdegree $0$) play a special role in this context. In particular, it turns out that noncrossing trees with a given number of sources and sinks correspond bijectively to ternary trees with a given number of middle- and right-edges, and an explicit bijection is provided for this fact. Finally, the in- and outdegree distribution of a single vertex is considered and explicit counting formulas are provided again.
Stability for Vertex Cycle Covers
Authors: Balogh József , Mousset Frank , Skokan Jozef
Published: January 2020

In 1996 Kouider and Lonc proved the following natural generalization of Dirac's Theorem: for any integer $k\geq 2$, if $G$ is an $n$-vertex graph with minimum degree at least $n/k$, then there are $k-1$ cycles in $G$ that together cover all the vertices.This is tight in the sense that there are $n$-vertex graphs that have minimum degree $n/k-1$ and that do not contain $k-1$ cycles with this property. A concrete example is given by $I_{n,k} = K_n\setminus K_{(k-1)n/k+1}$ (an edge-maximal graph on $n$ vertices with an independent set of size $(k-1)n/k+1$). This graph has minimum degree $n/k-1$ and cannot be covered with fewer than $k$ cycles. More generally, given positive integers $k_1,\dotsc,k_r$ summing to $k$, the disjoint union $I_{k_1n/k,k_1}+ \dotsb + I_{k_rn/k,k_r}$ is an $n$-vertex graph with the same properties.In this paper, we show that there are no extremal examples that differ substantially from the ones given by this construction. More precisely, we obtain the following stability result: if a graph $G$ has $n$ vertices and minimum degree nearly $n/k$, then it either contains $k-1$ cycles covering all vertices, or else it must be close (in ‘edit distance') to a subgraph of $I_{k_1n/k,k_1}+ \dotsb + I_{k_rn/k,k_r}$, for some sequence $k_1,\dotsc,k_r$ of positive integers that sum to $k$.Our proof uses Szemerédi's Regularity Lemma and the related machinery.
The Coupling Method for Inhomogeneous Random Intersection Graphs.
Authors: Rybarczyk Katarzyna
Published: January 2020

We present new results concerning threshold functions for a wide family of random intersection graphs. To this end we improve and generalize  the coupling method introduced for random intersection graphs so that it may be used for a wider range of parameters. Using the new approach we are able to tighten the best known results concerning random intersection graphs and establish threshold functions for some monotone properties of inhomogeneous random intersection graphs. Considered properties are: $k$-connectivity, matching containment and hamiltonicity.
An Exact Turán Result for Tripartite 3-Graphs
Authors: Sanitt Adam , Talbot John
Published: January 2020

Mantel's theorem says that among all triangle-free graphs of a given order the balanced complete bipartite graph is the unique graph of maximum size. We prove an analogue of this result for 3-graphs. Let $K_4^-=\{123,124,134\}$, $F_6=\{123,124,345,156\}$ and $\mathcal{F}=\{K_4^-,F_6\}$: for $n\neq 5$ the unique $\mathcal{F}$-free 3-graph of order $n$ and maximum size is the balanced complete tripartite 3-graph $S_3(n)$ (for $n=5$ it is $C_5^{(3)}=\{123,234,345,145,125\}$). This extends an old result of Bollobás that $S_3(n) $ is the unique 3-graph of maximum size with no copy of $K_4^-=\{123,124,134\}$ or $F_5=\{123,124,345\}$.
A Note on $\mathtt{V}$-free 2-matchings
Authors: Bérczi Kristóf , Bernáth Attila , Vizer Máté
Published: January 2020

Motivated by a conjecture of Liang, we introduce a restricted path packing problem in bipartite graphs that we call a $\mathtt{V}$-free $2$-matching. We verify the conjecture through a weakening of the hypergraph matching problem. We close the paper by showing that it is NP-complete to decide whether one of the color classes of a bipartite graph can be covered by a $\mathtt{V}$-free $2$-matching.
Tropical Linear Spaces and Tropical Convexity
Authors: Hampe Simon
Published: January 2020

In classical geometry, a linear space is a space that is closed under linear combinations. In tropical geometry, it has long been a consensus that tropical varieties defined by valuated matroids are the tropical analogue of linear spaces. It is not difficult to see that each such space is tropically convex, i.e. closed under tropical linear combinations. However, we will also show that the converse is true: Each tropical variety that is also tropically convex is supported on the complex of a valuated matroid. We also prove a tropical local-to-global principle: Any closed, connected, locally tropically convex set is tropically convex.
Cluster Algebras of Type D: Pseudotriangulations Approach
Authors: Ceballos Cesar , Pilaud Vincent
Published: January 2020

We present a combinatorial model for cluster algebras of type $D_n$ in terms of centrally symmetric pseudotriangulations of a regular $2n$ gon with a small disk in the centre. This model provides convenient and uniform interpretations for clusters, cluster variables and their exchange relations, as well as for quivers and their mutations. We also present a new combinatorial interpretation of cluster variables in terms of perfect matchings of a graph after deleting two of its vertices. This interpretation differs from known interpretations in the literature. Its main feature, in contrast with other interpretations, is that for a fixed initial cluster seed, one or two graphs serve for the computation of all cluster variables. Finally, we discuss applications of our model to polytopal realizations of type $D$ associahedra and connections to subword complexes and $c$-cluster complexes.
Inverse Expander Mixing for Hypergraphs
Authors: Cohen Emma , Mubayi Dhruv , Ralli Peter , Tetali Prasad
Published: January 2020

We formulate and prove inverse mixing lemmas in the settings of simplicial complexes and $k$-uniform hypergraphs. In the hypergraph setting, we extend results of Bilu and Linial for graphs. In the simplicial complex setting, our results answer a question of Parzanchevski et al.
The Total Acquisition Number of Random Graphs
Authors: Bal Deepak , Bennett Patrick , Dudek Andrzej , Prałat Paweł
Published: January 2020

Let $G$ be a graph in which each vertex initially has weight 1. In each step, the weight from a vertex $u$ to a neighbouring vertex $v$ can be moved, provided that the weight on $v$ is at least as large as the weight on $u$. The total acquisition number of $G$, denoted by $a_t(G)$, is the minimum possible size of the set of vertices with positive weight at the end of the process.LeSaulnier, Prince, Wenger, West, and Worah asked for the minimum value of $p=p(n)$ such that $a_t(\mathcal{G}(n,p)) = 1$ with high probability, where $\mathcal{G}(n,p)$ is a binomial random graph. We show that $p = \frac{\log_2 n}{n} \approx 1.4427 \ \frac{\log n}{n}$ is a sharp threshold for this property. We also show that almost all trees $T$ satisfy $a_t(T) = \Theta(n)$, confirming a conjecture of West.
A Multipartite Version of the Turán Problem – Density Conditions and Eigenvalues
Authors: Nagy Zoltán Lóránt
Published: January 2020

In this paper we propose a multipartite version of the classical Turán problem of determining the minimum number of edges needed for an arbitrary graph to contain a given subgraph. As it turns out, here the non-trivial problem is the determination of the minimal edge density between two classes that implies the existence of a given subgraph. We determine the critical edge density for trees and cycles as forbidden subgraphs, and give the extremal structure. Surprisingly, this critical edge density is strongly connected to the maximal eigenvalue of the graph. Furthermore, we give a sharp upper and lower bound in general, in terms of the maximum degree of the forbidden graph.
A Combinatorial Proof of a Relationship Between Maximal $(2k-1,2k+1)$-Cores and $(2k-1,2k,2k+1)$-Cores
Authors: Nath Rishi , Sellers James A.
Published: January 2020

Integer partitions which are simultaneously $t$-cores for distinct values of $t$ have attracted significant interest in recent years.  When $s$ and $t$ are relatively prime, Olsson and Stanton have determined the size of the maximal $(s,t)$-core $\kappa_{s,t}$.  When $k\geq 2$, a conjecture of Amdeberhan on the maximal $(2k-1,2k,2k+1)$-core $\kappa_{2k-1,2k,2k+1}$ has also recently been verified by numerous authors.In this work, we analyze the relationship between maximal $(2k-1,2k+1)$-cores and maximal $(2k-1,2k,2k+1)$-cores. In previous work, the first author noted that, for all $k\geq 1,$$$\vert \, \kappa_{2k-1,2k+1}\, \vert = 4\vert \, \kappa_{2k-1,2k,2k+1}\, \vert$$and requested a combinatorial interpretation of this unexpected identity.  Here, using the theory of abaci, partition dissection, and elementary results relating triangular numbers and squares, we provide such a combinatorial proof.
The Phase Transition in Site Percolation on Pseudo-Random Graphs
Authors: Krivelevich Michael
Published: January 2020

We establish the existence of the phase transition in site percolation on pseudo-random $d$-regular graphs. Let $G=(V,E)$ be an $(n,d,\lambda)$-graph, that is, a $d$-regular graph on $n$ vertices in which all eigenvalues of the adjacency matrix, but the first one, are at most $\lambda$ in their absolute values. Form a random subset $R$ of $V$ by putting every vertex $v\in V$ into $R$ independently with probability $p$. Then for any small enough constant $\epsilon>0$, if $p=\frac{1-\epsilon}{d}$, then with high probability all connected components of the subgraph of $G$ induced by $R$ are of size at most logarithmic in $n$, while for $p=\frac{1+\epsilon}{d}$, if the eigenvalue ratio $\lambda/d$ is small enough as a function of $\epsilon$, then typically $R$ contains a connected component of size at least $\frac{\epsilon n}{d}$ and a path of length proportional to $\frac{\epsilon^2n}{d}$.
Partitioning $3$-Colored Complete Graphs into Three Monochromatic Cycles
Authors: Gyárfás András , Ruszinkó Miklós , Sárközy Gábor N. , Szemerédi Endre
Published: January 2020

We show in this paper that in every $3$-coloring of the edges of $K^n$ all but $o(n)$ of its vertices can be partitioned into three monochromatic cycles. From this, using our earlier results, actually it follows that we can partition all the vertices into at most 17 monochromatic cycles, improving the best known bounds. If the colors of the three monochromatic cycles must be different then one can cover $({3\over 4}-o(1))n$ vertices and this is close to best possible.
On Erdős-Sós Conjecture for Trees of Large Size
Authors: Goerlich Agnieszka , Żak Andrzej
Published: January 2020

Erdős and Sós conjectured that every graph $G$ of average degree greater than $k-1$ contains every tree of size $k$. Several results based upon the number of vertices in $G$ have been proved including the special cases where $G$ has exactly $k+1$ vertices (Zhou), $k+2$ vertices (Slater, Teo and Yap), $k+3$ vertices (Woźniak) and $k+4$ vertices (Tiner). We further explore this direction. Given an arbitrary integer $c\geq 1$, we prove Erdős-Sós conjecture in the case when $G$ has $k+c$ vertices provided that $k\geq k_0(c)$ (here $k_0(c)=c^{12}{\rm polylog}(c)$). We also derive a corollary related to the Tree Packing Conjecture.
The Peeling Process of Infinite Boltzmann Planar Maps
Authors: Budd Timothy
Published: January 2020

We start by studying a peeling process on finite random planar maps with faces of arbitrary degrees determined by a general weight sequence, which satisfies an admissibility criterion. The corresponding perimeter process is identified as a biased random walk, in terms of which the admissibility criterion has a very simple interpretation. The finite random planar maps under consideration were recently proved to possess a well-defined local limit known as the infinite Boltzmann planar map (IBPM). Inspired by recent work of Curien and Le Gall, we show that the peeling process on the IBPM can be obtained from the peeling process of finite random maps by conditioning the perimeter process to stay positive. The simplicity of the resulting description of the peeling process allows us to obtain the scaling limit of the associated perimeter and volume process for arbitrary regular critical weight sequences.
Intersections of the Hermitian Surface with Irreducible Quadrics in Even Characteristic
Authors: Aguglia Angela , Giuzzi Luca
Published: January 2020

We determine the possible intersection sizes of a Hermitian surface ${\mathcal H}$ with an irreducible quadric of $PG(3,q^2)$ sharing at least a tangent plane at a common non-singular point when $q$ is even.
Inversion Formulae on Permutations Avoiding 321
Authors: Chen Pingge , Mei Zhousheng , Wang Suijie
Published: January 2020

We will study the inversion statistic of $321$-avoiding permutations, and obtain that the number of $321$-avoiding permutations on $[n]$ with $m$ inversions is given by\[|\mathcal {S}_{n,m}(321)|=\sum_{b \vdash m}{n-\frac{\Delta(b)}{2}\choose l(b)}.\]where the sum runs over all compositions $b=(b_1,b_2,\ldots,b_k)$ of $m$, i.e.,\[m=b_1+b_2+\cdots+b_k \quad{\rm and}\quad  b_i\ge 1,\]$l(b)=k$ is the length of $b$, and $\Delta(b):=|b_1|+|b_2-b_1|+\cdots+|b_k-b_{k-1}|+|b_k|$. We obtain a new bijection from $321$-avoiding permutations to Dyck paths which establishes a relation on inversion number of $321$-avoiding permutations and valley height of Dyck paths.
Sets of Integers that do not Contain Long Arithmetic Progressions
Authors: O'Bryant Kevin
Published: January 2020

Combining ideas of Rankin, Elkin, Green & Wolf, we give constructive lower bounds for $r_k(N)$, the largest size of a subset of $\{1,2,\dots,N\}$ that does not contain a $k$-element arithmetic progression: For every $\epsilon>0$, if $N$ is sufficiently large, then $$r_3(N) \geq N \left(\frac{6\cdot 2^{3/4} \sqrt{5}}{e \,\pi^{3/2}}-\epsilon\right) \exp\left({-\sqrt{8\log N}+\tfrac14\log\log N}\right),$$ $$r_k(N) \geq N \, C_k\,\exp\left({-n 2^{(n-1)/2} \sqrt[n]{\log N}+\tfrac{1}{2n}\log\log N}\right),$$ where $C_k>0$ is an unspecified constant, $\log=\log_2$, $\exp(x)=2^x$, and $n=\lceil{\log k}\rceil$. These are currently the best lower bounds for all $k$, and are an improvement over previous lower bounds for all $k\neq4$.
Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive
Authors: Gasarch William , Haeupler Bernhard
Published: January 2020

The van der Waerden number $W(k,2)$ is the smallest integer $n$ such that every $2$-coloring of 1 to $n$ has a monochromatic arithmetic progression of length $k$. The existence of such an $n$ for any $k$ is due to van der Waerden but known upper bounds on $W(k,2)$ are enormous. Much effort was put into developing lower bounds on $W(k,2)$. Most of these lower bound proofs employ the probabilistic method often in combination with the Lovász Local Lemma. While these proofs show the existence of a $2$-coloring that has no monochromatic arithmetic progression of length $k$ they provide no efficient algorithm to find such a coloring. These kind of proofs are often informally called nonconstructive in contrast to constructive proofs that provide an efficient algorithm. This paper clarifies these notions and gives definitions for deterministic- and randomized-constructive proofs as different types of constructive proofs. We then survey the literature on lower bounds on $W(k,2)$ in this light. We show how known nonconstructive lower bound proofs based on the Lovász Local Lemma can be made randomized-constructive using the recent algorithms of Moser and Tardos. We also use a derandomization of Chandrasekaran, Goyal and Haeupler to transform these proofs into deterministic-constructive proofs. We provide greatly simplified and fully self-contained proofs and descriptions for these algorithms.
Generalizing the Classic Greedy and Necklace Constructions of de Bruijn Sequences and Universal Cycles
Authors: Sawada Joe , Williams Aaron , Wong Dennis
Published: January 2020

We present a class of languages that have an interesting property: For each language $\mathbf{L}$ in the class, both the classic greedy algorithm and the classic Lyndon word (or necklace) concatenation algorithm provide the lexicographically smallest universal cycle for $\mathbf{L}$. The languages consist of length $n$ strings over $\{1,2,\ldots ,k\}$ that are closed under rotation with their subset of necklaces also being closed under replacing any suffix of length $i$ by $i$ copies of $k$. Examples include all strings (in which case universal cycles are commonly known as de Bruijn sequences), strings that sum to at least $s$, strings with at most $d$ cyclic descents for a fixed $d>0$, strings with at most $d$ cyclic decrements for a fixed $d>0$, and strings avoiding a given period. Our class is also closed under both union and intersection, and our results generalize results of several previous papers.
Signed Lozenge Tilings
Authors: Cook II D. , Nagel Uwe
Published: January 2020

It is well-known that plane partitions, lozenge tilings of a hexagon, perfect matchings on a honeycomb graph, and families of non-intersecting lattice paths in a hexagon are all in bijection. In this work we consider regions that are more general than hexagons. They are obtained by further removing upward-pointing triangles. We call the resulting shapes triangular regions. We establish signed versions of the latter three bijections for triangular regions. We first investigate the tileability of triangular regions by lozenges. Then we use perfect matchings and families of non-intersecting lattice paths to define two signs of a lozenge tiling. Using a new method that we call resolution of a puncture, we show that the two signs are in fact equivalent. As a consequence, we obtain the equality of determinants, up to sign, that enumerate signed perfect matchings and signed families of lattice paths of a triangular region, respectively. We also describe triangular regions, for which the signed enumerations agree with the unsigned enumerations.
Colored Triangulations of Arbitrary Dimensions are Stuffed Walsh Maps
Authors: Bonzom Valentin , Lionni Luca , Rivasseau Vincent
Published: January 2020

Regular edge-colored graphs encode colored triangulations of pseudo-manifolds. Here we study families of edge-colored graphs built from a finite but arbitrary set of building blocks, which extend the notion of $p$-angulations to arbitrary dimensions. We prove the existence of a bijection between any such family and some colored combinatorial maps which we call stuffed Walsh maps. Those maps generalize Walsh's representation of hypermaps as bipartite maps, by replacing the vertices which correspond to hyperedges with non-properly-edge-colored maps. This shows the equivalence of tensor models with multi-trace, multi-matrix models by extending the intermediate field method perturbatively to any model. We further use the bijection to study the graphs which maximize the number of faces at fixed number of vertices and provide examples where the corresponding stuffed Walsh maps can be completely characterized.
Strongly Cancellative and Recovering Sets on Lattices
Authors: Bidkhori Hoda , Huang ShinnYih
Published: January 2020

We use information theory to study recovering sets ${\mathbf{R}}_L$ and strongly cancellative sets ${\mathbf{C}}_L$ on different lattices. These sets are special classes of recovering pairs and cancellative sets previously discussed in the papers of Simonyi, Frankl, and Füredi. We mainly focus on the lattices $B_n$ and $D_{l}^{k}$. Specifically, we find upper bounds and constructions for the sets ${\mathbf{R}}_{B_n}$, ${\mathbf{C}}_{B_n}$, and ${\mathbf{C}}_{D_{l}^{k}}$.
Higher Bruhat Orders in Type B
Authors: Shelley-Abrahamson Seth , Vijaykumar Suhas
Published: January 2020

Motivated by the geometry of hyperplane arrangements, Manin and Schechtman defined for each integer $n \geq 1$ a hierarchy of finite partially ordered sets $B(n, k),$ indexed by positive integers $k$, called the higher Bruhat orders.  The poset $B(n, 1)$ is naturally identified with the weak left Bruhat order on the symmetric group $S_n$, each $B(n, k)$ has a unique maximal and a unique minimal element, and the poset $B(n, k + 1)$ can be constructed from the set of maximal chains in $B(n, k)$.  Ben Elias has demonstrated a striking connection between the posets $B(n, k)$ for $k = 2$ and the diagrammatics of Bott-Samelson bimodules in type A, providing significant motivation for the development of an analogous theory of higher Bruhat orders in other Cartan-Killing types, particularly for $k = 2$.  In this paper we present a partial generalization to type B, complete up to $k = 2$, prove a direct analogue of the main theorem of Manin and Schechtman, and relate our construction to the weak Bruhat order and reduced expression graph for Weyl group $B_n$.
Web Matrices: Structural Properties and Generating Combinatorial Identities
Authors: Dukes Mark , White Chris D
Published: January 2020

In this paper we present new results for the combinatorics of web diagrams and web worlds. These are discrete objects that arise in the physics of calculating scattering amplitudes in non-abelian gauge theories. Web-colouring and web-mixing matrices (collectively known as web matrices) are indexed by ordered pairs of web-diagrams and contain information relating the number of colourings of the first web diagram that will produce the second diagram.We introduce the black diamond product on power series and show how it determines the web-colouring matrix of disjoint web worlds. Furthermore, we show that combining known physical results with the black diamond product gives a new technique for generating combinatorial identities. Due to the complicated action of the product on power series, the resulting identities appear highly non-trivial.We present two results to explain repeated entries that appear in the web matrices. The first of these shows how diagonal web matrix entries will be the same if the comparability graphs of their associated decomposition posets are the same. The second result concerns general repeated entries in conjunction with a flipping operation on web diagrams.We present a combinatorial proof of idempotency of the web-mixing matrices, previously established using physical arguments only. We also show how the entries of the square of the web-colouring matrix can be achieved by a linear transformation that maps the standard basis for formal power series in one variable to a sequence of polynomials. We look at one parameterized web world that is related to indecomposable permutations and show how determining the web-colouring matrix entries in this case is equivalent to a combinatorics onwords problem.
A $q$-Analogue of some Binomial Coefficient Identities of Y. Sun
Authors: Guo Victor J. W. , Yang Dan-Mei
Published: January 2020

We give a $q$-analogue of some binomial coefficient identities of Y. Sun [Electron. J. Combin. 17 (2010), #N20] as follows: \begin{align*} \sum_{k=0}^{\lfloor n/2\rfloor}{m+k\brack k}_{q^2}{m+1\brack n-2k}_{q} q^{n-2k\choose 2} &={m+n\brack n}_{q}, \\ \sum_{k=0}^{\lfloor n/4\rfloor}{m+k\brack k}_{q^4}{m+1\brack n-4k}_{q} q^{n-4k\choose 2} &=\sum_{k=0}^{\lfloor n/2\rfloor}(-1)^k{m+k\brack k}_{q^2}{m+n-2k\brack n-2k}_{q}, \end{align*} where ${n\brack k}_q$ stands for the $q$-binomial coefficient. We provide two proofs, one of which is combinatorial via partitions.
On Matchings in Stochastic Kronecker Graphs
Authors: Banaszak Justyna
Published: January 2020

The stochastic Kronecker graph is a random structure whose vertex set is a hypercube and the probability of an edge depends on the structure of its ends. We prove that a.a.s. as soon as the stochastic Kronecker graph becomes connected it contains a perfect matching.
A Survey of Binary Covering Arrays
Authors: Lawrence Jim , Kacker Raghu N. , Lei Yu , Kuhn D. Richard , Forbes Michael
Published: January 2020

Binary covering arrays of strength $t$ are 0–1 matrices having the property that for each $t$ columns and each of the possible $2^t$ sequences of $t$ 0's and 1's, there exists a row having that sequence in that set of $t$ columns. Covering arrays are an important tool in certain applications, for example, in software testing. In these applications, the number of columns of the matrix is dictated by the application, and it is desirable to have a covering array with a small number of rows. Here we survey some of what is known about the existence of binary covering arrays and methods of producing them, including both explicit constructions and search techniques.
Corners in Tree-Like Tableaux
Authors: Hitczenko Paweł , Lohss Amanda
Published: January 2020

In this paper, we study tree–like tableaux, combinatorial objects which exhibit a natural tree structure and are connected to the partially asymmetric simple exclusion process (PASEP). There was a conjecture made on the total number of corners in tree–like tableaux and the total number of corners in symmetric tree–like tableaux. In this paper, we prove both conjectures. Our proofs are based off of the bijection with permutation tableaux or type–B permutation tableaux and consequently, we also prove results for these tableaux. In addition, we derive the limiting distribution of the number of occupied corners in random tree–like tableaux and random symmetric tree–like tableaux.
Embedding Factorizations for 3-Uniform Hypergraphs II: $r$-Factorizations into $s$-Factorizations
Authors: Bahmanian Amin , Newman Mike
Published: January 2020

Motivated by a 40-year-old problem due to Peter Cameron on extending partial parallelisms, we provide necessary and sufficient conditions under which one can extend an $r$-factorization of a complete $3$-uniform hypergraph on $m$ vertices, $K_m^3$, to an $s$-factorization of $K_n^3$. This generalizes an existing result of Baranyai and Brouwer — where they proved it for the case $r=s=1$.
Cliques in Graphs Excluding a Complete Graph Minor
Authors: Wood David R.
Published: January 2020

This paper considers the following question: What is the maximum number of $k$-cliques in an $n$-vertex graph with no $K_t$-minor? This question generalises the extremal function for $K_t$-minors, which corresponds to the $k=2$ case. The exact answer is given for $t\leq 9$ and all values of $k$. We also determine the maximum total number of cliques in an $n$-vertex graph with no $K_t$-minor for $t\leq 9$. Several observations are made about the case of general $t$.
Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences
Authors: Schaeffer Luke , Shallit Jeffrey
Published: January 2020

We prove that the property of being closed (resp., palindromic, rich, privileged trapezoidal, balanced) is expressible in first-order logic for automatic (and some related) sequences. It therefore follows that the characteristic function of those $n$ for which an automatic sequence $\bf x$ has a closed (resp., palindromic, privileged, rich, trapezoidal, balanced) factor of length  $n$ is itself automatic. For privileged words this requires a new characterization of the privileged property. We compute the corresponding characteristic functions for various famous sequences, such as the Thue-Morse sequence, the Rudin-Shapiro sequence, the ordinary  paperfolding sequence, the period-doubling sequence, and the Fibonacci sequence. Finally, we also show that the function counting the total number of palindromic factors in the prefix of length $n$ of a $k$-automatic sequence is not $k$-synchronized.
Exterior Pairs and Up Step Statistics on Dyck Paths
Authors: Eu Sen-Peng , Fu Tung-Shan
Published: January 2020

Let $\mathcal{C}_n$ be the set of Dyck paths of length $n$. In this paper, by a new automorphism of ordered trees, we prove that the statistic 'number of exterior pairs', introduced by A. Denise and R. Simion, on the set $\mathcal{C}_n$ is equidistributed with the statistic 'number of up steps at height $h$ with $h\equiv 0$ (mod 3)'. Moreover, for $m\ge 3$, we prove that the two statistics 'number of up steps at height $h$ with $h\equiv 0$ (mod $m$)' and 'number of up steps at height $h$ with $h\equiv m-1$ (mod $m$)' on the set $\mathcal{C}_n$ are 'almost equidistributed'. Both results are proved combinatorially.