bluuebunny/crossref_metadata_2025 huggingface dataset:
On-Line List Colouring of Graphs
Authors: Zhu Xuding
Published: January 2020

This paper studies on-line list colouring of graphs. It is proved that the on-line choice number of a graph $G$ on $n$ vertices is at most $\chi(G) \ln n+1$, and the on-line $b$-choice number of $G$ is at most ${e\chi(G)-1\over e-1} (b-1+ \ln n)+b$. Suppose $G$ is a graph with a given $\chi(G)$-colouring of $G$. Then for any $(\chi(G) \ln n +1)$-assignment $L$ of $G$, we give a polynomial time algorithm which constructs an $L$-colouring of $G$. For any $({e\chi(G)-1\over e-1} (b-1+ \ln n)+b)$-assignment $L$ of $G$, we give a polynomial time algorithm which constructs an $(L,b)$-colouring of $G$. We then characterize all on-line $2$-choosable graphs. It is also proved that a complete bipartite graph of the form $K_{3,q}$ is on-line $3$-choosable if and only if it is $3$-choosable, but there are graphs of the form $K_{6,q}$ which are $3$-choosable but not on-line $3$-choosable. Some open questions concerning on-line list colouring are posed in the last section.
On the Unitary Cayley Graph of a Ring
Authors: Kiani Dariush , Molla Haji Aghaei Mohsen
Published: January 2020

Let $R$ be a ring with identity. The unitary Cayley graph of a ring $R$, denoted by $G_{R}$, is the graph, whose vertex set is $R$, and in which $\{x,y\}$ is an edge if and only if $x-y$ is a unit of $R$. In this paper we find chromatic, clique and independence number of $G_{R}$, where $R$ is a finite ring. Also, we prove that if $G_{R} \simeq G_{S}$, then $G_{R/J_{R}} \simeq G_{S/J_{S}}$, where $\rm J_{R}$ and $\rm J_{S}$ are Jacobson radicals of $R$ and $S$, respectively. Moreover, we prove if $G_{R} \simeq G_{M_{n}(F)}$ then $R\simeq M_{n}(F)$, where $R$ is a ring and $F$ is a finite field. Finally, let $R$ and $S$ be finite commutative rings, we show that if $G_{R} \simeq G_{S}$, then $\rm R/ {J}_{R}\simeq S/J_{S}$.
The Spectral Gap of Random Graphs with Given Expected Degrees
Authors: Coja-Oghlan Amin , Lanka André
Published: January 2020

We investigate the Laplacian eigenvalues of a random graph $G(n,\vec d)$ with a given expected degree distribution $\vec d$. The main result is that w.h.p. $G(n,\vec d)$ has a large subgraph core$(G(n,\vec d))$ such that the spectral gap of the normalized Laplacian of core$(G(n,\vec d))$ is $\geq1-c_0\bar d_{\min}^{-1/2}$ with high probability; here $c_0>0$ is a constant, and $\bar d_{\min}$ signifies the minimum expected degree. The result in particular applies to sparse graphs with $\bar d_{\min}=O(1)$ as $n\rightarrow\infty$. The present paper complements the work of Chung, Lu, and Vu [Internet Mathematics 1, 2003].
Genus Distributions for Iterated Claws
Authors: Gross Jonathan L. , Khan Imran F. , Poshni Mehvish I.
Published: January 2020

We derive a recursion for the genus distributions of the graphs obtained by iteratively attaching a claw to the dipole $D_3$. The minimum genus of the graphs in this sequence grows arbitrarily large. The families of graphs whose genus distributions have been calculated previously are either planar or almost planar, or they can be obtained by iterative single-vertex or single-edge amalgamation of small graphs. A significant simplifying construction within this calculation achieves the effect of an amalgamation at three vertices with a single root vertex, rather than with multiple roots.
Distinguishability of Infinite Groups and Graphs
Authors: Smith Simon M , Tucker Thomas W , Watkins Mark E
Published: January 2020

The distinguishing number of a group $G$ acting faithfully on a set $V$ is the least number of colors needed to color the elements of $V$ so that no non-identity element of the group preserves the coloring. The distinguishing number of a graph is the distinguishing number of its automorphism group acting on its vertex set. A connected graph $\Gamma$ is said to have connectivity 1 if there exists a vertex $\alpha \in V\Gamma$ such that $\Gamma \setminus \{\alpha\}$ is not connected. For $\alpha \in V$, an orbit of the point stabilizer $G_\alpha$ is called a suborbit of $G$.We prove that every nonnull, primitive graph with infinite diameter and countably many vertices has distinguishing number $2$. Consequently, any nonnull, infinite, primitive, locally finite graph is $2$-distinguishable; so, too, is any infinite primitive permutation group with finite suborbits. We also show that all denumerable vertex-transitive graphs of connectivity 1 and all Cartesian products of connected denumerable graphs of infinite diameter have distinguishing number $2$. All of our results follow directly from a versatile lemma which we call The Distinct Spheres Lemma.
Hypohamiltonian Graphs and their Crossing Number
Authors: Zamfirescu Carol T.
Published: January 2020

We prove that for every $k \ge 0$ there is an integer $n_0(k)$ such that, for every $n \ge n_0$, there exists a hypohamiltonian graph which has order $n$ and crossing number $k$.
On a Conjecture Concerning the Petersen Graph: Part II
Authors: Plummer Michael , Zha Xiaoya
Published: January 2020

Robertson conjectured that the only 3-connected, internally 4-connected graph of girth 5 in which every odd cycle of length greater than 5 has a chord is the Petersen graph.  We provide a counterexample to this conjecture.
Euler Characteristic of the Truncated Order Complex of Generalized Noncrossing Partitions
Authors: Armstrong D. , Krattenthaler C.
Published: January 2020

The purpose of this paper is to complete the study, begun in the first author's PhD thesis, of the topology of the poset of generalized noncrossing partitions associated to real reflection groups. In particular, we calculate the Euler characteristic of this poset with the maximal and minimal elements deleted. As we show, the result on the Euler characteristic extends to generalized noncrossing partitions associated to well-generated complex reflection groups.
Tight Co-Degree Condition for Perfect Matchings in 4-Graphs
Authors: Czygrinow Andrzej , Kamat Vikram
Published: January 2020

We will give a tight minimum co-degree condition for a 4-uniform hypergraph to contain a perfect matching.
Arc-transitive Pentavalent Graphs of Order 4pq
Authors: Pan Jiangmin , Lou Bengong , Liu Cuifeng
Published: January 2020

This  paper determines all arc-transitive pentavalent graphs of order $4pq$, where $p,q\ge 5$ are distinct primes. The cases $q=1,2,3$ and $q=p$ is a prime have been treated previously by Hua et al. [Pentavalent symmetric graphs of order $2pq$, Discrete Math. 311 (2011), 2259-2267], Hua and Feng [Pentavalent symmetric graphs of order $8p$, J. Beijing Jiaotong University 35 (2011), 132-135], Guo et al. [Pentavalent symmetric graphs of order $12p$, Electronic J. Combin. 18 (2011), #P233] and Huang et al. [Pentavalent symmetric graphs of order four time a prime power, submitted for publication], respectively.
An Approximate Vertex-Isoperimetric Inequality for $r$-sets
Authors: Christofides Demetres , Ellis David , Keevash Peter
Published: January 2020

We prove a vertex-isoperimetric inequality for \([n]^{(r)}\), the set of all \(r\)-element subsets of \(\{1,2,\ldots,n\}\), where \(x,y \in [n]^{(r)}\) are adjacent if \(|x \Delta y|=2\). Namely, if \(\mathcal{A} \subset [n]^{(r)}\) with \(|\mathcal{A}|=\alpha {n \choose r}\), then its vertex-boundary \(b(\mathcal{A})\) satisfies\[|b(\mathcal{A})| \geq c\sqrt{\frac{n}{r(n-r)}} \alpha(1-\alpha) {n \choose r},\]where \(c\) is a positive absolute constant. For \(\alpha\) bounded away from 0 and 1, this is sharp up to a constant factor (independent of \(n\) and \(r\)).
Polyhedral Embeddings of Snarks with Arbitrary Nonorientable Genera
Authors: Liu Wenzhong , Chen Yichao
Published: January 2020

Mohar and Vodopivec [Combinatorics, Probability and Computing (2006) 15, 877-893] proved that for every integer $k$ ($k \geq 1$ and $k\neq 2$), there exists a snark which polyhedrally embeds in $\mathbb{N}_k$ and presented the problem: Is there a snark that has a polyhedral embedding in the Klein bottle? In the paper, we give a positive solution of the problem and strengthen Mohar and Vodopivec's  result. We prove that for every integer $k$ ($k\geq 2$), there exists an infinite family of snarks with nonorientable genus $k$ which polyhedrally embed in $\mathbb{N}_k$. Furthermore, for every integer $k$ ($k> 0$), there exists a snark with nonorientable genus $k$ which polyhedrally embeds in $\mathbb{N}_k$.
On Slowly Percolating Sets of Minimal Size in Bootstrap Percolation
Authors: Benevides Fabricio , Przykucki Michał
Published: January 2020

Bootstrap percolation, one of the simplest cellular automata, can be seen as a model of the spread of infection. In $r$-neighbour bootstrap percolation on a graph $G$ we assign a state, infected or healthy, to every vertex of $G$ and then update these states in successive rounds, according to the following simple local update rule: infected vertices of $G$ remain infected forever and a healthy vertex becomes infected if it has at least $r$ already infected neighbours. We say that percolation occurs if eventually every vertex of $G$ becomes infected. A well known and celebrated fact about the classical model of $2$-neighbour bootstrap percolation on the $n \times n$ square grid is that the smallest size of an initially infected set which percolates in this process is $n$. In this paper we consider the problem of finding the maximum time a $2$-neighbour bootstrap process on $[n]^2$ with $n$ initially infected vertices can take to eventually infect the entire vertex set. Answering a question posed by Bollobás we compute the exact value for this maximum showing that, for $n \ge 4$, it is equal to the integer nearest to $(5n^2-2n)/8$.
Cospectral Graphs on 12 Vertices
Authors: Brouwer A. E. , Spence E.
Published: January 2020

We found the characteristic polynomials for all graphs on 12 vertices, and report statistics related to the number of cospectral graphs.
Higher Chain Formula proved by Combinatorics
Authors: Ma Tsoy-Wo
Published: January 2020

We present an elementary combinatorial proof of a formula to express the higher partial derivatives of composite functions in terms of those of factor functions.
A Complete Classification of Doubly Even Self-dual Codes of Length 40
Authors: Betsumiya Koichi , Harada Masaaki , Munemasa Akihiro
Published: January 2020

A complete classification of binary doubly even self-dual codes of length $40$ is given. As a consequence, a classification of binary extremal self-dual codes of length $38$ is also given.
Connectivity for Random Graphs from a Weighted Bridge-Addable Class
Authors: McDiarmid Colin
Published: January 2020

There has been much recent interest in random graphs sampled uniformly from the $n$-vertex graphs in a suitable structured class, such as the class of all planar graphs. Here we consider a general bridge-addable class $\cal A$ of graphs -- if a graph is in $\cal A$ and $u$ and $v$ are vertices in different components   then the graph obtained by adding an edge (bridge) between $u$ and $v$ must also be in $\cal A$. Various bounds are known concerning the probability of a random graph from such a   class being connected or having many components, sometimes under the additional assumption that bridges can be deleted as well as added. Here we improve or amplify or generalise these bounds (though we do not resolve the main conjecture). For example, we see that the expected number of vertices left when we remove a largest component is less than 2. The generalisation is to consider `weighted' random graphs, sampled from a suitable more general distribution, where the focus is on the bridges.
On Short Zero-Sum Subsequences of Zero-Sum Sequences
Authors: Fan Yushuang , Gao Weidong , Wang Guoqing , Zhong Qinghai , Zhuang Jujuan
Published: January 2020

Let $G$ be a finite abelian group of exponent $\exp(G)$. By $D(G)$ we denote the smallest integer $d\in \mathbb N$ such that every sequence over $G$ of length at least $d$ contains a nonempty zero-sum subsequence. By $\eta(G)$ we denote the smallest integer $d\in \mathbb N$ such that every sequence over $G$ of length at least $d$ contains a zero-sum subsequence $T$ with length $|T|\in [1,\exp(G)]$, such a sequence $T$ will be called a short zero-sum sequence. Let $C_0(G)$ denote the set consists of all integer $t\in [D(G)+1,\eta(G)-1]$ such that every zero-sum sequence of length exactly $t$ contains a short zero-sum subsequence. In this paper, we investigate the question whether $C_0(G)\neq \emptyset$ for all non-cyclic finite abelian groups $G$. Previous results showed that $C_0(G)\neq \emptyset$ for the groups $C_n^2$ ($n\geq 3$) and $C_3^3$. We show that more groups including the groups $C_m\oplus C_n$ with $3\leq m\mid n$, $C_{3^a5^b}^3$, $C_{3\times 2^a}^3$, $C_{3^a}^4$ and $C_{2^b}^r$ ($b\geq 2$) have this property. We also determine $C_0(G)$ completely  for some groups including the groups of rank two, and some special groups with large exponent.
T-systems with Boundaries from Network Solutions
Authors: Di Francesco Philippe , Kedem Rinat
Published: January 2020

In this paper, we use the network solution of the $A_r$ $T$-system to derive that of the unrestricted $A_\infty$ $T$-system, equivalent to the octahedron relation.  We then present a method for implementing various boundary conditions on this system, which consists of picking initial data with suitable symmetries. The corresponding restricted $T$-systems are solved exactly in terms of networks. This gives a simple explanation for phenomena such as the Zamolodchikov periodicity property for $T$-systems (corresponding to the case $A_\ell\times A_r$) and a combinatorial interpretation for the positive Laurent property for the variables of the associated cluster algebra. We also explain the relation between the $T$-system wrapped on a torus and the higher pentagram maps of Gekhtman et al.
A Superlocal Version of Reed's Conjecture
Authors: Edwards Katherine , King Andrew D.
Published: January 2020

Reed's well-known $\omega$, $\Delta$, $\chi$ conjecture proposes that every graph satisfies $\chi \leq \lceil \frac 12(\Delta+1+\omega)\rceil$. The second author formulated a local strengthening of this conjecture that considers a bound supplied by the neighbourhood of a single vertex. Following the idea that the chromatic number cannot be greatly affected by any particular stable set of vertices, we propose a further strengthening that considers a bound supplied by the neighbourhoods of two adjacent vertices. We provide some fundamental evidence in support, namely that the stronger bound holds in the fractional relaxation and holds for both quasi-line graphs and graphs with stability number two. We also conjecture that in the fractional version, we can push the locality even further.
Random Lifts of Graphs are Highly Connected
Authors: Witkowski Marcin
Published: January 2020

In this note we study asymptotic properties of random lifts of graphs introduced by Amit and Linial as a new model of random graphs. Given a base graph $G$ and an integer $n$, a random lift of $G$ is obtained by replacing each vertex of $G$ by a set of $n$ vertices, and joining these sets by random matchings whenever the corresponding vertices of $G$ are adjacent. In this paper we study connectivity properties of random lifts. We show that the size of the largest topological clique in typical random lifts, with $G$ fixed and $n\rightarrow\infty$, is equal to the maximum degree of the core of $G$ plus one. A similar idea can be used to prove that for any graph $G$ with $\delta(G)\geq2k-1$ almost every random lift of $G$ is $k$-linked.
Degree Distribution of an Inhomogeneous Random Intersection Graph
Authors: Bloznelis Mindaugas , Damarackas Julius
Published: January 2020

We show the asymptotic degree distribution of the typical vertex of a sparse inhomogeneous random intersection graph.
On the Skew Spectra of Cartesian Products of Graphs
Authors: Denglan Cui , Yaoping Hou
Published: January 2020

An oriented graph ${G^{\sigma}}$ is a simple undirected graph $G$ with an orientation, which assigns to each edge of $G$ a direction so that ${G^{\sigma}}$ becomes a directed graph. $G$ is called the underlying graph of ${G^{\sigma}}$ and we denote by $S({G^{\sigma}})$ the skew-adjacency matrix of ${G^{\sigma}}$ and its spectrum $Sp({G^{\sigma}})$ is called the skew-spectrum of ${G^{\sigma}}$. In this paper, the skew spectra of two orientations of the Cartesian products are discussed, as applications, new families of oriented bipartite graphs ${G^{\sigma}}$ with $Sp({G^{\sigma}})={\bf i} Sp(G)$ are given and the orientation of a product graph with maximum skew energy is obtained.
Graph Powers and Graph Homomorphisms
Authors: Hajiabolhassan Hossein , Taherkhani Ali
Published: January 2020

In this paper, we investigate some basic properties of fractional powers. In this regard, we show that for any non-bipartite graph $G$ and positive rational numbers ${2r+1\over 2s+1} < {2p+1\over 2q+1}$, we have $G^{2r+1\over 2s+1} < G^{2p+1\over 2q+1}$. Next, we study the power thickness of $G$, that is, the supremum of rational numbers ${2r+1\over 2s+1}$ such that $G$ and $G^{2r+1\over 2s+1}$ have the same chromatic number. We prove that the power thickness of any non-complete circular complete graph is greater than one. This provides a sufficient condition for the equality of the chromatic number and the circular chromatic number of graphs. Finally, we introduce an equivalent definition for the circular chromatic number of graphs in terms of fractional powers. Also, we show that for any non-bipartite graph $G$ if $0 < {{2r+1}\over {2s+1}} \leq {{\chi(G)}\over{3(\chi(G)-2)}}$, then $\chi(G^{{2r+1}\over {2s+1}})=3$. Moreover, $\chi(G)\neq\chi_c(G)$ if and only if there exists a rational number ${{2r+1}\over {2s+1}}>{{\chi(G)}\over{3(\chi(G)-2)}}$ for which $\chi(G^{{2r+1}\over {2s+1}})= 3$.
The Adjacency Matroid of a Graph
Authors: Traldi Lorenzo , Brijder Robert , Hoogeboom Hendrik Jan
Published: January 2020

If $G$ is a looped graph, then its adjacency matrix represents a binary matroid $M_{A}(G)$ on $V(G)$. $M_{A}(G)$ may be obtained from the delta-matroid represented by the adjacency matrix of $G$, but $M_{A}(G)$ is less sensitive to the structure of $G$. Jaeger proved that every binary matroid is $M_{A}(G)$ for some $G$ [Ann. Discrete Math. 17 (1983), 371-376]. The relationship between the matroidal structure of $M_{A}(G)$ and the graphical structure of $G$ has many interesting features. For instance, the matroid minors $M_{A}(G)-v$ and $M_{A}(G)/v$ are both of the form $M_{A}(G^{\prime}-v)$ where $G^{\prime}$ may be obtained from $G$ using local complementation. In addition, matroidal considerations lead to a principal vertex tripartition, analogous in some ways to the principal edge tripartition of Rosenstiehl and Read [Ann. Discrete Math. 3 (1978), 195-226]. Several of these results are given two very different proofs, the first involving linear algebra and the second involving set systems or delta-matroids. Also, the Tutte polynomials of the adjacency matroids of $G$ and its full subgraphs are closely connected to the interlace polynomial of Arratia, Bollobás and Sorkin [Combinatorica 24 (2004), 567-584].
Distance-Restricted Matching Extension in Triangulations of the Torus and the Klein Bottle
Authors: Aldred Robert E.L. , Fujisawa Jun
Published: January 2020

A graph $G$ with at least $2m+2$ edges is said to be distance $d$ $m$-extendable if for any matching $M$ in $G$ with $m$ edges in which the edges lie pair-wise distance at least $d$, there exists a perfect matching in $G$ containing $M$. In a previous paper, Aldred and Plummer proved that every $5$-connected triangulation of the plane or the projective plane of even order is distance $5$ $m$-extendable for any $m$. In this paper we prove that the same conclusion holds for every triangulation of the torus or the Klein bottle.
General Restriction of $(s,t)$-Wythoff's Game
Authors: Liu Wen An , Li Haiyan
Published: January 2020

A.S. Fraenkel introduced a new $(s,t)$-Wythoff's game which is a generalization of both Wythoff's game and $a$-Wythoff's game. Four new models of a restricted version of $(s,t)$-Wythoff's game, Odd-Odd $(s,t)$-Wythoff's Game, Even-Even $(s,t)$-Wythoff's Game, Odd-Even $(s,t)$-Wythoff's Game and Even-Odd $(s,t)$-Wythoff's Game, are investigated. Under normal or misère play conventions, all $P$-positions of these four models are given for arbitrary integers $s,t\geq 1$. For Even-Even $(s,t)$-Wythoff's Game, the structure of $P$-positions is given by recursive characterizations in terms of the mex function. For other models, the structures of $P$-positions are of algebraic form, which permit us to decide in polynomial time whether or not a given game position $(a,b)$ is a $P$-position.
Bootstrap Percolation and Diffusion in Random Graphs with Given Vertex Degrees
Authors: Amini Hamed
Published: January 2020

We consider diffusion in random graphs with given vertex degrees. Our diffusion model can be viewed as a variant of a cellular automaton growth process: assume that each node can be in one of the two possible states, inactive or active. The parameters of the model are two given functions $\theta: {\Bbb N} \rightarrow {\Bbb N}$ and $\alpha:{\Bbb N} \rightarrow [0,1]$. At the beginning of the process, each node $v$ of degree $d_v$ becomes active with probability $\alpha(d_v)$ independently of the other vertices. Presence of the active vertices triggers a percolation process: if a node $v$ is active, it remains active forever. And if it is inactive, it will become active when at least $\theta(d_v)$ of its neighbors are active. In the case where $\alpha(d) =\alpha$ and $\theta(d) =\theta$, for each $d \in {\Bbb N}$, our diffusion model is equivalent to what is called bootstrap percolation. The main result of this paper is a theorem which enables us to find the final proportion of the active vertices in the asymptotic case, i.e., when $n \rightarrow \infty$. This is done via analysis of the process on the multigraph counterpart of the graph model.
On the Characteristic Polynomial of $n$-Cayley Digraphs
Authors: Arezoomand Majid , Taeri Bijan
Published: January 2020

A digraph $\Gamma$ is called $n$-Cayley digraph over a group $G$‎, ‎if there exists a semiregular subgroup $R_G$ of Aut$(\Gamma)$ isomorphic to $G$ with $n$ orbits‎. ‎In this paper‎, ‎we represent the adjacency matrix of $\Gamma$ as a diagonal block‎ ‎matrix in terms of irreducible representations of $G$ and determine its characteristic polynomial‎. ‎As corollaries of this result we find‎:  ‎the spectrum of  semi-Cayley graphs over abelian groups‎, ‎a relation between the characteristic polynomial of an $n$-Cayley graph and its complement‎, ‎and   the spectrum of‎ ‎Calye graphs over groups with cyclic subgroups‎. ‎Finally we determine the eigenspace of $n$-Cayley digraphs and their main eigenvalues‎.
Stirling Numbers of Forests and Cycles
Authors: Galvin David , Thanh Do Trong
Published: January 2020

For a graph $G$ and a positive integer $k$, the graphical Stirling number $S(G,k)$ is the number of partitions of the vertex set of $G$ into $k$ non-empty independent sets. Equivalently it is the number of proper colorings of $G$ that use exactly $k$ colors, with two colorings identified if they differ only on the names of the colors. If $G$ is the empty graph on $n$ vertices then $S(G,k)$ reduces to  $S(n,k)$, the familiar Stirling number  of the second kind.In this note we first consider Stirling numbers of forests. We show that if $(F^{c(n)}_n)_{n\geq 0}$ is any sequence of forests with $F^{c(n)}_n$ having $n$ vertices and $c(n)=o(\sqrt{n/\log n})$ components, and if $X^{c(n)}_n$ is a random variable that takes value $k$ with probability proportional to $S(F^{c(n)}_n,k)$ (that is, $X^{c(n)}_n$ is the number of classes in a uniformly chosen partition of $F^{c(n)}_n$ into non-empty independent sets), then $X^{c(n)}_n$ is asymptotically normal, meaning that suitably normalized it tends in distribution to the standard normal. This generalizes a seminal result of Harper on the ordinary Stirling numbers. Along the way we give recurrences for calculating the generating functions of the sequences $(S(F^c_n,k))_{k \geq 0}$, show that these functions have all real zeroes, and exhibit three different interlacing patterns between the zeroes of pairs of consecutive generating functions.We next consider Stirling numbers of cycles. We establish asymptotic normality for the number of classes in a uniformly chosen partition of $C_n$ (the cycle on $n$ vertices) into non-empty independent sets. We give a recurrence for calculating the generating function of the sequence $(S(C_n,k))_{k \geq 0}$, and use this to give a direct proof of a log-concavity result that had previously only been arrived at in a very indirect way.
The Cyclic Sieving Phenomenon for Faces of Cyclic Polytopes
Authors: Eu Sen-Peng , Fu Tung-Shan , Pan Yeh-Jong
Published: January 2020

A cyclic polytope of dimension $d$ with $n$ vertices is a convex polytope combinatorially equivalent to the convex hull of $n$ distinct points on a moment curve in ${\Bbb R}^d$. In this paper, we prove the cyclic sieving phenomenon, introduced by Reiner-Stanton-White, for faces of an even-dimensional cyclic polytope, under a group action that cyclically translates the vertices. For odd-dimensional cyclic polytopes, we enumerate the faces that are invariant under an automorphism that reverses the order of the vertices and an automorphism that interchanges the two end vertices, according to the order on the curve. In particular, for $n=d+2$, we give instances of the phenomenon under the groups that cyclically translate the odd-positioned and even-positioned vertices, respectively.
On the Size of Kakeya Sets in Finite Vector Spaces
Authors: Kyureghyan Gohar , Müller Peter , Wang Qi
Published: January 2020

For a finite field $\mathbb{F}_q$, a Kakeya set $K$ is a subset of $\mathbb{F}_q^n$ that contains a line in every direction. This paper derives new upper bounds on the minimum size of Kakeya sets when $q$ is even.
Gromov Hyperbolicity in Strong Product Graphs
Authors: Carballosa Walter , Casablanca Rocío M. , De la Cruz Amauris , Rodríguez José M.
Published: January 2020

If X is a geodesic metric space and $x_1,x_2,x_3\in X$, a geodesic triangle $T=\{x_1,x_2,x_3\}$ is the union of the three geodesics $[x_1x_2]$, $[x_2x_3]$ and $[x_3x_1]$ in $X$. The space $X$ is $\delta$-hyperbolic $($in the Gromov sense$)$ if any side of $T$ is contained in a $\delta$-neighborhood of the union of the two other sides, for every geodesic triangle $T$ in $X$. If $X$ is hyperbolic, we denote by $\delta (X)$ the sharp hyperbolicity constant of $X$, i.e., $\delta (X)=\inf\{\delta\geq 0: \, X \, \text{ is $\delta$-hyperbolic}\,\}\,.$ In this paper we characterize the strong product of two graphs $G_1\boxtimes G_2$ which are hyperbolic, in terms of $G_1$ and $G_2$: the strong product graph $G_1\boxtimes G_2$ is hyperbolic if and only if one of the factors is hyperbolic and the other one is bounded. We also prove some sharp relations between $\delta (G_1\boxtimes G_2)$, $\delta (G_1)$, $\delta (G_2)$ and the diameters of $G_1$ and $G_2$ (and we find families of graphs for which the inequalities are attained). Furthermore, we obtain the exact values of the hyperbolicity constant for many strong product graphs.
Knots in Collapsible and Non-Collapsible Balls
Authors: Benedetti Bruno , Lutz Frank H.
Published: January 2020

We construct the first explicit example of a simplicial 3-ball $B_{15,66}$ that is not collapsible. It has only 15 vertices. We exhibit a second 3-ball $B_{12,38}$ with 12 vertices that is collapsible and not shellable, but evasive. Finally, we present the first explicit triangulation of a 3-sphere $S_{18, 125}$ (with only 18 vertices) that is not locally constructible. All these examples are based on knotted subcomplexes with only three edges; the knots are the trefoil, the double trefoil, and the triple trefoil, respectively. The more complicated the knot is, the more distant the triangulation is from being polytopal, collapsible, etc. Further consequences of our work are:(1) Unshellable 3-spheres may have vertex-decomposable barycentric subdivisions. (This shows the strictness of an implication proven by Billera and Provan.)(2) For $d$-balls, vertex-decomposable implies non-evasive implies collapsible, and for $d=3$ all implications are strict. (This answers a question by Barmak.)(3) Locally constructible 3-balls may contain a double trefoil knot as a 3-edge subcomplex. (This improves a result of Benedetti and Ziegler.)(4) Rudin's ball is non-evasive.
Shattering, Graph Orientations, and Connectivity
Authors: Kozma László , Moran Shay
Published: January 2020

We present a connection between two seemingly disparate fields: VC-theory and graph theory. This connection yields natural correspondences between fundamental concepts in VC-theory, such as shattering and VC-dimension, and well-studied concepts of graph theory related to connectivity, combinatorial optimization, forbidden subgraphs, and others.In one direction, we use this connection to derive results in graph theory. Our main tool is a generalization of the Sauer-Shelah Lemma (Pajor, 1985; Bollobás and Radcliffe, 1995; Dress, 1997; Holzman and Aharoni). Using this tool we obtain a series of inequalities and equalities related to properties of orientations of a graph. Some of these results appear to be new, for others we give new and simple proofs.In the other direction, we present new illustrative examples of shattering-extremal systems - a class of set-systems in VC-theory whose understanding is considered by some authors to be incomplete Bollobás and Radcliffe, 1995; Greco, 1998; Rónyai and Mészáros, 2011). These examples are derived from properties of orientations related to distances and flows in networks.
On Convexity of Polynomial Paths and Generalized Majorizations
Authors: Dodig Marija , Stošić Marko
Published: January 2020

In this paper we give some useful combinatorial properties of polynomial paths. We also introduce generalized majorization between three sequences of integers and explore its combinatorics. In addition, we give a new, simple, purely polynomial proof of the convexity lemma of E. M. de Sá and R. C. Thompson. All these results have applications in matrix completion theory.
Tree Reconstruction from Triplet Cover Distances
Authors: Huber Katharina T. , Steel Mike
Published: January 2020

It is a classical result that any finite tree with positively weighted edges, and without vertices of degree 2, is uniquely determined by the weighted path distance between each pair of leaves. Moreover, it is possible for a (small) strict subset $\mathcal{L}$ of leaf pairs to suffice for reconstructing the tree and its edge weights, given just the distances between the leaf pairs in $\mathcal{L}$. It is known that any set ${\mathcal L}$ with this property for a tree in which all interior vertices have degree 3 must form a cover  for $T$ - that is, for each interior vertex $v$ of $T$, ${\mathcal L}$ must contain a pair of leaves from each pair of the three components of  $T-v$.  Here we provide a partial converse of this result by showing that if a set ${\mathcal L}$ of leaf pairs forms a cover  of a certain type for such a tree $T$ then $T$ and its edge weights can be uniquely determined from the distances between the pairs of leaves in ${\mathcal L}$. Moreover,  there is a polynomial-time algorithm for achieving this reconstruction. The result establishes a special case of a recent question concerning 'triplet covers', and is relevant to a problem arising in evolutionary genomics.
Decomposing Dense Bipartite Graphs into 4-Cycles
Authors: Cavenagh Nicholas
Published: January 2020

Let $G$ be an even bipartite graph with partite sets $X$ and $Y$ such that $|Y|$ is even and the minimum degree of a vertex in $Y$ is at least $95|X|/96$. Suppose furthermore that the number of edges in $G$ is divisible by $4$. Then $G$ decomposes into 4-cycles.
The Spectra of Certain Classes of Room Frames: The Last Cases
Authors: Dinitz Jeffrey H. , Warrington Gregory S.
Published: January 2020

In this paper we study the spectra of certain classes of Room frames. The three spectra which we study are incomplete Room squares, uniform Room frames and Room frames of type $2^ut^1$. These problems have been studied in numerous papers over the years; in this paper, we complete the three spectra. In addition we find a Howell cube of type $H_3(6,10)$. This corrects a previous claim of nonexistence of this design.
Enumeration of Specific Classes of Polycubes
Authors: Champarnaud Jean-Marc , Cohen-Solal Quentin , Dubernard Jean-Philippe , Jeanne Hadrien
Published: January 2020

The aim of this paper is to gather several results concerning the enumeration of specific classes of polycubes. We first consider two classes of $3$-dimensional vertically-convex directed polycubes: the plateau polycubes and the parallelogram polycubes. An expression of the generating function is provided for the former class, as well as an asymptotic result for the number of polycubes of each class with respect to volume and width. We also consider three classes of $d$-dimensional polycubes $(d\geq 3)$ and we state asymptotic results for the number of polycubes of each class with respect to volume and width.
On the Möbius Function of Permutations with One Descent
Authors: Smith Jason P.
Published: January 2020

The set of all permutations, ordered by pattern containment, is a poset. We give a formula for the Möbius function of intervals $[1,\pi]$ in this poset, for any permutation $\pi$ with at most one descent. We compute the Möbius function as a function of the number and positions of pairs of consecutive letters in $\pi$ that are consecutive in value. As a result of this we show that the Möbius function is unbounded on the poset of all permutations. We show that the Möbius function is zero on any interval $[1,\pi]$ where $\pi$ has a triple of consecutive letters whose values are consecutive and monotone. We also conjecture values of the Möbius function on some other intervals of permutations with at most one descent.
Zero-Sum Magic Labelings and Null Sets of Regular Graphs
Authors: Akbari Saieed , Rahmati Farhad , Zare Sanaz
Published: January 2020

For every $h\in  \mathbb{N}$, a graph $G$ with the vertex set $V(G)$ and the  edge set $E(G)$ is said to be $h$-magic if there exists a labeling $l : E(G) \rightarrow\mathbb{Z}_h \setminus \{0\}$  such that the induced vertex labeling $s : V (G) \rightarrow \mathbb{Z}_h$, defined  by $s(v) =\sum_{uv \in E(G)} l(uv)$ is a constant map. When this constant is zero, we say that $G$ admits a zero-sum $h$-magic labeling. The null set of a graph $G$, denoted by $N(G)$, is the set of all natural numbers $h \in \mathbb{ N} $ such that $G$ admits a zero-sum $h$-magic labeling.  In 2012, the null sets of 3-regular graphs were determined. In this paper we show that if $G$ is an $r$-regular graph, then for even $r$ ($r > 2$), $N(G)=\mathbb{N}$ and for odd $r$ ($r\neq5$),  $\mathbb{N} \setminus \{2,4\}\subseteq N(G)$. Moreover,  we prove that if $r$ is odd and $G$ is a $2$-edge connected $r$-regular graph ($r\neq 5$), then $ N(G)=\mathbb{N} \setminus \{2\}$. Also, we show that if $G$ is a $2$-edge connected bipartite graph, then $\mathbb{N} \setminus \{2,3,4,5\}\subseteq N(G)$.
Congruences of Finite Summations of the Coefficients in certain Generating Functions
Authors: Huang Po-Yi , Liu Shu-Chung , Yeh Yeong-Nan
Published: January 2020

In this paper we develop a general method to enumerate the congruences of finite summations $\sum_{k=0}^{p-1} \frac{a_k}{m^k} \!\pmod{p}$ and $\sum_{k=0}^{p-1-h} \frac{a_k a_{k+h}}{B^k} \!\pmod{p}$ for the the infinite sequence $\{a_n\}_{n\ge 0}$ with generating functions $(1+x f(x))^\frac{N}{2}$, where $f(x)$ is an integer polynomial and $N$ is an odd integer with $|N|< p$. We also enumerate the congruences of some similar finite summations involving generating functions $\frac{1-\alpha x -\sqrt{1-2(\alpha+\beta)x + Bx^2}}{\beta x}$ and $\frac{1-\alpha x-\sqrt{1-2\alpha x+(\alpha^2-4\beta)x^2}}{2\beta x^2}$.
Periodicity and Other Structure in a Colorful Family of Nim-like Arrays
Authors: Abrams Lowell , Cowen-Morton Dena S.
Published: January 2020

We study aspects of the combinatorial and graphical structure shared by a certain family of recursively generated arrays related to the operation of Nim-addition. In particular, these arrays display periodic behavior along rows and diagonals. We explain how various features of computer-generated graphics depicting these arrays are reflections of the theorems we prove.
A General Central Limit Theorem for Shape Parameters of $m$-ary Tries and PATRICIA Tries
Authors: Fuchs Michael , Lee Chung-Kuei
Published: January 2020

Tries and PATRICIA tries are fundamental data structures in computer science with numerous applications. In a recent paper, a general framework for obtaining the mean and variance of additive shape parameters of tries and PATRICIA tries under the Bernoulli model was proposed. In this note, we show that a slight modification of this framework yields a central limit theorem for shape parameters, too. This central limit theorem contains many of the previous central limit theorems from the literature and it can be used to prove recent conjectures and derive new results. As an example, we will consider a refinement of the size of tries and PATRICIA tries, namely, the number of nodes of fixed outdegree and obtain (univariate and bivariate) central limit theorems. Moreover, trivariate central limit theorems for size, internal path length and internal Wiener index of tries and PATRICIA tries are derived as well.
Arcs with Large Conical Subsets
Authors: Coolsaet K. , Sticker H.
Published: January 2020

We classify the arcs in $\mathrm{PG}(2,q)$, $q$ odd, which consist of $(q+3)/2$ points of a conic $C$ and two points not on te conic but external to $C$, or $(q+1)/2$ points of $C$ and two additional points, at least one of which is an internal point of $C$. We prove that for arcs of the latter type, the number of points internal to $C$ can be at most $4$, and we give a complete classification of all arcs that attain this bound. Finally, we list some computer results on extending arcs of both types with further points.
Treewidth of the Kneser Graph and the Erdős-Ko-Rado Theorem
Authors: Harvey Daniel J. , Wood David R.
Published: January 2020

Treewidth is an important and well-known graph parameter that measures the complexity of a graph. The Kneser graph Kneser$(n,k)$ is the graph with vertex set $\binom{[n]}{k}$, such that two vertices are adjacent if they are disjoint. We determine, for large values of $n$ with respect to $k$, the exact treewidth of the Kneser graph. In the process of doing so, we also prove a strengthening of the Erdős-Ko-Rado Theorem (for large $n$ with respect to $k$) when a number of disjoint pairs of $k$-sets are allowed.
Optimal Packings of 13 and 46 Unit Squares in a Square
Authors: Bentz Wolfram
Published: January 2020

Let $s(n)$ be the side length of the smallest square into which $n$ non-overlapping unit squares can be packed. We show that $s(m^2-3)=m$ for $m=4,7$, implying that the most efficient packings of 13 and 46 squares are the trivial ones.
New Infinite Families of Congruences Modulo 8 for Partitions with Even Parts Distinct
Authors: Xia Ernest X. W.
Published: January 2020

Let $ped(n)$ denote the number of partitions of an integer $n$ wherein even parts are distinct. Recently, Andrews, Hirschhorn and Sellers, Chen, and Cui and Gu have derived a number of interesting congruences modulo 2, 3 and 4 for $ped(n)$. In this paper we prove several new infinite families of congruences modulo 8 for $ped(n)$. For example, we prove that for $ \alpha \geq 0$ and $n\geq 0$,\[ ped\left(3^{4\alpha+4}n+\frac{11\times 3^{4\alpha+3}-1}{8}\right)\equiv 0 \  ({\rm mod \ 8}).\]
Random Threshold Digraphs
Authors: Reilly Elizabeth , Scheinerman Edward , Zhang Yiguang
Published: January 2020

This paper introduces a notion of a random threshold directed graph, extending the work of Reilly and Scheinerman in the undirected case and closely related to random Ferrers digraphs.We begin by presenting the main definition: $D$ is a threshold digraph provided we can find a pair of weighting functions $f,g:V(D)\to\mathbb{R}$ such that for distinct $v,w\in V(D)$ we have $v\to w$ iff $f(v)+g(w)\ge1$. We also give an equivalent formulation based on an order representation that is purely combinatorial (no arithmetic). We show that our formulations are equivalent to the definition in the work of Cloteaux, LaMar, Moseman, and Shook in which the focus is on the degree sequence, and present a new characterization theorem for threshold digraphs.We then develop the notion of a random threshold digraph formed by choosing vertex weights independently and uniformly at random from $[0,1]$. We show that this notion of a random threshold digraph is equivalent to a purely combinatorial approach, and present a formula for the probability of a digraph based on counting linear extensions of an auxiliary partially ordered set.We capitalize on this equivalence to develop exact and asymptotic properties of random threshold digraphs such as the number of vertices with in-degree (or out-degree) equal to zero, domination number, connectivity and strong connectivity, clique and independence number, and chromatic number.
On-line Ramsey Numbers of Paths and Cycles
Authors: Cyman Joanna , Dzido Tomasz , Lapinskas John , Lo Allan
Published: January 2020

Consider a game played on the edge set of the infinite clique by two players, Builder and Painter. In each round, Builder chooses an edge and Painter colours it red or blue. Builder wins by creating either a red copy of $G$ or a blue copy of $H$ for some fixed graphs $G$ and $H$. The minimum number of rounds within which Builder can win, assuming both players play perfectly, is the on-line Ramsey number $\tilde{r}(G,H)$. In this paper, we consider the case where $G$ is a path $P_k$. We prove that $\tilde{r}(P_3,P_{\ell+1}) = \lceil 5\ell/4\rceil = \tilde{r}(P_3,C_{\ell})$ for all $\ell \ge 5$, and determine $\tilde{r}(P_4,P_{\ell+1})$ up to an additive constant for all $\ell \ge 3$. We also prove some general lower bounds for on-line Ramsey numbers of the form $\tilde{r}(P_{k+1},H)$.
Lines in Higgledy-Piggledy Arrangement
Authors: Fancsali Szabolcs L. , Sziklai Péter
Published: January 2020

In this article, we examine sets of lines in $\mathsf{PG}(d,\mathbb{F})$ meeting each hyperplane in a generator set of points. We prove that such a set has to contain at least $\lfloor1.5d\rfloor$ lines if the field $\mathbb{F}$ has at least $\lfloor1.5d\rfloor$ elements, and at least $2d-1$ lines if the field $\mathbb{F}$ is algebraically closed. We show that suitable $2d-1$ lines constitute such a set (if $|\mathbb{F}|\ge2d-1$), proving that the lower bound is tight over algebraically closed fields. At last, we will see that the strong $(s,A)$ subspace designs constructed by Guruswami and Kopparty have better (smaller) parameter $A$ than one would think at first sight.
On Tours that contain all Edges of a Hypergraph
Authors: Lonc Zbigniew , Naroski Paweł
Published: January 2020

Let $H$ be a $k$-uniform hypergraph, $k\geqslant 2$. By an Euler tour in $H$ we mean an alternating sequence $v_0,e_1,v_1,e_2,v_2,\ldots,v_{m-1},e_m,v_m=v_0$ of vertices and edges in $H$ such that each edge of $H$ appears in this sequence exactly once and $v_{i-1},v_i\in e_i$, $v_{i-1}\neq v_i$, for every $i=1,2,\ldots,m$. This is an obvious generalization of the graph theoretic concept of an Euler tour. A straightforward necessary condition for existence of an Euler tour in a $k$-uniform hypergraph is $|V_{odd}(H)|\leqslant (k-2)|E(H)|$, where $V_{odd}(H)$ is the set of vertices of odd degrees in $H$ and $E(H)$ is the set of edges in $H$. In this paper we show that this condition is also sufficient for hypergraphs of a broad class of $k$-uniform hypergraphs, that we call strongly connected hypergraphs. This result reduces to the Euler theorem on existence of Euler tours, when $k=2$, i.e. for graphs, and is quite simple to prove for $k>3$. Therefore, we concentrate on the most interesting case of $k=3$. In this case we further consider the problem of existence of an Euler tour in a certain class of $3$-uniform hypergraphs containing the class of strongly connected hypergraphs as a proper subclass. For hypergraphs in this class we give a sufficient condition for existence of an Euler tour and prove intractability (NP-completeness) of the problem in this class in general.
Young Diagrams and Intersection Numbers for Toric Manifolds associated with Weyl Chambers
Authors: Abe Hiraku
Published: January 2020

We study intersection numbers of invariant divisors in the toric manifold associated with the fan determined by the collection of Weyl chambers for each root system of classical type and of exceptional type $G_2$. We give a combinatorial formula for intersection numbers of certain subvarieties which are naturally indexed by elements of the Weyl group. These numbers describe the ring structure of the cohomology of the toric manifold.
Faster Rumor Spreading With Multiple Calls
Authors: Panagiotou Konstantinos , Pourmiri Ali , Sauerwald Thomas
Published: January 2020

We consider the random phone call model introduced by Demers et al., which is a well-studied model for information dissemination on networks. One basic protocol in this model is the so-called Push protocol which proceeds in synchronous rounds. Starting with a single node which knows of a rumor, every informed node calls in each round a random neighbor and informs it of the rumor. The Push-Pull protocol works similarly, but additionally every uninformed node calls a random neighbor and may learn the rumor from it.It is well-known that both protocols need $\Theta(\log n)$ rounds to spread a rumor on a complete network with $n$ nodes. Here we are interested in how much the spread can be speeded by enabling nodes to make more than one call in each round. We propose a new model where the number of calls of a node is chosen independently according to a probability distribution $R$. We provide both lower and upper bounds on the rumor spreading time depending on statistical properties of $R$ such as the mean or the variance (if they exist). In particular, if $R$ follows a power law distribution with exponent $\beta \in (2,3)$, we show that the Push-Pull protocol spreads a rumor in $\Theta(\log \log n)$ rounds. Moreover when $\beta=3$, the Push-Pull protocol spreads a rumor in $\Theta(\frac{ \log n}{\log\log n})$ rounds.
Polygons as Sections of Higher-Dimensional Polytopes
Authors: Padrol Arnau , Pfeifle Julian
Published: January 2020

We show that every heptagon is a section of a $3$-polytope with $6$ vertices. This implies that every $n$-gon with $n\geq 7$ can be obtained as a section of a $(2+\lfloor\frac{n}{7}\rfloor)$-dimensional polytope with at most $\lceil\frac{6n}{7}\rceil$ vertices; and provides a geometric proof of the fact that every nonnegative $n\times m$ matrix of rank $3$ has nonnegative rank not larger than $\lceil\frac{6\min(n,m)}{7}\rceil$. This result has been independently proved, algebraically, by Shitov (J. Combin. Theory Ser. A 122, 2014).
Energies and Structure of Additive Sets
Authors: Ilya Shkredov
Published: January 2020

In this paper we prove that any sumset or difference set has large $\textsf{E}_3$ energy. Also, we give a full description of families of sets having critical relations between some kind of energies such as $\textsf{E}_k$, $\textsf{T}_k$ and Gowers norms. In particular, we give criteria for a set to be a set of the form $H\dotplus \Lambda$, where $H+H$ is small and $\Lambda$ has "random structure",set equal to a disjoint union of sets $H_j$ each with small doubling,set having a large subset $A'$ with $2A'$ equal to a set with small doubling and $|A'+A'| \approx |A|^4 / \textsf{E}(A)$.