bluuebunny/crossref_metadata_2025 huggingface dataset:
Lai's Conditions for Spanning and Dominating Closed Trails
Authors: Chen Wei-Guo , Chen Zhi-Hong , Lu Mei
Published: January 2020

A graph is supereulerian if it has a spanning closed trail. For an integer $r$, let ${\cal Q}_0(r)$ be  the family of 3-edge-connected nonsupereulerian graphs of order at most $r$. For a graph $G$, define $\delta_L(G)=\min\{\max\{d(u), d(v) \}| \  \mbox{ for any $uv\in E(G)$} \}$. For a given integer $p\ge 2$ and a given real number $\epsilon$,  a graph $G$ of order $n$ is said to satisfy a Lai's condition if $\delta_L(G)\ge \frac{n}{p}-\epsilon$.  In this paper, we show that  if $G$ is  a  3-edge-connected graph of order $n$ with $\delta_L(G)\ge \frac{n}{p}-\epsilon$, then there is an integer $N(p, \epsilon)$ such that when $n> N(p,\epsilon)$, $G$ is supereulerian if and only if $G$ is not  a graph obtained from a  graph $G_p$ in the finite family ${\cal Q}_0(3p-5)$ by replacing some vertices in $G_p$ with nontrivial graphs. Results on the best possible Lai's  conditions for Hamiltonian line graphs of 3-edge-connected graphs or 3-edge-connected supereulerian graphs are given,  which are improvements of the results in [J. Graph Theory 42(2003) 308-319] and in [Discrete Mathematics, 310(2010) 2455-2459].
Shattering-Extremal Set Systems of VC Dimension at most 2
Authors: Mészáros Tamás , Rónyai Lajos
Published: January 2020

We say that a set system $\mathcal{F}\subseteq 2^{[n]}$ shatters a given set $S\subseteq [n]$ if $2^S=\{F~\cap~S ~:~F~\in~\mathcal{F}\}$. The Sauer inequality states that in general, a set system $\mathcal{F}$ shatters at least $|\mathcal{F}|$ sets. Here we concentrate on the case of equality. A set system is called shattering-extremal if it shatters exactly $|\mathcal{F}|$ sets. In this paper we characterize shattering-extremal set systems of Vapnik-Chervonenkis dimension $2$ in terms of their inclusion graphs, and as a corollary we answer an open question about leaving out elements from shattering-extremal set systems in the case of families of Vapnik-Chervonenkis dimension $2$.
Sprague-Grundy Values of the $\mathcal{R}$-Wythoff Game
Authors: Gu Albert
Published: January 2020

We examine the Sprague-Grundy values of the game of $\mathcal{R}$-Wythoff, a restriction of Wythoff's game introduced by Ho, where each move is either to remove a positive number of tokens from the larger pile or to remove the same number of tokens from both piles. Ho showed that the $P$-positions of $\mathcal{R}$-Wythoff agree with those of Wythoff's game, and found all positions of Sprague-Grundy value $1$. We describe all the positions of Sprague-Grundy value $2$ and $3$, and also conjecture a general form of the positions of Sprague-Grundy value $g$.
The Maximum Difference between the Number of Atoms and Number of Coatoms of a Bruhat Interval of the Symmetric Group
Authors: Tsukerman Emmanuel
Published: January 2020

We determine the largest difference between the number of atoms and number of coatoms of a Bruhat interval of the symmetric group $S_n$. We then pose the question of describing such extremal intervals $[u,v] \subset S_n$ and give a partial description by specifying the elements $v$ that can occur.
An improved lower bound related to the Furstenberg-Sárközy theorem
Authors: Lewko Mark
Published: January 2020

Let $D(n)$ denote the cardinality of the largest subset of the set $\{1,2,\ldots,n\}$ such that the difference of no pair of distinct elements is a square. A well-known theorem of Furstenberg and Sárközy states that $D(n)=o(n)$. In the other direction, Ruzsa has proven that $D(n) \gtrsim n^{\gamma}$ for $\gamma = \frac{1}{2}\left( 1 + \frac{\log 7}{\log 65} \right) \approx 0.733077$. We improve this to $\gamma = \frac{1}{2}\left( 1 + \frac{\log 12}{\log 205} \right)  \approx 0.733412$.
Exchangeable Pairs, Switchings, and Random Regular Graphs
Authors: Johnson Tobias
Published: January 2020

We consider the distribution of cycle counts in a random regular graph, which is closely linked to the graph's spectral properties. We broaden the asymptotic regime in which the cycle counts are known to be approximately Poisson, and we give an explicit bound in total variation distance for the approximation. Using this result, we calculate limiting distributions of linear eigenvalue statistics for random regular graphs. Previous results on the distribution of cycle counts by McKay, Wormald, and Wysocka (2004) used the method of switchings, a combinatorial technique for asymptotic enumeration. Our proof uses Stein's method of exchangeable pairs and demonstrates an interesting connection between the two techniques.
On the Number of Independent Sets in a Tree
Authors: Law Hiu-Fai
Published: January 2020

We show in a simple way that for any $k,m\in{\Bbb N}$, there exists a tree $T$ such that the number of independent sets of $T$ is congruent to $k$ modulo $m$. This resolves a conjecture of Wagner (Almost all trees have an even number of independent sets, Electron. J. Combin. 16 (2009), # R93).
Generalized Cages
Authors: Boben Marko , Jajcay Robert , Pisanski Tomaz
Published: January 2020

Let $2 \leq k_1 < k_2 < \ldots < k_t $, $3 \leq g_1 < g_2 < \ldots < g_s < N$ be integer parameters. A $(k_1,k_2,\ldots,k_t;g_1,g_2,\dots,g_s;N)$-graph is a graph that contains vertices of degrees $k_1,k_2,\ldots,k_t$ but no other degrees and cycles of lengths $g_1,g_2,\dots,g_s$ but no other cycles of length $< N$. For any given set of parameters satisfying the above conditions, we present an explicit construction of $(k_1,k_2,\ldots,k_t;g_1,g_2,\dots,g_s;N)$-graphs and extend the concept of a cage (a smallest graph of given degree and girth) to that of a generalized cage -- a smallest $(k_1,k_2,\ldots,k_t;g_1,g_2,\dots,g_s;N)$-graph. We introduce several infinite families of generalized cages and study their basic properties in the context of connected, bipartite, and vertex-transitive graphs,  as well as combinatorial configurations (in the context of multilaterals).
Biembeddings of 2-Rotational Steiner Triple Systems
Authors: Grannell M. J. , Schroeder J. Z.
Published: January 2020

It is shown that for $v\equiv 1$ or 3 (mod 6), every pair of Heffter difference sets modulo $v$ gives rise to a biembedding of two 2-rotational Steiner triple systems of order $2v+1$ in a nonorientable surface.
Ehrhart Series of Polytopes Related to Symmetric Doubly-Stochastic Matrices
Authors: Davis Robert
Published: January 2020

In Ehrhart theory, the $h^*$-vector of a rational polytope often provides insights into properties of the polytope that may be otherwise obscured. As an example, the Birkhoff polytope, also known as the polytope of real doubly-stochastic matrices, has a unimodal $h^*$-vector, but when even small modifications are made to the polytope, the same property can be very difficult to prove. In this paper, we examine the $h^*$-vectors of a class of polytopes containing real doubly-stochastic symmetric matrices.
A Generalization of Generalized Paley Graphs and New Lower Bounds for $R(3,q)$
Authors: Wu Kang , Su Wenlong , Luo Haipeng , Xu Xiaodong
Published: January 2020

Generalized Paley graphs are cyclic graphs constructed from quadratic or higher residues of finite fields. Using this type of cyclic graphs to study the lower bounds for classical Ramsey numbers, has high computing efficiency in both looking for parameter sets and computing clique numbers. We have found a new generalization of generalized Paley graphs, i.e. automorphism cyclic graphs, also having the same advantages. In this paper we study the properties of the parameter sets of automorphism cyclic graphs, and develop an algorithm to compute the order of the maximum independent set, based on which we get new lower bounds for $8$ classical Ramsey numbers: $R(3,22) \geq 131$, $R(3,23) \geq 137$, $R(3,25) \geq 154$, $R(3,28) \geq 173$, $R(3,29) \geq 184$, $R(3,30) \geq 190$, $R(3,31) \geq 199$, $R(3,32) \geq 214$. Furthermore, we also get $R(5,23) \geq 521$ based on $R(3,22) \geq 131$. These nine results above improve their corresponding best known lower bounds.
On Stanley's Partition Function
Authors: Chen William Y. C. , Ji Kathy Q. , Zhu Albert J. W.
Published: January 2020

Stanley defined a partition function $t(n)$ as the number of partitions $\lambda$ of $n$ such that the number of odd parts of $\lambda$ is congruent to the number of odd parts of the conjugate partition $\lambda'$ modulo $4$. We show that $t(n)$ equals the number of partitions of $n$ with an even number of hooks of even length. We derive a closed-form formula for the generating function for the numbers $p(n)-t(n)$. As a consequence, we see that $t(n)$ has the same parity as the ordinary partition function $p(n)$. A simple combinatorial explanation of this fact is also provided.
Asymptotically Optimal Pairing Strategy for Tic-Tac-Toe with Numerous Directions
Authors: Mukkamala Padmini , Pálvölgyi Dömötör
Published: January 2020

We show that there is an $m=2n+o(n)$, such that, in the Maker-Breaker game played on $\mathbb{Z}^d$ where Maker needs to put at least $m$ of his marks consecutively in one of $n$ given winning directions, Breaker can force a draw using a pairing strategy. This improves the result of Kruczek and Sundberg [Electronic Journal of Combinatorics 15(1):N42, 2008] who showed that such a pairing strategy exists if $m\ge 3n$. A simple argument shows that $m$ has to be at least $2n+1$ if Breaker is only allowed to use a pairing strategy, thus the main term of our bound is optimal.
Clusters in a Multigraph with Elevated Density
Authors: Goldberg Mark K.
Published: January 2020

In this paper, we prove that in a multigraph whose density $\Gamma$ exceeds the maxiimum vertex degree $\Delta$, the collection of minimal clusters (maximally dense sets of vertices) is cycle-free. We also prove that for multigraphs with $\Gamma\gt\Delta+1$, the size of any cluster is bounded from the above by $(\Gamma-3)/(\Gamma-\Delta-1)$. Finally, we show that two well-known lower bounds for the chromatic index of a multigraph are equal.
The Edge-Count Criterion for Graphic Lists
Authors: Isaak Garth , West Douglas B.
Published: January 2020

We give a new short proof of Koren's characterization of graphic lists, extended to multigraphs with bounded multiplicity $p$, called $p$-graphs. The Edge-Count Criterion (ECC) for an integer $n$-tuple $d$ and integer $p$ is the statement that for all disjoint sets $I$ and $J$ of indices, $\sum_{i\in I} d_i+\sum_{j\in J} [p(n-1)-d_j]\ge p|I|\,|J|$. An integer list $d$ is the degree list of a $p$-graph if and only if it has even sum and satisfies ECC. Analogous statements hold for bipartite or directed graphs, and an old characterization of degree lists of signed graphs follows as a corollary of the extension to multigraphs.
On the Modes of Polynomials Derived from Nondecreasing Sequences
Authors: Dou Donna Q. J. , Yang Arthur L. B.
Published: January 2020

Wang and Yeh proved that if $P(x)$ is a polynomial with nonnegative and nondecreasing coefficients, then $P(x+d)$ is unimodal for any $d>0$. A mode of a unimodal polynomial $f(x)=a_0+a_1x+\cdots + a_mx^m$ is an index $k$ such that $a_k$ is the maximum coefficient. Suppose that $M_*(P,d)$ is the smallest mode of $P(x+d)$, and $M^*(P,d)$ the greatest mode. Wang and Yeh conjectured that if $d_2>d_1>0$, then $M_*(P,d_1)\geq M_*(P,d_2)$ and $M^*(P,d_1)\geq M^*(P,d_2)$. We give a proof of this conjecture.
Subplanes of Order $3$ in Hughes Planes
Authors: Caliskan Cafer , Moorhouse G. Eric
Published: January 2020

In this study we show the existence of subplanes of order $3$ in Hughes planes of order $q^2$, where $q$ is a prime power and $q \equiv 5 \ (mod \ 6)$. We further show that there exist finite partial linear spaces which cannot embed in any Hughes plane.
Which Chessboards have a Closed Knight's Tour within the Rectangular Prism?
Authors: DeMaio Joe , Mathew Bindia
Published: January 2020

A closed knight's tour of a chessboard uses legal moves of the knight to visit every square exactly once and return to its starting position. In 1991 Schwenk completely classified the $m\times n$ rectangular chessboards that admit a closed knight's tour. In honor of the upcoming twentieth anniversary of the publication of Schwenk's paper, this article extends his result by classifying the $i\times j\times k$ rectangular prisms that admit a closed knight's tour.
On the Number of Maximal Intersecting $k$-Uniform Families and Further Applications of Tuza's Set Pair Method
Authors: Nagy Zoltán Lóránt , Patkós Balázs
Published: January 2020

We study the function $M(n,k)$ which denotes the number of maximal $k$-uniform intersecting families $\mathcal{F}\subseteq \binom{[n]}{k}$. Improving a bound of Balogh, Das, Delcourt, Liu and Sharifzadeh on $M(n,k)$, we determine the order of magnitude of $\log M(n,k)$ by proving that for any fixed $k$, $M(n,k) =n^{\Theta(\binom{2k}{k})}$ holds. Our proof is based on Tuza's set pair approach.The main idea is to bound the size of the largest possible point set of a cross-intersecting system. We also introduce and investigate some related functions and parameters.
Asymptotic Enumeration of Labelled Graphs by Genus
Authors: Bender Edward A. , Gao Zhicheng
Published: January 2020

We obtain asymptotic formulas for the number of rooted 2-connected and 3-connected surface maps on an orientable surface of genus $g$ with respect to vertices and edges simultaneously. We also derive the bivariate version of the large face-width result for random 3-connected maps. These results are then used to derive asymptotic formulas for the number of labelled $k$-connected graphs of orientable genus $g$ for $k\le3$.
On Multicolor Ramsey Number of Paths Versus Cycles
Authors: Omidi Gholam Reza , Raeisi Ghaffar
Published: January 2020

Let $G_1, G_2, G_3, \ldots , G_t$ be graphs. The multicolor Ramsey number $R(G_1, G_2, \ldots, G_t)$ is the smallest positive integer $n$ such that if the edges of a complete graph $K_n$ are partitioned into $t$ disjoint color classes giving $t$ graphs $H_1,H_2,\ldots,H_t$, then at least one $H_i$ has a subgraph isomorphic to $G_i$. In this paper, we provide the exact value of $R(P_{n_1}, P_{n_2},\ldots, P_{n_t},C_k)$ for certain values of $n_i$ and $k$. In addition, the exact values of $R(P_5,C_4,P_k)$, $R(P_4,C_4,P_k)$, $R(P_5,P_5,P_k)$ and $R(P_5,P_6,P_k)$ are given. Finally, we give a lower bound for $R(P_{2n_1}, P_{2n_2},\ldots, P_{2n_t})$ and we conjecture that this lower bound is the exact value of this number. Moreover, some evidence is given for this conjecture.
A Combinatorial Formula for Orthogonal Idempotents in the $0$-Hecke Algebra of the Symmetric Group
Authors: Denton Tom
Published: January 2020

Building on the work of P.N. Norton, we give combinatorial formulae for two maximal decompositions of the identity into orthogonal idempotents in the $0$-Hecke algebra of the symmetric group, $\mathbb{C}H_0(S_N)$. This construction is compatible with the branching from $S_{N-1}$ to $S_{N}$.
A Generalization of Some Huang–Johnson Semifields
Authors: Johnson N. L. , Marino Giuseppe , Polverino Olga , Trombetti Rocco
Published: January 2020

In [H. Huang, N.L. Johnson: Semifield planes of order $8^2$, Discrete Math., 80 (1990)], the authors exhibited seven sporadic semifields of order $2^6$, with left nucleus ${\mathbb F}_{2^3}$ and center ${\mathbb F}_2$. Following the notation of that paper, these examples are referred as the Huang–Johnson semifields of type $II$, $III$, $IV$, $V$, $VI$, $VII$ and $VIII$. In [N. L. Johnson, V. Jha, M. Biliotti: Handbook of Finite Translation Planes, Pure and Applied Mathematics, Taylor Books, 2007], the question whether these semifields are contained in larger families, rather then sporadic, is posed. In this paper, we first prove that the Huang–Johnson semifield of type $VI$ is isotopic to a cyclic semifield, whereas those of types $VII$ and $VIII$ belong to infinite families recently constructed in [N.L. Johnson, G. Marino, O. Polverino, R. Trombetti: Semifields of order $q^6$ with left nucleus ${\mathbb F}_{q^3}$ and center ${\mathbb F}_q$, Finite Fields Appl., 14 (2008)] and [G.L. Ebert, G. Marino, O. Polverino, R. Trombetti: Infinite families of new semifields, Combinatorica, 6 (2009)]. Then, Huang–Johnson semifields of type $II$ and $III$ are extended to new infinite families of semifields of order $q^6$, existing for every prime power $q$.
The Number of $f$-Matchings in Almost Every Tree is a Zero Residue
Authors: Alon Noga , Haber Simi , Krivelevich Michael
Published: January 2020

For graphs $F$ and $G$ an $F$-matching in $G$ is a subgraph of $G$ consisting of pairwise vertex disjoint copies of $F$. The number of $F$-matchings in $G$ is denoted by $s(F,G)$. We show that for every fixed positive integer $m$ and every fixed tree $F$, the probability that $s(F,\mathcal{T}_n) \equiv 0 \pmod{m}$, where $\mathcal{T}_n$ is a random labeled tree with $n$ vertices, tends to one exponentially fast as $n$ grows to infinity. A similar result is proven for induced $F$-matchings. As a very special special case this implies that the number of independent sets in a random labeled tree is almost surely a zero residue. A recent result of Wagner shows that this is the case for random unlabeled trees as well.
GBRDs with Block Size Three over 2-Groups, Semi-Dihedral Groups and Nilpotent Groups
Authors: Abel R. Julian R. , Combe Diana , Nelson Adrian M. , Palmer William D.
Published: January 2020

There are well known necessary conditions for the existence of a generalized Bhaskar Rao design over a group $\mathbb{G}$, with block size $k=3$. We prove that they are sufficient for nilpotent groups $\mathbb{G}$ of even order, and in particular for $2$-groups. In addition, we prove that they are sufficient for semi-dihedral groups.
The Inverse Problem Associated to the Davenport Constant for $C_2\oplus C_2 \oplus C_{2n}$, and Applications to the Arithmetical Characterization of Class Groups
Authors: Schmid Wolfgang A.
Published: January 2020

The inverse problem associated to the Davenport constant for some finite abelian group is the problem of determining the structure of all minimal zero-sum sequences of maximal length over this group, and more generally of long minimal zero-sum sequences. Results on the maximal multiplicity of an element in a long minimal zero-sum sequence for groups with large exponent are obtained. For groups of the form $C_2^{r-1}\oplus C_{2n}$ the results are optimal up to an absolute constant. And, the inverse problem, for sequences of maximal length, is solved completely for groups of the form $C_2^2 \oplus C_{2n}$. Some applications of this latter result are presented. In particular, a characterization, via the system of sets of lengths, of the class group of rings of algebraic integers is obtained for certain types of groups, including $C_2^2 \oplus C_{2n}$ and $C_3 \oplus C_{3n}$; and the Davenport constants of groups of the form $C_4^2 \oplus C_{4n}$ and $C_6^2 \oplus C_{6n}$ are determined.
Independence Complexes and Edge Covering Complexes via Alexander Duality
Authors: Kawamura Kazuhiro
Published: January 2020

The combinatorial Alexander dual of the independence complex $\mathrm{Ind}(G)$ and that of the edge covering complex $\mathrm{EC}(G)$ are shown to have isomorphic homology groups for each non-null graph $G$. This yields isomorphisms of homology groups of $\mathrm{Ind}(G)$ and $\mathrm{EC}(G)$ with homology dimensions being appropriately shifted and restricted. The results exhibits the complementary nature of homology groups of $\mathrm{Ind}(G)$ and $\mathrm{EC}(G)$ which had been proved by Ehrenborg-Hetyei, Engström, and Marietti-Testa for forests at homotopy level.
Counting $k$-Marked Durfee Symbols
Authors: Kurşungöz Kağan
Published: January 2020

An alternative characterization of $k$-marked Durfee symbols defined by Andrews is given. Some identities involving generating functions of $k$-marked Durfee symbols are proven combinatorially by considering the symbols not individually, but in equivalence classes. Also, a related binomial coefficient identity is obtained in the course.
Composition Matrices, (2+2)-Free Posets and their Specializations
Authors: Dukes Mark , Jelínek Vít , Kubitzke Martina
Published: January 2020

In this paper we present a bijection between composition matrices and ($\mathbf{2+2}$)-free posets. This bijection maps partition matrices to factorial posets, and induces a bijection from upper triangular matrices with non-negative entries having no rows or columns of zeros to unlabeled ($\mathbf{2+2}$)-free posets. Chains in a ($\mathbf{2+2}$)-free poset are shown to correspond to entries in the associated composition matrix whose hooks satisfy a simple condition. It is shown that the action of taking the dual of a poset corresponds to reflecting the associated composition matrix in its anti-diagonal. We further characterize posets which are both ($\mathbf{2+2}$)- and ($\mathbf{3+1}$)-free by certain properties of their associated composition matrices.
On a Conjecture of Frankl and Füredi
Authors: Chowdhury Ameera
Published: January 2020

Frankl and Füredi conjectured that if ${\cal F} \subset 2^{X}$ is a non-trivial $\lambda$-intersecting family of size $m$, then the number of pairs $\{x,y\} \in \binom{X}{2}$ that are contained in some $F \in {\cal F}$ is at least $\binom{m}{2}$ [P. Frankl and Z. Füredi. A Sharpening of Fisher's Inequality. Discrete Math., 90(1):103-107, 1991]. We verify this conjecture in some special cases, focusing especially on the case where ${\cal F}$ is additionally required to be $k$-uniform and $\lambda$ is small.
Enumeration of Pin-Permutations
Authors: Bassino Frédérique , Bouvel Mathilde , Rossin Dominique
Published: January 2020

In this paper, we study the class of pin-permutations, that is to say of permutations having a pin representation. This class has been recently introduced by Brignall, Huczynska and Vatter who used it to find properties (algebraicity of the generating function, decidability of membership) of classes of permutations, depending on the simple permutations this class contains. We give a recursive characterization of the substitution decomposition trees of pin-permutations, which allows us to compute the generating function of this class, and consequently to prove, as it is conjectured by Brignall, Ruškuc and Vatter, the rationality of this generating function. Moreover, we show that the basis of the pin-permutation class is infinite.
Hamiltonicity of $k$-Traceable Graphs
Authors: Bullock Frank , Dankelmann Peter , Frick Marietjie , Henning Michael A. , Oellermann Ortrud R. , Van Aardt Susan
Published: January 2020

Let $G$ be a graph. A Hamilton path in $G$ is a path containing every vertex of $G$. The graph $G$ is traceable if it contains a Hamilton path, while $G$ is $k$-traceable if every induced subgraph of $G$ of order $k$ is traceable. In this paper, we study hamiltonicity of $k$-traceable graphs. For $k \geq 2$ an integer, we define $H(k)$ to be the largest integer such that there exists a $k$-traceable graph of order $H(k)$ that is nonhamiltonian. For $k \le 10$, we determine the exact value of $H(k)$. For $k \ge 11$, we show that $k+2 \le H(k) \le \frac{1}{2}(3k-5)$.
Colorings and Nowhere-Zero Flows of Graphs in Terms of Berlekamp's Switching Game
Authors: Schauz Uwe
Published: January 2020

We work with a unifying linear algebra formulation for nowhere-zero flows and colorings of graphs and matrices. Given a subspace (code) $U\leq{\mathbb{Z}_k^n}$ – e.g. the bond or the cycle space over ${\mathbb{Z}}_k$ of an oriented graph – we call a nowhere-zero tuple $f\in{\mathbb{Z}_k^n}$ a flow of $U$ if $f$ is orthogonal to $U$. In order to detect flows, we view the subspace $U$ as a light pattern on the $n$-dimensional Berlekamp Board ${\mathbb{Z}_k^n}$ with $k^n$ light bulbs. The lights corresponding to elements of $U$ are ON, the others are OFF. Then we allow axis-parallel switches of complete rows, columns, etc. The core result of this paper is that the subspace $U$ has a flow if and only if the light pattern $U$ cannot be switched off. In particular, a graph $G$ has a nowhere-zero $k$-flow if and only if the ${\mathbb{Z}}_k$-bond space of $G$ cannot be switched off. It has a vertex coloring with $k$ colors if and only if a certain corresponding code over ${\mathbb{Z}}_k$ cannot be switched off. Similar statements hold for Tait colorings, and for nowhere-zero points of matrices. Studying different normal forms to equivalence classes of light patterns, we find various new equivalents, e.g., for the Four Color Problem, Tutte's Flow Conjectures and Jaeger's Conjecture. Two of our equivalents for colorability and existence of nowhere zero flows of graphs include as special cases results by Matiyasevich, by Balázs Szegedy, and by Onn. Alon and Tarsi's sufficient condition for $k$-colorability also arrives, remarkably, as a generalized full equivalent.
Further Hopping with Toads and Frogs
Authors: Thanatipanonda Thotsaporn "Aek"
Published: January 2020

We prove some new results about the combinatorial game "Toads and Frogs". We give a finite number of recurrence relations for computing the values of all positions with exactly one $\Box$. We show that ${\rm T}^{a}\Box\Box{\rm F}^{a}$ is an infinitesimal for $a\geq 4$. At the end, we make five new conjectures and describe possible future work.
Nonexistence of Graphs with Cyclic Defect
Authors: Miller Mirka
Published: January 2020

In this note we consider graphs of maximum degree $\Delta$, diameter $D$ and order ${\rm M}(\Delta,D) - 2$, where ${\rm M}(\Delta,D)$ is the Moore bound, that is, graphs of defect 2. Delorme and Pineda-Villavicencio conjectured that such graphs do not exist for $D\geq 3$ if they have the so called 'cyclic defect'. Here we prove that this conjecture holds.
Unimodal Rays in the Regular and Generalized Pascal Pyramids
Authors: Belbachir Hacène , Szalay László
Published: January 2020

The present paper shows that any sequence of integers laying along a finite ray in any Pascal-pyramid is log-concave, consequently unimodal. Further, we describe an algorithm which provides the plateaus of the diagonal sequences locating on layer $n$ of the regular Pascal pyramid.
Alspach's Problem: The Case of Hamilton Cycles and 5-Cycles
Authors: Jordon Heather
Published: January 2020

In this paper, we settle Alspach's problem in the case of Hamilton cycles and 5-cycles; that is, we show that for all odd integers $n\ge 5$ and all nonnegative integers $h$ and $t$ with $hn + 5t = n(n-1)/2$, the complete graph $K_n$ decomposes into $h$ Hamilton cycles and $t$ 5-cycles and for all even integers $n \ge 6$ and all nonnegative integers $h$ and $t$ with $hn + 5t = n(n-2)/2$, the complete graph $K_n$ decomposes into $h$ Hamilton cycles, $t$ 5-cycles, and a $1$-factor. We also settle Alspach's problem in the case of Hamilton cycles and 4-cycles.
On Cubic Planar Hypohamiltonian and Hypotraceable Graphs
Authors: Araya Makoto , Wiener Gábor
Published: January 2020

We present a cubic planar hypohamiltonian graph on 70 vertices, improving the best known bound of 94 by Thomassen and derive some consequences concerning longest paths and cycles of planar $3$-connected graphs. We also show that cubic planar hypohamiltonian graphs on $n$ vertices exist for every even number $n\geq 86$ and that cubic planar hypotraceable graphs exist on $n$ vertices for every even number $n \geq 356$, settling an open question of Holton and Sheehan.
Extensions of Toric Varieties
Authors: Şahin Mesut
Published: January 2020

In this paper, we introduce the notion of "extension" of a toric variety and study its fundamental properties. This gives rise to infinitely many toric varieties with a special property, such as being set theoretic complete intersection or arithmetically Cohen-Macaulay (Gorenstein) and having a Cohen-Macaulay tangent cone or a local ring with non-decreasing Hilbert function, from just one single example with the same property, verifying Rossi's conjecture for larger classes and extending some results appeared in literature.
Embedding a Forest in a Graph
Authors: Goldberg Mark K. , Magdon-Ismail Malik
Published: January 2020

For $p\ge 1$, we prove that every forest with $p$ trees whose sizes are $a_1, \ldots, a_p$ can be embedded in any graph containing at least $\sum_{i=1}^p (a_i + 1)$ vertices and having minimum degree at least $\sum_{i=1}^p a_i$.
Vertex-Transitive $q$-Complementary Uniform Hypergraphs
Authors: Gosselin Shonda
Published: January 2020

For a positive integer $q$, a $k$-uniform hypergraph $X=(V,E)$ is $q$-complementary if there exists a permutation $\theta$ on $V$ such that the sets $E, E^{\theta}, E^{\theta^2},\ldots, E^{\theta^{q-1}}$ partition the set of $k$-subsets of $V$. The permutation $\theta$ is called a $q$-antimorphism of $X$. The well studied self-complementary uniform hypergraphs are 2-complementary. For an integer $n$ and a prime $p$, let $n_{(p)}=\max\{i:p^i \text{divides} n\}$. In this paper, we prove that a vertex-transitive $q$-complementary $k$-hypergraph of order $n$ exists if and only if $n^{n_{(p)}}\equiv 1 (\bmod q^{\ell+1})$ for every prime number $p$, in the case where $q$ is prime, $k = bq^\ell$ or $k=bq^{\ell}+1$ for a positive integer $b < k$, and $n\equiv 1(\bmod q^{\ell+1})$. We also find necessary conditions on the order of these structures when they are $t$-fold-transitive and $n\equiv t (\bmod q^{\ell+1})$, for $1\leq t < k$, in which case they correspond to large sets of isomorphic $t$-designs. Finally, we use group theoretic results due to Burnside and Zassenhaus to determine the complete group of automorphisms and $q$-antimorphisms of these hypergraphs in the case where they have prime order, and then use this information to write an algorithm to generate all of these objects. This work extends previous, analagous results for vertex-transitive self-complementary uniform hypergraphs due to Muzychuk, Potočnik, Šajna, and the author. These results also extend the previous work of Li and Praeger on decomposing the orbitals of a transitive permutation group.
Quantum Field Theory over $\mathbb{F}_q$
Authors: Schnetz Oliver
Published: January 2020

We consider the number $\bar N(q)$ of points in the projective complement of graph hypersurfaces over $\mathbb{F}_q$ and show that the smallest graphs with non-polynomial $\bar N(q)$ have 14 edges. We give six examples which fall into two classes. One class has an exceptional prime 2 whereas in the other class $\bar N(q)$ depends on the number of cube roots of unity in $\mathbb{F}_q$. At graphs with 16 edges we find examples where $\bar N(q)$ is given by a polynomial in $q$ plus $q^2$ times the number of points in the projective complement of a singular K3 in $\mathbb{P}^3$. In the second part of the paper we show that applying momentum space Feynman-rules over $\mathbb{F}_q$ lets the perturbation series terminate for renormalizable and non-renormalizable bosonic quantum field theories.
Permutation Tableaux and the Dashed Permutation Pattern 32–1
Authors: Chen William Y.C. , Liu Lewis H.
Published: January 2020

We give a solution to a problem posed by Corteel and Nadeau concerning permutation tableaux of length $n$ and the number of occurrences of the dashed pattern 32–1 in permutations on $[n]$. We introduce the inversion number of a permutation tableau. For a permutation tableau $T$ and the permutation $\pi$ obtained from $T$ by the bijection of Corteel and Nadeau, we show that the inversion number of $T$ equals the number of occurrences of the dashed pattern 32–1 in the reverse complement of $\pi$. We also show that permutation tableaux without inversions coincide with L-Bell tableaux introduced by Corteel and Nadeau.
Finite Factors of Bernoulli Schemes and Distinguishing Labelings of Directed Graphs
Authors: Lazowski Andrew , Shea Stephen M.
Published: January 2020

A labeling of a graph is a function from the vertices of the graph to some finite set.  In 1996, Albertson and Collins defined distinguishing labelings of undirected graphs.  Their definition easily extends to directed graphs.  Let $G$ be a directed graph associated to the $k$-block presentation of a Bernoulli scheme $X$.  We determine the automorphism group of $G$, and thus the distinguishing labelings of $G$.  A labeling of $G$ defines a finite factor of $X$.  We define demarcating labelings and prove that demarcating labelings define finitarily Markovian finite factors of $X$.  We use the Bell numbers to find a lower bound for the number of finitarily Markovian finite factors of a Bernoulli scheme.  We show that demarcating labelings of $G$ are distinguishing.
Blocking Wythoff Nim
Authors: Larsson Urban
Published: January 2020

The 2-player impartial game of Wythoff Nim is played on two piles of tokens. A move consists in removing any number of tokens from precisely one of the piles or the same number of tokens from both piles. The winner is the player who removes the last token. We study this game with a blocking maneuver, that is, for each move, before the next player moves the previous player may declare at most a predetermined number, $k - 1 \ge 0$, of the options as forbidden. When the next player has moved, any blocking maneuver is forgotten and does not have any further impact on the game. We resolve the winning strategy of this game for $k = 2$ and $k = 3$ and, supported by computer simulations, state conjectures of 'sets of aggregation points' for the $P$-positions whenever $4 \le k \le 20$. Certain comply variations of impartial games are also discussed.
The Quantifier Semigroup for Bipartite Graphs
Authors: Schulman Leonard J.
Published: January 2020

In a bipartite graph there are two widely encountered monotone mappings from subsets of one side of the graph to subsets of the other side: one corresponds to the quantifier "there exists a neighbor in the subset" and the other to the quantifier "all neighbors are in the subset." These mappings generate a partially ordered semigroup which we characterize in terms of "run-unimodal" words.
Identities Derived from Noncrossing Partitions of Type $B$
Authors: Chen William Y. C. , Wang Andrew Y. Z. , Zhao Alina F. Y.
Published: January 2020

Based on weighted noncrossing partitions of type $B$, we obtain type $B$ analogues of Coker's identities on the Narayana polynomials. A parity reversing involution is given for the alternating sum of Narayana numbers of type $B$. Moreover, we find type $B$ analogues of the refinements of Coker's identities due to Chen, Deutsch and Elizalde. By combinatorial constructions, we provide type $B$ analogues of three identities of Mansour and Sun also on the Narayana polynomials.
Enumerating all Hamilton Cycles and Bounding the Number of Hamilton Cycles in 3-Regular Graphs
Authors: Gebauer Heidi
Published: January 2020

We describe an algorithm which enumerates all Hamilton cycles of a given 3-regular $n$-vertex graph in time $O(1.276^{n})$, improving on Eppstein's previous bound. The resulting new upper bound of $O(1.276^{n})$ for the maximum number of Hamilton cycles in 3-regular $n$-vertex graphs gets close to the best known lower bound of $\Omega(1.259^{n})$. Our method differs from Eppstein's in that he considers in each step a new graph and modifies it, while we fix (at the very beginning) one Hamilton cycle $C$ and then proceed around $C$, successively producing partial Hamilton cycles.
Further Applications of a Power Series Method for Pattern Avoidance
Authors: Rampersad Narad
Published: January 2020

In combinatorics on words, a word $w$ over an alphabet $\Sigma$ is said to avoid a pattern $p$ over an alphabet $\Delta$ if there is no factor $x$ of $w$ and no non-erasing morphism $h$ from $\Delta^*$ to $\Sigma^*$ such that $h(p) = x$. Bell and Goh have recently applied an algebraic technique due to Golod to show that for a certain wide class of patterns $p$ there are exponentially many words of length $n$ over a $4$-letter alphabet that avoid $p$. We consider some further consequences of their work. In particular, we show that any pattern with $k$ variables of length at least $4^k$ is avoidable on the binary alphabet. This improves an earlier bound due to Cassaigne and Roth.
Uniqueness of Graph Square Roots of Girth Six
Authors: Adamaszek Anna , Adamaszek Michał
Published: January 2020

We prove that if two graphs of girth at least $6$ have isomorphic squares, then the graphs themselves are isomorphic. This is the best possible extension of the results of Ross and Harary on trees and the results of Farzad et al. on graphs of girth at least $7$. We also make a remark on reconstruction of graphs from their higher powers.
Mr. Paint and Mrs. Correct go Fractional
Authors: Gutowski Grzegorz
Published: January 2020

We study a fractional counterpart of the on-line list colouring game "Mr. Paint and Mrs. Correct" introduced recently by Schauz. We answer positively a question of Zhu by proving that for any given graph the on-line choice ratio and the (off-line) choice ratio coincide. On the other hand it is known from the paper of Alon et al. that the choice ratio equals the fractional chromatic number. It was also shown that the limits used in the definitions of these last two notions can be realised. We show that this is not the case for the on-line choice ratio. Both our results are obtained by exploring the strong links between the on-line choice ratio, and a new on-line game with probabilistic flavour which we introduce.
The Möbius Function of the Consecutive Pattern Poset
Authors: Bernini Antonio , Ferrari Luca , Steingrímsson Einar
Published: January 2020

An occurrence of a consecutive permutation pattern $p$ in a permutation $\pi$ is a segment of consecutive letters of $\pi$ whose values appear in the same order of size as the letters in $p$. The set of all permutations forms a poset with respect to such pattern containment. We compute the Möbius function of intervals in this poset. For most intervals our results give an immediate answer to the question. In the remaining cases, we give a polynomial time algorithm to compute the Möbius function. In particular, we show that the Möbius function only takes the values $-1$, $0$ and $1$.
Characteristic Polynomials of Skew-Adjacency Matrices of Oriented Graphs
Authors: Hou Yaoping , Lei Tiangang
Published: January 2020

An oriented graph $\overleftarrow{G}$ is a simple undirected graph $G$ with an orientation, which assigns to each edge a direction so that $\overleftarrow{G}$ becomes a directed graph. $G$ is called the underlying graph of $\overleftarrow{G}$ and we denote by $S(\overleftarrow{G})$ the skew-adjacency matrix of $\overleftarrow{G}$ and its spectrum $Sp(\overleftarrow{G})$ is called the skew-spectrum of $\overleftarrow{G}$. In this paper, the coefficients of the characteristic polynomial of the skew-adjacency matrix $S(\overleftarrow{G}) $ are given in terms of $\overleftarrow{G}$ and as its applications, new combinatorial proofs of known results are obtained and new families of oriented bipartite graphs $\overleftarrow{G}$ with $Sp(\overleftarrow{G})={\bf i} Sp(G) $ are given.
A Differential Approach for Bounding the Index of Graphs under Perturbations
Authors: Dalfó C. , Fiol M. A. , Garriga E.
Published: January 2020

This paper presents bounds for the variation of the spectral radius $\lambda(G)$ of a graph $G$ after some perturbations or local vertex/edge modifications of $G$. The perturbations considered here are the connection of a new vertex with, say, $g$ vertices of $G$, the addition of a pendant edge (the previous case with $g=1$) and the addition of an edge. The method proposed here is based on continuous perturbations and the study of their differential inequalities associated. Within rather economical information (namely, the degrees of the vertices involved in the perturbation), the best possible inequalities are obtained. In addition, the cases when equalities are attained are characterized. The asymptotic behavior of the bounds obtained is also discussed. For instance, if $G$ is a connected graph and $G_u$ denotes the graph obtained from $G$ by adding a pendant edge at vertex $u$ with degree $\delta_u$, then, $$ \textstyle \lambda(G_u)\le \lambda(G)+\frac{\delta_u}{\lambda^3(G)}+\textrm{o}\left(\frac{1}{\lambda^3(G)}\right). $$
Cyclic and Dihedral 1-Factorizations of Multipartite Graphs
Authors: Bogaerts Mathieu , Mazzuoccolo Giuseppe
Published: January 2020

An automorphism group $G$ of a $1$-factorization of the complete multipartite graph $K_{m\times n}$ consists of permutations of the vertices of the graph mapping factors to factors. In this paper, we give a complete answer to the existence problem of a $1$-factorization of $K_{m\times n}$ admitting a cyclic or dihedral group acting sharply transitively on the vertices of the graph.
Domino Shuffling on Novak Half-Hexagons and Aztec Half-Diamonds
Authors: Nordenstam Eric , Young Benjamin
Published: January 2020

We explore the connections between the well-studied Aztec Diamond graphs and a new family of graphs called the Half-Hexagons, discovered by Jonathan Novak. In particular, both families of graphs have very simple domino shuffling algorithms, which turn out to be intimately related. This connection allows us to prove an "arctic parabola" theorem for the Half-Hexagons as a corollary of the Arctic Circle theorem for the Aztec Diamond.
A Construction for Biembeddings of Latin Squares
Authors: Grannell M. J. , Knor M.
Published: January 2020

An existing construction for face 2-colourable triangular embeddings of complete regular tripartite graphs is extended and then re-examined from the viewpoint of the underlying Latin squares. We prove that this generalization gives embeddings which are not isomorphic to any of those produced by the original construction.
Connected, Bounded Degree, Triangle Avoidance Games
Authors: Mehta Nishali , Seress Ákos
Published: January 2020

We consider variants of the triangle-avoidance game first defined by Harary and rediscovered by Hajnal a few years later. A graph game begins with two players and an empty graph on $n$ vertices. The two players take turns choosing edges within $K_{n}$, building up a simple graph. The edges must be chosen according to a set of restrictions $\mathcal{R}$. The winner is the last player to choose an edge that does not violate any of the restrictions in $\mathcal{R}$. For fixed $n$ and $\mathcal{R}$, one of the players has a winning strategy. For a pair of games where $\mathcal{R}$ includes bounded degree, connectedness, and triangle-avoidance, we determine the winner for all values of $n$.
Symmetric Distribution of Crossings and Nestings in Permutations of Type $B$
Authors: Hamdi Adel
Published: January 2020

This note contains two results on the distribution of crossing numbers and nesting numbers in permutations of type B. More precisely, we prove a $B_n$-analogue of the symmetric distribution of crossings and nestings of permutations due to Corteel [Adv. Appl. Math. 38(2)(2007), 149–163] as well as the symmetric distribution of $k$-crossings and $k$-nestings of permutations due to Burrill et al. [DMTCS proc. AN (2010), 593–600].
On $(C_n;k)$ Stable Graphs
Authors: Cichacz Sylwia , Görlich Agnieszka , Zwonek Magorzata , Żak Andrzej
Published: January 2020

A graph $G$ is called $(H;k)$-vertex stable if $G$ contains a subgraph isomorphic to $H$ ever after removing any $k$ of its vertices; stab$(H;k)$ denotes the minimum size among the sizes of all $(H;k)$-vertex stable graphs. In this paper we deal with $(C_{n};k)$-vertex stable graphs with minimum size. For each $n$ we prove that stab$(C_{n};1)$ is one of only two possible values and we give the exact value for infinitely many $n$'s. Furthermore we establish an upper and lower bound for stab$(C_{n};k)$ for $k\geq 2$.
Nonrepetitive Sequences on Arithmetic Progressions
Authors: Grytczuk Jarosław , Kozik Jakub , Witkowski Marcin
Published: January 2020

A sequence $S=s_{1}s_{2}\ldots s_{n}$ is said to be nonrepetitive if no two adjacent blocks of $S$ are identical. In 1906 Thue proved that there exist arbitrarily long nonrepetitive sequences over $3$-element set of symbols. We study a generalization of nonrepetitive sequences involving arithmetic progressions. We prove that for every $k\geqslant 1$, there exist arbitrarily long sequences over at most $2k+10 \sqrt{k}$ symbols whose subsequences, indexed by arithmetic progressions with common differences from the set $\{1,2,\ldots ,k\}$, are nonrepetitive. This improves a previous bound of $e^{33}k$ obtained by Grytczuk. Our approach is based on a technique introduced recently by Grytczuk Kozik and Micek, which was originally inspired by a constructive proof of the Lovász Local Lemma due to Moser and Tardos. We also discuss some related problems that can be attacked by this method.
On the Spectra of General Random Graphs
Authors: Chung Fan , Radcliffe Mary
Published: January 2020

We consider random graphs such that each edge is determined by an independent random variable, where the probability of each edge is not assumed to be equal. We use a Chernoff inequality for matrices to show that the eigenvalues of the adjacency matrix and the normalized Laplacian of such a random graph can be approximated by those of the weighted expectation graph, with error bounds dependent upon the minimum and maximum expected degrees. In particular, we use these results to bound the spectra of random graphs with given expected degree sequences, including random power law graphs. Moreover, we prove a similar result giving concentration of the spectrum of a matrix martingale on its expectation.
A Ramsey Theorem for Indecomposable Matchings
Authors: Fairbanks James P.
Published: January 2020

A matching is indecomposable if it does not contain a nontrivial contiguous segment of vertices whose neighbors are entirely contained in the segment. We prove a Ramsey-like result for indecomposable matchings, showing that every sufficiently long indecomposable matching contains a long indecomposable matching of one of three types: interleavings, broken nestings, and proper pin sequences.
On Identifying Codes in the King Grid that are Robust Against Edge Deletions
Authors: Honkala Iiro , Laihonen Tero
Published: January 2020

Assume that $G = (V, E)$ is an undirected graph, and $C \subseteq V$. For every $v \in V$, we denote $I_r(G;v) = \{ u \in C: d(u,v) \leq r\}$, where $d(u,v)$ denotes the number of edges on any shortest path from $u$ to $v$. If all the sets $I_r(G;v)$ for $v \in V$ are pairwise different, and none of them is the empty set, the code $C$ is called $r$-identifying. If $C$ is $r$-identifying in all graphs $G'$ that can be obtained from $G$ by deleting at most $t$ edges, we say that $C$ is robust against $t$ known edge deletions. Codes that are robust against $t$ unknown edge deletions form a related class. We study these two classes of codes in the king grid with the vertex set ${\Bbb Z}^2$ where two different vertices are adjacent if their Euclidean distance is at most $\sqrt{2}$.
Explicit Ramsey Graphs and Erdős Distance Problems over Finite Euclidean and Non-Euclidean Spaces
Authors: Vinh Le Anh
Published: January 2020

We study the Erdős distance problem over finite Euclidean and non-Euclidean spaces. Our main tools are graphs associated to finite Euclidean and non-Euclidean spaces that are considered in Bannai-Shimabukuro-Tanaka (2004, 2007). These graphs are shown to be asymptotically Ramanujan graphs. The advantage of using these graphs is twofold. First, we can derive new lower bounds on the Erdős distance problems with explicit constants. Second, we can construct many explicit tough Ramsey graphs $R(3,k)$.