bluuebunny/crossref_metadata_2025 huggingface dataset:
The Range of a Simple Random Walk on $\mathbb{Z}$: An Elementary Combinatorial Approach
Authors: Moser Bernhard A.
Published: January 2020

Two different elementary approaches for deriving an explicit formula for the distribution of the range of a simple random walk on $\mathbb{Z}$ of length $n$ are presented. Both of them rely on Hermann Weyl's discrepancy norm, which equals the maximal partial sum of the elements of a sequence. By this the original combinatorial problem on $\mathbb{Z}$ can be turned into a known path-enumeration problem on a bounded lattice. The solution is provided by means of the adjacency matrix $\mathbf Q_d$ of the walk on a bounded lattice $(0,1,\ldots,d)$. The second approach is algebraic in nature, and starts with the adjacency matrix $\mathbf{Q_d}$. The powers of the adjacency matrix are expanded in terms of products of non-commutative left and right shift matrices. The representation of such products by means of the discrepancy norm reveals the solution directly.
On the Number of Walks in a Triangular Domain
Authors: Mortimer Paul R.G. , Prellberg Thomas
Published: January 2020

We consider walks on a triangular domain that is a subset of the triangular lattice. We then specialise this by dividing the lattice into two directed sublattices with different weights. Our central result is an explicit formula for the generating function of walks starting at a fixed point in this domain and ending anywhere within the domain. Intriguingly, the specialisation of this formula to walks starting in a fixed corner of the triangle shows that these are equinumerous to two-coloured Motzkin paths, and two-coloured three-candidate Ballot paths, in a strip of finite height.
On Saturated $k$-Sperner Systems
Authors: Morrison Natasha , Noel Jonathan A. , Scott Alex
Published: January 2020

Given a set $X$, a collection $\mathcal{F}\subseteq\mathcal{P}(X)$ is said to be $k$-Sperner if it does not contain a chain of length $k+1$ under set inclusion and it is saturated if it is maximal with respect to this property. Gerbner et al. conjectured that, if $|X|$ is sufficiently large with respect to $k$, then the minimum size of a saturated $k$-Sperner system $\mathcal{F}\subseteq\mathcal{P}(X)$ is $2^{k-1}$. We disprove this conjecture by showing that there exists $\varepsilon>0$ such that for every $k$ and $|X| \geq n_0(k)$ there exists a saturated $k$-Sperner system $\mathcal{F}\subseteq\mathcal{P}(X)$ with cardinality at most $2^{(1-\varepsilon)k}$.A collection $\mathcal{F}\subseteq \mathcal{P}(X)$ is said to be an oversaturated $k$-Sperner system if, for every $S\in\mathcal{P}(X)\setminus\mathcal{F}$, $\mathcal{F}\cup\{S\}$ contains more chains of length $k+1$ than $\mathcal{F}$. Gerbner et al. proved that, if $|X|\geq k$, then the smallest such collection contains between $2^{k/2-1}$ and $O\left(\frac{\log{k}}{k}2^k\right)$ elements. We show that if $|X|\geq k^2+k$, then the lower bound is best possible, up to a polynomial factor.
An Extension of Turán's Theorem, Uniqueness and Stability
Authors: Allen Peter , Böttcher Julia , Hladký Jan , Piguet Diana
Published: January 2020

We determine the maximum number of edges of an $n$-vertex graph $G$ with the property that none of its $r$-cliques intersects a fixed set $M\subset V(G)$.  For $(r-1)|M|\ge n$, the $(r-1)$-partite Turán graph turns out to be the unique extremal graph. For $(r-1)|M|<n$, there is a whole family of extremal graphs, which we describe explicitly. In addition we provide corresponding stability results.
Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width
Authors: Bordewich Magnus , Kang Ross J.
Published: January 2020

Motivated by the 'subgraphs world' view of the ferromagnetic Ising model, we analyse the mixing times of Glauber dynamics based on subset expansion expressions for classes of graph, hypergraph and matroid polynomials. With a canonical paths argument, we demonstrate that the chains defined within this framework mix rapidly upon graphs, hypergraphs and matroids of bounded tree-width.This extends known results on rapid mixing for the Tutte polynomial, adjacency-rank ($R_2$-)polynomial and interlace polynomial. In particular Glauber dynamics for the $R_2$-polynomial was known to mix rapidly on trees, which led to hope of rapid mixing on a wider class of graphs. We show that Glauber dynamics for a very wide class of polynomials mixes rapidly on graphs of bounded tree-width, including many cases in which the Glauber dynamics does not mix rapidly for all graphs. This demonstrates that rapid mixing on trees or bounded tree-width graphs does not offer strong evidence towards rapid mixing on all graphs.
Infinitely many Hypermaps of a given Type and Genus
Authors: Jones Gareth A. , Pinto Daniel
Published: January 2020

It is conjectured that given positive integers $l$, $m$, $n$ with $l^{-1}+m^{-1}+n^{-1} < 1$ and an integer $g \geq 0$, the triangle group $\Delta=\Delta (l,m,n)=\langle X, Y, Z | X^l=Y^m=Z^n=XYZ=1 \rangle $ contains infinitely many subgroups of finite index and of genus $g$. A slightly stronger version of this conjecture is as follows: given positive integers $l$, $m$, $n$ with $l^{-1}+m^{-1}+n^{-1} < 1$ and an integer $g \geq 0$, there are infinitely many nonisomorphic compact orientable hypermaps of type $(l,m,n)$ and genus $g$. We prove that these conjectures are true when two of the parameters $l$, $m$, $n$ are equal, by showing how to construct appropriate hypermaps.
Integer Decomposition Property of Dilated Polytopes
Authors: Cox David A. , Haase Christian , Hibi Takayuki , Higashitani Akihiro
Published: January 2020

An integral convex polytope $\mathcal{P} \subset \mathbb{R}^N$ possesses the integer decomposition property if, for any integer $k > 0$ and for any $\alpha \in k \mathcal{P} \cap \mathbb{Z}^{N}$, there exist $\alpha_{1}, \ldots, \alpha_k \in \mathcal{P} \cap \mathbb{Z}^{N}$ such that $\alpha = \alpha_{1} + \cdots + \alpha_k$. A fundamental question is to determine the integers $k > 0$ for which the dilated polytope $k\mathcal{P}$ possesses the integer decomposition property. In the present paper, combinatorial invariants related to the integer decomposition property of dilated polytopes will be proposed and studied.
On a Certain Vector Crank Modulo 7
Authors: Hirschhorn Michael D. , Toh Pee Choon
Published: January 2020

We define a vector crank to provide a combinatorial interpretation for a certain Ramanujan type congruence modulo 7.
Avoiding 7-Circuits in 2-Factors of Cubic Graphs
Authors: Lukoťka Robert
Published: January 2020

Let $G$ be a cyclically $4$-edge-connected cubic graph with girth at least $7$ on $n$ vertices. We show that $G$ has a $2$-factor $F$ such that at least a linear amount of vertices is not in $7$-circuits of $F$. More precisely, there are at least $n/657$ vertices of $G$ that are not in $7$-circuits of $F$. If $G$ is cyclically $6$-edge-connected then the bound can be improved to $n/189$. As a corollary we obtain bounds on the oddness and on the length of the shortest travelling salesman tour in a cyclically $4$-edge-connected ($6$-edge-connected) cubic graph of girth at least $7$.
Bruhat Order on Partial Fixed Point Free Involutions
Authors: Can Mahir Bilen , Cherniavsky Yonah , Twelbeck Tim
Published: January 2020

The order complex of inclusion poset $PF_n$ of Borel orbit closures in skew-symmetric matrices is investigated. It is shown that $PF_n$ is an EL-shellable poset, and furthermore, its order complex triangulates a ball. The rank-generating function of $PF_n$ is computed and the resulting polynomial is contrasted with the Hasse-Weil zeta function of the variety of skew-symmetric matrices over finite fields.
Dissimilarity Vectors of Trees are Contained in the Tropical Grassmannian
Authors: Giraldo Benjamin Iriarte
Published: January 2020

In this short writing, we prove that the set of $m$-dissimilarity vectors of phylogenetic $n$-trees is contained in the tropical Grassmannian ${\cal G}_{m,n}$, answering a question of Pachter and Speyer. We do this by proving an equivalent conjecture proposed by Cools.
Another Abstraction of the Erdős-Szekeres Happy End Theorem
Authors: Alon Noga , Chiniforooshan Ehsan , Chvátal Vašek , Genest François
Published: January 2020

The Happy End Theorem of Erdős and Szekeres asserts that for every integer $n$ greater than two there is an integer $N$ such that every set of $N$ points in general position in the plane includes the $n$ vertices of a convex $n$-gon. We generalize this theorem in the framework of certain simple structures, which we call "happy end spaces".
A Note on Coloring Vertex-Transitive Graphs
Authors: Cranston Daniel W. , Rabern Landon
Published: January 2020

We prove bounds on the chromatic number $\chi$ of a vertex-transitive graph in terms of its clique number $\omega$ and maximum degree $\Delta$. We conjecture that every vertex-transitive graph satisfies $\chi \le \max \{\omega, \left\lceil\frac{5\Delta + 3}{6}\right\rceil\}$, and we prove results supporting this conjecture. Finally, for vertex-transitive graphs with $\Delta \ge 13$ we prove the Borodin–Kostochka conjecture, i.e., $\chi\le\max\{\omega,\Delta-1\}$.
Leapfrog Constructions: From Continuant Polynomials to Permanents of Matrices
Authors: Facchini Alberto , Leroy André
Published: January 2020

We study noncommutative continuant polynomials via a new leapfrog construction. This needs the introduction of new indeterminates and leads to generalizations of Fibonacci polynomials, Lucas polynomials and other families of polynomials. We relate these polynomials to various topics such as quiver algebras and tilings. Finally, we use permanents to give a broad perspective on the subject.
A $q$-Analogue of Graham, Hoffman and Hosoya's Theorem
Authors: Sivasubramanian Sivaramakrishnan
Published: January 2020

Graham, Hoffman and Hosoya gave a very nice formula about the determinant of the distance matrix $D_G$ of a graph $G$ in terms of the distance matrix of its blocks. We generalize this result to a $q$-analogue of $D_G$. Our generalization yields results about the equality of the determinant of the mod-2 (and in general mod-$k$) distance matrix (i.e. each entry of the distance matrix is taken modulo 2 or $k$) of some graphs. The mod-2 case can be interpreted as a determinant equality result for the adjacency matrix of some graphs.
On the Chromatic Number of the Erdős-Rényi Orthogonal Polarity Graph
Authors: Peng Xing , Tait Michael , Timmons Craig
Published: January 2020

For a prime power $q$, let $ER_q$ denote the Erdős-Rényi orthogonal polarity graph. We prove that if $q$ is an even power of an odd prime, then $\chi ( ER_{q}) \leq 2 \sqrt{q} + O ( \sqrt{q} / \log q)$. This upper bound is best possible up to a constant factor of at most 2. If $q$ is an odd power of an odd prime and satisfies some condition on irreducible polynomials, then we improve the best known upper bound for $\chi(ER_{q})$ substantially. We also show that for sufficiently large $q$, every $ER_q$ contains a subgraph that is not 3-chromatic and has at most 36 vertices.
A New Bound on the Domination Number of Graphs with Minimum Degree Two
Authors: Henning Michael A. , Schiermeyer Ingo , Yeo Anders
Published: January 2020

For a graph $G$, let $\gamma(G)$ denote the domination number of $G$ and let $\delta(G)$ denote the minimum degree among the vertices of $G$. A vertex $x$ is called a bad-cut-vertex of $G$ if $G-x$ contains a component, $C_x$, which is an induced $4$-cycle and $x$ is adjacent to at least one but at most three vertices on $C_x$. A cycle $C$ is called a special-cycle if $C$ is a $5$-cycle in $G$ such that if $u$ and $v$ are consecutive vertices on $C$, then at least one of $u$ and $v$ has degree $2$ in $G$. We let ${\rm bc}(G)$ denote the number of bad-cut-vertices in $G$, and ${\rm sc}(G)$ the maximum number of vertex disjoint special-cycles in $G$ that contain no bad-cut-vertices. We say that a graph is $(C_4,C_5)$-free if it has no induced $4$-cycle or $5$-cycle. Bruce Reed [Paths, stars and the number three. Combin. Probab. Comput. 5 (1996), 277–295] showed that if $G$ is a graph of order $n$ with $\delta(G) \ge 3$, then $\gamma(G) \le 3n/8$. In this paper, we relax the minimum degree condition from three to two. Let $G$ be a connected graph of order $n \ge 14$ with $\delta(G) \ge 2$. As an application of Reed's result, we show that $\gamma(G) \le \frac{1}{8} ( 3n + {\rm sc}(G) + {\rm bc}(G))$. As a consequence of this result, we have that (i) $\gamma(G) \le 2n/5$; (ii) if $G$ contains no special-cycle and no bad-cut-vertex, then $\gamma(G) \le 3n/8$; (iii) if $G$ is $(C_4,C_5)$-free, then $\gamma(G) \le 3n/8$; (iv) if $G$ is $2$-connected and $d_G(u) + d_G(v) \ge 5$ for every two adjacent vertices $u$ and $v$, then $\gamma(G) \le 3n/8$. All bounds are sharp.
A Generalization of Very Odd Sequences
Authors: Ku Cheng Yeaw , Wong Kok Bin
Published: January 2020

Let $\mathbb N$ be the set of positive integers and $n\in \mathbb N$. Let $\mathbf{a}=(a_0,a_1,\dots, a_{n-1})$ be a sequence of length $n$, with $a_i\in \{0,1\}$. For $0\leq k\leq n-1$, let \[ A_k(\mathbf{a})=\sum_{\substack{0\leq i\leq j\leq n-1\\ j-i=k}} a_ia_j.\] The sequence $\mathbf{a}$ is called a very odd sequence if $A_k(\mathbf{a})$ is odd for all $0\leq k\leq n-1$. In this paper, we study a generalization of very odd sequences and give a characterisation of these sequences.
The Disjoint $m$-Flower Intersection Problem for Latin Squares
Authors: Lefevre James G. , McCourt Thomas A.
Published: January 2020

An $m$-flower in a latin square is a set of $m$ entries which share either a common row, a common column, or a common symbol, but which are otherwise distinct. Two $m$-flowers are disjoint if they share no common row, column or entry. In this paper we give a solution of the intersection problem for disjoint $m$-flowers in latin squares; that is, we determine precisely for which triples $(n,m,x)$ there exists a pair of latin squares of order $n$ whose intersection consists exactly of $x$ disjoint $m$-flowers.
Graph Products and New Solutions to Oberwolfach Problems
Authors: Rinaldi Gloria , Traetta Tommaso
Published: January 2020

We introduce the circle product, a method to construct simple graphs starting from known ones. The circle product can be applied in many different situations and when applied to regular graphs and to their decompositions, a new regular graph is obtained together with a new decomposition. In this paper we show how it can be used to construct infinitely many new solutions to the Oberwolfach problem, in both the classic and the equipartite case.
Sweeping the ${\bf cd}$-Index and the Toric $h$-Vector
Authors: Lee Carl W.
Published: January 2020

We derive formulas for the ${\bf cd}$-index and the toric $h$-vector of a convex polytope $P$ from a sweeping by a hyperplane. These arise from interpreting the corresponding $S$-shelling of the dual of $P$. We describe a partition of the faces of the complete truncation of $P$ to reflect explicitly the nonnegativity of its ${\bf cd}$-index and what its components are counting. One corollary is a quick way to compute the toric $h$-vector directly from the ${\bf cd}$-index that turns out to be an immediate consequence of formulas of Bayer and Ehrenborg. We also propose an "extended toric" $h$-vector that fully captures the information in the flag $h$-vector.
Orthogonal Arrays with Parameters $OA(s^3,s^2+s+1,s,2)$ and 3-Dimensional Projective Geometries
Authors: Ishii Kazuaki
Published: January 2020

There are many nonisomorphic orthogonal arrays with parameters $OA(s^3,s^2+s+1,s,2)$ although the existence of the arrays yields many restrictions. We denote this by $OA(3,s)$ for simplicity. V. D. Tonchev showed that for even the case of $s=3$, there are at least 68 nonisomorphic orthogonal arrays. The arrays that are constructed by the $n-$dimensional finite spaces have parameters $OA(s^n, (s^n-1)/(s-1),s,2)$. They are called Rao-Hamming type. In this paper we characterize the $OA(3,s)$ of 3-dimensional Rao-Hamming type. We prove several results for a special type of $OA(3,s)$ that satisfies the following condition: For any three rows in the orthogonal array, there exists at least one column, in which the entries of the three rows equal to each other. We call this property $\alpha$-type. We prove the following. (1) An $OA(3,s)$ of $\alpha$-type exists if and only if $s$ is a prime power. (2) $OA(3,s)$s of $\alpha$-type are isomorphic to each other as orthogonal arrays. (3) An $OA(3,s)$ of $\alpha$-type yields $PG(3,s)$. (4) The 3-dimensional Rao-Hamming is an $OA(3,s)$ of $\alpha$-type. (5) A linear $OA(3,s)$ is of $\alpha $-type.
Unimodality Problems of Multinomial Coefficients and Symmetric Functions
Authors: Su Xun-Tuan , Wang Yi , Yeh Yeong-Nan
Published: January 2020

In this note we consider unimodality problems of sequences of multinomial coefficients and symmetric functions. The results presented here generalize our early results for binomial coefficients. We also give an answer to a question of Sagan about strong $q$-log-concavity of certain sequences of symmetric functions, which can unify many known results for $q$-binomial coefficients and $q$-Stirling numbers of two kinds.
A Decomposition Algorithm for the Oriented Adjacency Graph of the Triangulations of a Bordered Surface with Marked Points
Authors: Gu Weiwen
Published: January 2020

In this paper we consider an oriented version of adjacency graphs of triangulations of bordered surfaces with marked points. We develop an algorithm that determines whether a given oriented graph is an oriented adjacency graph of a triangulation. If a given oriented graph corresponds to many triangulations, our algorithm finds all of them. As a corollary we find out that there are only finitely many oriented connected graphs with non-unique associated triangulations. We also discuss a new algorithm which determines whether a given quiver is of finite mutation type. This algorithm is linear in the number of nodes and is more effective than the previously known one.
Chung-Feller Property in View of Generating Functions
Authors: Liu Shu-Chung , Wang Yi , Yeh Yeong-Nan
Published: January 2020

The classical Chung-Feller Theorem offers an elegant perspective for enumerating the Catalan number $c_n= \frac{1}{n+1}\binom{2n}{n}$. One of the various proofs is by the uniform-partition method. The method shows that the set of the free Dyck $n$-paths, which have $\binom{2n}{n}$ in total, is uniformly partitioned into $n+1$ blocks, and the ordinary Dyck $n$-paths form one of these blocks; therefore the cardinality of each block is $\frac{1}{n+1}\binom{2n}{n}$. In this article, we study the Chung-Feller property: a sup-structure set can be uniformly partitioned such that one of the partition blocks is (isomorphic to) a well-known structure set. The previous works about the uniform-partition method used bijections, but here we apply generating functions as a new approach. By claiming a functional equation involving the generating functions of sup- and sub-structure sets, we re-prove two known results about Chung-Feller property, and explore several new examples including the ones for the large and the little Schröder paths. Especially for the Schröder paths, we are led by the new approach straightforwardly to consider "weighted" free Schröder paths as sup-structures. The weighted structures are not obvious via bijections or other methods.
On $(\delta, \chi)$-Bounded Families of Graphs
Authors: Gyárfás András , Zaker Manouchehr
Published: January 2020

A family ${\mathcal{F}}$ of graphs is said to be $(\delta,\chi)$-bounded if there exists a function $f(x)$ satisfying $f(x)\rightarrow \infty$ as $x\rightarrow \infty$, such that for any graph $G$ from the family, one has $f(\delta(G))\leq \chi(G)$, where $\delta(G)$ and $\chi(G)$ denotes the minimum degree and chromatic number of $G$, respectively. Also for any set $\{H_1, H_2, \ldots, H_k\}$ of graphs by $Forb(H_1, H_2, \ldots, H_k)$ we mean the class of graphs that contain no $H_i$ as an induced subgraph for any $i=1, \ldots, k$. In this paper we first answer affirmatively the question raised by the second author by showing that for any tree $T$ and positive integer $\ell$, $Forb(T, K_{\ell, \ell})$ is a $(\delta, \chi)$-bounded family. Then we obtain a necessary and sufficient condition for $Forb(H_1, H_2, \ldots, H_k)$ to be a $(\delta, \chi)$-bounded family, where $\{H_1, H_2, \ldots, H_k\}$ is any given set of graphs. Next we study $(\delta, \chi)$-boundedness of $Forb({\mathcal{C}})$ where ${\mathcal{C}}$ is an infinite collection of graphs. We show that for any positive integer $\ell$, $Forb(K_{\ell,\ell}, C_6, C_8, \ldots)$ is $(\delta, \chi)$-bounded. Finally we show a similar result when ${\mathcal{C}}$ is a collection consisting of unicyclic graphs.
Rotary Polygons in Configurations
Authors: Boben Marko , Miklavič Štefko , Potočnik Primož
Published: January 2020

A polygon $A$ in a configuration $\mathcal{C}$ is called rotary if $\mathcal{C}$ admits an automorphism which acts upon $A$ as a one-step rotation. We study rotary polygons and their orbits under the group of automorphisms (and antimorphisms) of $\mathcal{C}$. We determine the number of such orbits for several symmetry types of rotary polygons in the case when $\mathcal{C}$ is flag-transitive. As an example, we provide tables of flag-transitive $(v_3)$ and $(v_4)$ configurations of small order containing information on the number and symmetry types of corresponding rotary polygons.
Relating Different Cycle Spaces of the Same Infinite Graph
Authors: Richter R. Bruce , Rooney Brendan
Published: January 2020

Casteels and Richter have shown that if $X$ and $Y$ are distinct compactifications of a locally finite graph $G$ and $f:X\to Y$ is a continuous surjection such that $f$ restricts to a homeomorphism on $G$, then the cycle space $Z_X$ of $X$ is contained in the cycle space $Z_Y$ of $Y$. In this work, we show how to extend a basis for $Z_X$ to a basis of $Z_Y$.
A Strengthening of Brooks' Theorem for Line Graphs
Authors: Rabern Landon
Published: January 2020

We prove that if $G$ is the line graph of a multigraph, then the chromatic number $\chi(G)$ of $G$ is at most $\max\left\{\omega(G), \frac{7\Delta(G) + 10}{8}\right\}$ where $\omega(G)$ and $\Delta(G)$ are the clique number and the maximum degree of $G$, respectively. Thus Brooks' Theorem holds for line graphs of multigraphs in much stronger form. Using similar methods we then prove that if $G$ is the line graph of a multigraph with $\chi(G) \geq \Delta(G) \geq 9$, then $G$ contains a clique on $\Delta(G)$ vertices. Thus the Borodin-Kostochka Conjecture holds for line graphs of multigraphs.
Independence Number and Disjoint Theta Graphs
Authors: Fujita Shinya , Magnant Colton
Published: January 2020

The goal of this paper is to find vertex disjoint even cycles in graphs. For this purpose, define a $\theta$-graph to be a pair of vertices $u, v$ with three internally disjoint paths joining $u$ to $v$. Given an independence number $\alpha$ and a fixed integer $k$, the results contained in this paper provide sharp bounds on the order $f(k, \alpha)$ of a graph with independence number $\alpha(G) \leq \alpha$ which contains no $k$ disjoint $\theta$-graphs. Since every $\theta$-graph contains an even cycle, these results provide $k$ disjoint even cycles in graphs of order at least $f(k, \alpha) + 1$. We also discuss the relationship between this problem and a generalized ramsey problem involving sets of graphs.
Chromatic Roots of a Ring of Four Cliques
Authors: Dong F. M. , Royle Gordon , Wagner Dave
Published: January 2020

For any positive integers $a,b,c,d$, let $R_{a,b,c,d}$ be the graph obtained from the complete graphs $K_a, K_b, K_c$ and $K_d$ by adding edges joining every vertex in $K_a$ and $K_c$ to every vertex in $K_b$ and $K_d$. This paper shows that for arbitrary positive integers $a,b,c$ and $d$, every root of the chromatic polynomial of $R_{a,b,c,d}$ is either a real number or a non-real number with its real part equal to $(a+b+c+d-1)/2$.
A Note on Obstructions to Clustered Planarity
Authors: Sneddon Jamie , Bonnington Paul
Published: January 2020

A planar digraph $D$ is clustered planar if in some planar embedding of $D$ we have at each vertex the in-arcs occurring sequentially in the local rotation. By supplementing the operations used to form the usual minors in Kuratowski's theorem, clustered planar digraphs are characterised.
Quantum Walks on Regular Graphs and Eigenvalues
Authors: Godsil Chris , Guo Krystal
Published: January 2020

We study the transition matrix of a quantum walk on strongly regular graphs. It is proposed by Emms, Hancock, Severini and Wilson in 2006, that the spectrum of $S^+(U^3)$, a matrix based on the amplitudes of walks in the quantum walk, distinguishes strongly regular graphs. We find the eigenvalues of $S^+(U)$ and $S^+(U^2)$ for regular graphs and show that $S^+(U^2) = S^+(U)^2 + I$.
Extremal Problems for Independent Set Enumeration
Authors: Cutler Jonathan , Radcliffe A. J.
Published: January 2020

The study of the number of independent sets in a graph has a rich history. Recently, Kahn proved that disjoint unions of $K_{r,r}$'s have the maximum number of independent sets amongst $r$-regular bipartite graphs. Zhao extended this to all $r$-regular graphs. If we instead restrict the class of graphs to those on a fixed number of vertices and edges, then the Kruskal-Katona theorem implies that the graph with the maximum number of independent sets is the lex graph, where edges form an initial segment of the lexicographic ordering. In this paper, we study three related questions. Firstly, we prove that the lex graph has the maximum number of weighted independent sets for any appropriate weighting. Secondly, we solve the problem of maximizing the number of independents sets in graphs with specified independence number or clique number. Finally, for $m\leq n$, we find the graphs with the minimum number of independent sets for graphs with $n$ vertices and $m$ edges.
Burnside-Brauer Theorem for Table Algebras
Authors: Bagherian J. , Barghi A. Rahnamai
Published: January 2020

In the character theory of finite groups the Burnside-Brauer Theorem is a well-known result which deals with products of characters in finite groups. In this paper, we first define the character products for table algebras and then by observing the relationship between the characters of a table algebra and the characters of its quotient, we provide a condition in which the products of characters of table algebras are characters. As a main result we state and prove the Burnside-Brauer Theorem on finite groups for table algebras.
Genus Distributions of 4-Regular Outerplanar Graphs
Authors: Poshni Mehvish I. , Khan Imran F. , Gross Jonathan L.
Published: January 2020

We present an $O(n^2)$-time algorithm for calculating the genus distribution of any 4-regular outerplanar graph. We characterize such graphs in terms of what we call split graphs and incidence trees. The algorithm uses post-order traversal of the incidence tree and productions that are adapted from a previous paper that analyzes double-root vertex-amalgamations and self-amalgamations.
Minimum Light Numbers in the $\sigma$-Game and Lit-Only $\sigma$-Game on Unicyclic and Grid Graphs
Authors: Goldwasser John , Wang Xinmao , Wu Yaokun
Published: January 2020

Consider a graph each of whose vertices is either in the ON state or in the OFF state and call the resulting ordered bipartition into ON vertices and OFF vertices a configuration of the graph. A regular move at a vertex changes the states of the neighbors of that vertex and hence sends the current configuration to another one. A valid move is a regular move at an ON vertex. For any graph $G,$ let $\mathcal{D}(G)$ be the minimum integer such that given any starting configuration $\bf x$ of $G$ there must exist a sequence of valid moves which takes $\bf x$ to a configuration with at most $\ell +\mathcal{D}(G)$ ON vertices provided there is a sequence of regular moves which brings $\bf x$ to a configuration in which there are $\ell$ ON vertices. The shadow graph $\mathcal{S}(G)$ of a graph $G$ is obtained from $G$ by deleting all loops. We prove that $\mathcal{D}(G)\leq 3$ if $\mathcal{S}(G)$ is unicyclic and give an example to show that the bound $3$ is tight. We also prove that $\mathcal{D}(G)\leq 2$ if $ G $ is a two-dimensional grid graph and $\mathcal{D}(G)=0$ if $\mathcal{S}(G)$ is a two-dimensional grid graph but not a path and $G\neq \mathcal{S}(G)$.
On a Conjecture of G. Malle and G. Navarro on Nilpotent Blocks
Authors: Gramain Jean-Baptiste
Published: January 2020

In a recent article, G. Malle and G. Navarro conjectured that the $p$-blocks of a finite group all of whose height 0 characters have the same degree are exactly the nilpotent blocks defined by M. Broué and L. Puig. In this paper, we check that this conjecture holds for spin-blocks of the covering group $2.{\mathfrak A}_n$ of the alternating group ${\mathfrak A}_n$, thereby solving a case excluded from the study of quasi-simple groups by Malle and Navarro.
A Note on Path Factors of $(3,4)$-Biregular Bipartite Graphs
Authors: Casselgren Carl Johan
Published: January 2020

A proper edge coloring of a graph $G$ with colors $1,2,3,\dots$ is called an interval coloring if the colors on the edges incident with any vertex are consecutive. A bipartite graph is $(3,4)$-biregular if all vertices in one part have degree $3$ and all vertices in the other part have degree $4$. Recently it was proved [J. Graph Theory 61 (2009), 88-97] that if such a graph $G$ has a spanning subgraph whose components are paths with endpoints at 3-valent vertices and lengths in $\{2, 4, 6, 8\}$, then $G$ has an interval coloring. It was also conjectured that every simple $(3,4)$-biregular bipartite graph has such a subgraph. We provide some evidence for this conjecture by proving that a simple $(3,4)$-biregular bipartite graph has a spanning subgraph whose components are nontrivial paths with endpoints at $3$-valent vertices and lengths not exceeding $22$.
Invariant Relations and Aschbacher Classes of Finite Linear Groups
Authors: Xu Jing , Giudici Michael , Li Cai Heng , Praeger Cheryl E.
Published: January 2020

For a positive integer $k$, a $k$-relation on a set $\Omega$ is a non-empty subset $\Delta$ of the $k$-fold Cartesian product $\Omega^k$; $\Delta$ is called a $k$-relation for a permutation group $H$ on $\Omega$ if $H$ leaves $\Delta$ invariant setwise. The $k$-closure $H^{(k)}$ of $H$, in the sense of Wielandt, is the largest permutation group $K$ on $\Omega$ such that the set of $k$-relations for $K$ is equal to the set of $k$-relations for $H$. We study $k$-relations for finite semi-linear groups $H\leq{\rm\Gamma L}(d,q)$ in their natural action on the set $\Omega$ of non-zero vectors of the underlying vector space. In particular, for each Aschbacher class ${\mathcal C}$ of geometric subgroups of ${\rm\Gamma L}(d,q)$, we define a subset ${\rm Rel}({\mathcal C})$ of $k$-relations (with $k=1$ or $k=2$) and prove (i) that $H$ lies in ${\mathcal C}$ if and only if $H$ leaves invariant at least one relation in ${\rm Rel}({\mathcal C})$, and (ii) that, if $H$ is maximal among subgroups in ${\mathcal C}$, then an element $g\in{\rm\Gamma L}(d,q)$ lies in the $k$-closure of $H$ if and only if $g$ leaves invariant a single $H$-invariant $k$-relation in ${\rm Rel}({\mathcal C})$ (rather than checking that $g$ leaves invariant all $H$-invariant $k$-relations). Consequently both, or neither, of $H$ and $H^{(k)}\cap{\rm\Gamma L}(d,q)$ lie in ${\mathcal C}$. As an application, we improve a 1992 result of Saxl and the fourth author concerning closures of affine primitive permutation groups.
Part-Products of 1-Free Integer Compositions
Authors: Shapcott Caroline
Published: January 2020

If $\vec{\lambda}$ is a composition of the positive integer $n$, define ${\bf B}(\vec{\lambda})$ to be the product of the parts of $\vec{\lambda}$. We present a modified version of Hitczenko's stopped sequence construction that leads to a proof of the asymptotic lognormality of ${\bf B}$ for random 1-free compositions (compositions containing no parts of size 1).
The Minor Crossing Number of Graphs with an Excluded Minor
Authors: Bokal Drago , Fijavž Gašper , Wood David R.
Published: January 2020

The minor crossing number of a graph $G$ is the minimum crossing number of a graph that contains $G$ as a minor. It is proved that for every graph $H$ there is a constant $c$, such that every graph $G$ with no $H$-minor has minor crossing number at most $c|V(G)|$.
Constructing Fifteen Infinite Classes of Nonregular Bipartite Integral Graphs
Authors: Wang Ligong , Hoede Cornelis
Published: January 2020

A graph is called integral if all its eigenvalues (of the adjacency matrix) are integers. In this paper, the graphs $S_1(t)=K_{1,t}$, $S_2(n,t)$, $S_3(m,n,t)$, $S_4(m,n,p,q)$, $S_5(m,n)$, $S_6(m,n,t)$, $S_8(m,n)$, $S_9(m,n,p,q)$, $S_{10}(n)$, $S_{13}(m,n)$, $S_{17}(m, n, p, q)$, $S_{18}(n,p,q,t)$, $S_{19}(m,n,p,t)$, $S_{20}(n,p,q)$ and $S_{21}(m,t)$ are defined. We construct the fifteen classes of larger graphs from the known 15 smaller integral graphs $S_1-S_6$, $S_8-S_{10}$, $S_{13}$, $S_{17}-S_{21}$ (see also Figures 4 and 5, Balińska and Simić, Discrete Math. 236(2001) 13-24). These classes consist of nonregular and bipartite graphs. Their spectra and characteristic polynomials are obtained from matrix theory. We obtain their integral property by using number theory and computer search. All these classes are infinite. They are different from those in the literature. It is proved that the problem of finding such integral graphs is equivalent to solving Diophantine equations. We believe that it is useful for constructing other integral graphs. The discovery of these integral graphs is a new contribution to the search of integral graphs. Finally, we propose several open problems for further study.
Vector Spaces and the Petersen Graph
Authors: De Carvalho Marcelo H. , Little C. H. C.
Published: January 2020

It is shown that a matching covered graph has an ear decomposition with no more than one double ear if and only if there is no set $S$ of edges such that $|S \cap A|$ is even for every alternating circuit $A$ but $|S \cap C|$ is odd for some even circuit $C$. Two proofs are presented. The first uses vector spaces and the second is constructive. Some applications are also given.
Avoiding Rainbow Induced Subgraphs in Vertex-Colorings
Authors: Axenovich Maria , Martin Ryan
Published: January 2020

For a fixed graph $H$ on $k$ vertices, and a graph $G$ on at least $k$ vertices, we write $G\longrightarrow H$ if in any vertex-coloring of $G$ with $k$ colors, there is an induced subgraph isomorphic to $H$ whose vertices have distinct colors. In other words, if $G\longrightarrow H$ then a totally multicolored induced copy of $H$ is unavoidable in any vertex-coloring of $G$ with $k$ colors. In this paper, we show that, with a few notable exceptions, for any graph $H$ on $k$ vertices and for any graph $G$ which is not isomorphic to $H$, $G\not\!\!\longrightarrow H$. We explicitly describe all exceptional cases. This determines the induced vertex-anti-Ramsey number for all graphs and shows that totally multicolored induced subgraphs are, in most cases, easily avoidable.
An Inverse Matrix Formula in the Right-Quantum Algebra
Authors: Konvalinka Matjaž
Published: January 2020

The right-quantum algebra was introduced recently by Garoufalidis, Lê and Zeilberger in their quantum generalization of the MacMahon master theorem. A bijective proof of this identity due to Konvalinka and Pak, and also the recent proof of the right-quantum Sylvester's determinant identity, make heavy use of a bijection related to the first fundamental transformation on words introduced by Foata. This paper makes explicit the connection between this transformation and right-quantum linear algebra identities; we give a new, bijective proof of the right-quantum matrix inverse theorem, we show that similar techniques prove the right-quantum Jacobi ratio theorem, and we use the matrix inverse formula to find a generalization of the (right-quantum) MacMahon master theorem.
The Maximum Piercing Number for some Classes of Convex Sets with the $(4,3)$-property
Authors: Kynčl Jan , Tancer Martin
Published: January 2020

A finite collection ${\cal C}$ of closed convex sets in ${\Bbb R}^d$ is said to have a $(p,q)$-property if among any $p$ members of ${\cal C}$ some $q$ have a non-empty intersection, and $|{\cal C}| \ge p$. A piercing number of ${\cal C}$ is defined as the minimal number $k$ such that there exists a $k$-element set which intersects every member of ${\cal C}$. We focus on the simplest non-trivial case in ${\Bbb R}^2$, i.e., $p=4$ and $q=3$. It is known that the maximum possible piercing number of a finite collection of closed convex sets in the plane with $(4,3)$-property is at least $3$ and at most $13$. We consider the following three special types of collections of closed convex sets: segments in ${\Bbb R}^d$, unit discs in the plane and positively homothetic triangles in the plane, in each case only those satisfying $(4,3)$-property. We prove that the maximum possible piercing number is $2$ for the collections of segments and $3$ for the collections of the other two types.
Dominating Sets of Random 2-in 2-out Directed Graphs
Authors: Howe Stephen
Published: January 2020

We analyse an algorithm for finding small dominating sets of $2$-in $2$-out directed graphs using a deprioritised algorithm and differential equations. This deprioritised approach determines an a.a.s. upper bound of $0.39856n$ on the size of the smallest dominating set of a random $2$-in $2$-out digraph on $n$ vertices. Direct expectation arguments determine a corresponding lower bound of $0.3495n$.
Using Algebraic Properties of Minimal Idempotents for Exhaustive Computer Generation of Association Schemes
Authors: Coolsaet K. , Degraer J.
Published: January 2020

During the past few years we have obtained several new computer classification results on association schemes and in particular distance regular and strongly regular graphs. Central to our success is the use of two algebraic constraints based on properties of the minimal idempotents $E_{i}$ of these association schemes : the fact that they are positive semidefinite and that they have known rank. Incorporating these constraints into an actual isomorph-free exhaustive generation algorithm turns out to be somewhat complicated in practice. The main problem to be solved is that of numerical inaccuracy: we do not want to discard a potential solution because a value which is close to zero is misinterpreted as being negative (in the first case) or nonzero (in the second). In this paper we give details on how this can be accomplished and also list some new classification results that have been recently obtained using this technique: the uniqueness of the strongly regular $(126,50,13,24)$ graph and some new examples of antipodal distance regular graphs. We give an explicit description of a new antipodal distance regular $3$-cover of $K_{14}$, with vertices that can be represented as ordered triples of collinear points of the Fano plane.
Generating Function Identities for $\zeta(2n+2), \zeta(2n+3)$ via the WZ Method
Authors: Pilehrood Kh. Hessami , Pilehrood T. Hessami
Published: January 2020

Using WZ-pairs we present simpler proofs of Koecher, Leshchiner and Bailey-Borwein-Bradley's identities for generating functions of the sequences $\{\zeta(2n+2)\}_{n\ge 0}$ and $\{\zeta(2n+3)\}_{n\ge 0}.$ By the same method, we give several new representations for these generating functions yielding faster convergent series for values of the Riemann zeta function.
On a Covering Problem for Equilateral Triangles
Authors: Dumitrescu Adrian , Jiang Minghui
Published: January 2020

Let $T$ be a unit equilateral triangle, and $T_1,\dots,T_n$ be $n$ equilateral triangles that cover $T$ and satisfy the following two conditions: (i) $T_i$ has side length $t_i$ ($0 < t_i < 1$); (ii) $T_i$ is placed with each side parallel to a side of $T$. We prove a conjecture of Zhang and Fan asserting that any covering that meets the above two conditions (i) and (ii) satisfies $\sum_{i=1}^n t_i \geq 2$. We also show that this bound cannot be improved.
A New Family of Somos-like Recurrences
Authors: Heideman Paul , Hogan Emilie
Published: January 2020

We exhibit a three parameter infinite family of quadratic recurrence relations inspired by the well known Somos sequences. For one infinite subfamily we prove that the recurrence generates an infinite sequence of integers by showing that the same sequence is generated by a linear recurrence (with suitable initial conditions). We also give conjectured relations among the three parameters so that the quadratic recurrences generate sequences of integers.
On Rainbow Connection
Authors: Caro Yair , Lev Arie , Roditty Yehuda , Tuza Zsolt , Yuster Raphael
Published: January 2020

An edge-colored graph $G$ is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph $G$, denoted $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this paper we prove several non-trivial upper bounds for $rc(G)$, as well as determine sufficient conditions that guarantee $rc(G)=2$. Among our results we prove that if $G$ is a connected graph with $n$ vertices and with minimum degree $3$ then $rc(G) < 5n/6$, and if the minimum degree is $\delta$ then $rc(G) \le {\ln \delta\over\delta}n(1+o_\delta(1))$. We also determine the threshold function for a random graph to have $rc(G)=2$ and make several conjectures concerning the computational complexity of rainbow connection.
Tetrahedra on Deformed and Integral Group Cohomology
Authors: Blagojević Pavle V. M. , Ziegler Günter M.
Published: January 2020

We show that for every injective continuous map $f:S^2\rightarrow{\Bbb R}^3$ there are four distinct points in the image of $f$ such that the convex hull is a tetrahedron with the property that two opposite edges have the same length and the other four edges are also of equal length. This result represents a partial result for the topological Borsuk problem for ${\Bbb R}^3$. Our proof of the geometrical claim, via Fadell–Husseini index theory, provides an instance where arguments based on group cohomology with integer coefficients yield results that cannot be accessed using only field coefficients.
The Number of Graphs Not Containing $K_{3,3}$ as a Minor
Authors: Gerke Stefanie , Giménez Omer , Noy Marc , Weißl Andreas
Published: January 2020

We derive precise asymptotic estimates for the number of labelled graphs not containing $K_{3,3}$ as a minor, and also for those which are edge maximal. Additionally, we establish limit laws for parameters in random $K_{3,3}$-minor-free graphs, like the number of edges. To establish these results, we translate a decomposition for the corresponding graphs into equations for generating functions and use singularity analysis. We also find a precise estimate for the number of graphs not containing the graph $K_{3,3}$ plus an edge as a minor.
Compression of Root Systems and the $E$-Sequence
Authors: Purbhoo Kevin
Published: January 2020

We examine certain maps from root systems to vector spaces over finite fields. By choosing appropriate bases, the images of these maps can turn out to have nice combinatorial properties, which reflect the structure of the underlying root system. The main examples are $E_6$ and $E_7$.
Affine Partitions and Affine Grassmannians
Authors: Billey Sara C. , Mitchell Stephen A.
Published: January 2020

We give a bijection between certain colored partitions and the elements in the quotient of an affine Weyl group modulo its Weyl group. By Bott's formula these colored partitions give rise to some partition identities. In certain types, these identities have previously appeared in the work of Bousquet-Melou-Eriksson, Eriksson-Eriksson and Reiner. In other types the identities appear to be new. For type $A_{n}$, the affine colored partitions form another family of combinatorial objects in bijection with $(n+1)$-core partitions and $n$-bounded partitions. Our main application is to characterize the rationally smooth Schubert varieties in the affine Grassmannians in terms of affine partitions and a generalization of Young's lattice which refines weak order and is a subposet of Bruhat order. Several of the proofs are computer assisted.
Balancing Cyclic $R$-ary Gray Codes$\,$ II
Authors: Flahive Mary
Published: January 2020

New cyclic $n$-digit Gray codes are constructed over $\{0, 1, \ldots, R-1 \}$ for all $R \ge 2$, $n \ge 3$. These codes have the property that the distribution of digit changes (transition counts) between two successive elements is close to uniform. For $R=2$, the construction and proof are simpler than earlier balanced cyclic binary Gray codes. For $R \ge 3$ and $n \ge 2$, every transition count is within $2$ of the average $R^n/n$. For even $R >2$, the codes are as close to uniform as possible, except when there are two anomalous transition counts for $R \equiv 2 \pmod{4}$ and $R^n$ is divisible by $n$.
Partitioning 3-Edge-Colored Complete Equi-Bipartite Graphs by Monochromatic Trees under a Color Degree Condition
Authors: Li Xueliang , Liu Fengxia
Published: January 2020

The monochromatic tree partition number of an $r$-edge-colored graph $G$, denoted by $t_r(G)$, is the minimum integer $k$ such that whenever the edges of $G$ are colored with $r$ colors, the vertices of $G$ can be covered by at most $k$ vertex-disjoint monochromatic trees. In general, to determine this number is very difficult. For 2-edge-colored complete multipartite graph, Kaneko, Kano, and Suzuki gave the exact value of $t_2(K(n_1,n_2,\cdots,n_k))$. In this paper, we prove that if $n\geq 3$, and $K(n,n)$ is 3-edge-colored such that every vertex has color degree 3, then $t_3(K(n,n))=3$.
On Certain Eigenspaces of Cographs
Authors: Sander Torsten
Published: January 2020

For every cograph there exist bases of the eigenspaces for the eigenvalues $0$ and $-1$ that consist only of vectors with entries from $\{0, 1, -1\}$, a property also exhibited by other graph classes. Moreover, the multiplicities of the eigenvalues $0$ and $-1$ of a cograph can be determined by counting certain vertices of the associated cotree.
An Extremal Characterization of Projective Planes
Authors: De Winter Stefaan , Lazebnik Felix , Verstraëte Jacques
Published: January 2020

In this article, we prove that amongst all $n$ by $n$ bipartite graphs of girth at least six, where $n = q^2 + q + 1 \ge 157$, the incidence graph of a projective plane of order $q$, when it exists, has the maximum number of cycles of length eight. This characterizes projective planes as the partial planes with the maximum number of quadrilaterals.
Extension of Strongly Regular Graphs
Authors: Gera Ralucca , Shen Jian
Published: January 2020

The Friendship Theorem states that if any two people in a party have exactly one common friend, then there exists a politician who is a friend of everybody. In this paper, we generalize the Friendship Theorem. Let $\lambda$ be any nonnegative integer and $\mu$ be any positive integer. Suppose each pair of friends have exactly $\lambda$ common friends and each pair of strangers have exactly $\mu$ common friends in a party. The corresponding graph is a generalization of strongly regular graphs obtained by relaxing the regularity property on vertex degrees. We prove that either everyone has exactly the same number of friends or there exists a politician who is a friend of everybody. As an immediate consequence, this implies a recent conjecture by Limaye et. al.
An Identity Generator: Basic Commutators
Authors: Farrokhi D. G. M.
Published: January 2020

We introduce a group theoretical tool on which one can derive a family of identities from sequences that are defined by a recursive relation. As an illustration it is shown that $$\sum_{i=1}^{n-1}F_{n-i}F_i^2 ={1\over2}\sum_{i=1}^n(-1)^{n-i}(F_{2i}-F_i) ={F_{n+1}\choose2}-{F_n\choose2}, $$ where $\{F_n\}$ denotes the sequence of Fibonacci numbers.
On the Number of Orthogonal Systems in Vector Spaces over Finite Fields
Authors: Vinh Le Anh
Published: January 2020

Iosevich and Senger (2008) showed that if a subset of the $d$-dimensional vector space over a finite field is large enough, then it contains many $k$-tuples of mutually orthogonal vectors. In this note, we provide a graph theoretic proof of this result.