bluuebunny/crossref_metadata_2025 huggingface dataset:
Pairs of Disjoint $q$-element Subsets Far from Each Other
Authors: Enomoto Hikoe , Katona Gyula O. H.
Published: January 2020

Let $n$ and $q$ be given integers and $X$ a finite set with $n$ elements. The following theorem is proved for $n>n_0(q)$. The family of all $q$-element subsets of $X$ can be partitioned into disjoint pairs (except possibly one if $n\choose q$ is odd), so that $|A_1\cap A_2|+|B_1\cap B_2|\leq q$, $|A_1\cap B_2|+|B_1\cap A_2| \leq q$ holds for any two such pairs $\{ A_1,B_1\} $ and $\{ A_2,B_2\} $. This is a sharpening of a theorem in [2]. It is also shown that this is a coding type problem, and several problems of similar nature are posed.
New Lower Bounds for Heilbronn Numbers
Authors: Comellas Francesc , Yebra J. Luis A.
Published: January 2020

The $n$-th Heilbronn number, $H_n$, is the largest value such that $n$ points can be placed in the unit square in such a way that all possible triangles defined by any three of the points have area at least $H_n$. In this note we establish new bounds for the first Heilbronn numbers. These new values have been found by using a simple implementation of simulated annealing to obtain a first approximation and then optimizing the results by finding the nearest exact local maximum.
Identifying Codes with Small Radius in Some Infinite Regular Graphs
Authors: Charon Irène , Hudry Olivier , Lobstein Antoine
Published: January 2020

Let $G=(V,E)$ be a connected undirected graph and $S$ a subset of vertices. If for all vertices $v \in V$, the sets $B_r(v) \cap S$ are all nonempty and different, where $B_r(v)$ denotes the set of all points within distance $r$ from $v$, then we call $S$ an $r$-identifying code. We give constructive upper bounds on the best possible density of $r$-identifying codes in four infinite regular graphs, for small values of $r$.
Certificates of Factorisation for Chromatic Polynomials
Authors: Morgan Kerri , Farr Graham
Published: January 2020

The chromatic polynomial gives the number of proper $\lambda$-colourings of a graph $G$. This paper considers factorisation of the chromatic polynomial as a first step in an algebraic study of the roots of this polynomial. The chromatic polynomial of a graph is said to have a chromatic factorisation if $P({G},\lambda)=P({H_{1}},\lambda)P({H_{2}},\lambda)/P({K_{r}},\lambda)$ for some graphs $H_{1}$ and $H_{2}$ and clique $K_{r}$. It is known that the chromatic polynomial of any clique-separable graph, that is, a graph containing a separating $r$-clique, has a chromatic factorisation. We show that there exist other chromatic polynomials that have chromatic factorisations but are not the chromatic polynomial of any clique-separable graph and identify all such chromatic polynomials of degree at most 10. We introduce the notion of a certificate of factorisation, that is, a sequence of algebraic transformations based on identities for the chromatic polynomial that explains the factorisations for a graph. We find an upper bound of $n^{2}2^{n^{2}/2}$ for the lengths of these certificates, and find much smaller certificates for all chromatic factorisations of graphs of order $\leq 9$.
Triangle Free Sets and Arithmetic Progressions – Two Pisier Type Problems
Authors: Davenport Dennis , Hindman Neil , Strauss Dona
Published: January 2020

Let ${\cal P}_f({\bf N})$ be the set of finite nonempty subsets of ${\bf N}$ and for $F,G\in{\cal P}_f({\bf N})$ write $F < G$ when $\max F < \min G$. Let $X=\{(F,G):F,G\in{\cal P}_f({\bf N})$ and $F < G\}$. A triangle in $X$ is a set of the form $\{(F\cup H,G),(F,G),(F,H\cup G)\}$ where $F < H < G$. Motivated by a question of Erdős, Nešetríl, and Rödl regarding three term arithmetic progressions, we show that any finite subset $Y$ of $X$ contains a relatively large triangle free subset. Exact values are obtained for the largest triangle free sets which can be guaranteed to exist in any set $Y\subseteq X$ with $n$ elements for all $n\leq 14$.
Linearly Independent Products of Rectangularly Complementary Schur Functions
Authors: Kleber Michael
Published: January 2020

Fix a rectangular Young diagram $R$, and consider all the products of Schur functions $s_\lambda s_\lambda^{c}$, where $\lambda$ and $\lambda^{c}$ run over all (unordered) pairs of partitions which are complementary with respect to $R$. Theorem: The self-complementary products, $s_\lambda^2$ where $\lambda=\lambda^{c}$, are linearly independent of all other $s_\lambda s_\lambda^{c}$. Conjecture: The products $s_\lambda s_\lambda^{c}$ are all linearly independent.
Parking Functions, Stack-Sortable Permutations, and Spaces of Paths in the Johnson Graph
Authors: Zara Catalin
Published: January 2020

We prove that the space of possible final configurations for a parking problem is parameterized by the vertices of a regular Bruhat graph associated to a 231-avoiding permutation, and we show how this relates to parameterizing certain spaces of paths in the Johnson graph.
Longest Increasing Subsequences in Pattern-Restricted Permutations
Authors: Deutsch Emeric , Hildebrand A. J. , Wilf Herbert S.
Published: January 2020

Inspired by the results of Baik, Deift and Johansson on the limiting distribution of the lengths of the longest increasing subsequences in random permutations, we find those limiting distributions for pattern-restricted permutations in which the pattern is any one of the six patterns of length 3. We show that the (132)-avoiding case is identical to the distribution of heights of ordered trees, and that the (321)-avoiding case has interesting connections with a well known theorem of Erdős-Szekeres.
On $k$-Ordered Bipartite Graphs
Authors: Faudree Jill R. , Gould Ronald J. , Pfender Florian , Wolf Allison
Published: January 2020

In 1997, Ng and Schultz introduced the idea of cycle orderability. For a positive integer $k$, a graph $G$ is k-ordered if for every ordered sequence of $k$ vertices, there is a cycle that encounters the vertices of the sequence in the given order. If the cycle is also a hamiltonian cycle, then $G$ is said to be k-ordered hamiltonian. We give minimum degree conditions and sum of degree conditions for nonadjacent vertices that imply a balanced bipartite graph to be $k$-ordered hamiltonian. For example, let $G$ be a balanced bipartite graph on $2n$ vertices, $n$ sufficiently large. We show that for any positive integer $k$, if the minimum degree of $G$ is at least $(2n+k-1)/4$, then $G$ is $k$-ordered hamiltonian.
A Note on the Edge-Connectivity of Cages
Authors: Wang Ping , Xu Baoguang , Wang Jianfang
Published: January 2020

A $(k;g)$-graph is a $k$-regular graph with girth $g$. A $(k;g)$-cage is a $(k;g)$-graph with the smallest possible number of vertices. In this paper we prove that $(k;g)$-cages are $k$-edge-connected if $k \geq 3$ and $g$ is odd.
The Rank of a Cograph
Authors: Royle Gordon F.
Published: January 2020

The rank of the adjacency matrix of a graph is bounded above by the number of distinct non-zero rows of that matrix. In general, the rank is lower than this number because there may be some non-trivial linear combination of the rows equal to zero. We show the somewhat surprising result that this never occurs for the class of cographs. Therefore, the rank of a cograph is equal to the number of distinct non-zero rows of its adjacency matrix.
A Dual of the Rectangle-Segmentation Problem for Binary Matrices
Authors: Kalinowski Thomas
Published: January 2020

We consider the problem to decompose a binary matrix into a small number of binary matrices whose 1-entries form a rectangle. We show that the linear relaxation of this problem has an optimal integral solution corresponding to a well known geometric result on the decomposition of rectilinear polygons.
Bottom Schur Functions
Authors: Clifford Peter , Stanley Richard P.
Published: January 2020

We give a basis for the space spanned by the sum $\hat{s}_\lambda$ of the lowest degree terms in the expansion of the Schur symmetric functions $s_\lambda$ in terms of the power sum symmetric functions $p_\mu$, where deg$(p_i)=1$. These lowest degree terms correspond to minimal border strip tableaux of $\lambda$. The dimension of the space spanned by $\hat{s}_\lambda$, where $\lambda$ is a partition of $n$, is equal to the number of partitions of $n$ into parts differing by at least 2. Applying the Rogers-Ramanujan identity, the generating function also counts the number of partitions of $n$ into parts $5k+1$ and $5k-1$. We also show that a symmetric function closely related to $\hat{s}_\lambda$ has the same coefficients when expanded in terms of power sums or augmented monomial symmetric functions.
Generating Functions for the Number of Permutations with Limited Displacement
Authors: Kløve Torleiv
Published: January 2020

Let $V(d,n)$ be the number of permutations $p$ of $\{1,2,\ldots ,n\}$ that satisfy $|p_i-i|\le d$ for all $i$. Generating functions for $V(d,n)$, for fixed $d$, are given.
Refined Inversion Statistics on Permutations
Authors: Sack Joshua , Úlfarsson Henning
Published: January 2020

We introduce and study new refinements of inversion statistics for permutations, such as $k$-step inversions, (the number of inversions with fixed position differences) and non-inversion sums (the sum of the differences of positions of the non-inversions of a permutation). We also provide a distribution function for non-inversion sums, a distribution function for $k$-step inversions that relates to the Eulerian polynomials, and special cases of distribution functions for other statistics we introduce, such as $(\le\!\!k)$-step inversions and $(k_1,k_2)$-step inversions (that fix the value separation as well as the position).  We connect our refinements to other work, such as inversion tops that are $0$ modulo a fixed integer $d$, left boundary sums of paths, and marked meshed patterns.   Finally, we use non-inversion sums to show that for every number $n>34$, there is a permutation such that the dot product of that permutation and the identity permutation (of the same length) is $n$.
Arithmetic Properties of Plane Partitions
Authors: Amdeberhan Tewodros , Moll Victor H.
Published: January 2020

The $2$-adic valuations of sequences counting the number of alternating sign matrices of size $n$ and the number of totally symmetric plane partitions are shown to be related in a simple manner.
The 2-adic Valuation of Plane Partitions and Totally Symmetric Plane Partitions
Authors: Keith William J.
Published: January 2020

This paper confirms a conjecture of Amdeberhan and Moll that the power of 2 dividing the number of plane partitions in an $n$-cube is greater than the power of 2 dividing the number of totally symmetric plane partitions in the same cube when $n$ is even, and less when $n$ is odd.
Small Ramsey Numbers
Authors: Radziszowski Stanisław
Published: January 2020

We present data which, to the best of our knowledge, includes all known nontrivial values and bounds for specific graph, hypergraph and multicolor Ramsey numbers, where the avoided graphs are complete or complete without one edge. Many results pertaining to other more studied cases are also presented. We give references to all cited bounds and values, as well as to previous similar compilations. We do not attempt complete coverage of asymptotic behavior of Ramsey numbers, but concentrate on their specific values.
Which Cayley Graphs are Integral?
Authors: Abdollahi A. , Vatandoost E.
Published: January 2020

Let $G$ be a non-trivial group, $S\subseteq G\setminus \{1\}$ and $S=S^{-1}:=\{s^{-1} \;|\; s\in S\}$. The Cayley graph of $G$ denoted by $\Gamma(S:G)$ is a graph with vertex set $G$ and two vertices $a$ and $b$ are adjacent if $ab^{-1}\in S$. A graph is called integral, if its adjacency eigenvalues are integers. In this paper we determine all connected cubic integral Cayley graphs. We also introduce some infinite families of connected integral Cayley graphs.
Periodic Rigidity on a Variable Torus Using Inductive Constructions
Authors: Nixon Anthony , Ross Elissa
Published: January 2020

In this paper we prove a recursive characterisation of generic rigidity for frameworks periodic with respect to a partially variable lattice. We follow the approach of modelling periodic frameworks as frameworks on a torus and use the language of gain graphs for the finite counterpart of a periodic graph. In this setting we employ variants of the Henneberg operations used frequently in rigidity theory.
On Extensions of the Alon-Tarsi Latin Square Conjecture
Authors: Kotlar Daniel
Published: January 2020

Expressions involving the product of the permanent with the $(n-1)^{st}$ power of the determinant of a matrix of indeterminates, and of (0,1)-matrices, are shown to be related to an extension to odd dimensions of the Alon-Tarsi Latin Square Conjecture, first stated by Zappa. These yield an alternative proof of a theorem of Drisko, stating that the extended conjecture holds for Latin squares of odd prime order. An identity involving an alternating sum of permanents of (0,1)-matrices is obtained.
Positivity of the T-System Cluster Algebra
Authors: Francesco Philippe Di , Kedem Rinat
Published: January 2020

We give the path model solution for the cluster algebra variables of the $T$-system of type $A_r$ with generic boundary conditions. The solutions are partition functions of (strongly) non-intersecting paths on weighted graphs. The graphs are the same as those constructed for the $Q$-system in our earlier work, and depend on the seed or initial data in terms of which the solutions are given. The weights are "time-dependent" where "time" is the extra parameter which distinguishes the $T$-system from the $Q$-system, usually identified as the spectral parameter in the context of representation theory. The path model is alternatively described on a graph with non-commutative weights, and cluster mutations are interpreted as non-commutative continued fraction rearrangements. As a consequence, the solution is a positive Laurent polynomial of the seed data.
On the Parity of Certain Coefficients for a $q$-Analogue of the Catalan Numbers
Authors: Killpatrick Kendra
Published: January 2020

The 2-adic valuation (highest power of 2) dividing the well-known Catalan numbers, $C_n$, has been completely determined by Alter and Kubota and further studied combinatorially by Deutsch and Sagan.  In particular, it is well known that $C_n$ is odd if and only if $n = 2^k-1$ for some $k \geq 0$.  The polynomial $F_n^{ch}(321;q) = \sum_{\sigma \in Av_n(321)} q^{ch(\sigma)}$, where $Av_n(321)$ is the set of permutations in $S_n$ that avoid 321 and $ch$ is the charge statistic, is a $q$-analogue of the Catalan numbers since specializing $q=1$ gives $C_n$.  We prove that the coefficient of $q^i$ in $F_{2^k-1}^{ch}(321;q)$ is even if $i \geq 1$, giving a refinement of the "if" direction of the $C_n$ parity result.  Furthermore, we use a bijection between the charge statistic and the major index to prove a conjecture of Dokos, Dwyer, Johnson, Sagan and Selsor regarding powers of 2 and the major index.    In addition, Sagan and Savage have recently defined a notion of $st$-Wilf equivalence for any permutation statistic $st$ and any two sets of permutations $\Pi$ and $\Pi'$.  We say $\Pi$ and $\Pi'$ are $st$-Wilf equivalent if $\sum_{\sigma \in Av_n(\Pi)} q^{st(\sigma)} = \sum_{\sigma \in Av_n(\Pi')} q^{st(\sigma)}$.  In this paper we show how one can characterize the charge-Wilf equivalence classes for subsets of $S_3$.
The Decomposition Algorithm for Skew-Symmetrizable Exchange Matrices
Authors: Gu Weiwen
Published: January 2020

Some skew-symmetrizable integer exchange matrices are associated to ideal (tagged) triangulations of marked bordered surfaces. These exchange matrices admit unfoldings to skew-symmetric matrices. We develop a combinatorial algorithm that determines if a given skew-symmetrizable matrix is of such type. This algorithm generalizes the one in Weiwen Gu's Decomposition Algorithm for Median Graph of Triangulation of a Bordered 2D Surface. As a corollary, we use this algorithm to determine if a given skew-symmetrizable matrix has finite mutation type.
On 021-Avoiding Ascent Sequences
Authors: Chen William Y.C. , Dai Alvin Y.L. , Dokos Theodore , Dwyer Tim , Sagan Bruce E.
Published: January 2020

Ascent sequences were introduced by Bousquet-Mélou, Claesson, Dukes and Kitaev in their study of $(\bf{2+2})$-free posets. An ascent sequence of length $n$ is a nonnegative integer sequence $x=x_{1}x_{2}\ldots x_{n}$ such that $x_{1}=0$ and $x_{i}\leq {\rm asc}(x_{1}x_{2}\ldots x_{i-1})+1$ for all $1<i\leq n$, where ${\rm asc}(x_{1}x_{2}\ldots x_{i-1})$ is the number of ascents in the sequence $x_{1}x_{2}\ldots x_{i-1}$. We let $\mathcal{A}_n$ stand for the set of such sequences and use $\mathcal{A}_n(p)$ for the subset of sequences avoiding a pattern $p$. Similarly, we let $S_{n}(\tau)$ be the set of $\tau$-avoiding permutations in the symmetric group $S_{n}$. Duncan and Steingrímsson have shown that the ascent statistic has the same distribution over  $\mathcal{A}_n(021)$ as over $S_n(132)$. Furthermore, they conjectured that the pair $({\rm asc}, {\rm rmin})$ is equidistributed over $\mathcal{A}_n(021)$ and  $S_n(132)$ where ${\rm rmin}$ is the right-to-left minima statistic.  We prove this conjecture by constructing a bistatistic-preserving bijection.
Counting Packings of Generic Subsets in Finite Groups
Authors: Bacher Roland
Published: January 2020

A packing of subsets $\mathcal S_1,\dots,\mathcal S_n$ in a group $G$ is an element $(g_1,\dots,g_n)$ of $G^n$ such that $g_1\mathcal S_1,\dots,g_n\mathcal S_n$ are disjoint subsets of $G$. We give a formula for the number of packings if the group $G$ is finite and if the subsets $\mathcal S_1,\dots,\mathcal S_n$ satisfy a genericity condition. This formula can be seen as a generalization of the falling factorials which encode the number of packings in the case where all the sets $\mathcal S_i$ are singletons.
A Note on Total and Paired Domination of Cartesian Product Graphs
Authors: Choudhary K. , Margulies S. , Hicks I. V.
Published: January 2020

A dominating set $D$ for a graph $G$ is a subset of $V(G)$ such that any vertex not in $D$ has at least one neighbor in $D$. The domination number $\gamma(G)$ is the size of a minimum dominating set in G. Vizing's conjecture from 1968 states that for the Cartesian product of graphs $G$ and $H$, $\gamma(G)\gamma(H) \leq \gamma(G \Box H)$, and Clark and Suen (2000) proved that $\gamma(G)\gamma(H) \leq 2 \gamma(G \Box H)$. In this paper, we modify the approach of Clark and Suen to prove a variety of similar bounds related to total and paired domination, and also extend these bounds to the $n$-Cartesian product of graphs $A^1$ through $A^n$.
Ramsey Numbers $R(K_3, G)$ for Graphs of Order 10
Authors: Brinkmann Gunnar , Goedgebeur Jan , Schlage-Puchta Jan-Christoph
Published: January 2020

In this article we give the generalized triangle Ramsey numbers $R(K_3, G)$ of 12 005 158 of the 12 005 168 graphs of order 10. There are 10 graphs remaining for which we could not determine the Ramsey number. Most likely these graphs need approaches focusing on each individual graph in order to determine their triangle Ramsey number. The results were obtained by combining new computational and theoretical results.  We also describe an optimized algorithm for the generation of all  maximal triangle-free graphs and triangle Ramsey graphs.  All Ramsey numbers up to 30 were computed by our implementation of this algorithm. We also prove some theoretical results that are applied to determine several triangle Ramsey numbers larger than 30. As not only the number of graphs is increasing very fast, but also the difficulty to determine Ramsey numbers, we consider it very likely that the table of all triangle Ramsey numbers for graphs of order 10 is the last complete table that can possibly be determined for a very long time.
Nonexistence of Almost Moore Digraphs of Diameter Four
Authors: Conde Josep , Gimbert Joan , González Josep , Miret Josep M. , Moreno Ramiro
Published: January 2020

Regular digraphs of degree $d>1$, diameter $k>1$ and order $N(d,k) = d+\cdots +d^k$ will be called almost Moore $(d,k)$-digraphs. So far, the problem of their existence has only been solved when $d=2, 3$ or $k = 2, 3$. In this paper we prove that almost Moore digraphs of diameter 4 do not exist for any degree $d$.
Decomposing Sets of Inversions
Authors: Katthän Lukas
Published: January 2020

In this paper we consider the question how the set of inversions of a permutation $\pi \in S_n$ can be partitioned into two subsets, which are themselves inversion sets of permutations in $S_n$. Our method is to study the modular decomposition of the inversion graph of $\pi$. A correspondence to the substitution decomposition of $\pi$ is also given. Moreover, we consider the special case of multiplicative decompositions.
Maximum Independent Sets in Certain Powers of Odd Cycles
Authors: Bohman Tom , Holzman Ron , Natarajan Venkatesh
Published: January 2020

We give a complete classification of all maximum independent sets in powers of odd cycles of the form $C_{k 2^d + 1}^d$.
Matching Covered Graphs with Three Removable Classes
Authors: De Carvalho Marcelo H. , Little Charles H. C.
Published: January 2020

The notion of removable classes arises in connection with ear decompositions of matching covered graphs introduced by Lovász and Plummer. The last (single or double) ear of an ear decomposition is defined as a removable class. Every matching covered graph not induced by a circuit has at least three removable classes. In this paper, we characterize matching covered graphs with precisely three removable classes and show, as a corollary, that every non-planar matching covered graph has at least four removable classes. Let $G$ be a matching covered graph. A matching covered subgraph $H$ of $G$ is conformal if $G-VH$ has a perfect matching. Given $S \subseteq EG$, what is a minimal conformal subgraph of $G$ that contains $S$? It is known that if $|S|=2$ then it is induced by a circuit. As an application of the main result, we answer this question for $|S|=3$.
Self-Avoiding Walks and the Fisher Transformation
Authors: Grimmett Geoffrey , Li Zhongyang
Published: January 2020

The Fisher transformation acts on cubic graphs by replacing each vertex by a triangle. We explore the action of the Fisher transformation on the set of self-avoiding walks of a cubic graph. Iteration of the transformation yields a sequence of graphs with common critical exponents, and with connective constants converging geometrically to the golden mean. We consider the application of the Fisher transformation to one of the two classes of vertices of a bipartite cubic graph. The connective constant of the ensuing graph may be expressed in terms of that of the initial graph. When applied to the hexagonal lattice, this identifies a further lattice whose connective constant may be computed rigorously.
New Spectral Bounds on the Chromatic Number Encompassing all Eigenvalues of the Adjacency Matrix
Authors: Wocjan Pawel , Elphick Clive
Published: January 2020

The purpose of this article is to improve existing lower bounds on the chromatic number $\chi$. Let $\mu_1,\ldots,\mu_n$ be the eigenvalues of the adjacency matrix sorted in non-increasing order.First, we prove the lower bound $\chi \ge 1 + \max_m\{\sum_{i=1}^m \mu_i / -\sum_{i=1}^m \mu_{n - i +1}\}$ for $m=1,\ldots,n-1$. This generalizes the Hoffman lower bound which only involves the maximum and minimum eigenvalues, i.e., the case $m=1$. We provide several examples for which the new bound exceeds the Hoffman lower bound.Second, we conjecture the lower bound $\chi \ge 1 + s^+ / s^-$, where $s^+$ and $s^-$ are the sums of the squares of positive and negative eigenvalues, respectively. To corroborate this conjecture, we prove the bound $\chi \ge s^+/s^-$. We show that the conjectured lower bound is true for several families of graphs. We also performed various searches for a counter-example, but none was found.Our proofs rely on a new technique of considering a family of conjugates of the adjacency matrix, which add to the zero matrix, and use majorization of spectra of self-adjoint matrices.We also show that the above bounds are actually lower bounds on the normalized orthogonal rank of a graph, which is always less than or equal to the chromatic number. The normalized orthogonal rank is the minimum dimension making it possible to assign vectors with entries of modulus one to the vertices such that two such vectors are orthogonal if the corresponding vertices are connected.All these bounds are also valid when we replace the adjacency matrix $A$ by $W * A$ where $W$ is an arbitrary self-adjoint matrix and $*$ denotes the Schur product, that is, entrywise product of $W$ and $A$.
Integral Cayley Multigraphs over Abelian and Hamiltonian Groups
Authors: DeVos Matt , Krakovski Roi , Mohar Bojan , Sheikh Ahmady Azhvan
Published: January 2020

It is shown that a Cayley multigraph over a group $G$ with generating multiset $S$ is integral (i.e., all of its eigenvalues are integers) if $S$ lies in the integral cone over the boolean algebra generated by the normal subgroups of $G$. The converse holds in the case when $G$ is abelian. This in particular gives an alternative, character theoretic proof of a theorem of Bridges and Mena (1982). We extend this result to provide a necessary and sufficient condition for a Cayley multigraph over a Hamiltonian group to be integral, in terms of character sums and the structure of the generating set.
Packing Unit Squares in Squares: A Survey and New Results
Authors: Friedman Erich
Published: January 2020

Let $s(n)$ be the side of the smallest square into which we can pack n unit squares. We present a history of this problem, and give the best known upper and lower bounds for $s(n)$ for $n\le100$, including the best known packings. We also give relatively simple proofs for the values of $s(n)$ when $n = 2$, 3, 5, 8, 15, 24, and 35, and more complicated proofs for $n=7$ and 14. We also prove many other lower bounds for various $s(n)$.
Some Design Theoretic Results on the Conway Group $\cdot$0
Authors: Fairbairn Ben
Published: January 2020

Let $\Omega$ be a set of 24 points with the structure of the (5,8,24) Steiner system, $\cal{S}$, defined on it. The automorphism group of $\cal{S}$ acts on the famous Leech lattice, as does the binary Golay code defined by $\cal{S}$. Let $A,B\subset\Omega$ be subsets of size four ("tetrads"). The structure of $\cal{S}$ forces each tetrad to define a certain partition of $\Omega$ into six tetrads called a sextet. For each tetrad Conway defined a certain automorphism of the Leech lattice that extends the group generated by the above to the full automorphism group of the lattice. For the tetrad $A$ he denoted this automorphism $\zeta_A$. It is well known that for $\zeta_A$ and $\zeta_B$ to commute it is sufficient to have A and B belong to the same sextet. We extend this to a much less obvious necessary and sufficient condition, namely $\zeta_A$ and $\zeta_B$ will commute if and only if $A\cup B$ is contained in a block of $\cal{S}$. We go on to extend this result to similar conditions for other elements of the group and show how neatly these results restrict to certain important subgroups.
A Proof of Erdős-Fishburn's Conjecture for $g(6)=13$
Authors: Xianglin Wei
Published: January 2020

A planar point set $X$ in the Euclidean plane is called a $k$-distance set if there are exactly $k$ distances between two distinct points in $X$. An interesting problem is to find the largest possible cardinality of a $k$-distance set. This problem was introduced by Erdős and Fishburn (1996). Maximum planar sets that determine $k$ distances for $k$ less than 5 have been identiﬁed. The 6-distance conjecture of Erdős and Fishburn states that 13 is the maximum number of points in the plane that determine exactly 6 different distances. In this paper, we prove the conjecture.
Combinatorial Constructions of Weight Bases: The Gelfand-Tsetlin Basis
Authors: Hersh Patricia , Lenart Cristian
Published: January 2020

This work is part of a project on weight bases for the irreducible representations of semisimple Lie algebras with respect to which the representation matrices of the Chevalley generators are given by explicit formulas. In the case of $\mathfrak{ sl}$$_n$, the celebrated Gelfand-Tsetlin basis is the only such basis known. Using the setup of supporting graphs developed by Donnelly, we present a new interpretation and a simple combinatorial proof of the Gelfand-Tsetlin formulas based on a rational function identity (all the known proofs use more sophisticated algebraic tools). A constructive approach to the Gelfand-Tsetlin formulas is then given, based on a simple algorithm for solving certain equations on the lattice of semistandard Young tableaux. This algorithm also implies certain extremal properties of the Gelfand-Tsetlin basis.
On Some Small Classical Ramsey Numbers
Authors: Exoo Geoffrey
Published: January 2020

This note is a report on a computer investigation of some small classical Ramsey numbers. We establish new lower bounds for the classical Ramsey numbers $R(3,11)$ and $R(4,8)$. In the first case, the bound is improved from $46$ (a record that had stood for 46 years) to $47$; and in the second case the bound is improved from $57$ to $58$.
A Complete Annotated Bibliography of Work Related to Sidon Sequences
Authors: O'Bryant Kevin
Published: January 2020

A Sidon sequence is a sequence of integers $a_1 < a_2 < \cdots$ with the property that the sums $a_i + a_j$ $(i\le j)$ are distinct. This work contains a survey of Sidon sequences and their generalizations, and an extensive annotated and hyperlinked bibliography of related work.
Aperiodic Non-Isomorphic Lattices with Equivalent Percolation and Random-Cluster Models
Authors: Markström Klas , Wierman John C.
Published: January 2020

We explicitly construct an uncountable class of infinite aperiodic plane graphs which have equal, and explicitly computable, bond percolation thresholds. Furthermore for both bond percolation and the random-cluster model all large scale properties, such as the values of the percolation threshold and the critical exponents, of the graphs are equal. This equivalence holds for all values of $p$ and all $q\in[0,\infty]$ for the random-cluster model. The graphs are constructed by placing a copy of a rotor gadget graph or its reflection in each hyperedge of a connected self-dual 3-uniform plane hypergraph lattice. The exact bond percolation threshold may be explicitly determined as the root of a polynomial by using a generalised star-triangle transformation. Related randomly oriented models share the same bond percolation threshold value.
Encodings of Cladograms and Labeled Trees
Authors: Ford Daniel J.
Published: January 2020

This paper deals with several bijections between cladograms and perfect matchings. The first of these is due to Diaconis and Holmes. The second is a modification of the Diaconis-Holmes matching which makes deletion of the largest labeled leaf correspond to gluing together the last two points in the perfect matching. The third is an entirely new encoding of cladograms, first as a bijection with a certain set of strings and then via this to perfect matchings. In this pair of bijections, deletion of the largest labeled leaf corresponds to deletion of the corresponding symbols from the string or deletion of the corresponding pair from the matching. These two new bijections are related through a common max-min labeling of internal vertices with two different choices for the label of the root node. All these encodings are extended to cladograms with edge lengths and left-right ordered children. Moving a single symbol in this last encoding corresponds to a subtree prune and regraft operation on the cladogram, making it well suited for use in phylogentics software. Finally, a perfect Gray code for cladograms is derived from the bar encoding, along with a total ordering on all cladograms, Algorithms are also provided for finding the next and previous cladogram, the cladogram at any position, and the position of any cladogram in the sequence.
The Spectral Excess Theorem for Distance-Biregular Graphs.
Authors: Fiol Miquel Àngel
Published: January 2020

The spectral excess theorem for distance-regular graphs states that a regular (connected) graph is distance-regular if and only if its spectral-excess equals its average excess. A bipartite graph $\Gamma$ is distance-biregular when it is distance-regular around each vertex and the intersection array only depends on the stable set such a vertex belongs to. In this note we derive a new version of the spectral excess theorem for bipartite distance-biregular graphs.
Kauffman's Clock Lattice as a Graph of Perfect Matchings: a Formula for its Height
Authors: Cohen Moshe , Teicher Mina
Published: January 2020

We give an algorithmic computation for the height of Kauffman's clock lattice obtained from a knot diagram with two adjacent regions starred and without crossing information specified. We show that this lattice is more familiarly the graph of perfect matchings of a bipartite graph obtained from the knot diagram by overlaying the two dual Tait graphs of the knot diagram. Furthermore we prove structural properties of the bipartite graph in general. This setting also makes evident applications to Chebyshev or harmonic knots, whose related bipartite graph is the popular grid graph, and to discrete Morse functions.
A Note on Irreducible Maps with Several Boundaries
Authors: Bouttier J. , Guitter E.
Published: January 2020

We derive a formula for the generating function of $d$-irreducible bipartite planar maps with several boundaries, i.e. having several marked faces of controlled degrees. It extends a formula due to Collet and Fusy for the case of arbitrary (non necessarily irreducible) bipartite planar maps, which is recovered by taking $d=0$. As an application, we obtain an expression for the number of $d$-irreducible bipartite planar maps with a prescribed number of faces of each allowed degree. Very explicit expressions are given in the case of maps without multiple edges ($d=2$), $4$-irreducible maps and maps of girth at least $6$ ($d=4$). Our derivation is based on a tree interpretation of the various encountered generating functions.
Regularity of Join-meet Ideals of Distributive Lattices
Authors: Ene Viviana , Qureshi Ayesha Asloob , Rauf Asia
Published: January 2020

Let $L$ be a distributive lattice and $R(L)$ the associated Hibi ring. We compute reg $R(L)$ when $L$ is  a planar  lattice and give  bounds for reg $R(L)$ when $L$ is non-planar, in terms of the combinatorial data of $L.$  As a consequence, we characterize the distributive lattices $L$ for which the associated Hibi ring has a linear resolution.
Spanning $k$-trees of Bipartite Graphs
Authors: Kano Mikio , Ozeki Kenta , Suzuki Kazuhiro , Tsugaki Masao , Yamashita Tomoki
Published: January 2020

A tree is called a $k$-tree if its maximum degree is at most $k$. We prove the following theorem. Let $k \geq 2$ be an integer, and $G$ be a connected bipartite graph with bipartition $(A,B)$ such that $|A| \le |B| \le (k-1)|A|+1$. If $\sigma_k(G) \ge |B|$, then $G$ has a spanning $k$-tree, where $\sigma_k(G)$ denotes the minimum degree sum of $k$ independent vertices of $G$. Moreover, the condition on $\sigma_k(G)$ is sharp. It was shown by Win (Abh. Math. Sem. Univ. Hamburg, 43, 263–267, 1975) that if a connected graph $H$ satisfies $\sigma_k(H) \ge |H|-1$, then $H$ has a spanning $k$-tree. Thus our theorem shows that the condition becomes much weaker if the graph is bipartite.
Non-Normal Very Ample Polytopes and their Holes
Authors: Higashitani Akihiro
Published: January 2020

In this paper, we show that for given integers $h$ and $d$ with $h \geq 1$ and $d \geq 3$, there exists a non-normal very ample integral convex polytope of dimension $d$ which has exactly $h$ holes.
A Characteristic Factor for the 3-Term IP Roth Theorem in $\mathbb{Z}_3^\mathbb{N}$
Authors: McCutcheon Randall , Windsor Alistair
Published: January 2020

Let $\Omega = \bigoplus_{i=1}^\infty \mathbb{Z}_3$ and $e_i = (0, \dots, 0 , 1, 0, \dots)$ where the $1$ occurs in the $i$-th coordinate. Let $\mathscr{F}=\{ \alpha \subset \mathbb{N} : \varnothing \neq \alpha, \alpha \text{ is finite} \}$. There is a natural inclusion of $\mathscr{F}$ into $\Omega$ where $\alpha \in \mathscr{F}$ is mapped to $e_\alpha = \sum_{i \in \alpha} e_i$. We give a new proof that if $E \subset \Omega$ with $d^*(E) >0$ then there exist $\omega \in \Omega$ and $\alpha \in \mathscr{F}$ such that \[ \{ \omega, \omega+ e_\alpha, \omega + 2 e_\alpha \} \subset E.\]Our proof establishes that for the ergodic reformulation of the problem there is a characteristic factor that is a one step compact extension of the Kronecker factor.
Random Procedures for Dominating Sets in Graphs
Authors: Artmann Sarah , Göring Frank , Harant Jochen , Rautenbach Dieter , Schiermeyer Ingo
Published: January 2020

We present and analyze some random procedures for the construction of small dominating sets in graphs. Several upper bounds for the domination number of a graph are derived from these procedures.
Equivalence Classes of Permutations Modulo Replacements Between 123 and Two-Integer Patterns
Authors: Fazel-Rezai Vahid
Published: January 2020

We explore a new type of replacement of patterns in permutations, suggested by James Propp, that does not preserve the length of permutations. In particular, we focus on replacements between 123 and a pattern of two integer elements. We apply these replacements in the classical sense; that is, the elements being replaced need not be adjacent in position or value. Given each replacement, the set of all permutations is partitioned into equivalence classes consisting of permutations reachable from one another through a series of bi-directional replacements. We break the eighteen replacements of interest into four categories by the structure of their classes and fully characterize all of their classes.
Inequivalence of Skew Hadamard Difference Sets and Triple Intersection Numbers Modulo a Prime
Authors: Momihara Koji
Published: January 2020

Recently, Feng and Xiang found a new construction of skew Hadamard difference sets in elementary abelian groups. In this paper, we introduce a new invariant for equivalence of skew Hadamard difference sets, namely triple intersection numbers modulo a prime, and discuss inequivalence between Feng-Xiang skew Hadamard difference sets and the Paley difference sets. As a consequence, we show that their construction produces infinitely many skew Hadamard difference sets inequivalent to the Paley difference sets.
Schur-Positivity in a Square
Authors: Ballantine Cristina , Orellana Rosa
Published: January 2020

Determining if a symmetric function is Schur-positive is a prevalent and, in general, a notoriously difficult problem.  In this paper we study the Schur-positivity of a family of symmetric functions.  Given a partition $\nu$, we denote by $\nu^c$ its complement in a square partition $(m^m)$.   We conjecture a  Schur-positivity criterion  for symmetric functions of the form $s_{\mu'}s_{\mu^c}-s_{\nu'}s_{\nu^c}$, where $\nu$ is a partition of weight $|\mu|-1$ contained in $\mu$ and the complement of $\mu$ is taken in the same square partition as the complement of $\nu$. We prove the conjecture in many cases.
The Gap Structure of a Family of Integer Subsets
Authors: Bernardino André , Pacheco Rui , Silva Manuel
Published: January 2020

In this paper we investigate the gap structure of a certain family of subsets of $\mathbb{N}$ which produces counterexamples both to the "density version" and the "canonical version" of Brown's lemma. This family includes the members of all complementing pairs of $\mathbb{N}$. We will also relate the asymptotical gap structure of subsets of $\mathbb{N}$ with their density and investigate the asymptotical gap structure of monochromatic and rainbow sets with respect to arbitrary infinite colorings of $\mathbb{N}$.
$k$-Fold Sidon Sets
Authors: Cilleruelo Javier , Timmons Craig
Published: January 2020

Let $k \geq 1$ be an integer.  A set $A \subset \mathbb{Z}$ is a $k$-fold Sidon set if $A$ has only trivial solutions to each equation of the form $c_1 x_1 + c_2 x_2 + c_3 x_3 + c_4 x_4 = 0$ where $0 \leq |c_i | \leq k$, and $c_1 + c_2 + c_3 + c_4 = 0$.  We prove that for any integer $k \geq 1$, a $k$-fold Sidon set $A \subset [N]$ has at most $(N/k)^{1/2} + O((Nk)^{1/4})$ elements. Indeed we prove that given any $k$ positive integers $c_1<\cdots <c_k$, any set $A\subset [N]$ that contains only trivial solutions to $c_i(x_1-x_2)=c_j(x_3-x_4)$ for each $1 \le i \le j \le k$, has at most $(N/k)^{1/2}+O((c_k^2N/k)^{1/4})$ elements. On the other hand, for any $k \geq 2$ we can exhibit $k$ positive integers $c_1,\dots, c_k$ and a set $A\subset [N]$ with $|A|\ge (\frac 1k+o(1))N^{1/2}$, such that $A$ has only trivial solutions to $c_i(x_1 - x_2) = c_j (x_3 -  x_4)$ for each $1 \le i \le j\le k$.
More on the Wilson $W_{tk}(v)$ Matrices
Authors: Ahmadi M.H. , Akhlaghinia N. , Khosrovshahi G.B. , Maysoori Ch.
Published: January 2020

For integers $0\leq t\leq k\leq v-t$, let $X$ be a $v$-set, and let $W_{tk}(v)$ be a ${v \choose t}\times{v \choose k}$ inclusion matrix where rows and columns are indexed by $t$-subsets and $k$-subsets of $X$, respectively, and for row $T$ and column $K$, $W_{tk}(v)(T,K)=1$ if $T\subseteq K$ and zero otherwise. Since $W_{tk}(v)$ is a full rank matrix, by reordering the columns of $W_{tk}(v)$ we can write $W_{tk}(v) = (S|N)$, where $N$ denotes a set of independent columns of $W_{tk}(v)$. In this paper, first by classifying $t$-subsets and $k$-subsets, we present a new decomposition of $W_{tk}(v)$. Then by employing this decomposition, the Leibniz Triangle, and a known right inverse of $W_{tk}(v)$, we  construct  the inverse of $N$ and consequently special basis for the null space (known as the standard basis) of $W_{tk}(v)$.
A Note on Independent Sets in Graphs with Large Minimum Degree and Small Cliques
Authors: Lyle Jeremy
Published: January 2020

Graphs with large minimum degree containing no copy of a clique on $r$ vertices ($K_r$) must contain relatively large independent sets. A classical result of Andrásfai, Erdős, and Sós implies that $K_r$-free graphs $G$ with degree larger than $((3r-7)/(3r-4))|V(G)|$ must be $(r-1)$-partite. An obvious consequence of this result is that the same degree threshold implies an independent set of order $(1/(r-1))|V(G)|$. The following paper provides improved bounds on the minimum degree which would imply the same conclusion. This problem was first considered by Brandt, and we provide improvements over these initial results for $r > 5$.
Characteristic Points of Recursive Systems
Authors: Bell Jason P. , Burris Stanley N. , Yeats Karen A.
Published: January 2020

Characteristic points have been a primary tool in the study of a generating function defined by a single recursive equation. We investigate the proper way to adapt this tool when working with multi-equation recursive systems. Given an irreducible non-negative power series system with $m$ equations, let $\rho$ be the radius of convergence of the solution power series and let $\pmb{\tau}$ be the values of the solution series evaluated at $\rho$. The main results of the paper include: (a) the set of characteristic points form an antichain in ${\mathbb R}^{m+1}$, (b) given a characteristic point $(a,\mathbf{b})$, (i) the spectral radius of the Jacobian of $\pmb \gamma$ at $(a, \mathbf{b})$ is $\ge 1$, and (ii) it is $=1$ iff $(a,\mathbf{b}) = (\rho,\pmb{\tau})$, (c) if $(\rho,\pmb{\tau})$ is a characteristic point, then (i) $\rho$ is the largest $a$ for $(a,\mathbf{b})$ a characteristic point, and (ii) a characteristic point $(a,\mathbf{b})$ with $a=\rho$ is the extreme point $(\rho,\pmb{\tau})$.
On the Group of Alternating Colored Permutations
Authors: Bagno Eli , Garber David , Mansour Toufik
Published: January 2020

The group of alternating colored permutations is the natural analogue of the classical alternating group, inside the wreath product $\mathbb{Z}_r \wr S_n$. We present a 'Coxeter-like' presentation for this group and compute the length function with respect to that presentation. Then, we present this group as a covering of $\mathbb{Z}_{\frac{r}{2}} \wr S_n$ and use this point of view to give another expression for the length function. We also use this covering to lift several known parameters of $\mathbb{Z}_{\frac{r}{2}} \wr S_n$ to the group of alternating colored permutations.
Counting 2-Connected 4-Regular Maps on the Projective Plane
Authors: Long Shude , Ren Han
Published: January 2020

In this paper the number of rooted (near-) 4-regular maps on the projective plane are investigated with respect to the root-valency, the number of edges, the number of inner faces, the number of nonroot-vertex-loops, the number of nonroot-vertex-blocks. As special cases, formulae for several types of rooted 4-regular maps such as 2-connected 4-regular projective planar maps, rooted 2-connected (connected) 4-regular projective planar maps without loops are also presented. Several known results on the number of 4-regular maps on the projective plane are also concluded. Finally, by use of Darboux's method, very nice asymptotic formulae for the numbers of those types of maps are given.
Sharp Lower Bound for the Total Number of Matchings of Tricyclic Graphs
Authors: Li Shuchao , Zhu Zhongxun
Published: January 2020

Let $\mathscr{T}_n$ be the class of tricyclic graphs on $n$ vertices. In this paper, a sharp lower bound for the total number of matchings of graphs in $\mathscr{T}_n$ is determined.
Coloring the Edges of a Random Graph without a Monochromatic Giant Component
Authors: Spöhel Reto , Steger Angelika , Thomas Henning
Published: January 2020

We study the following two problems: i) Given a random graph $G_{n, m}$ (a graph drawn uniformly at random from all graphs on $n$ vertices with exactly $m$ edges), can we color its edges with $r$ colors such that no color class contains a component of size $\Theta(n)$? ii) Given a random graph $G_{n,m}$ with a random partition of its edge set into sets of size $r$, can we color its edges with $r$ colors subject to the restriction that every color is used for exactly one edge in every set of the partition such that no color class contains a component of size $\Theta(n)$? We prove that for any fixed $r\geq 2$, in both settings the (sharp) threshold for the existence of such a coloring coincides with the known threshold for $r$-orientability of $G_{n,m}$, which is at $m=rc_r^*n$ for some analytically computable constant $c_r^*$. The fact that the two problems have the same threshold is in contrast with known results for the two corresponding Achlioptas-type problems.
A 64-Dimensional Counterexample to Borsuk's Conjecture
Authors: Jenrich Thomas , Brouwer Andries E.
Published: January 2020

Bondarenko's 65-dimensional counterexample to Borsuk's conjecture contains a 64-dimensional counterexample. It is a two-distance set of 352 points.
Combinatorial Nullstellensatz Modulo Prime Powers and the Parity Argument
Authors: Varga László
Published: January 2020

We present new generalizations of Olson's theorem and of a consequence of Alon's Combinatorial Nullstellensatz. These enable us to extend some of their combinatorial applications with conditions modulo primes to conditions modulo prime powers. We analyze computational search problems corresponding to these kinds of combinatorial questions and we prove that the problem of finding degree-constrained subgraphs modulo $2^d$ such as $2^d$-divisible subgraphs and the search problem corresponding to the Combinatorial Nullstellensatz over $\mathbb{F}_2$ belong to the complexity class Polynomial Parity Argument (PPA).