bluuebunny/crossref_metadata_2025 huggingface dataset:
On the Possible Orders of a Basis for a Finite Cyclic Group
Authors: Dukes Peter , Hegarty Peter , Herke Sarada
Published: January 2020

We prove a result concerning the possible orders of a basis for the cyclic group ${\Bbb Z}_n$, namely: For each $k \in {\Bbb N}$ there exists a constant $c_k > 0$ such that, for all $n \in {\Bbb N}$, if $A \subseteq {\Bbb Z}_n$ is a basis of order greater than $n/k$, then the order of $A$ is within $c_k$ of $n/l$ for some integer $l \in [1,k]$. The proof makes use of various results in additive number theory concerning the growth of sumsets. Additionally, exact results are summarized for the possible basis orders greater than $n/4$ and less than $\sqrt{n}$. An equivalent problem in graph theory is discussed, with applications.
From Edge-Coloring to Strong Edge-Coloring
Authors: Borozan Valentin , Chang Gerard Jennhwa , Cohen Nathann , Fujita Shinya , Narayanan Narayanan , Naserasr Reza , Valicov Petru
Published: January 2020

In this paper we study a generalization of both proper edge-coloring and strong edge-coloring: $k$-intersection edge-coloring, introduced by Muthu, Narayanan and Subramanian. In this coloring, the set $S(v)$ of colors used by edges incident to a vertex $v$ does not intersect $S(u)$ on more than $k$ colors when $u$ and $v$ are adjacent. We provide some sharp upper and lower bounds for $\chi'_{k\text{-int}}$ for several classes of graphs. For $l$-degenerate graphs we prove that $\chi'_{k\text{-int}}(G)\leq (l+1)\Delta -l(k-1)-1$. We improve this bound for subcubic graphs by showing that $\chi'_{2\text{-int}}(G)\leq 6$. We show that calculating $\chi'_{k\text{-int}}(K_n)$ for arbitrary values of $k$ and $n$ is related to some problems in combinatorial set theory and we provide bounds that are tight for infinitely many values of $n$. Furthermore, for complete bipartite graphs we prove that $\chi'_{k\text{-int}}(K_{n,m}) = \left\lceil \frac{mn}{k}\right\rceil$. Finally, we show that computing $\chi'_{k\text{-int}}(G)$ is NP-complete for every $k\geq 1$.An addendum was added to this paper on Jul 4, 2015.
On the Codegree Density of Complete 3-Graphs and Related Problems
Authors: Falgas-Ravry Victor
Published: January 2020

Given a 3-graph $F$, its codegree threshold $\textrm{co-ex}(n, F)$ is the largest number $d=d(n)$ such that there exists an $n$-vertex 3-graph in which every pair of vertices is contained in at least $d$ triples but which contains no member of $F$ as a subgraph. The limit\[\gamma(F)=\lim_{n\rightarrow \infty} \frac{\textrm{co-ex}(n,F)}{n-2}\] is known to exist and is called the codegree density of $F$.In this paper we generalise a construction of Czygrinow and Nagle to bound below the codegree density of complete 3-graphs: for all integers $s\geq 4$, the codegree density of the complete 3-graph on $s$ vertices $K_s$ satisfies\[\gamma(K_s)\geq 1-\frac{1}{s-2}.\]We then provide constructions based on Steiner triple systems which show that if this lower bound is sharp, then we do not have stability in general.In addition we prove bounds on the codegree density for two other infinite families of 3-graphs.
The Solution of the $A_r$ T-System for Arbitrary Boundary
Authors: Francesco Philippe Di
Published: January 2020

We present an explicit solution of the $A_r$ $T$-system for arbitrary boundary conditions. For each boundary, this is done by constructing a network, i.e. a graph with positively weighted edges, and the solution is expressed as the partition function for a family of non-intersecting paths on the network. This proves in particular the positive Laurent property, namely that the solutions are all Laurent polynomials of the initial data with non-negative integer coefficients.
Sortable Elements for Quivers with Cycles
Authors: Reading Nathan , Speyer David E
Published: January 2020

Each Coxeter element $c$ of a Coxeter group $W$ defines a subset of $W$ called the $c$-sortable elements. The choice of a Coxeter element of $W$ is equivalent to the choice of an acyclic orientation of the Coxeter diagram of $W$. In this paper, we define a more general notion of $\Omega$-sortable elements, where $\Omega$ is an arbitrary orientation of the diagram, and show that the key properties of $c$-sortable elements carry over to the $\Omega$-sortable elements. The proofs of these properties rely on reduction to the acyclic case, but the reductions are nontrivial; in particular, the proofs rely on a subtle combinatorial property of the weak order, as it relates to orientations of the Coxeter diagram. The $c$-sortable elements are closely tied to the combinatorics of cluster algebras with an acyclic seed; the ultimate motivation behind this paper is to extend this connection beyond the acyclic case.
On the Sharpness of Some Results Relating Cuts and Crossing Numbers
Authors: Beaudou Laurent , Bokal Drago
Published: January 2020

It is already known that for very small edge cuts in graphs, the crossing number of the graph is at least the sum of the crossing number of (slightly augmented) components resulting from the cut. Under stronger connectivity condition in each cut component that was formalized as a graph operation called zip product, a similar result was obtained for edge cuts of any size, and a natural question was asked, whether this stronger condition is necessary. In this paper, we prove that the relaxed condition is not sufficient when the size of the cut is at least four, and we prove that the gap can grow quadratically with the cut size.
The Ramsey Number $R(3,K_{10}-e)$ and Computational Bounds for $R(3,G)$
Authors: Goedgebeur Jan , Radziszowski Stanisław P.
Published: January 2020

Using computer algorithms we establish that the Ramsey number $R(3,K_{10}-e)$ is equal to 37, which solves the smallest open case for Ramsey numbers of this type. We also obtain new upper bounds for the cases of $R(3,K_k-e)$ for $11 \le k \le 16$, and show by construction a new lower bound $55 \le R(3,K_{13}-e)$.The new upper bounds on $R(3,K_k-e)$ are obtained by using the values and lower bounds on $e(3,K_l-e,n)$ for $l \le k$, where $e(3,K_k-e,n)$ is the minimum number of edges in any triangle-free graph on $n$ vertices without $K_k-e$ in the complement. We complete the computation of the exact values of $e(3,K_k-e,n)$ for all $n$ with $k \leq 10$ and for $n \leq 34$ with $k = 11$, and establish many new lower bounds on $e(3,K_k-e,n)$ for higher values of $k$.Using the maximum triangle-free graph generation method, we determine two other previously unknown Ramsey numbers, namely $R(3,K_{10}-K_3-e)=31$ and $R(3,K_{10}-P_3-e)=31$. For graphs $G$ on 10 vertices, besides $G=K_{10}$, this leaves 6 open cases of the form $R(3,G)$. The hardest among them appears to be $G=K_{10}-2K_2$, for which we establish the bounds $31 \le R(3,K_{10}-2K_2) \le 33$.
The Expected Characteristic and Permanental Polynomials of the Random Gram Matrix
Authors: Martin Jacob G. , Canfield E. Rodney
Published: January 2020

A $t \times n$ random matrix $A$ can be formed by sampling $n$ independent random column vectors, each containing $t$ components. The random Gram matrix of size $n$, $G_{n}=A^{T}A$, contains the dot products between all pairs of column vectors in the randomly generated matrix $A$, and has characteristic roots coinciding with the singular values of $A$. Furthermore, the sequences $\det{(G_{i})}$ and $\text{perm}(G_{i})$ (for $i = 0, 1, \dots, n$) are factors that comprise the expected coefficients of the characteristic and permanental polynomials of $G_{n}$. We prove theorems that relate the generating functions and recursions for the traces of matrix powers, expected characteristic coefficients, expected determinants $E(\det{(G_{n})})$, and expected permanents $E(\text{perm}(G_{n}))$ in terms of each other. Using the derived recursions, we exhibit the efficient computation of the expected determinant and expected permanent of a random Gram matrix $G_{n}$, formed according to any underlying distribution. These theoretical results may be used both to speed up numerical algorithms and to investigate the numerical properties of the expected characteristic and permanental coefficients of any matrix comprised of independently sampled columns.
On Counterexamples to a Conjecture of Wills and Ehrhart Polynomials whose Roots have Equal Real Parts
Authors: Henze Matthias
Published: January 2020

As a discrete analog to Minkowski's theorem on convex bodies, Wills conjectured that the Ehrhart coefficients of a $0$-symmetric lattice polytope with exactly one interior lattice point are maximized by those of the cube of side length two. We discuss several counterexamples to this conjecture and, on the positive side, we identify a family of lattice polytopes that fulfill the claimed inequalities. This family is related to the recently introduced class of $l$-reflexive polytopes.
Genus Ranges of 4-Regular Rigid Vertex Graphs
Authors: Buck Dorothy , Dolzhenko Egor , Jonoska Natasa , Saito Masahico , Valencia Karin
Published: January 2020

A rigid vertex of a graph is one that has a prescribed cyclic order of its incident edges. We study orientable genus ranges of 4-regular rigid vertex graphs. The (orientable) genus range is a set of genera values over all orientable surfaces into which a graph is embedded cellularly, and the embeddings of rigid vertex graphs are required to preserve the prescribed cyclic order of incident edges at every vertex. The genus ranges of 4-regular rigid vertex graphs are sets of consecutive integers, and we address two questions: which intervals of integers appear as genus ranges of such graphs, and what types of graphs realize a given genus range. For graphs with $2n$ vertices ($n>1$), we prove that all intervals $[a, b]$ for all $a<b \leq n$, and singletons $[h, h]$ for some $h\leq n$, are realized as genus ranges. For graphs with $2n-1$ vertices ($n\geq 1$), we prove that all intervals $[a, b]$ for all $a<b \leq n$ except $[0,n]$, and $[h,h]$ for some $h\leq n$, are realized as genus ranges. We also provide constructions of graphs that realize these ranges.
Two Simple Proofs of Winquist's Identity
Authors: Nupet Chutchai , Kongsiriwong Sarachai
Published: January 2020

We give two new proofs of Winquist's identity. In the first proof, we use basic properties of cube roots of unity and the Jacobi triple product identity. The latter does not use the Jacobi triple product identity.
Steiner systems $S(2,4,v)$ - a survey
Authors: Reid Colin , Rosa Alex
Published: January 2020

We survey the basic properties and results on Steiner systems $S(2, 4, v)$, as well as open problems.
Cubic Non-Cayley Vertex-Transitive Bi-Cayley Graphs over a Regular $p$-Group
Authors: Zhou Jin-Xin , Feng Yan-Quan
Published: January 2020

A bi-Cayley graph is a graph which admits a semiregular group of automorphisms with two orbits of equal size. In this paper, we give a characterization of cubic non-Cayley vertex-transitive bi-Cayley graphs over a regular $p$-group, where $p>5$ is an odd prime. As an application, a classification of cubic non-Cayley vertex-transitive graphs of order $2p^3$ is given for each prime $p$.
Conditions for the Parameters of the Block Graph of Quasi-Symmetric Designs
Authors: Pawale Rajendra M. , Shrikhande Mohan S. , Nyayate Shubhada M.
Published: January 2020

A quasi-symmetric design (QSD) is a 2-$(v,k,\lambda)$ design with intersection numbers $x$ and $y$ with $x< y$. The block graph of such a design is formed on its blocks with two distinct blocks being adjacent if they intersect in $y$ points. It is well known that the block graph of a QSD is a strongly regular graph (SRG) with parameters $(b,a,c,d)$ with smallest eigenvalue $ -m =-\frac{k-x}{y-x}$.The classification result of SRGs with smallest eigenvalue $-m$, is used to prove that for a fixed pair $(\lambda\ge 2,m\ge 2)$, there are only finitely many QSDs. This gives partial support towards Marshall Hall Jr.'s conjecture, that for a fixed $\lambda\ge 2$, there exist finitely many symmetric $(v, k, \lambda)$-designs.We classify QSDs with $m=2$ and characterize QSDs whose block graph is the complete multipartite graph with $s$ classes of size $3$. We rule out the possibility of a QSD whose block graph is the Latin square graph $LS_m (n)$ or complement of $LS_m (n)$, for $m=3,4$.SRGs with no triangles have long been studied and are of current research interest. The characterization of QSDs with triangle-free block graph for $x=1$ and $y=x+1$ is obtained and the non-existence of such designs with $x=0$ or $\lambda > 2(x+2)$ or if it is a $3$-design is proven. The computer algebra system Mathematica is used to find parameters of QSDs with triangle-free block graph for $2\le m \le 100$. We also give the parameters of QSDs whose block graph parameters are $(b,a,c,d)$ listed in Brouwer's table of SRGs.
On a General $q$-Identity
Authors: Xu Aimin
Published: January 2020

In this paper, by means of the $q$-Rice formula we obtain a general $q$-identity which is a unified generalization of three kinds of identities. Some known results are special cases of ours. Meanwhile, some identities on $q$-generalized harmonic numbers are also derived.
On the Koolen–Park inequality and Terwilliger graphs
Authors: Gavrilyuk Alexander L.
Published: January 2020

J.H. Koolen and J. Park proved a lower bound for the intersection number $c_2$ of a distance-regular graph $\Gamma$. Moreover, they showed that a graph $\Gamma$, for which equality is attained in this bound, is a Terwilliger graph. We prove that $\Gamma$ is the icosahedron, the Doro graph or the Conway–Smith graph if equality is attained and $c_2\ge 2$.
Fan-Extensions in Fragile Matroids
Authors: Chun Carolyn , Chun Deborah , Mayhew Dillon , Van Zwam Stefan H. M.
Published: January 2020

If $\mathcal{S}$ is a set of matroids, then the matroid $M$ is $\mathcal{S}$-fragile if, for every element $e\in E(M)$, either $M\backslash e$ or $M/e$ has no minor isomorphic to a member of $\mathcal{S}$. Excluded-minor characterizations often depend, implicitly or explicitly, on understanding classes of fragile matroids. In certain cases, when $\mathcal{M}$ is a minor-closed class of $\mathcal{S}$-fragile matroids, and $N\in \mathcal{M}$, the only members of $\mathcal{M}$ that contain $N$ as a minor are obtained from $N$ by increasing the length of fans. We prove that if this is the case, then we can certify it with a finite case-analysis. The analysis  involves examining matroids that are at most two elements larger than $N$.
A Note on a Ramsey-Type Problem for Sequences
Authors: Dudek Andrzej
Published: January 2020

Two sequences $\{x_i\}_{i=1}^{t}$ and $\{y_i\}_{i=1}^t$ of distinct integers are similar if their entries are order-isomorphic. Let $f(r,X)$ be the length of the shortest sequence $Y$ such that any $r$-coloring of the entries of $Y$ yields a monochromatic subsequence that is also similar to $X$. In this note we show that for any fixed non-monotone sequence $X$, $f(r,X)=\Theta(r^2)$, otherwise, for a monotone $X$, $f(r,X)=\Theta(r)$.
Partial List Colouring of Certain Graphs
Authors: Janssen Jeannette , Mathew Rogers , Rajendraprasad Deepak
Published: January 2020

The partial list colouring conjecture due to Albertson, Grossman, and Haas (2000) states that for every $s$-choosable graph $G$ and every assignment of lists of size $t$, $1 \leq t \leq s$, to the vertices of $G$ there is an induced subgraph of $G$ on at least $\frac{t|V(G)|}{s}$ vertices which can be properly coloured from these lists. In this paper, we show that the partial list colouring conjecture holds true for certain  classes of graphs like claw-free graphs, graphs with chromatic number at least $\frac{|V(G)|-1}{2}$, chordless graphs, and series-parallel graphs.
The Parity of a Thicket
Authors: De Carvalho M. H. , Little C. H. C.
Published: January 2020

A thicket in a graph $G$ is defined as a set of even circuits such that every edge lies in an even number of them. If $G$ is directed, then each circuit in the thicket has a well defined directed parity. The parity of the thicket is the sum of the parities of its members, and is independent of the orientation of $G$. We study the problem of determining the parity of a thicket $\mathcal{T}$ in terms of structural properties of $\mathcal{T}$. Specifically, we reduce the problem to studying the case where the underlying graph $G$ is cubic. In this case we solve the problem if $|\mathcal{T}| = 3$ or $G$ is bipartite. Some applications to the problem of characterising Pfaffian graphs are also considered.
Decomposing Labeled Interval Orders as Pairs of Permutations
Authors: Claesson Anders , Hannah Stuart A.
Published: January 2020

We introduce ballot matrices, a signed combinatorial structure whose definition naturally follows from the generating function for labeled interval orders. A sign reversing involution on ballot matrices is defined. We show that matrices fixed under this involution are in bijection with labeled interval orders and that they decompose to a pair consisting of a permutation and an inversion table. To fully classify such pairs, results pertaining to the enumeration of permutations having a given set of ascent bottoms are given. This allows for a new formula for the number of labeled interval orders.
Coxeter-Knuth Graphs and a Signed Little Map for Type B Reduced Words
Authors: Billey Sara , Hamaker Zachary , Roberts Austin , Young Benjamin
Published: January 2020

We define an analog of David Little’s algorithm for reduced words in type B, and investigate its main properties. In particular, we show that our algorithm preserves the recording tableau of Kraśkiewicz insertion, and that it provides a bijective realization of the Type B transition equations in Schubert calculus. Many other aspects of type A theory carry over to this new setting. Our primary tool is a shifted version of the dual equivalence graphs defined by Assaf and further developed by Roberts. We provide an axiomatic characterization of shifted dual equivalence graphs, and use them to prove a structure theorem for the graph of Type B Coxeter-Knuth relations.
Restricted Frame Graphs and a Conjecture of Scott
Authors: Chalopin Jérémie , Esperet Louis , Li Zhentao , Ossona de Mendez Patrice
Published: January 2020

Scott proved in 1997 that for any tree $T$, every graph with bounded clique number which does not contain any subdivision of $T$ as an induced subgraph has bounded chromatic number. Scott also conjectured that the same should hold if $T$ is replaced by any graph $H$. Pawlik et al. recently constructed a family of triangle-free intersection graphs of segments in the plane with unbounded chromatic number (thereby disproving an old conjecture of Erdős). This shows that Scott's conjecture is false whenever $H$ is obtained from a non-planar graph by subdividing every edge at least once.It remains interesting to decide which graphs $H$ satisfy Scott's conjecture and which do not. In this paper, we study the construction of Pawlik et al. in more details to extract more counterexamples to Scott's conjecture. For example, we show that Scott's conjecture is false for any graph obtained from $K_4$ by subdividing every edge at least once.  We also prove that if $G$ is a 2-connected multigraph with no vertex contained in every cycle of $G$, then any graph obtained from $G$ by subdividing every edge at least twice is a counterexample to Scott's conjecture.
The Degree/Diameter Problem in Maximal Planar Bipartite graphs
Authors: Dalfó Cristina , Huemer Clemens , Salas Julián
Published: January 2020

The $(\Delta,D)$ (degree/diameter) problem consists of finding the largest possible number of vertices $n$ among all the graphs with maximum degree $\Delta$ and diameter $D$. We consider the $(\Delta,D)$ problem for maximal planar bipartite graphs, that is, simple planar graphs in which every face is a quadrangle. We obtain that for the $(\Delta,2)$ problem, the number of vertices is $n=\Delta+2$; and for the $(\Delta,3)$ problem, $n= 3\Delta-1$ if $\Delta$ is odd and $n= 3\Delta-2$ if $\Delta$ is even. Then, we prove that, for the general case of the $(\Delta,D)$ problem, an upper bound on $n$ is approximately $3(2D+1)(\Delta-2)^{\lfloor D/2\rfloor}$, and another one is $C(\Delta-2)^{\lfloor D/2\rfloor}$ if $\Delta\geq D$ and $C$ is a sufficiently large constant. Our upper bounds improve for our kind of graphs the one given by Fellows, Hell and Seyffarth for general planar graphs. We also give a lower bound on $n$ for maximal planar bipartite graphs, which is approximately $(\Delta-2)^{k}$ if $D=2k$, and $3(\Delta-3)^k$ if $D=2k+1$, for $\Delta$ and $D$ sufficiently large in both cases.
On the Uniform Generation of Modular Diagrams
Authors: Huang Fenix W.D. , Reidys Christian M.
Published: January 2020

In this paper we present an algorithm that generates $k$-noncrossing, $\sigma$-modular diagrams with uniform probability. A diagram is a labeled graph of degree $\le 1$ over $n$ vertices drawn in a horizontal line with arcs $(i,j)$ in the upper half-plane. A $k$-crossing in a diagram is a set of $k$ distinct arcs $(i_1, j_1), (i_2, j_2),\ldots,(i_k, j_k)$ with the property $i_1 < i_2 < \ldots < i_k < j_1 < j_2 < \ldots < j_k$. A diagram without any $k$-crossings is called a $k$-noncrossing diagram and a stack of length $\sigma$ is a maximal sequence $((i,j),(i+1,j-1),\dots,(i+(\sigma-1),j-(\sigma-1)))$. A diagram is $\sigma$-modular if any arc is contained in a stack of length at least $\sigma$. Our algorithm generates after $O(n^k)$ preprocessing time, $k$-noncrossing, $\sigma$-modular diagrams in $O(n)$ time and space complexity.
Mutually Disjoint Steiner Systems $S(5, 8, 24)$ and $5$-$(24,12,48)$ Designs
Authors: Araya Makoto , Harada Masaaki
Published: January 2020

We demonstrate that there are at least $50$ mutually disjoint Steiner systems $S(5,8,24)$ and there are at least $35$ mutually disjoint $5$-$(24,12,48)$ designs. The latter result provides the existence of a simple $5$-$(24,12,6m)$ design for $m= 24$, 32, 40, 48, 56, 64, 72, 80, 112, 120, 128, 136, 144, 152, 160, 168, 200, 208, 216, 224, 232, 240, 248 and 256.
On the h-Vector of a Lattice Path Matroid
Authors: Schweig Jay
Published: January 2020

Stanley has conjectured that the h-vector of a matroid complex is a pure M-vector. We prove a strengthening of this conjecture for lattice path matroids by constructing a corresponding family of discrete polymatroids.
A Note on the First Occurrence of Strings
Authors: Hung Ying-Chao , Chen Robert W. , Zame Alan , Chen May-Ru
Published: January 2020

We consider the context of a three-person game in which each player selects strings over $\{0,1\}$ and observe a series of fair coin tosses. The winner of the game is the player whose selected string appears first. Recently, Chen et al. showed that if the string length is greater and equal to three, two players can collude to attain an advantage by choosing the pair of strings $11\ldots 10$ and $00\ldots 01$. We call these two strings "complement strings", since each bit of one string is the complement bit of the corresponding bit of the other string. In this note, we further study the property of complement strings for three-person games. We prove that if the string length is greater than five and two players choose any pair of complement strings (except for the pair $11\ldots 10$ and $00\ldots 01$), then the third player can always attain an advantage by choosing a particular string.
A Bijective Proof of the Alladi-Andrews-Gordon Partition Theorem
Authors: Zhao James J.Y.
Published: January 2020

Based on the combinatorial proof of Schur's partition theorem given by Bressoud, and the combinatorial proof of Alladi's partition theorem given by Padmavathamma, Raghavendra and Chandrashekara, we obtain a bijective proof of a partition theorem of Alladi, Andrews and Gordon.
Permutations Generated by a Depth 2 Stack and an Infinite Stack in Series are Algebraic
Authors: Elder Murray , Lee Geoffrey , Rechnitzer Andrew
Published: January 2020

We prove that the class of permutations generated by passing an ordered sequence $12\dots n$ through a stack of depth 2 and an infinite stack in series is in bijection with an unambiguous context-free language, where a permutation of length $n$ is encoded by a string of length $3n$. It follows that the sequence counting the number of permutations of each length has an algebraic generating function. We use the explicit context-free grammar to compute the generating function:\[\sum_{n\geq 0} c_n t^n = \frac{(1+q)\left(1+5q-q^2-q^3-(1-q)\sqrt{(1-q^2)(1-4q-q^2)}\right)}{8q}\]where $c_n$ is the number of permutations of length $n$ that can be generated, and $q \equiv q(t) = \frac{1-2t-\sqrt{1-4t}}{2t}$ is a simple variant of the Catalan generating function. This in turn implies that $c_n^{1/n} \to 2+2\sqrt{5}$.
Combinatorial Proof of a Curious $q$-Binomial Coefficient Identity
Authors: Guo Victor J. W. , Zeng Jiang
Published: January 2020

Using the Algorithm Z developed by Zeilberger, we give a combinatorial proof of the following $q$-binomial coefficient identity $$ \sum_{k=0}^m(-1)^{m-k}{m\brack k}{n+k\brack a}(-xq^a;q)_{n+k-a}q^{{k+1\choose 2}-mk+{a\choose 2}} $$ $$=\sum_{k=0}^n{n\brack k}{m+k\brack a}x^{m+k-a}q^{mn+{k\choose 2}}, $$ which was obtained by Hou and Zeng [European J. Combin. 28 (2007), 214–227].
On Modular $k$-Free Sets
Authors: Lambert Victor
Published: January 2020

Let $n$ and $k$ be integers. A set $A\subset\mathbb{Z}/n\mathbb{Z}$ is $k$-free if for all $x$ in $A$, $kx\notin A$. We determine the maximal cardinality of such a set when $k$ and $n$ are coprime. We also study several particular cases and we propose an efficient algorithm for solving the general case. We finally give the asymptotic behaviour of the minimal size of a $k$-free set in $\left[ 1,n\right]$ which is maximal for inclusion.
Normally Regular Digraphs
Authors: Jørgensen Leif K
Published: January 2020

A normally regular digraph with parameters $(v,k,\lambda,\mu)$ is a directed graph on $v$ vertices whose adjacency matrix $A$ satisfies the equation $AA^t=k I+\lambda (A+A^t)+\mu(J-I-A-A^t)$. This means that every vertex has out-degree $k$, a pair of non-adjacent vertices have $\mu$ common out-neighbours, a pair of vertices connected by an edge in one direction have $\lambda$ common out-neighbours and a pair of vertices connected by edges in both directions have $2\lambda-\mu$ common out-neighbours. We often assume that two vertices can not be connected in both directions. We prove that the adjacency matrix of a normally regular digraph is normal. A connected $k$-regular digraph with normal adjacency matrix is a normally regular digraph if and only if all eigenvalues other than $k$ are on one circle in the complex plane. We prove several non-existence results, structural characterizations, and constructions of normally regular digraphs. In many cases these graphs are Cayley graphs of abelian groups and the construction is then based on a generalization of difference sets.We also show connections to other combinatorial objects: strongly regular graphs, symmetric 2-designs and association schemes.
Rectangular Symmetries for Coefficients of Symmetric Functions
Authors: Briand Emmanuel , Orellana Rosa , Rosas Mercedes
Published: January 2020

We show that some of the main structural constants for symmetric functions (Littlewood-Richardson coefficients, Kronecker coefficients, plethysm coefficients, and the Kostka–Foulkes polynomials) share symmetries related to the operations of taking complements with respect to rectangles and adding rectangles.
Applications of Integer Programming Methods to Cages
Authors: De Ruiter Frans J.C.T. , Biggs Norman L.
Published: January 2020

The aim of this paper is to construct new small regular graphs with girth $7$ using integer programming techniques. Over the last two decades solvers for integer programs have become more and more powerful and have proven to be a useful aid for many hard combinatorial problems. Despite successes in many related fields, these optimisation tools have so far been absent in the quest for small regular graphs with a given girth. Here we illustrate the power of these solvers as an aid to construct small regular girth $7$ graphs from girth $8$ cages.
Heffter Arrays and Biembedding Graphs on Surfaces
Authors: Archdeacon Dan
Published: January 2020

A Heffter array is an $m \times n$ matrix with nonzero entries from $\mathbb{Z}_{2mn+1}$ such that i) every row and column sum to 0, and ii) exactly one of each pair $\{x,-x\}$ of nonzero elements appears in the array. We construct some Heffter arrays. These arrays are used to build current graphs used in topological graph theory. In turn, the current graphs are used to embed the complete graph $K_{2mn+1}$ so that the faces can be 2-colored, called a biembedding. Under certain conditions each color class forms a cycle system. These generalize biembeddings of Steiner triple systems. We discuss some variations including Heffter arrays with empty cells, embeddings on nonorientable surfaces, complete multigraphs, and using integer arithmetic in place of modular arithmetic.
Characterisations of Elementary Pseudo-Caps and Good Eggs
Authors: Rottey Sara , Van de Voorde Geertrui
Published: January 2020

In this note, we use the theory of Desarguesian spreads to investigate good eggs. Thas showed that an egg in $PG(4n-1,q)$, $q$ odd, with two good elements is elementary. By a short combinatorial argument, we show that a similar statement holds for large pseudo-caps, in odd and even characteristic. As a corollary, this improves and extends the result of Thas, Thas and Van Maldeghem (2006) where one needs at least $4$ good elements of an egg in even characteristic to obtain the same conclusion. We rephrase this corollary to obtain a characterisation of the generalised quadrangle $T_3(O)$ of Tits. Lavrauw (2005) characterises elementary eggs in odd characteristic as those good eggs containing a space that contains at least $5$ elements of the egg, but not the good element. We provide an adaptation of this characterisation for weak eggs in odd and even characteristic. As a corollary, we obtain a direct geometric proof for the theorem of Lavrauw.
Combinatorics of Tableau Inversions
Authors: Beagley Jonathan E. , Drube Paul
Published: January 2020

A tableau inversion is a pair of entries in row-standard tableau $T$ that lie in the same column of $T$ yet lack the appropriate relative ordering to make $T$ column-standard.  An $i$-inverted Young tableau is a row-standard tableau along with precisely $i$ inversion pairs. Tableau inversions were originally introduced by Fresse to calculate the Betti numbers of Springer fibers in Type A, with the number of $i$-inverted tableaux that standardize to a fixed standard Young tableau corresponding to a specific Betti number of the associated fiber. In this paper we approach the topic of tableau inversions from a completely combinatorial perspective. We develop formulas enumerating the number of $i$-inverted Young tableaux for a variety of tableaux shapes, not restricting ourselves to inverted tableau that standardize a specific standard Young tableau, and construct bijections between $i$-inverted Young tableaux of a certain shape with $j$-inverted Young tableaux of different shapes. Finally, we share some the results of a computer program developed to calculate tableaux inversions.
On the Largest Component of a Hyperbolic Model of Complex Networks
Authors: Bode Michel , Fountoulakis Nikolaos , Müller Tobias
Published: January 2020

We consider a model for complex networks that was introduced by Krioukov et al.  In this model, $N$ points are chosen randomly inside a disk on the hyperbolic plane and any two of them are joined by an  edge if they are within a certain hyperbolic distance.  The $N$ points are distributed according to a quasi-uniform distribution, which is a distorted version of  the uniform distribution. The model turns out to behave similarly to the well-known Chung-Lu model, but without the independence between the edges. Namely, it exhibits a power-law degree sequence and small distances but, unlike the Chung-Lu model and many other well-known models for complex networks, it also exhibits clustering.

The model is controlled by two parameters $\alpha$ and $\nu$ where, roughly speaking, $\alpha$ controls the exponent of the power-law and $\nu$ controls the average degree. The present paper focuses on the evolution of the component structure of the random graph.  We show that (a) for $\alpha > 1$ and $\nu$ arbitrary, with high probability, as the number of vertices grows, the largest component of the random graph has sublinear order; (b) for $\alpha < 1$ and $\nu$ arbitrary with high probability there is a "giant" component  of linear order,  and (c) when $\alpha=1$ then there is a non-trivial phase transition for the existence of a linear-sized component in terms of $\nu$.

A corrigendum was added to this paper 29 Dec 2018.
An Entropy Proof of the Kahn-Lovász Theorem
Authors: Cutler Jonathan , Radcliffe A. J.
Published: January 2020

Brègman gave a best possible upper bound for the number of perfect matchings in a balanced bipartite graph in terms of its degree sequence. Recently Kahn and Lovász extended Brègman's theorem to general graphs. In this paper, we use entropy methods to give a new proof of the Kahn-Lovász theorem. Our methods build on Radhakrishnan's use of entropy to prove Brègman's theorem.
On the Isomorphism Problem for Cayley Graphs of Abelian Groups whose Sylow Subgroups are Elementary Abelian or Cyclic
Authors: Dobson Ted
Published: January 2020

We show that if certain arithmetic conditions hold, then the Cayley isomorphism problem for abelian groups, all of whose Sylow subgroups are elementary abelian or cyclic, reduces to the Cayley isomorphism problem for its Sylow subgroups.  This yields a large number of results concerning the Cayley isomorphism problem, perhaps the most interesting of which is the following: if $p_1,\ldots, p_r$ are distinct primes satisfying certain arithmetic conditions, then two Cayley digraphs of $\mathbb{Z}_{p_1}^{a_1}\times\cdots\times\mathbb{Z}_{p_r}^{a_r}$, $a_i\le 5$, are isomorphic if and only if they are isomorphic by a group automorphism of $\mathbb{Z}_{p_1}^{a_1}\times\cdots\times\mathbb{Z}_{p_r}^{a_r}$.  That is, that such groups are CI-groups with respect to digraphs.
Random-Player Maker-Breaker games
Authors: Krivelevich Michael , Kronenberg Gal
Published: January 2020

In a $(1:b)$ Maker-Breaker game, one of the central questions is to find the maximal value of $b$ that allows Maker to win the game (that is, the critical bias $b^*$). Erdős conjectured that the critical bias for many Maker-Breaker games played on the edge set of $K_n$ is the same as if both players claim edges randomly. Indeed, in many Maker-Breaker games, "Erdős Paradigm" turned out to be true. Therefore, the next natural question to ask is the (typical) value of the critical bias for Maker-Breaker games where only one player claims edges randomly. A random-player Maker-Breaker game is a two-player game, played the same as an ordinary (biased) Maker-Breaker game, except that one player plays according to his best strategy and claims one element in each round, while the other plays randomly and claims $b$ (or $m$) elements. In fact, for every (ordinary) Maker-Breaker game, there are two different random-player versions; the $(1:b)$ random-Breaker game and the $(m:1)$ random-Maker game. We analyze the random-player version of several classical Maker-Breaker games such as the Hamilton cycle game, the perfect-matching game and the $k$-vertex-connectivity game (played on the edge set of $K_n$). For each of these games we find or estimate the asymptotic values of the bias (either $b$ or $m$) that allow each player to typically win the game. In fact, we provide the "smart" player with an explicit winning strategy for the corresponding value of the bias.
Connectivity of some Algebraically Defined Digraphs
Authors: Kodess Aleksandr , Lazebnik Felix
Published: January 2020

Let $p$ be a prime, $e$ a positive integer, $q = p^e$, and let $\mathbb{F}_q$ denote the finite field of $q$ elements. Let $f_i\colon\mathbb{F}_q^2\to\mathbb{F}_q$ be arbitrary functions, where $1\le i\le l$, $i$ and $l$ are integers. The digraph $D = D(q;\bf{f})$, where ${\bf f}=f_1,\dotso,f_l)\colon\mathbb{F}_q^2\to\mathbb{F}_q^l$, is defined as follows. The vertex set of $D$ is $\mathbb{F}_q^{l+1}$. There is an arc from a vertex ${\bf x} = (x_1,\dotso,x_{l+1})$ to a vertex ${\bf y} = (y_1,\dotso,y_{l+1})$ if $x_i + y_i = f_{i-1}(x_1,y_1)$ for all $i$, $2\le i \le l+1$. In this paper we study the strong connectivity of $D$ and completely describe its strong components. The digraphs $D$ are directed analogues of some algebraically defined graphs, which have been studied extensively and have many applications.
The CI Problem for Infinite Groups
Authors: Morris Joy
Published: January 2020

A finite group $G$ is a DCI-group if, whenever $S$ and $S'$ are subsets of $G$ with the Cayley graphs Cay$(G,S)$ and Cay$(G,S')$ isomorphic, there exists an automorphism $\varphi$ of $G$ with $\varphi(S)=S'$. It is a CI-group if this condition holds under the restricted assumption that $S=S^{-1}$. We extend these definitions to infinite groups, and make two closely-related definitions: an infinite group is a strongly (D)CI$_f$-group if the same condition holds under the restricted assumption that $S$ is finite; and an infinite group is a (D)CI$_f$-group if the same condition holds whenever $S$ is both finite and generates $G$.We prove that an infinite (D)CI-group must be a torsion group that is not locally-finite. We find infinite families of groups that are (D)CI$_f$-groups but not strongly (D)CI$_f$-groups, and that are strongly (D)CI$_f$-groups but not (D)CI-groups. We discuss which of these properties are inherited by subgroups. Finally, we completely characterise the locally-finite DCI-graphs on $\mathbb Z^n$. We suggest several open problems related to these ideas, including the question of whether or not any infinite (D)CI-group exists.
Periodic Graphs
Authors: Godsil Chris
Published: January 2020

Let $X$ be a graph on $n$ vertices with adjacency matrix $A$ and let $H(t)$ denote the matrix-valued function $\exp(iAt)$. If $u$ and $v$ are distinct vertices in $X$, we say perfect state transfer from $u$ to $v$ occurs if there is a time $\tau$ such that $|H(\tau)_{u,v}|=1$. If $u\in V(X)$ and there is a time $\sigma$ such that $|H(\sigma)_{u,u}|=1$, we say $X$ is periodic at $u$ with period $\sigma$. It is not difficult to show that if the ratio of distinct non-zero eigenvalues of $X$ is always rational, then $X$ is periodic. We show that the converse holds, from which it follows that a regular graph is periodic if and only if its eigenvalues are distinct. For a class of graphs $X$ including all vertex-transitive graphs we prove that, if perfect state transfer occurs at time $\tau$, then $H(\tau)$ is a scalar multiple of a permutation matrix of order two with no fixed points. Using certain Hadamard matrices, we construct a new infinite family of graphs on which perfect state transfer occurs.
The Parametric Frobenius Problem
Authors: Roune Bjarke Hammersholt , Woods Kevin
Published: January 2020

Given relatively prime positive integers $a_1,\ldots,a_n$, the Frobenius number is the largest integer that cannot be written as a nonnegative integer combination of the $a_i$. We examine the parametric version of this problem: given $a_i=a_i(t)$ as functions of $t$, compute the Frobenius number as a function of $t$. A function $f:\mathbb{Z}_+\rightarrow\mathbb{Z}$ is a quasi-polynomial if there exists a period $m$ and polynomials $f_0,\ldots,f_{m-1}$ such that $f(t)=f_{t\bmod m}(t)$ for all $t$. We conjecture that, if the $a_i(t)$ are polynomials (or quasi-polynomials) in $t$, then the Frobenius number agrees with a quasi-polynomial, for sufficiently large $t$. We prove this in the case where the $a_i(t)$ are linear functions, and also prove it in the case where $n$ (the number of generators) is at most 3.
Expansions of a Chord Diagram and Alternating Permutations
Authors: Nakamigawa Tomoki
Published: January 2020

A chord diagram is a set of chords of a circle such that no pair of chords has a common endvertex. A chord diagram $E$ with $n$ chords is called an $n$-crossing if all chords of $E$ are mutually crossing. A chord diagram $E$ is called nonintersecting if $E$ contains no $2$-crossing. For a chord diagram $E$ having a $2$-crossing $S = \{ x_1 x_3, x_2 x_4 \}$, the expansion of $E$ with respect to $S$ is to replace $E$ with $E_1 = (E \setminus S) \cup \{ x_2 x_3, x_4 x_1 \}$ or $E_2 = (E \setminus S) \cup \{ x_1 x_2, x_3 x_4 \}$. It is shown that there is a one-to-one correspondence between the multiset of all nonintersecting chord diagrams generated from an $n$-crossing with a finite sequence of expansions and the set of alternating permutations of order $n+1$.
The Three Colour Hat Guessing Game on Cycle Graphs
Authors: Szczechla Witold
Published: January 2020

We study a cooperative game in which each member of a team of N players, wearing coloured hats and situated at the vertices of the cycle graph with N vertices, is guessing their own hat colour merely on the basis of observing the hats worn by their two neighbours without exchanging the information. Each hat can have one of three colours. A predetermined guessing strategy is winning if it guarantees at least one correct individual guess for every assignment of colours. We prove that a winning strategy exists if and only if N is divisible by 3 or N = 4. This asymmetric game is an example of relational system using incomplete information about an unpredictable situation, where at least one participant has to act properly.
Proof of the $(n/2-n/2-n/2)$ Conjecture for Large $n$
Authors: Zhao Yi
Published: January 2020

A conjecture of Loebl, also known as the $(n/2 - n/2 - n/2)$ Conjecture, states that if $G$ is an $n$-vertex graph in which at least $n/2$ of the vertices have degree at least $n/2$, then $G$ contains all trees with at most $n/2$ edges as subgraphs. Applying the Regularity Lemma, Ajtai, Komlós and Szemerédi proved an approximate version of this conjecture. We prove it exactly for sufficiently large $n$. This immediately gives a tight upper bound for the Ramsey number of trees, and partially confirms a conjecture of Burr and Erdős.
Digraph Representations of 2-closed Permutation Groups with a Normal Regular Cyclic Subgroup
Authors: Xu Jing
Published: January 2020

In this paper, we classify 2-closed (in Wielandt's sense) permutation groups which contain a normal  regular cyclic subgroup and prove that for each such group $G$, there exists a circulant $\Gamma$ such that $\mathrm{Aut} (\Gamma)=G$.
Tiling Groups with Difference Sets
Authors: Ćustić Ante , Krčadinac Vedran , Zhou Yue
Published: January 2020

We study tilings of groups with mutually disjoint difference sets. Some necessary existence conditions are proved and shown not to be sufficient. In the case of tilings with two difference sets we show the equivalence to skew Hadamard difference sets, and prove that they must be normalized if the group is abelian. Furthermore, we present some constructions of tilings based on cyclotomy and investigate tilings consisting of Singer difference sets.
Absolute Differences Along Hamiltonian Paths
Authors: Monopoli Francesco
Published: January 2020

We prove that if the vertices of a complete graph are labeled with the elements of an arithmetic progression, then for any given vertex there is a Hamiltonian path starting at this vertex such that the absolute values of the differences of consecutive vertices along the path are pairwise distinct. In another extreme case where the label set has small additive energy, we show that the graph actually possesses a Hamiltonian cycle with the property just mentioned.  These results partially solve a conjecture by Z.-W. Sun.
A Generalization of Graham’s Conjecture
Authors: Guan Huanhuan , Yuan Pingzhi , Zeng Xiangneng
Published: January 2020

Let $G$ be a finite Abelian group of order $|G|=n$, and let $S=g_1\cdot\ldots\cdot g_{n-1}$ be a sequence over $G$ such that all nonempty zero-sum subsequences of $S$ have the same length. In this paper, we completely determine the structure of these sequences.
New Duality Operator for Complex Circulant Matrices and a Conjecture of Ryser
Authors: Gallardo Luis H.
Published: January 2020

We associate to any given circulant complex matrix $C$ another one $E(C)$ such that $E(E(C)) = C^{*}$ the transpose conjugate of $C.$ All circulant Hadamard matrices of order $4$ satisfy a condition $C_4$ on their eigenvalues, namely, the absolute value of the sum of all eigenvalues is bounded above by $2.$ We prove by a "descent" that uses our operator $E$ that the only circulant Hadamard matrices of order $n \geq 4$, that satisfy a condition $C_n$ that generalizes the condition $C_4$ and that consist of a list of $n/4$ inequalities for the absolute value of some sums of eigenvalues of $H$ are the known ones.
Rainbow Matchings and Rainbow Connectedness
Authors: Pokrovskiy Alexey
Published: January 2020

Aharoni and Berger conjectured that every collection of $n$ matchings of size $n+1$ in a bipartite graph contains a rainbow matching of size $n$. This conjecture is related to several old conjectures of Ryser, Brualdi, and Stein about transversals in Latin squares. There have been many recent partial results about the Aharoni-Berger Conjecture. The conjecture is known to hold when the matchings are much larger than $n+1$. The best bound is currently due to Aharoni, Kotlar, and Ziv who proved the conjecture when the matchings are of size at least $3n/2+1$. When the matchings are all edge-disjoint and perfect, the best result follows from a theorem of Häggkvist and Johansson which implies the conjecture when the matchings have size at least $n+o(n)$. In this paper we show that the conjecture is true when the matchings have size $n+o(n)$ and are all edge-disjoint (but not necessarily perfect). We also give an alternative argument to prove the conjecture when the matchings have size at least $\phi n+o(n)$ where $\phi\approx 1.618$ is the Golden Ratio.Our proofs involve studying connectedness in coloured, directed graphs. The notion of connectedness that we introduce is new, and perhaps of independent interest.
Maximum Multiplicity of Matching Polynomial Roots and Minimum Path Cover in General Graphs
Authors: Ku Cheng Yeaw , Wong Kok Bin
Published: January 2020

Let $G$ be a graph. It is well known that the maximum multiplicity of a root of the matching polynomial $\mu(G,x)$ is at most the minimum number of vertex disjoint paths needed to cover the vertex set of $G$. Recently, a necessary and sufficient condition for which this bound is tight was found for trees. In this paper, a similar structural characterization is proved for any graph. To accomplish this, we extend the notion of a $(\theta,G)$-extremal path cover (where $\theta$ is a root of $\mu(G,x)$) which was first introduced for trees to general graphs. Our proof makes use of the analogue of the Gallai-Edmonds Structure Theorem for general root. By way of contrast, we also show that the difference between the minimum size of a path cover and the maximum multiplicity of matching polynomial roots can be arbitrarily large.
New Lower Bounds for 28 Classical Ramsey Numbers
Authors: Exoo Geoffrey , Tatarevic Milos
Published: January 2020

We establish new lower bounds for $28$ classical two and three color Ramsey numbers, and describe the heuristic search procedures used. Several of the new three color bounds are derived from the two color constructions; specifically, we were able to use $(5,k)$-colorings to obtain new $(3,3,k)$-colorings, and $(7,k)$-colorings to obtain new $(3,4,k)$-colorings. Some of the other new constructions in the paper are derived from two well known colorings: the Paley coloring of $K_{101}$ and the cubic coloring of $K_{127}$.