bluuebunny/crossref_metadata_2025 huggingface dataset:
Constructions of Bipartite and Bipartite-regular Hypermaps
Authors: Duarte Rui
Published: January 2020

A hypermap is bipartite if its set of flags can be divided into two parts A and B so that both A and B are the union of vertices, and consecutive vertices around an edge or a face are contained in alternate parts. A bipartite hypermap is bipartite-regular if its set of automorphisms is transitive on A and on B.In this paper we see some properties of the constructions of bipartite hypermaps described algebraically by Breda and Duarte in 2007 which generalize the construction induced by the Walsh representation of hypermaps. As an application we show that all surfaces have bipartite-regular hypermaps.
Large Bounded Degree Trees in Expanding Graphs
Authors: Balogh József , Csaba Béla , Pei Martin , Samotij Wojciech
Published: January 2020

A remarkable result of Friedman and Pippenger gives a sufficient condition on the expansion properties of a graph to contain all small trees with bounded maximum degree. Haxell showed that under slightly stronger assumptions on the expansion rate, their technique allows one to find arbitrarily large trees with bounded maximum degree. Using a slightly weaker version of Haxell's result we prove that a certain family of expanding graphs, which includes very sparse random graphs and regular graphs with large enough spectral gap, contains all almost spanning bounded degree trees. This improves two recent tree-embedding results of Alon, Krivelevich and Sudakov.
The Evolution of Uniform Random Planar Graphs
Authors: Dowden Chris
Published: January 2020

Let $P_{n,m}$ denote the graph taken uniformly at random from the set of all planar graphs on $\{1,2, \ldots, n \}$ with exactly $m(n)$ edges. We use counting arguments to investigate the probability that $P_{n,m}$ will contain given components and subgraphs, finding that there is different asymptotic behaviour depending on the ratio ${m\over n}$.
A Bijection Proving the Aztec Diamond Theorem by Combing Lattice Paths
Authors: Bosio Frédéric , Van Leeuwen Marc A. A.
Published: January 2020

We give a bijective proof of the Aztec diamond theorem, stating that there are $2^{n(n+1)/2}$ domino tilings of the Aztec diamond of order $n$. The proof in fact establishes a similar result for non-intersecting families of $n+1$ Schröder paths, with horizontal, diagonal or vertical steps, linking the grid points of two adjacent sides of an $n\times n$ square grid; these families are well known to be in bijection with tilings of the Aztec diamond. Our bijection is produced by an invertible "combing'' algorithm, operating on families of paths without non-intersection condition, but instead with the requirement that any vertical steps come at the end of a path, and which are clearly $2^{n(n+1)/2}$ in number; it transforms them into non-intersecting families.
Beyond Sum-Free Sets in the Natural Numbers
Authors: Huczynska Sophie
Published: January 2020

For an interval $[1,N] \subseteq \mathbb{N}$, sets $S \subseteq [1,N]$ with the property that $|\{(x,y) \in S^2:x+y \in S\}|=0$, known as sum-free sets, have attracted considerable attention.  In this paper, we generalize this notion by considering $r(S)=|\{(x,y) \in S^2: x+y \in S\}|$, and analyze its behaviour as $S$ ranges over the subsets of $[1,N]$.  We obtain a comprehensive description of the spectrum of attainable $r$-values, constructive existence results and structural characterizations for sets attaining extremal and near-extremal values.
Edge Regular Graph Products
Authors: Frelih Boštjan , Miklavič Štefko
Published: January 2020

A regular nonempty graph $\Gamma$ is called edge regular, whenever there exists a nonegative integer $\lambda_{\Gamma}$, such that any two adjacent vertices of $\Gamma$ have precisely $\lambda_{\Gamma}$ common neighbours. An edge regular graph $\Gamma$ with at least one pair of vertices at distance 2 is called amply regular, whenever there exists a nonegative integer $\mu_{\Gamma}$, such that any two vertices at distance 2 have precisely $\mu_{\Gamma}$ common neighbours. In this paper we classify edge regular graphs, which can be obtained as a strong product, or a lexicographic product, or a deleted lexicographic product, or a co-normal product of two graphs. As a corollary we determine which of these graphs are amply regular.
The Biased Odd Cycle Game
Authors: Ferber Asaf , Glebov Roman , Krivelevich Michael , Liu Hong , Palmer Cory , Valla Tomas , Vizer Máté
Published: January 2020

In this paper we consider biased Maker-Breaker games played on the edge set of a given graph $G$. We prove that for every $\delta>0$ and large enough $n$, there exists a constant $k$ for which if $\delta(G)\geq \delta n$ and $\chi(G)\geq k$, then Maker can build an odd cycle in the $(1:b)$ game for $b=O\left(\frac{n}{\log^2 n}\right)$. We also consider the analogous game where Maker and Breaker claim vertices instead of edges. This is a special case of the following well known and notoriously difficult problem due to Duffus, Łuczak and Rödl: is it true that for any positive constants $t$ and $b$, there exists an integer $k$ such that for every graph $G$, if $\chi(G)\geq k$, then Maker can build a graph which is not $t$-colorable, in the $(1:b)$ Maker-Breaker game played on the vertices of $G$?
The Planarity Theorems of MacLane and Whitney for Graph-like Continua
Authors: Christian Robin , Richter R. Bruce , Rooney Brendan
Published: January 2020

The planarity theorems of MacLane and Whitney are extended to compact graph-like spaces. This generalizes recent results of Bruhn and Stein (MacLane's Theorem for the Freudenthal compactification of a locally finite graph) and of Bruhn and Diestel (Whitney's Theorem for an identification space obtained from a graph in which no two vertices are joined by infinitely many edge-disjoint paths).
An Inductive Approach to Constructing Universal Cycles on the k-Subsets of [n]
Authors: Rudoy Yevgeniy
Published: January 2020

In this paper, we introduce a method of constructing Universal Cycles on sets by taking "sums" and "products" of smaller cycles. We demonstrate this new approach by proving that if there exist Universal Cycles on the 4-subsets of [18] and the 4-subsets of [26], then for any integer $n\ge18$ equivalent to $2 \pmod{8}$, there exists a Universal Cycle on the 4-subsets of [n].
Pattern Hypergraphs
Authors: Dvořák Zdeněk , Kára Jan , Král' Daniel , Pangrác Ondřej
Published: January 2020

The notion of pattern hypergraph provides a unified view of several previously studied coloring concepts. A pattern hypergraph $H$ is a hypergraph where each edge is assigned a type $\Pi_i$ that determines which of possible colorings of the edge are proper. A vertex coloring of $H$ is proper if it is proper for every edge. In general, the set of integers $k$ such that $H$ can be properly colored with exactly $k$ colors need not be an interval. We find a simple sufficient and necessary condition on the edge types $\Pi_1,\ldots,\Pi_\lambda$ for the existence of a pattern hypergraph $H$ with edges of types $\Pi_1,\ldots,\Pi_\lambda$ such that the numbers of colors in proper colorings of $H$ do not form an interval of integers.
Residue Reduced Form of a Rational Function as an Iterated Laurent Series
Authors: Ce Xin Guo , Yue Zhou
Published: January 2020

Lipshitz showed that the diagonal of a D-finite power series is still D-finite, but his proof seems hard to implement. This paper may be regarded as the first step towards an efficient algorithm realizing Lipshitz's theory. We show that the idea of a reduced form may be a big saving for computing the D-finite functional equation. For the residue in one variable of a rational function, we develop an algorithm for computing its minimal algebraic functional equation.
Distinguishing Number of Countable Homogeneous Relational Structures
Authors: Laflamme C. , Van Thé L. Nguyen , Sauer N.
Published: January 2020

The distinguishing number of a graph $G$ is the smallest positive integer $r$ such that $G$ has a labeling of its vertices with $r$ labels for which there is no non-trivial automorphism of $G$ preserving these labels. In early work, Michael Albertson and Karen Collins computed the distinguishing number for various finite graphs, and more recently Wilfried Imrich, Sandi Klavžar and Vladimir Trofimov computed the distinguishing number of some infinite graphs, showing in particular that the Random Graph has distinguishing number 2. We compute the distinguishing number of various other finite and countable homogeneous structures, including undirected and directed graphs, and posets. We show that this number is in most cases two or infinite, and besides a few exceptions conjecture that this is so for all primitive homogeneous countable structures.
A Bound on Permutation Codes
Authors: Bierbrauer Jürgen , Metsch Klaus
Published: January 2020

Consider the symmetric group $S_n$ with the Hamming metric. A  permutation code on $n$ symbols is a subset $C\subseteq S_n.$ If $C$ has minimum distance $\geq n-1,$ then $\vert C\vert\leq n^2-n.$ Equality can be reached if and only if a projective plane of order $n$ exists. Call $C$ embeddable if it is contained in a permutation code of minimum distance $n-1$ and cardinality $n^2-n.$ Let $\delta =\delta (C)=n^2-n-\vert C\vert$ be the deficiency of the permutation code $C\subseteq S_n$ of minimum distance $\geq n-1.$We prove that $C$ is embeddable if either $\delta\leq 2$ or if $(\delta^2-1)(\delta +1)^2<27(n+2)/16.$ The main part of the proof is an adaptation of the method used to obtain the famous Bruck completion theorem for mutually orthogonal latin squares.
Promotion Operator on Rigged Configurations of Type $A$
Authors: Schilling Anne , Wang Qiang
Published: January 2020

In an earlier paper of the first author, the analogue of the promotion operator on crystals of type $A$ under a generalization of the bijection of Kerov, Kirillov and Reshetikhin between crystals (or Littlewood–Richardson tableaux) and rigged configurations was proposed. In this paper, we give a proof of this conjecture. This shows in particular that the bijection between tensor products of type $A_n^{(1)}$ crystals and (unrestricted) rigged configurations is an affine crystal isomorphism.
Identifying Codes of Lexicographic Product of Graphs
Authors: Feng Min , Xu Min , Wang Kaishun
Published: January 2020

Let $G$ be a connected graph and $H$ be an arbitrary graph. In this paper, we study the identifying codes of the lexicographic product $G[H]$ of $G$ and $H$. We first introduce two parameters of $H$, which are closely related to identifying codes of $H$. Then we provide the sufficient and necessary condition for $G[H]$ to be identifiable. Finally, if $G[H]$ is identifiable, we determine the minimum cardinality of identifying codes of $G[H]$ in terms of the order of $G$ and these two parameters of $H$.
On Randomly Generated Non-Trivially Intersecting Hypergraphs
Authors: Patkós Balázs
Published: January 2020

We propose two procedures to choose members of ${[n] \choose r}$ sequentially at random to form a non-trivially intersecting hypergraph. In both cases we show what is the limiting probability that if $r=c_nn^{1/3}$ with $c_n \rightarrow c$, then the process results in a Hilton-Milner-type hypergraph.
On the Directed Oberwolfach Problem with Equal Cycle Lengths
Authors: Burgess Andrea , Šajna Mateja
Published: January 2020

We examine the necessary and sufficient conditions for a complete symmetric digraph $K_n^\ast$ to admit a resolvable decomposition into directed cycles of length $m$. We give a complete solution for even $m$, and a partial solution for odd $m$.
Generating Functions for Permutations which Contain a Given Descent Set
Authors: Remmel Jeffrey , Riehl Manda
Published: January 2020

A large number of generating functions for permutation statistics can be obtained by applying homomorphisms to simple symmetric function identities. In particular, a large number of generating functions involving the number of descents of a permutation $\sigma$, $des(\sigma)$, arise in this way. For any given finite set $S$ of positive integers, we develop a method to produce similar generating functions for the set of permutations of the symmetric group $S_n$ whose descent set contains $S$. Our method will be to apply certain homomorphisms to symmetric function identities involving ribbon Schur functions.
Maximum Planar Subgraphs in Dense Graphs
Authors: Allen Peter , Skokan Jozef , Würfl Andreas
Published: January 2020

Kühn, Osthus and Taraz showed that for each $\gamma>0$ there exists $C$ such that any $n$-vertex graph with minimum degree $\gamma n$ contains a planar subgraph with at least $2n-C$ edges. We find the optimum value of $C$ for all $\gamma< 1/2$ and sufficiently large $n$.
Enumeration of Generalized $BCI$ Lambda-terms
Authors: Bodini Olivier , Gardy Danièle , Gittenberger Bernhard , Jacquot Alice
Published: January 2020

We investigate the asymptotic number of elements of size $n$ in a particular class of closed lambda-terms (so-called $BCI(p)$-terms) which are related to axiom systems of combinatory logic. By deriving a differential equation for the generating function of the counting sequence we obtain a recurrence relation which can be solved asymptotically. We derive differential equations for the generating functions of the counting sequences of other more general classes of terms as well: the class of $BCK(p)$-terms and that of closed lambda-terms. Using elementary arguments we obtain upper and lower estimates for the number of closed lambda-terms of size $n$. Moreover, a recurrence relation is derived which allows an efficient computation of the counting sequence. $BCK(p)$-terms are discussed briefly.
The Distinguishing Chromatic Number of Kneser Graphs
Authors: Che Zhongyuan , Collins Karen L.
Published: January 2020

A labeling $f: V(G) \rightarrow \{1, 2, \ldots, d\}$ of the vertex set of a graph $G$ is said to be proper $d$-distinguishing if it is a proper coloring of $G$ and any nontrivial automorphism of $G$ maps at least one vertex to a vertex with a different label. The distinguishing chromatic number of $G$, denoted by $\chi_D(G)$, is the minimum $d$ such that $G$ has a proper $d$-distinguishing labeling. Let $\chi(G)$ be the chromatic number of $G$ and $D(G)$ be the distinguishing number of $G$. Clearly, $\chi_D(G) \ge \chi(G)$ and $\chi_D(G) \ge D(G)$. Collins, Hovey and Trenk have given a tight upper bound on $\chi_D(G)-\chi(G)$ in terms of the order of the automorphism group of $G$, improved when the automorphism group of $G$ is a finite abelian group. The Kneser graph $K(n,r)$ is a graph whose vertices are the $r$-subsets of an $n$ element set, and two vertices of $K(n,r)$ are adjacent if their corresponding two $r$-subsets are disjoint. In this paper, we provide a class of graphs $G$, namely Kneser graphs $K(n,r)$, whose automorphism group is the symmetric group, $S_n$, such that $\chi_D(G) - \chi(G) \le 1$. In particular, we prove that $\chi_D(K(n,2))=\chi(K(n,2))+1$ for $n\ge 5$. In addition, we show that $\chi_D(K(n,r))=\chi(K(n,r))$ for $n \ge 2r+1$ and $r\ge 3$.
$B_h$ Sequences in Higher Dimensions
Authors: Rackham Laurence , Šarka Paulius
Published: January 2020

In this article we look at the well-studied upper bounds for $|A|$, where $A\subset{\Bbb N}$ is a $B_h$ sequence, and generalise these to the case where $A\subset{\Bbb N}^d$. In particular we give $d$-dimensional analogues to results of Chen, Jia, Graham and Green.
Toward a Graph Version of Rado's Theorem
Authors: Parrish Andy
Published: January 2020

An equation is called graph-regular if it always has monochromatic solutions under edge-colorings of $K_{\mathbb{N}}$. We present two Rado-like conditions which are respectively necessary and sufficient for an equation to be graph-regular.
Combinatorial vs. Algebraic Characterizations of Completely Pseudo-Regular Codes
Authors: Cámara M. , Fàbrega J. , Fiol M. A. , Garriga E.
Published: January 2020

Given a simple connected graph $\Gamma$ and a subset of its vertices $C$, the pseudo-distance-regularity around $C$ generalizes, for not necessarily regular graphs, the notion of completely regular code. We then say that $C$ is a completely pseudo-regular code. Up to now, most of the characterizations of pseudo-distance-regularity has been derived from a combinatorial definition. In this paper we propose an algebraic (Terwilliger-like) approach to this notion, showing its equivalence with the combinatorial one. This allows us to give new proofs of known results, and also to obtain new characterizations which do not depend on the so-called $C$-spectrum of $\Gamma$, but only on the positive eigenvector of its adjacency matrix. Along the way, we also obtain some new results relating the local spectra of a vertex set and its antipodal. As a consequence of our study, we obtain a new characterization of a completely regular code $C$, in terms of the number of walks in $\Gamma$ with an endvertex in $C$.
Avoider-Forcer Games on Hypergraphs with Small Rank
Authors: Bednarska-Bzdęga Małgorzata
Published: January 2020

We study biased $(a:f)$ Avoider-Forcer games played on hypergraphs, in the strict and monotone versions.  We give a sufficient condition for Avoider's win, useful  in the case of games on hypergraphs whose rank is smaller than $f$.  We apply this result to estimate the threshold bias in Avoider-Forcer $(1:f)$ games in which Avoider is trying not to build a copy of a fixed graph $G$ in $K_n$. We also study the $d$-degree $(1:f)$ game in which  Avoider's aim is to avoid a spanning subgraph of the minimal degree at least $d$ in $K_n$. We show that the strict 1-degree game has the threshold which is the same as the threshold of the Avoider-Forcer connectivity game.
On the Rank of $p$-Schemes
Authors: Raei Barandagh Fateme , Rahnamai Barghi Amir
Published: January 2020

Let $n>1$ be an integer and $p$ be a prime number. Denote by $\mathfrak{C}_{p^n}$ the class of non-thin association $p$-schemes of degree $p^n$. A sharp upper and lower bounds on the rank of schemes in $\mathfrak{C}_{p^n}$ with a certain order of thin radical are obtained. Moreover, all schemes in this class whose rank are equal to the lower bound are characterized and some schemes in this class whose rank are equal to the upper bound are constructed. Finally, it is shown that the scheme with minimum rank in $\mathfrak{C}_{p^n}$ is unique up to isomorphism, and it is a fusion of any association $p$-schemes with degree $p^n$.
Optimization Problems over Unit-Distance Representations of Graphs
Authors: De Carli Silva Marcel Kenji , Tunçel Levent
Published: January 2020

We study the relationship between unit-distance representations and the Lovász theta number of graphs, originally established by Lovász. We derive and prove min-max theorems. This framework allows us to derive a weighted version of the hypersphere number of a graph and a related min-max theorem. Then, we connect to sandwich theorems via graph homomorphisms. We present and study a generalization of the hypersphere number of a graph and the related optimization problems. The generalized problem involves finding the smallest ellipsoid of a given shape which contains a unit-distance representation of the graph. Arbitrary positive semidefinite forms describing the ellipsoids yield NP-hard problems.
A Family of Half-Transitive Graphs
Authors: Chen Jing , Li Cai Heng , Seress Ákos
Published: January 2020

We construct an infinite family of half-transitive graphs, which contains infinitely many Cayley graphs, and infinitely many non-Cayley graphs.
On the Turán Number of Forests
Authors: Liu Hong , Lidicky Bernard , Palmer Cory
Published: January 2020

The Turán number of a graph $H$, $\mathrm{ex}(n,H)$, is the maximum number of edges in a graph on $n$ vertices which does not have $H$ as a subgraph. We determine the Turán number and find the unique extremal graph for forests consisting of paths when $n$ is sufficiently large. This generalizes a result of Bushaw and Kettle [Combinatorics, Probability and Computing 20:837--853, 2011]. We also determine the Turán number and extremal graphs for forests consisting of stars of arbitrary order.
Integral Circulant Ramanujan Graphs of Prime Power Order
Authors: Le T. A. , Sander J. W.
Published: January 2020

A connected $\rho$-regular graph $G$ has largest eigenvalue $\rho$ in modulus. $G$ is called Ramanujan if it has at least $3$ vertices and the second largest modulus of its eigenvalues is at most $2\sqrt{\rho-1}$. In 2010 Droll classified all Ramanujan unitary Cayley graphs. These graphs of type ${\rm ICG}(n,\{1\})$ form a subset of the class of integral circulant graphs ${\rm ICG}(n,{\cal D})$, which can be characterised by their order $n$ and a set $\cal D$ of positive divisors of $n$ in such a way that they have vertex set $\mathbb{Z}/n\mathbb{Z}$ and edge set $\{(a,b):\, a,b\in\mathbb{Z}/n\mathbb{Z} ,\, \gcd(a-b,n)\in {\cal D}\}$. We extend Droll's result by drawing up a complete list of all graphs ${\rm ICG}(p^s,{\cal D})$ having the Ramanujan property for each prime power $p^s$ and arbitrary divisor set ${\cal D}$.
On Perfect Packings in Dense Graphs
Authors: Balogh József , Kostochka Alexandr , Treglown Andrew
Published: January 2020

We say that a graph $G$ has a perfect $H$-packing if there exists a set of vertex-disjoint copies of $H$ which cover all the vertices in $G$. We consider various problems concerning perfect $H$-packings: Given $n, r , D \in \mathbb N$, we characterise the edge density threshold that ensures a perfect $K_r$-packing in any graph $G$ on $n$ vertices and with minimum degree $\delta (G) \geq D$. We also give two conjectures concerning degree sequence conditions which force a graph to contain a perfect $H$-packing. Other related embedding problems are also considered. Indeed, we give a structural result concerning $K_r$-free graphs that satisfy a certain degree sequence condition.
Symmetry Breaking in Tournaments
Authors: Lozano Antoni
Published: January 2020

We provide upper bounds for the determining number and the metric dimension of tournaments. A set of vertices $S \subseteq V(T)$ is a determining set for a tournament $T$ if every nontrivial automorphism of $T$ moves at least one vertex of $S$, while $S$ is a resolving set for $T$ if every two distinct vertices in $T$ have different distances to some vertex in $S$. We show that the minimum size of a determining set for an order $n$ tournament (its determining number) is bounded by $\lfloor n/3 \rfloor$, while the minimum size of a resolving set for an order $n$ strong tournament (its metric dimension) is bounded by $\lfloor n/2 \rfloor$. Both bounds are optimal.
Positively Curved Combinatorial 3-Manifolds
Authors: Trout Aaron
Published: January 2020

We present two theorems in the "discrete differential geometry" of positively curved spaces. The first is a combinatorial analog of the Bonnet-Myers theorem: $\bullet$ A combinatorial 3-manifold whose edges have degree at most five has edge-diameter at most five. When all edges have unit length, this degree bound is equivalent to an angle-deficit along each edge. It is for this reason we call such spaces positively curved. Our second main result is analogous to the sphere theorems of Toponogov and Cheng: $\bullet$ A positively curved 3-manifold, as above, in which vertices $v$ and $w$ have edge-distance five is a sphere whose triangulation is completely determined by the structure of $Lk(v)$ or $Lk(w)$. In fact, we provide a procedure for constructing a maximum diameter sphere from a suitable $Lk(v)$ or $Lk(w)$. The compactness of these spaces (without an explicit diameter bound) was first proved via analytic arguments in a 1973 paper by David Stone. Our proof is completely combinatorial, provides sharp bounds, and follows closely the proof strategy for the classical results.
On the Shannon Capacity of Triangular Graphs
Authors: Kizhakkepallathu Ashik Mathew , Östergård Patric RJ , Popa Alexandru
Published: January 2020

The Shannon capacity of a graph $G$ is $c(G)=\sup_{d\geq 1}(\alpha(G^d))^{\frac{1}{d}},$ where $\alpha(G)$ is the independence number of $G$. The Shannon capacity of the Kneser graph $\mathrm{KG}_{n,r}$ was determined by Lovász in 1979, but little is known about the Shannon capacity of the complement of that graph when $r$ does not divide $n$. The complement of the Kneser graph, $\overline{\mathrm{KG}}_{n,2}$, is also called the triangular graph $T_n$. The graph $T_n$ has the $n$-cycle $C_n$ as an induced subgraph, whereby $c(T_n) \geq c(C_n)$, and these two families of graphs are closely related in the current context as both can be considered via geometric packings of the discrete $d$-dimensional torus of width $n$ using two types of $d$-dimensional cubes of width $2$. Bounds on $c(T_n)$ obtained in this work include $c(T_7) \geq \sqrt[3]{35} \approx 3.271$, $c(T_{13}) \geq \sqrt[3]{248} \approx 6.283$, $c(T_{15}) \geq \sqrt[4]{2802} \approx 7.276$, and $c(T_{21}) \geq \sqrt[4]{11441} \approx 10.342$.
Forbidden Configurations: Exact Bounds Determined by Critical Substructures
Authors: Anstee R. P. , Karp S. N.
Published: January 2020

We consider the following extremal set theory problem. Define a matrix to be simple if it is a (0,1)-matrix with no repeated columns. An $m$-rowed simple matrix corresponds to a family of subsets of $\{1,2,\ldots ,m\}$. Let $m$ be a given integer and $F$ be a given (0,1)-matrix (not necessarily simple). We say a matrix $A$ has $F$ as a configuration if a submatrix of $A$ is a row and column permutation of $F$. We define $\hbox{forb}(m,F)$ as the maximum number of columns that a simple $m$-rowed matrix $A$ can have subject to the condition that $A$ has no configuration $F$. We compute exact values for $\hbox{forb}(m,F)$ for some choices of $F$ and in doing so handle all $3\times 3$ and some $k\times 2$ (0,1)-matrices $F$. Often $\hbox{forb}(m,F)$ is determined by $\hbox{forb}(m,F')$ for some configuration $F'$ contained in $F$ and in that situation, with $F'$ being minimal, we call $F'$ a critical substructure.
Note on Upper Density of Quasi-Random Hypergraphs
Authors: Bhat Vindya , Rödl Vojtěch
Published: January 2020

In 1964, Erdős proved that for any $\alpha > 0$, an $l$-uniform hypergraph $G$ with $n \geq n_0(\alpha, l)$ vertices and $\alpha \binom{n}{l}$ edges contains a large complete $l$-equipartite subgraph. This implies that any sufficiently large $G$ with density $\alpha > 0$ contains a large subgraph with density at least $l!/l^l$.In this note we study a similar problem for $l$-uniform hypergraphs $Q$ with a weak quasi-random property (i.e. with edges uniformly distributed over the sufficiently large subsets of vertices). We prove that any sufficiently large quasi-random $l$-uniform hypergraph $Q$ with density $\alpha > 0$ contains a large subgraph with density at least $\frac{(l-1)!}{l^{l-1}-1}$. In particular, for $l=3$, any sufficiently large such $Q$ contains a large subgraph with density at least $\frac{1}{4}$ which is the best possible lower bound.We define jumps for quasi-random sequences of $l$-graphs and our result implies that every number between 0 and $\frac{(l-1)!}{l^{l-1}-1}$ is a jump for quasi-random $l$-graphs. For $l=3$ this interval can be improved based on a recent result of Glebov, Král' and Volec. We prove that every number between [0, 0.3192) is a jump for quasi-random $3$-graphs.
Direct Bijective Computation of the Generating Series for 2 and 3-Connection Coefficients of the Symmetric Group
Authors: Morales Alejandro H. , Vassilieva Ekaterina A.
Published: January 2020

We evaluate combinatorially certain connection coefficients of the symmetric group that count the number of factorizations of a long cycle as a product of three permutations. Such factorizations admit an important topological interpretation in terms of unicellular constellations on orientable surfaces. Algebraic computation of these coefficients was first done by Jackson using irreducible characters of the symmetric group. However, bijective computations of these coefficients are so far limited to very special cases. Thanks to a new bijection that refines the work of Schaeffer and Vassilieva, we give an explicit closed form evaluation of the generating series for these coefficients. The main ingredient in the bijection is a modified oriented tricolored tree tractable to enumerate. Finally, reducing this bijection to factorizations of a long cycle into two permutations, we get the analogue formula for the corresponding generating series.
The Size of Edge-critical Uniquely 3-Colorable Planar Graphs
Authors: Matsumoto Naoki
Published: January 2020

A graph $G$ is uniquely $k$-colorable if the chromatic number of $G$ is $k$ and $G$ has only one $k$-coloring up to permutation of the colors. A uniquely $k$-colorable graph $G$ is edge-critical if $G-e$ is not a uniquely $k$-colorable graph for any edge $e\in E(G)$. In this paper, we prove that if $G$ is an edge-critical uniquely $3$-colorable planar graph, then $|E(G)|\leq \frac{8}{3}|V(G)|-\frac{17}{3}$. On the other hand, there exists an infinite family of edge-critical uniquely 3-colorable planar graphs with $n$ vertices and $\frac{9}{4}n-6$ edges. Our result gives a first non-trivial upper bound for $|E(G)|$.
Enumeration of Alternating Sign Matrices of Even Size (Quasi-)Invariant under a Quarter-Turn Rotation
Authors: Aval Jean-Christophe , Duchon Philippe
Published: January 2020

The aim of this work is to enumerate alternating sign matrices (ASM) that are quasi-invariant under a quarter-turn. The enumeration formula (conjectured by Duchon) involves, as a product of three terms, the number of unrestricted ASM's and the number of half-turn symmetric ASM's.
Ascent Sequences and Upper Triangular Matrices Containing Non-Negative Integers
Authors: Dukes Mark , Parviainen Robert
Published: January 2020

This paper presents a bijection between ascent sequences and upper triangular matrices whose non-negative entries are such that all rows and columns contain at least one non-zero entry. We show the equivalence of several natural statistics on these structures under this bijection and prove that some of these statistics are equidistributed. Several special classes of matrices are shown to have simple formulations in terms of ascent sequences. Binary matrices are shown to correspond to ascent sequences with no two adjacent entries the same. Bidiagonal matrices are shown to be related to order-consecutive set partitions and a simple condition on the ascent sequences generate this class.
Characterizations of Regularity for certain $Q$-Polynomial Association Schemes
Authors: Suda Sho
Published: January 2020

It was shown that linked systems of symmetric designs with $a_1^*=0$ and mutually unbiased bases (MUBs) are triply regular association schemes. In this paper, we characterize triple regularity of linked systems of symmetric designs by its Krein number. And we prove that a maximal set of MUBs carries a quadruply regular association scheme and characterize the quadruple regularity of MUBs by its parameter.
Sparse Distance Sets in the Triangular Lattice
Authors: Ahmed Tanbir , Snevily Hunter
Published: January 2020

A planar point-set $X$ in Euclidean plane is called a $k$-distance set if there are exactly $k$ different distances among the points in $X$. The function $g(k)$ denotes the maximum number of points in the Euclidean plane that is a $k$-distance set. In 1996, Erdős and Fishburn conjectured that for $k\geq 7$, every $g(k)$-point subset of the plane that determines $k$ different distances is similar to a subset of the triangular lattice. We believe that if $g(k)$ is an increasing function of $k$, then the conjecture is false. We present data that supports our claim and a method of construction that unifies known optimal point configurations for $k\geq 3$.
Vanishing of Doubly Symmetrized Tensors
Authors: Berget Andrew , Dias da Silva J. A. , Fonseca Amélia
Published: January 2020

Symmetrizations of tensors by irreducible characters of the symmetric group serve as natural analogues of symmetric and skew-symmetric tensors. The question of when a symmetrized decomposable tensor is non-zero is intimately related to the rank partition of a matroid extracted from the tensor. In this paper we characterize the non-vanishing of the symmetrization of certain partially symmetrized decomposable tensors. Our answers are phrased in terms of rank partitions of matroids.
On Sumsets of Multisets in $\mathbb{Z}_p^m$
Authors: Matomäki Kaisa
Published: January 2020

For a sequence $A$ of given length $n$ contained in $\mathbb{Z}_p^2$ we study how many distinct subsums $A$ must have when $A$ is not "wasteful" by containing too many elements in same subgroup. Martin, Peilloux and Wong have made a conjecture for a sharp lower bound and established it when $n$ is not too large whereas Peng has previously established the conjecture for large $n$. In this note we build on these earlier works and add an elementary argument leading to the conjecture for every $n$.Martin, Peilloux and Wong also made a more general conjecture for sequences in $\mathbb{Z}_p^m$. Here we show that the special case $n = mp-1$ of this conjecture implies the whole conjecture and that the conjecture is equivalent to a strong version of the additive basis conjecture of Jaeger, Linial, Payan and Tarsi.
Random Walks on Quasirandom Graphs
Authors: Barber Ben , Long Eoin
Published: January 2020

Let $G$ be a quasirandom graph on $n$ vertices, and let $W$ be a random walk on $G$ of length $\alpha n^2$. Must the set of edges traversed by $W$ form a quasirandom graph? This question was asked by Böttcher, Hladký, Piguet and Taraz. Our aim in this paper is to give a positive answer to this question. We also prove a similar result for random embeddings of trees.
On Winning Fast in Avoider-Enforcer Games
Authors: Barát János , Stojaković Miloš
Published: January 2020

We analyze the duration of the unbiased Avoider-Enforcer game for three basic positional games. All the games are played on the edges of the complete graph on $n$ vertices, and Avoider's goal is to keep his graph outerplanar, diamond-free and $k$-degenerate, respectively. It is clear that all three games are Enforcer's wins, and our main interest lies in determining the largest number of moves Avoider can play before losing. Extremal graph theory offers a general upper bound for the number of Avoider's moves. As it turns out, for all three games we manage to obtain a lower bound that is just an additive constant away from that upper bound. In particular, we exhibit a strategy for Avoider to keep his graph outerplanar for at least $2n-8$ moves, being just $6$ short of the maximum possible. A diamond-free graph can have at most $d(n)=\lceil\frac{3n-4}{2}\rceil$ edges, and we prove that Avoider can play for at least $d(n)-3$ moves. Finally, if $k$ is small compared to $n$, we show that Avoider can keep his graph $k$-degenerate for as many as $e(n)$ moves, where $e(n)$ is the maximum number of edges a $k$-degenerate graph can have.
Chains of Length 2 in Fillings of Layer Polyominoes
Authors: Phillipson Mitch , Yan Catherine H. , Yeh Jean
Published: January 2020

The symmetry of the joint distribution of the numbers of crossings and nestings of length $2$ has been observed in many  combinatorial structures, including permutations, matchings, set partitions, linked partitions, and certain families of graphs.  These results have been unified in the larger context of enumeration of northeast and southeast chains of length $2$ in $01$-fillings of moon polyominoes. In this paper  we extend this symmetry to fillings of a more general family—layer polyominoes, which are intersection-free and row-convex, but not necessarily column-convex.  Our main result is that the joint distribution of the numbers of northeast  and southeast chains of length $2$ over $01$-fillings is symmetric and invariant under an arbitrary permutation of rows.
Total Colorings of $F_5$-Free Planar Graphs with Maximum Degree 8
Authors: Chang Jian , Wu Jian-Liang , Wang Hui-Juan , Guo Zhan-Hai
Published: January 2020

The total chromatic number of a graph $G$, denoted by $\chi′′(G)$, is the minimum number of colors needed to color the vertices and edges of $G$ such that no two adjacent or incident elements get the same color. It is known that if a planar graph $G$ has maximum degree $\Delta ≥ 9$, then $\chi′′(G) = \Delta + 1$. The join $K_1 \vee P_n$ of $K_1$ and $P_n$ is called a fan graph $F_n$. In this paper, we prove that if $G$ is a $F_5$-free planar graph with maximum degree 8, then $\chi′′(G) = 9$.
Face Numbers of Centrally Symmetric Polytopes Produced from Split Graphs
Authors: Freij Ragnar , Henze Matthias , Schmitt Moritz W. , Ziegler Günter M.
Published: January 2020

We analyze a remarkable class of centrally symmetric polytopes, the Hansen polytopes of split graphs. We confirm Kalai's $3^d$ conjecture for such polytopes (they all have at least $3^d$ nonempty faces) and show that the Hanner polytopes among them (which have exactly $3^d$ nonempty faces) correspond to threshold graphs. Our study produces a new family of Hansen polytopes that have only $3^d+16$ nonempty faces.
Counting Permutations Modulo Pattern-Replacement Equivalences for Three-Letter Patterns
Authors: Kuszmaul William
Published: January 2020

We study a family of equivalence relations on $S_n$, the group of permutations on $n$ letters, created in a manner similar to that of the Knuth relation and the forgotten relation. For our purposes, two permutations are in the same equivalence class if one can be reached from the other through a series of pattern-replacements using patterns whose order permutations are in the same part of a predetermined partition of $S_c$.When the partition is of $S_3$ and has one nontrivial part and that part is of size greater than two, we provide formulas for the number of classes created in all cases left unresolved by past authros. When the partition is of $S_3$ and has two nontrivial parts, each of size two (as do the Knuth and forgotten relations), we enumerate the classes for 13 of the 14 unresolved cases. In two of these cases, enumerations arise which are the same as those yielded by the Knuth and forgotten relations. The reasons for this phenomenon are still largely a mystery.
Upper-Bounding the $k$-Colorability Threshold by Counting Covers
Authors: Coja-Oghlan Amin
Published: January 2020

Let $G(n,m)$ be the random graph on $n$ vertices with $m$ edges. Let $d=2m/n$ be its average degree. We prove that $G(n,m)$ fails to be $k$-colorable with high probability if $d>2k\ln k-\ln k-1+o_k(1)$. This matches a conjecture put forward on the basis of sophisticated but non-rigorous statistical physics ideas (Krzakala, Pagnani, Weigt: Phys. Rev. E 70 (2004)). The proof is based on applying the first moment method to the number of "covers", a physics-inspired concept. By comparison, a standard first moment over the number of $k$-colorings shows that $G(n,m)$ is not $k$-colorable with high probability if $d>2k\ln k-k$.
On the Determining Number and the Metric Dimension of Graphs
Authors: Cáceres José , Garijo Delia , Puertas María Luz , Seara Carlos
Published: January 2020

This paper initiates a study on the problem of computing the difference between the metric dimension and the determining number of graphs. We provide new proofs and results on the determining number of trees and Cartesian products of graphs, and establish some lower bounds on the difference between the two parameters.
On Divisibility of Convolutions of Central Binomial Coefficients
Authors: Sepanski Mark Roger
Published: January 2020

Recently, Z. Sun proved that \[ 2(2m+1)\binom{2m}{m} \mid  \binom{6m}{3m}\binom{3m}{m} \] for $m\in\mathbb{Z}_{>0}$. In this paper, we consider a generalization of this result by defining \[ b_{n,k}=\frac{2^{k}\, (n+2k-2)!!}{((n-2)!!\, k!}. \] In this notation, Sun's result may be expressed as $2\, (2m+1) \mid  b_{(2m+1),(2m+1)-1}$ for $m\in\mathbb{Z}_{>0}$. In this paper, we prove that  \[ 2n \mid b_{n,un\pm 2^{r}} \] for $n\in\mathbb{Z}_{>0}$ and $u,r\in\mathbb{Z}_{\geq 0}$ with  $un \pm 2^{r} > 0$. In addition, we prove a type of converse. Namely, fix $k\in\mathbb{Z}$ and $u\in \mathbb{Z}_{≥0}$ with $u>0$ if $k<0$. If \[ 2n \mid b_{n,un+k} \] for all $n\in\mathbb{Z}_{>0}$ with $un+k>0$, then there exists a unique $r \in \mathbb{Z}_{≥0}$ so that either $k=2^{r} $ or  $k=-2^{r}$.
A Decomposition Algorithm for Noncrossing Trees
Authors: Lv Lun , Pang Sabrina X.M.
Published: January 2020

Based on the classic bijective algorithm for trees due to Chen, we present a decomposition algorithm for noncrossing trees. This leads to a combinatorial interpretation of a formula on noncrossing trees of size $n$ with $k$ descents. We also derive the formula for noncrossing trees of size $n$ with $k$ descents and $i$ leaves, which is a refinement of the formula given by Flajolet and Noy. As an application of our algorithm, we answer a question proposed by Hough, which asks for a bijection between two classes of noncrossing trees with a given number of descents.
Polyiamonds and Polyhexes with Minimum Site-Perimeter and Achievement Games
Authors: Fülep Gábor , Sieben Nándor
Published: January 2020

An animal is an edge connected set of finitely many cells of a regular tiling of the plane. The site-perimeter of an animal is the number of empty cells connected to the animal by an edge. The minimum site-perimeter with a given cell size is found for animals on the triangular and hexagonal grid. The formulas are used to show the effectiveness of a simple random strategy in full set animal achievement games.
On-Line Choice Number of Complete Multipartite Graphs: an Algorithmic Approach
Authors: Chang Fei-Huang , Chen Hong-Bin , Guo Jun-Yi , Huang Yu-Pei
Published: January 2020

This paper studies the on-line choice number on complete multipartite graphs with independence number $m$. We give a unified strategy for every prescribed $m$. Our main result leads to several interesting consequences comparable to known results. (1) If $k_1-\sum_{p=2}^m\left(\frac{p^2}{2}-\frac{3p}{2}+1\right)k_p\geq 0$, where $k_p$ denotes the number of parts of cardinality $p$, then $G$ is on-line chromatic-choosable. (2) If $|V(G)|\leq\frac{m^2-m+2}{m^2-3m+4}\chi(G)$, then $G$ is on-line chromatic-choosable. (3) The on-line choice number of regular complete multipartite graphs $K_{m\star k}$ is at most$\left(m+\frac{1}{2}-\sqrt{2m-2}\right)k$ for $m\geq 3$.
A Simple Havel–Hakimi Type Algorithm to Realize Graphical Degree Sequences of Directed Graphs
Authors: Erdős Péter L. , Miklós István , Toroczkai Zoltán
Published: January 2020

One of the simplest ways to decide whether a given finite sequence of positive integers can arise as the degree sequence of a simple graph is the greedy algorithm of Havel and Hakimi. This note extends their approach to directed graphs. It also studies cases of some simple forbidden edge-sets. Finally, it proves a result which is useful to design an MCMC algorithm to find random realizations of prescribed directed degree sequences.
Cyclic Sieving for Longest Reduced Words in the Hyperoctahedral Group
Authors: Petersen T. Kyle , Serrano Luis
Published: January 2020

We show that the set $R(w_0)$ of reduced expressions for the longest element in the hyperoctahedral group exhibits the cyclic sieving phenomenon. More specifically, $R(w_0)$ possesses a natural cyclic action given by moving the first letter of a word to the end, and we show that the orbit structure of this action is encoded by the generating function for the major index on $R(w_0)$.
Combinatorial Interpretations of the Jacobi-Stirling Numbers
Authors: Gelineau Yoann , Zeng Jiang
Published: January 2020

The Jacobi-Stirling numbers of the first and second kinds were introduced in the spectral theory and are polynomial refinements of the Legendre-Stirling numbers. Andrews and Littlejohn have recently given a combinatorial interpretation for the second kind of the latter numbers. Noticing that these numbers are very similar to the classical central factorial numbers, we give combinatorial interpretations for the Jacobi-Stirling numbers of both kinds, which provide a unified treatment of the combinatorial theories for the two previous sequences and also for the Stirling numbers of both kinds.
A Hilton-Milner Theorem for Vector Spaces
Authors: Blokhuis A. , Brouwer A. E. , Chowdhury A. , Frankl P. , Mussche T. , Patkós B. , Szőnyi T.
Published: January 2020

We show for $k \geq 2$ that if $q\geq 3$ and $n \geq 2k+1$, or $q=2$ and $n \geq 2k+2$, then any intersecting family ${\cal F}$ of $k$-subspaces of an $n$-dimensional vector space over $GF(q)$ with $\bigcap_{F \in {\cal F}} F=0$ has size at most $\left[{n-1\atop k-1}\right]-q^{k(k-1)}\left[{n-k-1\atop k-1}\right]+q^k$. This bound is sharp as is shown by Hilton-Milner type families. As an application of this result, we determine the chromatic number of the corresponding $q$-Kneser graphs.
About Half Permutations
Authors: Rinaldi Simone , Socci Samanta
Published: January 2020

In 2011, Beaton et al. analytically proved that the number of directed column-convex permutominoes of size $n$ is given by $(n+1)!/2$.  In this paper, we provide a different proof of this statement using a bijective method. More precisely, we present a bijective correspondence between the class $D_n$ of directed column-convex permutominoes of size $n$ and a set of permutations (called $dcc$-permutations) of length $n+1$, which we prove to be counted by $(n+1)!/2$.  The class of $dcc$-permutations is a new class of permutations counted by half factorial numbers, and here we show some combinatorial characterizations of this class, using the concept of logical formulas determined by a permutation and the notion of mesh pattern.
Non-Existence of Point-transitive 2-(106, 6, 1) Designs
Authors: Guan Haiyan , Zhou Shenglin
Published: January 2020

Let $\mathcal{S}$ be a  linear space with 106 points,  with lines of  size 6,  and let $G$ be an automorphism group of $\mathcal{S}$.  We prove that $G$ cannot be point-transitive. In other words, there exists no point-transitive 2-(106, 6, 1) designs.
Signed Excedance Enumeration in the Hyperoctahedral group
Authors: Sivasubramanian Sivaramakrishnan
Published: January 2020

Several signed excedance-like statistics have nice formulae or generating functions when summed over the symmetric group and over its subset of derangements.  We give counterparts of some of these results when we sum over the hyperoctahedral group and its subset of derangements.  Our results motivate us to define and derive attractive bivariate formulae which generalise some of these results for the symmetric group.
Minimum-Weight Edge Discriminators in Hypergraphs
Authors: Bhattacharya Bhaswar B. , Das Sayantan , Ganguly Shirshendu
Published: January 2020

In this paper we introduce the notion of minimum-weight edge-discriminators in hypergraphs, and study their various properties. For a hypergraph $\mathcal H=(\mathcal V, \mathscr E)$, a function $\lambda: \mathcal V\rightarrow \mathbb Z^{+}\cup\{0\}$ is said to be an edge-discriminator on $\mathcal H$ if $\sum_{v\in E_i}{\lambda(v)}>0$, for all hyperedges $E_i\in \mathscr E$, and $\sum_{v\in E_i}{\lambda(v)}\ne \sum_{v\in E_j}{\lambda(v)}$, for every two distinct hyperedges $E_i, E_j \in \mathscr E$. An optimal edge-discriminator on $\mathcal H$, to be denoted by $\lambda_\mathcal H$, is an edge-discriminator on $\mathcal H$ satisfying $\sum_{v\in \mathcal V}\lambda_\mathcal H (v)=\min_\lambda\sum_{v\in \mathcal V}{\lambda(v)}$, where the minimum is taken over all edge-discriminators on $\mathcal H$.  We prove that any hypergraph $\mathcal H=(\mathcal V, \mathscr E)$,  with $|\mathscr E|=m$, satisfies $\sum_{v\in \mathcal V} \lambda_\mathcal H(v)\leq m(m+1)/2$, and the equality holds if and only if the elements of $\mathscr E$ are mutually disjoint. For $r$-uniform hypergraphs $\mathcal H=(\mathcal V, \mathscr E)$, it follows from earlier results on Sidon sequences that $\sum_{v\in \mathcal V}\lambda_{\mathcal H}(v)\leq |\mathcal V|^{r+1}+o(|\mathcal V|^{r+1})$, and the bound is attained up to a constant factor by the complete $r$-uniform hypergraph. Finally, we show that no optimal edge-discriminator on any hypergraph $\mathcal H=(\mathcal V, \mathscr E)$, with $|\mathscr E|=m~(\geq 3)$, satisfies $\sum_{v\in \mathcal V} \lambda_\mathcal H (v)=m(m+1)/2-1$. This shows that all integer values between $m$ and $m(m+1)/2$ cannot be the weight of an optimal edge-discriminator of a hypergraph, and this raises many other interesting combinatorial questions.