bluuebunny/crossref_metadata_2025 huggingface dataset:
Induced Subarrays of Latin Squares Without Repeated Symbols
Authors: Abel R. Julian R. , Cavenagh Nicholas J. , Kuhl Jaromy
Published: January 2020

We show that for any Latin square $L$ of order $2m$, we can partition the rows and columns of $L$ into pairs so that at most $(m+3)/2$ of the $2\times 2$ subarrays induced contain a repeated symbol. We conjecture that any Latin square of order $2m$ (where $m\geq 2$, with exactly five transposition class exceptions of order $6$) has such a partition so that  every $2\times 2$ subarray induced contains no repeated symbol. We verify this conjecture by computer when $m\leq 4$.
The Number of Euler Tours of Random Directed Graphs
Authors: Creed Páidí , Cryan Mary
Published: January 2020

In this paper we obtain the expectation and variance of the number of Euler tours of a random Eulerian directed graph with fixed out-degree sequence. We use this to obtain the asymptotic distribution of the number of Euler tours of a random $d$-in/$d$-out graph and prove a concentration result. We are then able to show that a very simple approach for uniform sampling or approximately counting Euler tours yields algorithms running in expected polynomial time for almost every $d$-in/$d$-out graph. We make use of the BEST theorem of de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte, which shows that the number of Euler tours of an Eulerian directed graph with out-degree sequence $\mathbf{d}$ is the product of the number of arborescences and the term $\frac{1}{|V|}[\prod_{v\in V}(d_v-1)!]$. Therefore most of our effort is towards estimating the moments of the number of arborescences of a random graph with fixed out-degree sequence.
Maximal Percolation Time in Hypercubes Under 2-Bootstrap Percolation
Authors: Przykucki Michał
Published: January 2020

Bootstrap percolation is one of the simplest cellular automata. In $r$-bootstrap percolation on a graph $G$, an infection spreads according to the following deterministic rule: infected vertices of $G$ remain infected forever and in consecutive rounds healthy vertices with at least $r$ already infected neighbours become infected. Percolation occurs if eventually every vertex is infected. In this paper we prove that in the case of $2$-bootstrap percolation on the $n$-dimensional hypercube the maximal time the process can take to eventually infect the entire vertex set is $\lfloor \frac{n^2}{3} \rfloor$.
Recurrence Relations and Splitting Formulas for the Domination Polynomial
Authors: Kotek Tomer , Preen James , Simon Frank , Tittmann Peter , Trinks Martin
Published: January 2020

The domination polynomial $D(G,x)$ of a graph $G$ is the generating function of its dominating sets. We prove that $D(G,x)$ satisfies a wide range of reduction formulas. We show linear recurrence relations for $D(G,x)$ for arbitrary graphs and for various special cases. We give splitting formulas for $D(G,x)$ based on articulation vertices, and more generally, on splitting sets of vertices.
Cooperative Colorings and Independent Systems of Representatives
Authors: Aharoni Ron , Holzman Ron , Howard David , Sprüssel Philipp
Published: January 2020

We study a generalization of the notion of coloring of graphs, similar in spirit to that of list colorings: a cooperative coloring of a family of graphs $G_1,G_2, \ldots,G_k$ on the same vertex set $V$ is a choice of independent sets $A_i$ in $G_i$ ($1 \le i \le k)$ such that $\bigcup_{i=1}^kA_i=V$. This notion is linked (with translation in both directions) to the notion of ISRs, which are choice functions on given sets, whose range belongs to some simplicial complex. When the complex is that of the independent sets in a graph $G$, an ISR for a partition of the vertex set of a graph $G$ into sets $V_1,\ldots, V_n$ is a choice of a vertex $v_i \in V_i$ for each $i$ such that $\{v_1,\ldots,v_n\}$ is independent in $G$. Using topological tools, we study degree conditions for the existence of cooperative colorings and of ISRs. A sample result: Three cycles on the same vertex set have a cooperative coloring.
Recognition and Characterization of Chronological Interval Digraphs
Authors: Das Sandip , Francis Mathew , Hell Pavol , Huang Jing
Published: January 2020

Interval graphs admit elegant structural characterizations and linear time recognition algorithms; on the other hand, the usual interval digraphs lack a forbidden structure characterization as well as a low-degree polynomial time recognition algorithm. In this paper we identify another natural digraph analogue of interval graphs that we call ”chronological interval digraphs”. By contrast, the new class admits both a forbidden structure characterization and a linear time recognition algorithm. Chronological interval digraphs arise by interpreting the standard definition of an interval graph with a natural orientation of its edges. Specifically, $G$ is a chronological interval digraph if there exists a family of closed intervals $I_v$, $v \in V(G)$, such that $uv$ is an arc of $G$ if and only if $I_u$ intersects $I_v$ and the left endpoint of $I_u$ is not greater than the left endpoint of $I_v$. (Equivalently, if and only if $I_u$ contains the left endpoint of $I_v$.)We characterize chronological interval digraphs in terms of vertex orderings, in terms of forbidden substructures, and in terms of a novel structure of so-called $Q$-paths. The first two characterizations exhibit strong similarity with the corresponding characterizations of interval graphs. The last characterization leads to a linear time recognition algorithm.
On Coloring the Odd-Distance Graph
Authors: Steinhardt Jacob
Published: January 2020

We present a proof, using spectral techniques, that there is no finite measurable coloring of the odd-distance graph.
Degree Ramsey Numbers of Closed Blowups of Trees
Authors: Horn Paul , Milans Kevin G. , Rödl Vojtěch
Published: January 2020

The degree Ramsey number of a graph $G$, denoted $R_\Delta(G;s)$, is $\min\{\Delta(H)\colon\, H\stackrel{s}{\to} G\}$, where $H\stackrel{s}{\to} G$ means that every $s$-edge-coloring of $H$ contains a monochromatic copy of $G$.  The closed $k$-blowup of a graph is obtained by replacing every vertex with a clique of size $k$ and every edge with a complete bipartite graph where both partite sets have size $k$.  We prove that there is a function $f$ such that $R_\Delta(G;s) \le f(\Delta(G), s)$  when $G$ is a closed blowup of a tree.
Common Edges in Rooted Trees and Polygonal Triangulations
Authors: Cleary Sean , Rechnitzer Andrew , Wong Thomas
Published: January 2020

Rotation distance between rooted binary trees measures the degree of similarity of two trees with ordered leaves and is equivalent to edge-flip distance between triangular subdivisions of regular polygons. There are no known polynomial-time algorithms for computing rotation distance. Existence of common edges makes computing rotation distance more manageable by breaking the problem into smaller subproblems. Here we describe the distribution of common edges between randomly-selected triangulations and measure the sizes of the remaining pieces into which the common edges separate the polygons. We find that asymptotically there is a large component remaining after sectioning off numerous small polygons which gives some insight into the distribution of such distances and the difficulty of such distance computations, and we analyze the distributions of the sizes of the largest and smaller resulting polygons.
Orders Induced by Segments in Floorplans and $(2 - 14 - 3, 3 - 41 - 2)$-Avoiding Permutations
Authors: Asinowski Andrei , Barequet Gill , Bousquet-Mélou Mireille , Mansour Toufik , Pinter Ron Y.
Published: January 2020

A floorplan is a tiling of a rectangle by rectangles. There are natural ways to order the elements - rectangles and segments - of a floorplan. Ackerman, Barequet and Pinter studied a pair of orders induced by neighborhood relations between rectangles, and obtained a natural bijection between these pairs and $(2 - 41 - 3, 3 - 14 - 2)$-avoiding permutations, also known as (reduced) Baxter permutations.In the present paper, we first perform a similar study for a pair of orders induced by neighborhood relations between segments of a floorplan. We obtain a natural bijection between these pairs and another family of permutations, namely $(2 - 14 - 3, 3 - 41 - 2)$-avoiding permutations.Then, we investigate relations between the two kinds of pairs of orders - and, correspondingly, between $(2 - 41 - 3, 3 - 14 - 2)$- and $(2 - 14 - 3, 3 - 41 - 2)$-avoiding permutations. In particular, we prove that the superposition of both permutations gives a complete Baxter permutation (originally called $w$-admissible by Baxter and Joichi in the sixties). In other words, $(2 - 14 - 3, 3 - 41 - 2)$-avoiding permutations are the hidden part of complete Baxter permutations. We enumerate these permutations. To our knowledge, the characterization of these permutations in terms of forbidden patterns and their enumeration are both new results.Finally, we also study the special case of the so-called guillotine floorplans.
Monochromatic Path and Cycle Partitions in Hypergraphs
Authors: Gyárfás András , Sárközy Gábor N.
Published: January 2020

Here we address the problem to partition edge colored hypergraphs by monochromatic paths and cycles generalizing a well-known similar problem for graphs.We show that $r$-colored $r$-uniform complete hypergraphs can be partitioned into monochromatic Berge-paths of distinct colors. Also, apart from $2k-5$ vertices, $2$-colored $k$-uniform hypergraphs can be partitioned into two monochromatic loose paths.In general, we prove that in any $r$-coloring of a $k$-uniform hypergraph there is a partition of the vertex set intomonochromatic loose cycles such that their number depends only on $r$ and $k$.
A New Determinant Expression for the Weighted Bartholdi Zeta Function of a Digraph
Authors: Sato Iwao , Mitsuhasi Hideo , Morita Hideaki
Published: January 2020

We consider the weighted Bartholdi zeta function of a digraph $D$, and give a new determinant expression of it. Furthermore, we treat a weighted $L$-function of $D$, and give a new determinant expression of it. As a corollary, we present determinant expressions for the Bartholdi edge zeta functions of a graph and a digraph.
Schur Polynomials, Banded Toeplitz Matrices and Widom's Formula
Authors: Alexandersson Per
Published: January 2020

We prove that for arbitrary partitions $\mathbf{\lambda} \subseteq \mathbf{\kappa},$ and integers $0\leq c<r\leq n,$ the sequence of Schur polynomials $S_{(\mathbf{\kappa} + k\cdot\mathbf{1}^c)/(\mathbf{\lambda} + k\cdot\mathbf{1}^r)}(x_1,\dots,x_n)$ for $k$ sufficiently large, satisfy a linear recurrence. The roots of the characteristic equation are given explicitly. These recurrences are also valid for certain sequences of minors of banded Toeplitz matrices.In addition, we show that Widom's determinant formula from 1958 is a special case of a well-known identity for Schur polynomials.
The Ramsey Number of Loose Paths in 3-Uniform Hypergraphs
Authors: Maherani Leila , Omidi Gholam Reza , Raeisi Ghaffar , Shahsiah Maryam
Published: January 2020

Recently, asymptotic values of 2-color Ramsey numbers for loose cycles and also loose paths were determined. Here we determine the 2-color Ramsey number of $3$-uniform loose paths when one of the paths is significantly larger than the other:  for every $n\geq \Big\lfloor\frac{5m}{4}\Big\rfloor$, we show that $$R(\mathcal{P}^3_n,\mathcal{P}^3_m)=2n+\Big\lfloor\frac{m+1}{2}\Big\rfloor.$$
Integral Cayley Graphs Generated by Distance Sets in Vector Spaces over Finite Fields
Authors: Nguyen Ngoc Dai , Nguyen Minh Hai , Do Duy Hieu , Le Anh Vinh
Published: January 2020

Si Li and the fourth listed author (2008) considered unitary graphs attached to the vector spaces over finite rings using an analogue of the Euclidean distance. These graphs are shown to be integral when the cardinality of the ring is odd or the dimension is even. In this paper, we show that the statement also holds for the remaining case: the cardinality of the ring is even and the dimension is odd, by showing a sufficient condition for Cayley graphs generated by distance sets in vector spaces over finite fields to be integral.
Turán $H$-Densities for 3-Graphs
Authors: Falgas-Ravry Victor , Vaughan Emil R.
Published: January 2020

Given an $r$-graph $H$ on $h$ vertices, and a family $\mathcal{F}$ of forbidden subgraphs, we define $\mathrm{ex}_{H}(n, \mathcal{F})$ to be the maximum number of induced copies of $H$ in an $\mathcal{F}$-free $r$-graph on $n$ vertices. Then the Turán $H$-density of $\mathcal{F}$ is the limit\[\pi_{H}(\mathcal{F})= \lim_{n\rightarrow \infty}\mathrm{ex}_{H}(n, \mathcal{F})/\binom{n}{h}. \]This generalises the notions of Turán density (when $H$ is an $r$-edge), and inducibility (when $\mathcal{F}$ is empty). Although problems of this kind have received some attention, very few results are known.We use Razborov's semi-definite method to investigate Turán $H$-densities for $3$-graphs. In particular, we show that\[\pi_{K_4^-}(K_4) = 16/27,\]with Turán's construction being optimal. We prove a result in a similar flavour for $K_5$ and make a general conjecture on the value of $\pi_{K_t^-}(K_t)$. We also establish that\[\pi_{4.2}(\emptyset)=3/4,\]where $4.2$ denotes the $3$-graph on $4$ vertices with exactly $2$ edges. The lower bound in this case comes from a random geometric construction strikingly different from previous known extremal examples in $3$-graph theory. We give a number of other results and conjectures for $3$-graphs, and in addition consider the inducibility of certain directed graphs. Let $\vec{S}_k$ be the out-star on $k$ vertices; i.e. the star on $k$ vertices with all $k-1$ edges oriented away from the centre. We show that\[\pi_{\vec{S}_3}(\emptyset)=2\sqrt{3}-3,\]with an iterated blow-up construction being extremal. This is related to a conjecture of Mubayi and Rödl on the Turán density of the 3-graph $C_5$. We also determine $\pi_{\vec{S}_k}(\emptyset)$ when $k=4,5$, and conjecture its value for general $k$.
Upper Bounds for Perfect Matchings in Pfaffian and Planar Graphs
Authors: Behmaram Afshin , Friedland Shmuel
Published: January 2020

We give upper bounds on weighted perfect matchings in Pfaffian graphs. These upper bounds are better than Bregman's upper bounds on the number of perfect matchings. We show that some of our upper bounds are sharp for 3 and 4-regular Pfaffian graphs. We apply our results to fullerene graphs.
Scattered Linear Sets and Pseudoreguli
Authors: Lavrauw Michel , Van de Voorde Geertrui
Published: January 2020

In this paper, we show that one can associate a pseudoregulus with every scattered linear set of rank $3n$ in $\mathrm{PG}(2n-1,q^3)$. We construct a scattered linear set having a given pseudoregulus as associated pseudoregulus and prove that there are $q-1$ different scattered linear sets that have the same associated pseudoregulus. Finally, we give a characterisation of reguli and pseudoreguli in $\mathrm{PG}(3,q^3)$.
On Graph Parameters Guaranteeing Fast Sandpile Diffusion
Authors: Choure Ayush , Vishwanathan Sundar
Published: January 2020

The Abelian Sandpile Model (Dhar 1990) is a discrete diffusion process, defined on graphs, which serves as the standard model of self-organized criticality. One is allowed to add sand particles on the nodes of the graph such that each node can stably hold at most some bounded number of particles. The particles flow through the graph as a consequence of surpassing the node capacities, until they reach a special sink node possessing infinite capacity. These simple dynamics give rise to a very interesting Markovian system. The transience class of a sandpile is defined as the maximum number of particles that can be added without making the system recurrent. We identify a small set of key graph properties that guarantee polynomial bounds on transience classes of the sandpile families satisfying them. These properties governing the speed of sandpile diffusion process are volume growth parameters, boundary regularity type properties and non-empty interior type constraints.This generalizes a previous result by Babai and Gorodezky (2007), in which they establish polynomial bounds on the $n\times n$ grid. Indeed the properties we show are based on ideas extracted from their proof as well as the continuous analogs in the theory of harmonic functions.
A Mathematical Bibliography of Signed and Gain Graphs and Allied Areas
Authors: Zaslavsky Thomas
Published: January 2020

A signed graph is a graph whose edges are labeled by signs. This is a bibliography of signed graphs and related mathematics.Several kinds of labelled graph have been called "signed" yet are mathematically very different. I distinguish four types:Group-signed graphs: the edge labels are elements of a 2-element group and are multiplied around a polygon (or along any walk). Among the natural generalizations are larger groups and vertex signs.Sign-colored graphs, in which the edges are labelled from a two-element set that is acted upon by the sign group: - interchanges labels, + leaves them unchanged. This is the kind of "signed graph" found in knot theory. The natural generalization is to more colors and more general groups — or no group.Weighted graphs, in which the edge labels are the elements +1 and -1 of the integers or another additive domain. Weights behave like numbers, not signs; thus I regard work on weighted graphs as outside the scope of the bibliography — except (to some extent) when the author calls the weights "signs".Labelled graphs where the labels have no structure or properties but are called "signs" for any or no reason.
On the Maximum Number of $k$-Hooks of Partitions of $n$
Authors: Fan Anna R.B. , Yang Harold R.L. , Yu Rebecca T.
Published: January 2020

Let $\alpha_k(\lambda)$ denote the number of $k$-hooks in a partition $\lambda$ and let $b(n,k)$ be the maximum value of $\alpha_k(\lambda)$ among partitions of $n$. Amdeberhan posed a conjecture on the generating function of $b(n,1)$. We give a proof of this conjecture. In general, we obtain a formula that can be used to determine $b(n,k)$. This leads to a generating function formula for $b(n,k)$. We introduce the notion of nearly $k$-triangular partitions. We show that for any $n$, there is a nearly $k$-triangular partition which can be transformed into a partition of $n$ that attains the maximum number of $k$-hooks. The operations for the transformation enable us to compute the number $b(n,k)$.
Towards Random Uniform Sampling of Bipartite Graphs with given Degree Sequence
Authors: Miklós István , Erdős Péter L , Soukup Lajos
Published: January 2020

In this paper we consider a simple Markov chain for bipartite graphs with given degree sequence on $n$ vertices. We show that the mixing time of this Markov chain is bounded above by a polynomial in $n$ in case of half-regular degree sequence. The novelty of our approach lies in the construction of the multicommodity flow in Sinclair's method.
Biologically Unavoidable Sequences
Authors: Alexander Samuel A
Published: January 2020

A biologically unavoidable sequence is an infinite gender sequence which occurs in every gendered, infinite genealogical network satisfying certain tame conditions. We show that every eventually periodic sequence is biologically unavoidable (this generalizes König's Lemma), and we exhibit some biologically avoidable sequences. Finally we give an application of unavoidable sequences to cellular automata.
Congruence Classes of Orientable $2$-Cell Embeddings of Bouquets of Circles and Dipoles
Authors: Feng Yan-Quan , Kwak Jin-Ho , Zhou Jin-Xin
Published: January 2020

Two $2$-cell embeddings $\imath : X \to S$ and $\jmath : X \to S$ of a connected graph $X$ into a closed orientable surface $S$ are congruent if there are an orientation-preserving surface homeomorphism $h : S \to S$ and a graph automorphism $\gamma$ of $X$ such that $\imath h =\gamma\jmath$. Mull et al. [Proc. Amer. Math. Soc. 103(1988) 321–330] developed an approach for enumerating the congruence classes of $2$-cell embeddings of a simple graph (without loops and multiple edges) into closed orientable surfaces and as an application, two formulae of such enumeration were given for complete graphs and wheel graphs. The approach was further developed by Mull [J. Graph Theory 30(1999) 77–90] to obtain a formula for enumerating the congruence classes of $2$-cell embeddings of complete bipartite graphs into closed orientable surfaces. By considering automorphisms of a graph as permutations on its dart set, in this paper Mull et al.'s approach is generalized to any graph with loops or multiple edges, and by using this method we enumerate the congruence classes of $2$-cell embeddings of a bouquet of circles and a dipole into closed orientable surfaces.
Nonrepetitive Colourings of Planar Graphs with $O(\log n)$ Colours
Authors: Dujmović Vida , Joret Gwenaël , Frati Fabrizio , Wood David R.
Published: January 2020

A vertex colouring of a graph is nonrepetitive if there is no path for which the first half of the path is assigned the same sequence of colours as the second half. The nonrepetitive chromatic number of a graph $G$ is the minimum integer $k$ such that $G$ has a nonrepetitive $k$-colouring. Whether planar graphs have bounded nonrepetitive chromatic number is one of the most important open problems in the field. Despite this, the best known upper bound is $O(\sqrt{n})$ for $n$-vertex planar graphs. We prove a $O(\log n)$ upper bound.
The Minimal Perimeter for $N$ Confined Deformable Bubbles of Equal Area
Authors: Cox S. J. , Flikkema E.
Published: January 2020

Candidates to the least perimeter partition of various polygonal shapes into $N$ planar connected equal-area regions are calculated for $N\le 42$, compared to partitions of the disc, and discussed in the context of the energetic groundstate of a two-dimensional monodisperse foam. The total perimeter and the number of peripheral regions are presented, and the patterns classified according to the number and position of the topological defects, that is non-hexagonal regions (bubbles). The optimal partitions of an equilateral triangle are found to follow a pattern based on the position of no more than one defect pair, and this pattern is repeated for many of the candidate partitions of a hexagon. Partitions of a square and a pentagon show greater disorder. Candidates to the least perimeter partition of the surface of the sphere into $N$ connected equal-area regions are also calculated. For small $N$ these can be related to simple polyhedra and for $N \ge 14$ they consist of 12 pentagons and $N-12$ hexagons.
Limits of Modified Higher $q,t$-Catalan Numbers
Authors: Lee Kyungyong , Li Li , Loehr Nicholas A
Published: January 2020

The $q,t$-Catalan numbers can be defined using rational functions, geometry related to Hilbert schemes, symmetric functions, representation theory, Dyck paths, partition statistics, or Dyck words. After decades of intensive study, it was eventually proved that all these definitions are equivalent. In this paper, we study the similar situation for higher $q,t$-Catalan numbers, where the equivalence of the algebraic and combinatorial definitions is still conjectural. We compute the limits of several versions of the modified higher $q,t$-Catalan numbers and show that these limits equal the generating function for integer partitions. We also identify certain coefficients of the higher $q,t$-Catalan numbers as enumerating suitable integer partitions, and we make some conjectures on the homological significance of the Bergeron-Garsia nabla operator.
Periodic Coefficients and Random Fibonacci Sequences
Authors: McLellan Karyn
Published: January 2020

The random Fibonacci sequence is defined by $t_1 = t_2 = 1$ and $t_n = \pm t_{n-1} + t_{n-2}$, for $n \geq 3$, where each $\pm$ sign is chosen at random with probability $P(+) = P(-) = \frac{1}{2}$. Viswanath has shown that almost all random Fibonacci sequences grow exponentially at the rate $1.13198824\ldots$. We will consider what happens to random Fibonacci sequences when we remove the randomness; specifically, we will choose coefficients which belong to the set $\{1, -1\}$ and form periodic cycles. By rewriting our recurrences using matrix products, we will analyze sequence growth and develop criteria based on eigenvalue, trace and order for determining whether a given sequence is bounded, grows linearly or grows exponentially. Further, we will introduce an equivalence relation on the coefficient cycles such that each equivalence class has a common growth rate, and consider the number of such classes for a given cycle length.
Erdös-Gyárfás Conjecture for Cubic Planar Graphs
Authors: Heckman Christopher Carl , Krakovski Roi
Published: January 2020

In 1995, Paul Erdös and András Gyárfás conjectured that for every graph of minimum degree at least 3, there exists a non-negative integer $m$ such that $G$ contains a simple cycle of length $2^m$. In this paper, we prove that the conjecture holds for 3-connected cubic planar graphs. The proof is long, computer-based in parts, and employs the Discharging Method in a novel way.
Forbidden Triples Generating a Finite set of 3-Connected Graphs
Authors: Egawa Yoshimi , Fujisawa Jun , Furuya Michitaka , Plummer Michael D , Saito Akira
Published: January 2020

For a graph $G$ and a set $\mathcal{F}$ of connected graphs, $G$ is said be $\mathcal{F}$-free if $G$ does not contain any member of $\mathcal{F}$ as an induced subgraph. We let $\mathcal{G} _{3}(\mathcal{F})$ denote the set of all $3$-connected $\mathcal{F}$-free graphs. This paper is concerned with sets $\mathcal{F}$ of connected graphs such that $|\mathcal{F}|=3$ and $\mathcal{G} _{3}(\mathcal{F})$ is finite. Among other results, we show that for an integer $m\geq 3$ and a connected graph $T$ of order greater than or equal to $4$, $\mathcal{G} _{3}(\{K_{4},K_{2,m},T\})$ is finite if and only if $T$ is a path of order $4$ or $5$.
Enumerating Finite Racks, Quandles and Kei
Authors: Blackburn Simon R.
Published: January 2020

A rack of order $n$ is a binary operation $\vartriangleright$ on a set $X$ of cardinality $n$, such that right multiplication is an automorphism. More precisely, $(X,\vartriangleright)$ is a rack provided that the map $x\mapsto x\vartriangleright y$ is a bijection for all $y\in X$, and $(x\vartriangleright y)\vartriangleright z=(x\vartriangleright z)\vartriangleright (y\vartriangleright z)$ for all $x,y,z\in X$.The paper provides upper and lower bounds of the form $2^{cn^2}$ on the number of isomorphism classes of racks of order $n$. Similar results on the number of isomorphism classes of quandles and kei are obtained. The results of the paper are established by first showing how an arbitrary rack is related to its operator group (the permutation group on $X$ generated by the maps $x\mapsto x\vartriangleright y$ for $y\in Y$), and then applying some of the theory of permutation groups. The relationship between a rack and its operator group extends results of Joyce and of Ryder; this relationship might be of independent interest.
Repeated Columns and an Old Chestnut
Authors: Anstee R. P. , Lu Linyuan
Published: January 2020

Let $t\ge 1$ be a given integer. Let ${\cal F}$ be a family of subsets of $[m]=\{1,2,\ldots ,m\}$. Assume that for every pair of disjoint sets $S,T\subset [m]$ with $|S|=|T|=k$, there do not exist $2t$ sets in ${\cal F}$ where $t$ subsets of ${\cal F}$ contain $S$ and are disjoint from $T$ and $t$ subsets of ${\cal F}$ contain $T$ and are disjoint from $S$. We show that $|{\cal F}|$ is $O(m^{k})$. Our main new ingredient is allowing, during the inductive proof, multisets of subsets of $[m]$ where the multiplicity of a given set is bounded by $t-1$. We use a strong stability result of Anstee and Keevash. This is further evidence for a conjecture of Anstee and Sali. These problems can be stated in the language of matrices. Let $t\cdot M$ denote $t$ copies of the matrix $M$ concatenated together. We have established the conjecture for those configurations $t\cdot F$ for any $k\times 2$ (0,1)-matrix $F$.
The Number of Rooted Trees of Given Depth
Authors: Pach Péter Pál , Pluhár Gabriella , Pongrácz András , Szabó Csaba
Published: January 2020

In this paper it is shown that the logarithm of the number of non-isomorphic rooted trees of depth $k\geq 3$ is asymptotically $\frac{\pi^2}{6}\cdot\frac{n}{\log\log\dots\log n}$, where $\log$ is iterated $k-2$ times in the denominator.
Embedding Cycles in Finite Planes
Authors: Lazebnik Felix , Mellinger Keith E. , Vega Oscar
Published: January 2020

We define and study embeddings of cycles in finite affine and projective planes. We show that for all $k$, $3\le k\le q^2$,  a $k$-cycle can be embedded in any affine plane of order $q$. We also prove a similar result for finite projective planes: for all $k$, $3\le k\le q^2+q+1$,  a $k$-cycle can be embedded in any projective plane of order $q$.
A Criterion for the Log-Convexity of Combinatorial Sequences
Authors: Xia Ernest X.W. , Yao Olivia X.M.
Published: January 2020

Recently, Došlić, and Liu and Wang developed techniques for dealing with the log-convexity of sequences. In this paper, we present a criterion for the log-convexity of some combinatorial sequences. In order to prove the log-convexity of a sequence satisfying a three-term recurrence, by our method, it suffices to compute a constant number of terms at the beginning of the sequence. For example, in order to prove the log-convexity of the Apéry numbers $A_n$, by our method, we just need to evaluate the values of $A_n$ for $0\leq n \leq 6$. As applications, we prove the log-convexity of some famous sequences including the Catalan-Larcombe-French numbers. This confirms a conjecture given by Sun.
Moore Graphs and Beyond: A survey of the Degree/Diameter Problem
Authors: Miller Mirka , Sirán Jozef
Published: January 2020

The degree/diameter problem is to determine the largest graphs or digraphs of given maximum degree and given diameter.General upper bounds - called Moore bounds - for the order of such graphs and digraphs are attainable only for certain special graphs and digraphs. Finding better (tighter) upper bounds for the maximum possible number of vertices, given the other two parameters, and thus attacking the degree/diameter problem 'from above', remains a largely unexplored area. Constructions producing large graphs and digraphs of given degree and diameter represent a way of attacking the degree/diameter problem 'from below'.This survey aims to give an overview of the current state-of-the-art of the degree/diameter problem. We focus mainly on the above two streams of research. However, we could not resist mentioning also results on various related problems. These include considering Moore-like bounds for special types of graphs and digraphs, such as vertex-transitive, Cayley, planar, bipartite, and many others, on the one hand, and related properties such as connectivity, regularity, and surface embeddability, on the other hand.
Counting Words with Laguerre Series
Authors: Taylor Jair
Published: January 2020

We develop a method for counting words subject to various restrictions by finding a combinatorial interpretation for a product of weighted sums of Laguerre polynomials with parameter $\alpha = -1$.  We describe how such a series can be computed by finding an appropriate ordinary generating function and applying a certain transformation. We use this technique to find the generating function for the number of $k$-ary words avoiding any vincular pattern that has only ones, as well as words cyclically avoiding vincular patterns with only ones whose runs of ones between dashes are all of equal length.
Near-Colorings: Non-Colorable Graphs and NP-Completeness
Authors: Montassier M. , Ochem P.
Published: January 2020

A graph $G$ is $(d_1,...,d_l)$-colorable if the vertex set of $G$ can be partitioned into subsets $V_1,\ldots ,V_l$ such that the graph $G[V_i]$ induced by the vertices of $V_i$ has maximum degree at most $d_i$ for all $1 \leq i \leq l$. In this paper, we focus on complexity aspects of such colorings when $l=2,3$. More precisely, we prove that, for any fixed integers $k,j,g$ with $(k,j) \neq (0,0)$ and $g\geq3$, either every planar graph with girth at least $g$ is $(k,j)$-colorable or it is NP-complete to determine whether a planar graph with girth at least $g$ is $(k,j)$-colorable. Also, for any fixed integer $k$, it is NP-complete to determine whether a planar graph that is either $(0,0,0)$-colorable or non-$(k,k,1)$-colorable is $(0,0,0)$-colorable. Additionally, we exhibit non-$(3,1)$-colorable planar graphs with girth 5 and non-$(2,0)$-colorable planar graphs with girth 7.
A De Bruijn–Erdős Theorem for Chordal Graphs
Authors: Beaudou Laurent , Bondy Adrian , Chen Xiaomin , Chiniforooshan Ehsan , Chudnovsky Maria , Chvátal Vašek , Fraiman Nicolas , Zwols Yori
Published: January 2020

A special case of a combinatorial theorem of De Bruijn and Erdős asserts that every noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chávtal suggested a possible generalization of this assertion in metric spaces with appropriately defined lines. We prove this generalization in all metric spaces induced by connected chordal graphs.
Spectra of Edge-Independent Random Graphs
Authors: Lu Linyuan , Peng Xing
Published: January 2020

Let $G$ be a random graph on the vertex set $\{1,2,\ldots, n\}$ such that edges in $G$ are determined by independent random indicator variables, while the probabilities $p_{ij}$ for $\{i,j\}$ being an edge in $G$ are not assumed to be equal. Spectra of the adjacency matrix and the normalized Laplacian matrix of $G$ are recently studied by Oliveira and Chung-Radcliffe. Let $A$ be the adjacency matrix of $G$, $\bar A={\rm E}(A)$, and $\Delta$ be the maximum expected degree of $G$.  Oliveira first proved that asymptotically almost surely $\|A-\bar A\|=O(\sqrt{\Delta \ln n})$ provided $\Delta\geq C \ln n$ for some constant $C$. Chung-Radcliffe improved the hidden constant in the error term using a new Chernoff-type inequality for random matrices. Here we prove that asymptotically almost surely $\|A-\bar A\|\leq (2+o(1))\sqrt{\Delta}$ with a slightly stronger condition $\Delta\gg \ln^4 n$.  For the Laplacian matrix $L$ of $G$, Oliveira and Chung-Radcliffe proved similar results $\|L-\bar L\|=O(\sqrt{\ln n}/\sqrt{\delta})$ provided the minimum expected degree $\delta\geq C' \ln n$ for some constant $C'$; we also improve their results by removing the $\sqrt{\ln n}$ multiplicative factor from the error term under some mild conditions. Our results naturally apply to the classical Erdős–Rényi random graphs, random graphs with given expected degree sequences, and bond percolation of general graphs.
Rogers-Ramanujan-Slater Type Identities
Authors: Mc Laughlin James , Sills Andrew V. , Zimmer Peter
Published: January 2020

In this survey article, we present an expanded version of Lucy Slater's famous list of identities of the Rogers-Ramanujan type, including identities of similar type, which were discovered after the publication of Slater's papers, and older identities (such as those in Ramanujan's lost notebook) which were not included in Slater's papers. We attempt to supply the earliest known reference for each identity. Also included are identities of false theta functions, along with their relationship to Rogers-Ramanujan type identities. We also describe several ways in which pairs/larger sets of identities may be related, as well as dependence relationships between identities.
Extremal Edge Polytopes
Authors: Tran Tuan , M. Ziegler Günter
Published: January 2020

The "edge polytope" of a finite graph $G$ is the convex hull of the columns of its vertex-edge incidence matrix. We study extremal problems for this class of polytopes. For $k =2, 3, 5$ we determine the maximal number of vertices of $k$-neighborly edge polytopes up to a sublinear term. We also construct a family of edge polytopes with exponentially-many facets.
Dynamic Cage Survey
Authors: Exoo Geoffrey , Jajcay Robert
Published: January 2020

A $(k, g)$-cage is a $k$-regular graph of girth $g$ of minimum order. In this survey, we present the results of over 50 years of searches for cages. We present the important theorems, list all the known cages, compile tables of current record holders, and describe in some detail most of the relevant constructions.
Polynomial Sequences of Binomial-Type Arising in Graph Theory
Authors: Schneider Jonathan
Published: January 2020

In this paper, we show that the solution to a large class of "tiling'' problems is given by a polynomial sequence of binomial type. More specifically, we show that the number of ways to place a fixed set of polyominos on an $n\times n$ toroidal chessboard such that no two polyominos overlap is eventually a polynomial in $n$, and that certain sets of these polynomials satisfy binomial-type recurrences. We exhibit generalizations of this theorem to higher dimensions and other lattices. Finally, we apply the techniques developed in this paper to resolve an open question about the structure of coefficients of chromatic polynomials of certain grid graphs (namely that they also satisfy a binomial-type recurrence).
On Some Densities in the Set of Permutations
Authors: Manstavičius Eugenijus
Published: January 2020

The asymptotic density of random permutations with given properties of the $k$th shortest cycle length is examined. The approach is based upon the saddle point method applied for appropriate sums of independent random variables.
On Zero-sum Free Subsets of Length 7
Authors: Yuan Pingzhi , Zeng Xiangneng
Published: January 2020

Let $G$ be a finite additively written abelian group, and let $X$ be a subset of 7 elements in $G$. We show that if $X$ contains no nonempty subset with sum zero, then the number of the elements which can be expressed as the sum over a nonempty subsequence of $X$ is at least $ 24$.
On Limits of Dense Packing of Equal Spheres in a Cube
Authors: Tatarevic Milos
Published: January 2020

We examine packing of $n$ congruent spheres in a cube when $n$ is close but less than the number of spheres in a regular cubic close-packed (ccp) arrangement of $\lceil p^{3}/2\rceil$ spheres. For this family of packings, the previous best-known arrangements were usually derived from a ccp by omission of a certain number of spheres without changing the initial structure. In this paper, we show that better arrangements exist for all $n\leq\lceil p^{3}/2\rceil-2$. We introduce an optimization method to reveal improvements of these packings, and present many new improvements for $n\leq4629$.
An Elementary Proof of Jin's Theorem with a Bound
Authors: Di Nasso Mauro
Published: January 2020

We present a short and self-contained proof of Jin's theorem about the piecewise syndeticity of difference sets which is entirely elementary, in the sense that no use is made of nonstandard analysis, ergodic theory, measure theory, ultrafilters, or other advanced tools. An explicit bound to the number of shifts that are needed to cover a thick set is provided. Precisely, we prove the following: If $A$ and $B$ are sets of integers having positive upper Banach densities $a$ and $b$ respectively, then there exists a finite set $F$ of cardinality at most $1/ab$ such that $(A-B)+F$ covers arbitrarily long intervals.
A Schur-Like Basis of NSym Defined by a Pieri Rule
Authors: Campbell John Maxwell , Feldman Karen , Light Jennifer , Shuldiner Pavel , Xu Yan
Published: January 2020

Recent research on the algebra of non-commutative symmetric functions and the dual algebra of quasi-symmetric functions has explored some natural analogues of the Schur basis of the algebra of symmetric functions. We introduce a new basis of the algebra of non-commutative symmetric functions using a right Pieri rule. The commutative image of an element of this basis indexed by a partition equals the element of the Schur basis indexed by the same partition and the commutative image is $0$ otherwise.  We establish a rule for right-multiplying an arbitrary element of this basis by an arbitrary element of the ribbon basis, and a Murnaghan-Nakayama-like rule for this new basis.  Elements of this new basis indexed by compositions of the form $(1^n, m, 1^r)$ are evaluated in terms of the complete homogeneous basis and the elementary basis.
Chip-Firing Game and a Partial Tutte Polynomial for Eulerian Digraphs
Authors: Perrot Kévin , Pham Trung Van
Published: January 2020

The Chip-firing game is a discrete dynamical system played on a graph, in which chips move along edges according to a simple local rule. Properties of the underlying graph are of course useful to the understanding of the game, but since a conjecture of Biggs that was proved by Merino López, we also know that the study of the Chip-firing game can give insights on the graph. In particular, a strong relation between the partial Tutte polynomial $T_G(1,y)$ and the set of recurrent configurations of a Chip-firing game (with a distinguished sink vertex) has been established for undirected graphs. A direct consequence is that the generating function of the set of recurrent configurations is independent of the choice of the sink for the game, as it characterizes the underlying graph itself. In this paper we prove that this property also holds for Eulerian directed graphs (digraphs), a class on the way from undirected graphs to general digraphs. It turns out from this property that the generating function of the set of recurrent configurations of an Eulerian digraph is a natural and convincing candidate for generalizing the partial Tutte polynomial $T_G(1,y)$ to this class. Our work also gives some promising directions of looking for a generalization of the Tutte polynomial to general digraphs.
Some Enumerations on Non-Decreasing Dyck Paths
Authors: Czabarka Éva , Flórez Rigoberto , Junes Leandro
Published: January 2020

We construct a formal power series on several variables that encodes many statistics on non-decreasing Dyck paths. In particular, we use this formal power series to count peaks, pyramid weights, and indexed sums of pyramid weights for all non-decreasing Dyck paths of length $2n.$ We also show that an indexed sum on pyramid weights depends only on the size and maximum element of the indexing set.
A Quantitative Study of Pure Parallel Processes
Authors: Bodini O. , Genitrini A. , Peschanski F.
Published: January 2020

In this paper, we study the interleaving – or pure merge – operator that most often characterizes parallelism in concurrency theory. This operator is a principal cause of the so-called combinatorial explosion that makes the analysis of process behaviours e.g. by model-checking, very hard – at least from the point of view of computational complexity. The originality of our approach is to study this combinatorial explosion phenomenon on average, relying on advanced analytic combinatorics techniques. We study various measures that contribute to a better understanding of the process behaviours represented as plane rooted trees: the number of runs (corresponding to the width of the trees), the expected total size of the trees as well as their overall shape. Two practical outcomes of our quantitative study are also presented: (1) a linear-time algorithm to compute the probability of a concurrent run prefix, and (2) an efficient algorithm for uniform random sampling of concurrent runs. These provide interesting responses to the combinatorial explosion problem.
On Embeddings of Circulant Graphs
Authors: Conder Marston , Grande Ricardo
Published: January 2020

A circulant of order $n$ is a Cayley graph for the cyclic group $\mathbb{Z}_n$, and as such, admits a transitive action of $\mathbb{Z}_n$ on its vertices. This paper concerns 2-cell embeddings of connected circulants on closed orientable surfaces. Embeddings on the sphere (the planar case) were classified by Heuberger (2003), and by a theorem of Thomassen (1991), there are only finitely many vertex-transitive graphs with minimum genus $g$, for any given integer $g \ge 3$. Here we completely determine all connected circulants with minimum genus 1 or 2; this corrects and extends an attempted classification of all toroidal circulants by Costa, Strapasson, Alves and Carlos (2010).
A Pseudoline Counterexample to the Strong Dirac Conjecture
Authors: Lund Ben , Purdy George B. , Smith Justin W.
Published: January 2020

We demonstrate an infinite family of pseudoline arrangements, in which an arrangement of $n$ pseudolines has no member incident to more than $4n/9$ points of intersection. This shows the "Strong Dirac" conjecture to be false for pseudolines.We also raise a number of open problems relating to possible differences between the structure of incidences between points and lines versus the structure of incidences between points and pseudolines.
New Upper Bounds for the Size of Permutation Codes via Linear Programming
Authors: Bogaerts Mathieu
Published: January 2020

An $(n,d)$-permutation code of size $s$ is a subset $C$ of $S_n$ with $s$ elements such that the Hamming distance $d_H$ between any two distinct elements of $C$ is at least equal to $d$. In this paper, we give new upper bounds for the maximal size $\mu(n,d)$ of an $(n,d)$-permutation code of degree $n$ with $11\le n\le 14$. In order to obtain these bounds, we use the structure of association scheme of the permutation group $S_n$ and the irreducible characters of $S_n$. The upper bounds for $\mu(n,d)$ are determined solving an optimization problem with linear inequalities.
Proof of the List Edge Coloring Conjecture for Complete Graphs of Prime Degree
Authors: Schauz Uwe
Published: January 2020

We prove that the list-chromatic index and paintability index of $K_{p+1}$ is $p$, for all odd primes $p$. This implies that the List Edge Coloring Conjecture holds for complete graphs with less then 10 vertices. It also shows that there are arbitrarily big complete graphs for which the conjecture holds, even among the complete graphs of class 1. Our proof combines the Quantitative Combinatorial Nullstellensatz with the Paintability Nullstellensatz and a group action on symmetric Latin squares. It displays various ways of using different Nullstellensätze. We also obtain a partial proof of a version of Alon and Tarsi's Conjecture about even and odd Latin squares.
Partitions of $\mathbf{Z}_m$ with the Same Weighted Representation Functions
Authors: Qu Zhenhua
Published: January 2020

Let $\mathbf{k}=(k_1,k_2,\cdots,k_t)$ be a $t$-tuple of integers, and $m$ be a positive integer. For a subset $A\subset\mathbf{Z}_m$ and any $n\in\mathbf{Z}_m$, let $r_A^{\mathbf{k}}(n)$ denote the number of solutions of the equation $k_1a_1+\cdots+k_ta_t=n$ with $a_1,\cdots,a_t\in A$. In this paper, we give a necessary and sufficient condition on $(\mathbf{k},m)$ such that there exists a subset $A\subset \mathbf{Z}_m$ satisifying $r_{A}^{\mathbf{k}}=r_{\mathbf{Z}_m\backslash A}^{\mathbf{k}}$. This settles a problem of Yang and Chen.
Factoring in Embedding Dimension Three Numerical Semigroups
Authors: Aguiló-Gost F. , García-Sánchez P. A.
Published: January 2020

Let us consider a $3$-numerical semigroup $S=\langle{a,b,N}\rangle$. Given $m\in S$, the triple $(x,y,z)\in\mathbb{N}^3$ is a factorization of $m$ in $S$ if $xa+yb+zN=m$. This work is focused on finding the full set of factorizations of any $m\in S$ and as an application we compute the catenary degree of $S$. To this end, we relate a 2D tessellation to $S$ and we use it as a main tool.