bluuebunny/crossref_metadata_2025 huggingface dataset:
Colorings and Orientations of Matrices and Graphs
Authors: Schauz Uwe
Published: January 2020

We introduce colorings and orientations of matrices as generalizations of the graph theoretic terms. The permanent per$(A[\zeta|\xi])$ of certain copies $A[\zeta|\xi]$ of a matrix $A$ can be expressed as a weighted sum over the orientations or the colorings of $A$. When applied to incidence matrices of graphs these equations include Alon and Tarsi's theorem about Eulerian orientations and the existence of list colorings. In the case of planar graphs we deduce Ellingham and Goddyn's partial solution of the list coloring conjecture and Scheim's equivalency between not vanishing permanents and the four color theorem. The general concept of matrix colorings in the background is also connected to hypergraph colorings and matrix choosability.
The Maximum Distinguishing Number of a Group
Authors: Chan Melody
Published: January 2020

Let $G$ be a group acting faithfully on a set $X$. The distinguishing number of the action of $G$ on $X$, denoted $D_G(X)$, is the smallest number of colors such that there exists a coloring of $X$ where no nontrivial group element induces a color-preserving permutation of $X$. In this paper, we show that if $G$ is nilpotent of class $c$ or supersolvable of length $c$ then $G$ always acts with distinguishing number at most $c+1$. We obtain that all metacyclic groups act with distinguishing number at most 3; these include all groups of squarefree order. We also prove that the distinguishing number of the action of the general linear group $GL_n(K)$ over a field $K$ on the vector space $K^n$ is 2 if $K$ has at least $n+1$ elements.
When are subset sums equidistributed modulo m?
Authors: Wagon Stan , Wilf Herbert S.
Published: January 2020

For a triple $(n,t,m)$ of positive integers, we attach to each $t$-subset $S=\{a_1,\ldots ,a_t\}\subseteq \{1,\ldots ,n\}$ the sum $f(S)=a_1+\cdots +a_t$ (modulo $m$). We ask: for which triples $(n,t,m)$ are the ${n\choose t}$ values of $f(S)$ uniformly distributed in the residue classes mod $m$? The obvious necessary condition, that $m$ divides ${n\choose t}$, is not sufficient, but a $q$-analogue of that condition is both necessary and sufficient, namely: $${{q^m-1}\over {q-1}}\quad \text{divides the Gaussian polynomial}\quad \binom{n}{t}_q.$$ We show that this condition is equivalent to: for each divisor $d>1$ of $m$, we have $t\ {\rm mod}\, d>n\ {\rm mod}\, d$. Two proofs are given, one by generating functions and another via a bijection. We study the analogous question on the full power set of $[n]$: given $(n,m)$; when are the $2^n$ subset sums modulo $m$ equidistributed into the residue classes? Finally we obtain some asymptotic information about the distribution when it is not uniform, and discuss some open questions.
Even Kernels
Authors: Fraenkel Aviezri
Published: January 2020

Given a graph $G = (V,E)$, an even kernel is a nonempty independent subset $V' \subseteq V$, such that every vertex of $G$ is adjacent to an even number (possibly 0) of vertices in $V'$. It is proved that the question of whether a graph has an even kernel is NP-complete. The motivation stems from combinatorial game theory. It is known that this question is polynomial if $G$ is bipartite. We also prove that the question of whether there is an even kernel whose size is between two given bounds, in a given bipartite graph, is NP-complete. This result has applications in coding and set theory.
Multicoloured Hamilton Cycles
Authors: Albert Michael , Frieze Alan , Reed Bruce
Published: January 2020

The edges of the complete graph $K_n$ are coloured so that no colour appears more than $\lceil cn\rceil$ times, where $c < 1/32$ is a constant. We show that if $n$ is sufficiently large then there is a Hamiltonian cycle in which each edge is a different colour, thereby proving a 1986 conjecture of Hahn and Thomassen. We prove a similar result for the complete digraph with $c < 1/64$. We also show, by essentially the same technique, that if $t\geq 3$, $c < (2t^2(1+t))^{-1}$, no colour appears more than $\lceil cn\rceil$ times and $t|n$ then the vertices can be partitioned into $n/t$ $t-$sets $K_1,K_2,\ldots,K_{n/t}$ such that the colours of the $n(t-1)/2$ edges contained in the $K_i$'s are distinct. The proof technique follows the lines of Erdős and Spencer's modification of the Local Lemma.
Algebraic Shifting and Sequentially Cohen-Macaulay Simplicial Complexes
Authors: Duval Art M.
Published: January 2020

Björner and Wachs generalized the definition of shellability by dropping the assumption of purity; they also introduced the $h$-triangle, a doubly-indexed generalization of the $h$-vector which is combinatorially significant for nonpure shellable complexes. Stanley subsequently defined a nonpure simplicial complex to be sequentially Cohen-Macaulay if it satisfies algebraic conditions that generalize the Cohen-Macaulay conditions for pure complexes, so that a nonpure shellable complex is sequentially Cohen-Macaulay. We show that algebraic shifting preserves the $h$-triangle of a simplicial complex $K$ if and only if $K$ is sequentially Cohen-Macaulay. This generalizes a result of Kalai's for the pure case. Immediate consequences include that nonpure shellable complexes and sequentially Cohen-Macaulay complexes have the same set of possible $h$-triangles.
Enumerating Up-Side Self-Avoiding Walks on Integer Lattices
Authors: Williams Lauren K.
Published: January 2020

A self-avoiding walk (saw) is a path on a lattice that does not pass through the same point twice. Though mathematicians have studied saws for over fifty years, the number of $n$-step saws is unknown. This paper examines a special case of this problem, finding the number of $n$-step "up-side" saws (ussaws), saws restricted to moving up and sideways. It presents formulas for the number of $n$-step ussaws on various lattices, found using generating functions with decomposition and recursive methods.
The Tutte Polynomial of a Graph, Depth-first Search
Authors: Gessel Ira M. , Sagan Bruce E.
Published: January 2020

One of the most important numerical quantities that can be computed from a graph $G$ is the two-variable Tutte polynomial. Specializations of the Tutte polynomial count various objects associated with $G$, e.g., subgraphs, spanning trees, acyclic orientations, inversions and parking functions. We show that by partitioning certain simplicial complexes related to $G$ into intervals, one can provide combinatorial demonstrations of these results. One of the primary tools for providing such a partition is depth-first search.
Union of all the Minimum Cycle Bases of a Graph
Authors: Vismara Philippe
Published: January 2020

The perception of cyclic structures is a crucial step in the analysis of graphs. To describe the cycle vector space of a graph, a minimum cycle basis can be computed in polynomial time using an algorithm of [Horton, 1987]. But the set of cycles corresponding to a minimum basis is not always relevant for analyzing the cyclic structure of a graph. This restriction is due to the fact that a minimum cycle basis is generally not unique for a given graph. Therefore, the smallest canonical set of cycles which describes the cyclic structure of a graph is the union of all the minimum cycle bases. This set of cycles is called the set of relevant cycles and denoted by ${\cal C_R}$. A relevant cycle can also be defined as a cycle which is not the sum of shorter cycles. A polynomial algorithm is presented that computes a compact representation of the potentially exponential-sized set ${\cal C_R}$ in $O(\nu m^3)$ (where $\nu$ denotes the cyclomatic number). This compact representation consists of a polynomial number of relevant cycle prototypes from which all the relevant cycles can be listed in $O(n\,|{\cal C_R}|)$. A polynomial method is also given that computes the number of relevant cycles without listing all of them.
Analysis of an Asymmetric Leader Election Algorithm
Authors: Janson Svante , Szpankowski Wojciech
Published: January 2020

We consider a leader election algorithm in which a set of distributed objects (people, computers, etc.) try to identify one object as their leader. The election process is randomized, that is, at every stage of the algorithm those objects that survived so far flip a biased coin, and those who received, say a tail, survive for the next round. The process continues until only one objects remains. Our interest is in evaluating the limiting distribution and the first two moments of the number of rounds needed to select a leader. We establish precise asymptotics for the first two moments, and show that the asymptotic expression for the duration of the algorithm exhibits some periodic fluctuations and consequently no limiting distribution exists. These results are proved by analytical techniques of the precise analysis of algorithms such as: analytical poissonization and depoissonization, Mellin transform, and complex analysis.
Limit Probabilities for Random Sparse Bit Strings
Authors: St. John Katherine
Published: January 2020

Let $n$ be a positive integer, $c$ a real positive constant, and $p(n) = c/n$. Let $U_{n,p}$ be the random unary predicate under the linear order, and $S_c$ the almost sure theory of $U_{n,{c\over n}}$. We show that for every first-order sentence $\phi$: $$ f_{\phi}(c) = \lim_{n\rightarrow\infty}{\Pr}[U_{n,{c\over n}} { has\ property\ } \phi] $$ is an infinitely differentiable function. Further, let $S = \bigcap_c S_c$ be the set of all sentences that are true in every almost sure theory. Then, for every $c>0$, $S_c = S$.
Hook lengths in a skew Young diagram
Authors: Janson Svante
Published: January 2020

Regev and Vershik (Electronic J. Combinatorics 4 (1997), #R22) have obtained some properties of the set of hook lengths for certain skew Young diagrams, using asymptotic calculations of character degrees. They also conjectured a stronger form of one of their results. We give a simple inductive proof of this conjecture. Very recently, Regev and Zeilberger (Annals of Combinatorics, to appear) have independently proved this conjecture.
Generating Random Elements of Finite Distributive Lattices
Authors: Propp James
Published: January 2020

This survey article describes a method for choosing uniformly at random from any finite set whose objects can be viewed as constituting a distributive lattice. The method is based on ideas of the author and David Wilson for using "coupling from the past" to remove initialization bias from Monte Carlo randomization. The article describes several applications to specific kinds of combinatorial objects such as tilings, constrained lattice paths, an alternating sign matrices.
A construction for sets of integers with distinct subset sums
Authors: Bohman Tom
Published: January 2020

A set S of positive integers has distinct subset sums if there are $2^{|S|}$ distinct elements of the set $\left\{ \sum_{x \in X} x: X \subset S \right\} . $ Let $$f(n) = \min\{ \max S: |S|=n {\rm \hskip2mm and \hskip2mm} S {\rm \hskip2mm has \hskip2mm distinct \hskip2mm subset \hskip2mm sums}\}.$$ Erdős conjectured $ f(n) \ge c2^{n}$ for some constant c. We give a construction that yields $f(n) < 0.22002 \cdot 2^{n}$ for n sufficiently large. This now stands as the best known upper bound on $ f(n).$
Random Even Graphs
Authors: Grimmett Geoffrey , Janson Svante
Published: January 2020

We study a random even subgraph of a finite graph $G$ with a general edge-weight $p\in(0,1)$. We demonstrate how it may be obtained from a certain random-cluster measure on $G$, and we propose a sampling algorithm based on coupling from the past. A random even subgraph of a planar lattice undergoes a phase transition at the parameter-value ${1\over2} p_{\rm c}$, where $p_{\rm c}$ is the critical point of the $q=2$ random-cluster model on the dual lattice. The properties of such a graph are discussed, and are related to Schramm–Löwner evolutions (SLE).
Crooked Functions, Bent Functions, and Distance Regular Graphs
Authors: Bending T. D. , Fon-Der-Flaass D.
Published: January 2020

Let $V$ and $W$ be $n$-dimensional vector spaces over $GF(2)$. A mapping $Q:V\rightarrow W$ is called crooked if it satisfies the following three properties: $Q(0)=0$; $Q(x)+Q(y)+Q(z)+Q(x+y+z)\neq 0$ for any three distinct $x,y,z$; $Q(x)+Q(y)+Q(z)+Q(x+a)+Q(y+a)+Q(z+a)\neq 0$ if $a\neq 0$ ($x,y,z$ arbitrary). We show that every crooked function gives rise to a distance regular graph of diameter 3 having $\lambda=0$ and $\mu=2$ which is a cover of the complete graph. Our approach is a generalization of a recent construction found by de Caen, Mathon, and Moorhouse. We study graph-theoretical properties of the resulting graphs, including their automorphisms. Also we demonstrate a connection between crooked functions and bent functions.
Codes and Projective Multisets
Authors: Dodunekov Stefan , Simonis Juriaan
Published: January 2020

The paper gives a matrix-free presentation of the correspondence between full-length linear codes and projective multisets. It generalizes the Brouwer-Van Eupen construction that transforms projective codes into two-weight codes. Short proofs of known theorems are obtained. A new notion of self-duality in coding theory is explored.
A Criterion for Unimodality
Authors: Boros George , Moll Victor H.
Published: January 2020

We show that if $P(x)$ is a polynomial with nondecreasing, nonnegative coefficients, then the coefficient sequence of $P(x+1)$ is unimodal. Applications are given.
Nim-Regularity of Graphs
Authors: Reading Nathan
Published: January 2020

Ehrenborg and Steingrímsson defined simplicial Nim, and defined Nim-regular complexes to be simplicial complexes for which simplicial Nim has a particular type of winning strategy. We completely characterize the Nim-regular graphs by the exclusion of two vertex-induced subgraphs, the graph on three vertices with one edge and the graph on five vertices which is complete except for one missing edge. We show that all Nim-regular graphs have as their basis the set of disjoint unions of circuits (minimal non-faces) of the graph.
Diagonal Checker-jumping and Eulerian Numbers for Color-signed Permutations
Authors: Eriksen Niklas , Eriksson Henrik , Eriksson Kimmo
Published: January 2020

We introduce color-signed permutations to obtain a very explicit combinatorial interpretation of the $q$-Eulerian identities of Brenti and some generalizations. In particular, we prove an identity involving the golden ratio, which allows us to compute upper bounds on how high a checker can reach in a classical checker-jumping problem, when the rules are relaxed to allow also diagonal jumps.
Restricted set addition in groups, II. A generalization of the Erdős-Heilbronn conjecture
Authors: Lev Vsevolod F.
Published: January 2020

In 1980, Erdős and Heilbronn posed the problem of estimating (from below) the number of sums $a+b$ where $a\in A$ and $b\in B$ range over given sets $A,B\subseteq{\Bbb Z}/p{\Bbb Z}$ of residues modulo a prime $p$, so that $a\neq b$. A solution was given in 1994 by Dias da Silva and Hamidoune. In 1995, Alon, Nathanson and Ruzsa developed a polynomial method that allows one to handle restrictions of the type $f(a,b)\neq 0$, where $f$ is a polynomial in two variables over ${\Bbb Z}/p{\Bbb Z}$. In this paper we consider restricting conditions of general type and investigate groups, distinct from ${\Bbb Z}/p{\Bbb Z}$. In particular, for $A,B\subseteq{\Bbb Z}/p{\Bbb Z}$ and ${\cal R}\subseteq A\times B$ of given cardinalities we give a sharp estimate for the number of distinct sums $a+b$ with $(a,b)\notin\ {\cal R}$, and we obtain a partial generalization of this estimate for arbitrary Abelian groups.
Online Coloring Known Graphs
Authors: Halldórsson M. M.
Published: January 2020

The problem of online coloring an unknown graph is known to be hard. Here we consider the problem of online coloring in the relaxed situation where the input must be isomorphic to a given known graph. All that foils a computationally powerful player is that it is not known to which sections of the graph the vertices to be colored belong. We show that the performance ratio of any online coloring algorithm with advance knowledge of the input graph is at least $\Omega(N/\log^2 N)$, where $N$ is the number of vertices. This matches and generalizes the bound for the case of an unknown input graph. We also show that any online independent set algorithm has a performance ratio at least $N/8$.
Evolutionary Families of Sets
Authors: Little C. H. C. , Campbell A. E.
Published: January 2020

A finite family of subsets of a finite set is said to be evolutionary if its members can be ordered so that each subset except the first has an element in the union of the previous subsets and also an element not in that union. The study of evolutionary families is motivated by a conjecture of Naddef and Pulleyblank concerning ear decompositions of 1-extendable graphs. The present paper gives some sufficient conditions for a family to be evolutionary.
Trees and Matchings
Authors: Kenyon Richard W. , Propp James G. , Wilson David B.
Published: January 2020

In this article, Temperley's bijection between spanning trees of the square grid on the one hand, and perfect matchings (also known as dimer coverings) of the square grid on the other, is extended to the setting of general planar directed (and undirected) graphs, where edges carry nonnegative weights that induce a weighting on the set of spanning trees. We show that the weighted, directed spanning trees (often called arborescences) of any planar graph $G$ can be put into a one-to-one weight-preserving correspondence with the perfect matchings of a related planar graph $H$. One special case of this result is a bijection between perfect matchings of the hexagonal honeycomb lattice and directed spanning trees of a triangular lattice. Another special case gives a correspondence between perfect matchings of the "square-octagon" lattice and directed weighted spanning trees on a directed weighted version of the cartesian lattice. In conjunction with results of Kenyon [1997b], our main theorem allows us to compute the measures of all cylinder events for random spanning trees on any (directed, weighted) planar graph. Conversely, in cases where the perfect matching model arises from a tree model, Wilson's algorithm allows us to quickly generate random samples of perfect matchings.
Hook Length Formulas for Trees by Han's Expansion
Authors: Chen William Y.C. , Gao Oliver X.Q. , Guo Peter L.
Published: January 2020

Recently Han obtained a general formula for the weight function corresponding to the expansion of a series in terms of hook lengths of binary trees. In this paper, we present weight function formulas for $k$-ary trees, plane trees, plane forests, labeled trees and forests. We also find appropriate generating functions which lead to unifications of the hook length formulas due to Du and Liu, Han, Gessel and Seo, and Postnikov.
On Planar Mixed Hypergraphs
Authors: Dvořák Zdeněk , Král' Daniel
Published: January 2020

A mixed hypergraph $H$ is a triple $(V,{\cal C},{\cal D})$ where $V$ is its vertex set and ${\cal C}$ and ${\cal D}$ are families of subsets of $V$, ${\cal C}$–edges and ${\cal D}$–edges. A mixed hypergraph is a bihypergraph iff ${\cal C}={\cal D}$. A hypergraph is planar if its bipartite incidence graph is planar. A vertex coloring of $H$ is proper if each ${\cal C}$–edge contains two vertices with the same color and each ${\cal D}$–edge contains two vertices with different colors. The set of all $k$'s for which there exists a proper coloring using exactly $k$ colors is the feasible set of $H$; the feasible set is called gap-free if it is an interval. The minimum (maximum) number of the feasible set is called a lower (upper) chromatic number. We prove that the feasible set of any planar mixed hypergraph without edges of size two and with an edge of size at least four is gap-free. We further prove that a planar mixed hypergraph with at most two ${\cal D}$–edges of size two is two-colorable. We describe a polynomial-time algorithm to decide whether the lower chromatic number of a planar mixed hypergraph equals two. We prove that it is NP-complete to find the upper chromatic number of a mixed hypergraph even for 3-uniform planar bihypergraphs. In order to prove the latter statement, we prove that it is NP-complete to determine whether a planar 3-regular bridgeless graph contains a $2$-factor with at least a given number of components.
Relaxed Graceful Labellings of Trees
Authors: Van Bussel Frank
Published: January 2020

A graph $G$ on $m$ edges is considered graceful if there is a labelling $f$ of the vertices of $G$ with distinct integers in the set $\{0,1,\dots,m\}$ such that the induced edge labelling $g$ defined by $g(uv)=|f(u)-f(v)|$ is a bijection to $\{1,\dots,m\}$. We here consider some relaxations of these conditions as applied to tree labellings: 1. Edge-relaxed graceful labellings, in which repeated edge labels are allowed, 2. Range-relaxed graceful labellings, in which the upper bound $m'$ is allowed to go higher than the number of edges, and 3. Vertex-relaxed graceful labellings, in which repeated vertex labels are allowed. The first of these had been looked at by Rosa and Širáň (1995). Here some linear bounds in the relevant metrics are given for range-relaxed and vertex-relaxed graceful labellings.
Non-Repetitive Tilings
Authors: Currie James D. , Simpson Jamie
Published: January 2020

In 1906 Axel Thue showed how to construct an infinite non-repetitive (or square-free) word on an alphabet of size 3. Since then this result has been rediscovered many times and extended in many ways. We present a two-dimensional version of this result. We show how to construct a rectangular tiling of the plane using 5 symbols which has the property that lines of tiles which are horizontal, vertical or have slope +1 or $-1$ contain no repetitions. As part of the construction we introduce a new type of word, one that is non-repetitive up to mod k, which is of interest in itself. We also indicate how our results might be extended to higher dimensions.
On the Excluded Minors for Matroids of Branch-Width Three
Authors: Hliněný Petr
Published: January 2020

Knowing the excluded minors for a minor-closed matroid property provides a useful alternative characterization of that property. It has been shown in [R. Hall, J. Oxley, C. Semple, G. Whittle, On Matroids of Branch-Width Three, submitted 2001] that if $M$ is an excluded minor for matroids of branch-width $3$, then $ M$ has at most $14$ elements. We show that there are exactly $10$ such binary matroids $M$ (7 of which are regular), proving a conjecture formulated by Dharmatilake in 1994. We also construct numbers of such ternary and quaternary matroids $ M$, and provide a simple practical algorithm for finding a width-$3$ branch-decomposition of a matroid. The arguments in our paper are computer-assisted — we use a program $MACEK$ [P. Hliněný, The MACEK Program, http://www.mcs.vuw.ac.nz/research/macek, 2002] for structural computations with represented matroids. Unfortunately, it seems to be infeasible to search through all matroids on at most $14$ elements.
On the Connectivity of Graphs Embedded in Surfaces II
Authors: Plummer Michael D. , Zha Xiaoya
Published: January 2020

Let $\kappa_{max}(\Sigma)$ denote the maximum value for the connectivity of any graph which embeds in the topological surface $\Sigma$. The connectivity interval for $\Sigma$ is the set of integers in the interval $[1,\kappa_{max}(\Sigma)]$. Given an integer $i$ in $[1,\kappa_{max}(\Sigma)]$ it is a trivial problem to demonstrate that there is a graph $G_i$ with connectivity $i$ which also embeds in $\Sigma$. We will say that one can saturate the connectivity interval in this case. Note that no restrictions have been placed on the embeddings in the above problem, however. What if we demand that the embeddings in question be 2-cell or even that they be genus embeddings? The problem of saturating the connectivity interval for 2-cell embeddings will be solved completely in the present work. In connection with the apparently much harder saturation question for genus embeddings, it will be shown that one can always saturate the subinterval $[1,\lfloor 0.7\kappa_{max}(\Sigma)\rfloor]$.
Parking Functions of Types A and B
Authors: Biane P.
Published: January 2020

The lattice of noncrossing partitions can be embedded into the Cayley graph of the symmetric group. This allows us to rederive connections between noncrossing partitions and parking functions. We use an analogous embedding for type B non-crossing partitions in order to answer a question raised by R. Stanley on the edge labeling of the type B non-crossing partitions lattice.
On the Diagram of Schröder Permutations
Authors: Reifegerste Astrid
Published: January 2020

Egge and Mansour have recently studied permutations which avoid $1243$ and $2143$ regarding the occurrence of certain additional patterns. Some of the open questions related to their work can easily be answered by using permutation diagrams. As for $132$-avoiding permutations the diagram approach gives insights into the structure of $\{1243,2143\}$-avoiding permutations that yield simple proofs for some enumerative results concerning forbidden patterns in such permutations.
Bent Hamilton Cycles in $d$-Dimensional Grid Graphs
Authors: Ruskey F. , Sawada Joe
Published: January 2020

A bent Hamilton cycle in a grid graph is one in which each edge in a successive pair of edges lies in a different dimension. We show that the $d$-dimensional grid graph has a bent Hamilton cycle if some dimension is even and $d \geq 3$, and does not have a bent Hamilton cycle if all dimensions are odd. In the latter case, we determine the conditions for when a bent Hamilton path exists. For the $d$-dimensional toroidal grid graph (i.e., the graph product of $d$ cycles), we show that there exists a bent Hamilton cycle when all dimensions are odd and $d \geq 3$. We also show that if $d=2$, then there exists a bent Hamilton cycle if and only if both dimensions are even.
A New Class of q-Fibonacci Polynomials
Authors: Cigler Johann
Published: January 2020

We introduce a new $q$-analogue of the Fibonacci polynomials and derive some of its properties. Extra attention is paid to a special case which has some interesting connections with Euler's pentagonal number theorem.
Some Families of Orthogonal Polynomials of a Discrete Variable and their Applications to Graphs and Codes
Authors: Cámara M. , Fàbrega J. , Fiol M. A. , Garriga E.
Published: January 2020

We present some related families of orthogonal polynomials of a discrete variable and survey some of their applications in the study of (distance-regular) graphs and (completely regular) codes. One of the main peculiarities of such orthogonal systems is their non-standard normalization condition, requiring that the square norm of each polynomial must equal its value at a given point of the mesh. For instance, when they are defined from the spectrum of a graph, one of these families is the system of the predistance polynomials which, in the case of distance-regular graphs, turns out to be the sequence of distance polynomials. The applications range from (quasi-spectral) characterizations of distance-regular graphs, walk-regular graphs, local distance-regularity and completely regular codes, to some results on representation theory.
On Randomly Generated Intersecting Hypergraphs
Authors: Bohman Tom , Cooper Colin , Frieze Alan , Martin Ryan , Ruszinkó Miklós
Published: January 2020

Let $c$ be a positive constant. We show that if $r=\lfloor{cn^{1/3}}\rfloor$ and the members of ${[n]\choose r}$ are chosen sequentially at random to form an intersecting hypergraph then with limiting probability $(1+c^3)^{-1}$, as $n\to\infty$, the resulting family will be of maximum size ${n-1\choose r-1}$.
Bounds for DNA Codes with Constant GC-Content
Authors: King Oliver D.
Published: January 2020

We derive theoretical upper and lower bounds on the maximum size of DNA codes of length $n$ with constant GC-content $w$ and minimum Hamming distance $d$, both with and without the additional constraint that the minimum Hamming distance between any codeword and the reverse-complement of any codeword be at least $d$. We also explicitly construct codes that are larger than the best previously-published codes for many choices of the parameters $n$, $d$ and $w$.
Matrix-Free Proof of a Regularity Characterization
Authors: Czygrinow A. , Nagle B.
Published: January 2020

The central concept in Szemerédi's powerful regularity lemma is the so-called $\epsilon$-regular pair. A useful statement of Alon et al. essentially equates the notion of an $\epsilon$-regular pair with degree uniformity of vertices and pairs of vertices. The known proof of this characterization uses a clever matrix argument. This paper gives a simple proof of the characterization without appealing to the matrix argument of Alon et al. We show the $\epsilon$-regular characterization follows from an application of Szemerédi's regularity lemma itself.
Correspondence between two Antimatroid Algorithmic Characterizations
Authors: Kempner Yulia , Levit Vadim E.
Published: January 2020

The basic distinction between already known algorithmic characterizations of matroids and antimatroids is in the fact that for antimatroids the ordering of elements is of great importance.While antimatroids can also be characterized as set systems, the question whether there is an algorithmic description of antimatroids in terms of sets and set functions was open for some period of time.This article provides a selective look at classical material on algorithmic characterization of antimatroids, i.e., the ordered version, and a new unordered version. Moreover we empathize formally the correspondence between these two versions.
Domination, Packing and Excluded Minors
Authors: Böhme Thomas , Mohar Bojan
Published: January 2020

Let $\gamma(G)$ be the domination number of a graph $G$, and let $\alpha_k(G)$ be the maximum number of vertices in $G$, no two of which are at distance $\le k$ in $G$. It is easy to see that $\gamma(G)\ge \alpha_2(G)$. In this note it is proved that $\gamma(G)$ is bounded from above by a linear function in $\alpha_2(G)$ if $G$ has no large complete bipartite graph minors. Extensions to other parameters $\alpha_k(G)$ are also derived.
On Hypergraphs with Every Four Points Spanning at Most Two Triples
Authors: Mubayi Dhruv
Published: January 2020

Let ${\cal F}$ be a triple system on an $n$ element set. Suppose that ${\cal F}$ contains more than $(1/3-\epsilon){n\choose 3}$ triples, where $\epsilon>10^{-6}$ is explicitly defined and $n$ is sufficiently large. Then there is a set of four points containing at least three triples of ${\cal F}$. This improves previous bounds of de Caen and Matthias.
On the Generation and Enumeration of some Classes of Convex Polyominoes
Authors: Del Lungo A. , Duchi E. , Frosini A. , Rinaldi S.
Published: January 2020

ECO is a method for the recursive generation, and thereby also the enumeration of classes of combinatorial objects. It has already found successful application in recent literature both to the exhaustive generation and to the uniform random generation of various objects classified according to several parameters of interest, as well as to their enumeration. In this paper we extend this approach to the generation and enumeration of some classes of convex polyominoes. We begin with a review of the ECO method and of the closely related notion of a succession rule. From this background, we develop the following principal findings: i) ECO constructions for both column-convex and convex polyominoes; ii) translations of these constructions into succession rules; iii) the consequent deduction of the generating functions of column-convex and of convex polyominoes according to their semi-perimeter, first of all analytically by means of the so-called kernel method, and then in a more novel manner by drawing on some ideas of Fedou and Garcia; iv) algorithms for the exhaustive generation of column convex and of convex polyominoes which are based on the ECO constructions of these object and which are shown to run in constant amortized time.
Locally Primitive Normal Cayley Graphs of Metacyclic Groups
Authors: Pan Jiangmin
Published: January 2020

A complete characterization of locally primitive normal Cayley graphs of metacyclic groups is given. Namely, let $\Gamma={\rm Cay}(G,S)$ be such a graph, where $G\cong{\Bbb Z}_m.{\Bbb Z}_n$ is a metacyclic group and $m=p_1^{r_1}p_2^{r_2}\cdots p_t^{r_t}$ such that $p_1 < p_2 < \dots < p_t$. It is proved that $G\cong D_{2m}$ is a dihedral group, and $val(\Gamma)=p$ is a prime such that $p|(p_1(p_1-1),p_2-1,\dots,p_t-1)$. Moreover, three types of graphs are constructed which exactly form the class of locally primitive normal Cayley graphs of metacyclic groups.
The Inverse Erdős-Heilbronn Problem
Authors: Vu Van H. , Wood Philip Matchett
Published: January 2020

The famous Erdős-Heilbronn conjecture (first proved by Dias da Silva and Hamidoune in 1994) asserts that if $A$ is a subset of ${\Bbb Z}/p{\Bbb Z}$, the cyclic group of the integers modulo a prime $p$, then $|A\widehat{+}A| \ge \min\{2|A| -3,p\}. $ The bound is sharp, as is shown by choosing $A$ to be an arithmetic progression. A natural inverse result was proven by Karolyi in 2005: if $A\subset {\Bbb Z}/p{\Bbb Z}$ contains at least 5 elements and $|A\widehat{+}A| \le 2|A| -3 < p$, then $A$ must be an arithmetic progression. We consider a large prime $p$ and investigate the following more general question: what is the structure of sets $A \subset {\Bbb Z}/p{\Bbb Z}$ such that $|A\widehat{+}A| \le (2+\epsilon)|A|$? Our main result is an asymptotically complete answer to this question: there exists a function $\delta(p) = o(1)$ such that if $200 < |A| \le (1-\epsilon')p/2$ and if $|A\widehat{+}A| \le (2+\epsilon)|A|$, where $\epsilon' -\epsilon \ge \delta > 0$, then $A$ is contained in an arithmetic progression of length $|A\widehat{+}A| -|A| + 3$. With the extra assumption that $|A| \le ({1\over 2}- {1\over\log^c p} ) p$, our main result has Dias da Silva and Hamidoune's theorem and Karolyi's theorem as corollaries, and thus, our main result provides purely combinatorial proofs for the Erdős-Heilbronn conjecture and an inverse Erdős-Heilbronn theorem.
Degree Powers in Graphs with a Forbidden Even Cycle
Authors: Nikiforov Vladimir
Published: January 2020

Let $C_{l}$ denote the cycle of length $l$. For $p\geq2$ and integer $k\geq1$, we prove that the function $$ \phi\left( k,p,n\right) =\max_G\left\{ \sum_{u\in V\left( G\right) } d^{p}\left( u\right)\right\} $$ (where the maximum is over graphs $G$ of order $n$ containing no $C_{2k+2}$) satisfies $\phi\left( k,p,n\right) =kn^{p}\left( 1+o\left( 1\right) \right)$. This settles a conjecture of Caro and Yuster. Our proof is based on a new sufficient condition for long paths.
Linear Recurrences and Asymptotic Behavior of Exponential Sums of Symmetric Boolean Functions
Authors: Castro Francis N. , Medina Luis A.
Published: January 2020

In this paper we give an improvement of the degree of the homogeneous linear recurrence with integer coefficients that exponential sums of symmetric Boolean functions satisfy. This improvement is tight. We also compute the asymptotic behavior of symmetric Boolean functions and provide a formula that allows us to determine if a symmetric boolean function is asymptotically not balanced. In particular, when the degree of the symmetric function is a power of two, then the exponential sum is much smaller than $2^n$.
Alternating Sign Matrices and Polynomiography
Authors: Kalantari Bahman
Published: January 2020

To each permutation matrix we associate a complex permutation polynomial with roots at lattice points corresponding to the position of the ones. More generally, to an alternating sign matrix (ASM) we associate a complex alternating sign polynomial. On the one hand visualization of these polynomials through polynomiography, in a combinatorial fashion, provides for a rich source of algorithmic art-making, interdisciplinary teaching, and even leads to games. On the other hand, this combines a variety of concepts such as symmetry, counting and combinatorics, iteration functions and dynamical systems, giving rise to a source of research topics. More generally, we assign classes of polynomials to matrices in the Birkhoff and ASM polytopes. From the characterization of vertices of these polytopes, and by proving a symmetry-preserving property, we argue that polynomiography of ASMs form building blocks for approximate polynomiography for polynomials corresponding to any given member of these polytopes. To this end we offer an algorithm to express any member of the ASM polytope as a convex of combination of ASMs. In particular, we can give exact or approximate polynomiography for any Latin Square or Sudoku solution. We exhibit some images.
Monotone Triangles and 312 Pattern Avoidance
Authors: Ayyer Arvind , Cori Robert , Gouyou-Beauchamps Dominique
Published: January 2020

We demonstrate a natural bijection between a subclass of alternating sign matrices (ASMs) defined by a condition on the corresponding monotone triangle which we call the gapless condition and a subclass of totally symmetric self-complementary plane partitions defined by a similar condition on the corresponding fundamental domains or Magog triangles. We prove that, when restricted to permutations, this class of ASMs reduces to 312-avoiding permutations. This leads us to generalize pattern avoidance on permutations to a family of words associated to ASMs, which we call Gog words. We translate the gapless condition on monotone triangles into a pattern avoidance-like condition on Gog words associated. We estimate the number of gapless monotone triangles using a bijection with $p$-branchings.
Automorphism Groups of Rational Circulant Graphs
Authors: Klin Mikhail , Kovács István
Published: January 2020

The paper concerns the automorphism groups of Cayley graphs over cyclic groups which have a rational spectrum (rational circulant graphs for short). With the aid of the techniques of Schur rings it is shown that the problem is equivalent to consider the automorphism groups of orthogonal group block structures of cyclic groups. Using this observation, the required groups are expressed in terms of generalized wreath products of symmetric groups.
The Chromatic Number and the Least Eigenvalue of a Graph
Authors: Fan Yi-Zheng , Yu Gui-Dong , Wang Yi
Published: January 2020

In this paper we get a structural property for a graph having the minimal least eigenvalue among all graphs of fixed order and given chromatic number, and characterize such graphs under the condition that the chromatic number is not larger than half the order of the graph.  As a result, we obtain a lower bound on the least eigenvalue in terms of the chromatic number, and an upper bound on the chromatic number in terms of the least eigenvalue of a graph.
The Full Automorphism Group of Cayley Graphs of $\mathbb{Z}_p\times\mathbb{Z}_{p^2}$
Authors: Dobson Edward
Published: January 2020

Let $p\ge 5$ be prime.  We determine the full automorphism groups of Cayley digraphs of $\mathbb{Z}_p\times\mathbb{Z}_{p^2}$.
Some Remarks on the Joint Distribution of Descents and Inverse Descents
Authors: Visontai Mirkó
Published: January 2020

We study the joint distribution of descents and inverse descents over the set of permutations of $n$ letters. Gessel conjectured that the two-variable generating function of this distribution can be expanded in a given basis with nonnegative integer coefficients. We investigate the action of the Eulerian operators that give the recurrence for these generating functions. As a result we devise a recurrence for the coefficients in question but are unable to settle the conjecture.  We examine generalizations of the conjecture and obtain a type $B$ analog of the recurrence satisfied by the two-variable generating function. We also exhibit some connections to cyclic descents and cyclic inverse descents. Finally, we propose a combinatorial model for the joint distribution of descents and inverse descents in terms of statistics on inversion sequences.
Hamiltonicity of Minimum Distance Graphs of 1-Perfect Codes
Authors: Romanov Alexander Mikhailovich
Published: January 2020

A 1-perfect code $\mathcal{C}_{q}^{n}$ is called Hamiltonian if its minimum distance graph $G(\mathcal{C}_{q}^{n})$ contains a Hamiltonian cycle. In this paper, for  all admissible lengths $n \geq 13$, we construct   Hamiltonian nonlinear ternary 1-perfect  codes,   and for  all admissible lengths $n \geq 21$, we construct  Hamiltonian nonlinear quaternary 1-perfect  codes. The existence of Hamiltonian nonlinear $q$-ary 1-perfect  codes of length $N = qn + 1$ is reduced to the question of the existence of such codes of length $n$. Consequently,  for   $q = p^r$, where $p$ is prime, $r \geq 1$ there exist Hamiltonian nonlinear $q$-ary 1-perfect  codes of length $n = (q ^{m} -1) / (q-1)$, $m \geq 2$. If $q =2, 3, 4$, then $ m \neq 2$.  If $q =2$, then $ m \neq 3$.
Generalized Galois Numbers, Inversions, Lattice Paths, Ferrers Diagrams and Limit Theorems
Authors: Janson Svante
Published: January 2020

Bliem and Kousidis recently considered a family of random variables whose distributions are given by the generalized Galois numbers (after normalization). We give probabilistic interpretations of these random variables, using inversions in random words, random lattice paths and random Ferrers diagrams, and use these to give new proofs of limit theorems as well as some further limit results.
Random Threshold Graphs
Authors: Reilly Elizabeth Perez , Scheinerman Edward R.
Published: January 2020

We introduce a pair of natural, equivalent models for random threshold graphs and use these models to deduce a variety of properties of random threshold graphs. Specifically, a random threshold graph $G$ is generated by choosing $n$ IID values $x_1,\ldots,x_n$ uniformly in $[0,1]$; distinct vertices $i,j$ of $G$ are adjacent exactly when $x_i + x_j \ge 1$. We examine various properties of random threshold graphs such as chromatic number, algebraic connectivity, and the existence of Hamiltonian cycles and perfect matchings.
An Algebraic Exploration of Dominating Sets and Vizing's Conjecture
Authors: Margulies Susan , Hicks I. V.
Published: January 2020

Systems of polynomial equations are commonly used to model combinatorial problems such as independent set, graph coloring, Hamiltonian path, and others. We formulate the dominating set problem as a system of polynomial equations in two different ways: first, as a single, high-degree polynomial, and second as a collection of polynomials based on the complements of domination-critical graphs. We then provide a sufficient criterion for demonstrating that a particular ideal representation is already the universal Grobner bases of an ideal, and show that the second representation of the dominating set ideal in terms of domination-critical graphs is the universal Grobner basis for that ideal. We also present the first algebraic formulation of Vizing's conjecture, and discuss the theoretical and computational ramifications to this conjecture when using either of the two dominating set representations described above.
Multiple Petersen Subdivisions in Permutation Graphs
Authors: Kaiser Tomáš , Sereni Jean-Sébastien , Yilma Zelealem B.
Published: January 2020

A permutation graph is a cubic graph admitting a 1-factor $M$ whose complement consists of two chordless cycles. Extending results of Ellingham and of Goldwasser and Zhang, we prove that if $e$ is an edge of $M$ such that every 4-cycle containing an edge of $M$ contains $e$, then $e$ is contained in a subdivision of the Petersen graph of a special type. In particular, if the graph is cyclically 5-edge-connected, then every edge of $M$ is contained in such a subdivision. Our proof is based on a characterization of cographs in terms of twin vertices. We infer a linear lower bound on the number of Petersen subdivisions in a permutation graph with no 4-cycles, and give a construction showing that this lower bound is tight up to a constant factor.
From Heaps of Matches to the Limits of Computability
Authors: Larsson Urban , Wästlund Johan
Published: January 2020

We study so-called invariant games played with a fixed number $d$ of heaps of matches. A game is described by a finite list $\mathcal{M}$ of integer vectors of length $d$ specifying the legal moves. A move consists in changing the current game-state by adding one of the vectors in $\mathcal{M}$, provided all elements of the resulting vector are nonnegative. For instance, in a two-heap game, the vector $(1,-2)$ would mean adding one match to the first heap and removing two matches from the second heap. If $(1,-2) \in \mathcal{M}$, such a move would be permitted provided there are at least two matches in the second heap. Two players take turns, and a player unable to make a move loses. We show that these games embrace computational universality, and that therefore a number of basic questions about them are algorithmically undecidable. In particular, we prove that there is no algorithm that takes two games $\mathcal{M}$ and $\mathcal{M}'$ (with the same number of heaps) as input, and determines whether or not they are equivalent in the sense that every starting-position which is a first player win in one of the games is a first player win in the other.
Arithmetic Properties of Overpartition Pairs into Odd Parts
Authors: Lin Lishuang
Published: January 2020

In this work, we investigate various arithmetic properties of the function $\overline{pp}_o(n)$, the number of overpartition pairs of $n$ into odd parts. We obtain a number of Ramanujan type congruences modulo small powers of $2$ for $\overline{pp}_o(n)$. For a fixed positive integer $k$, we further show that $\overline{pp}_o(n)$ is divisible by $2^k$ for almost all $n$. We also find several infinite families of congruences for $\overline{pp}_o(n)$ modulo $3$ and two formulae for $\overline{pp}_o(6n+3)$  and  $\overline{pp}_o(12n)$ modulo $3$.
Set Families with a Forbidden Subposet
Authors: Bukh Boris
Published: January 2020

We asymptotically determine the size of the largest family $\cal F$ of subsets of $\{1,\dots,n\}$ not containing a given poset $P$ if the Hasse diagram of $P$ is a tree. This is a qualitative generalization of several known results including Sperner's theorem.
On Codes that are Invariant under the Affine Group
Authors: Sin Peter
Published: January 2020

Let $k[V]$ be the space of functions from a finite vector space into the algebraically closure of its field of scalars. This paper describes the lattice of subspaces of $k[V]$ which are invariant under the affine group ${\mathrm AGL}(V)$. The description provides a simple method for finding the submodule generated by any set of functions given as polynomials in the standard coordinates.
Gelfand–Graev Characters of the Finite Unitary Groups
Authors: Thiem Nathaniel , Vinroot C. Ryan
Published: January 2020

Gelfand–Graev characters and their degenerate counterparts have an important role in the representation theory of finite groups of Lie type. Using a characteristic map to translate the character theory of the finite unitary groups into the language of symmetric functions, we study degenerate Gelfand–Graev characters of the finite unitary group from a combinatorial point of view. In particular, we give the values of Gelfand–Graev characters at arbitrary elements, recover the decomposition multiplicities of degenerate Gelfand–Graev characters in terms of tableau combinatorics, and conclude with some multiplicity consequences.
Some Results on Chromaticity of Quasi-Linear Paths and Cycles
Authors: Tomescu Ioan
Published: January 2020

Let $r\geq 1$ be an integer. An $h$-hypergraph $H$ is said to be $r$-quasi-linear (linear for $r=1$) if any two edges of $H$ intersect in 0 or $r$ vertices. In this paper it is shown that $r$-quasi-linear paths $P_{m}^{h,r}$ of length $m\geq 1$ and cycles $C_{m}^{h,r}$ of length $m\geq 3$ are chromatically unique in the set of $h$-uniform $r$-quasi-linear hypergraphs provided $r\geq 2$ and $h\geq 3r-1$.