bluuebunny/crossref_metadata_2025 huggingface dataset:
New Bounds for Codes Identifying Vertices in Graphs
Authors: Cohen Gérard , Honkala Iiro , Lobstein Antoine , Zémor Gilles
Published: January 2020

Let $G=(V,E)$ be an undirected graph. Let $C$ be a subset of vertices that we shall call a code. For any vertex $v\in V$, the neighbouring set $N(v,C)$ is the set of vertices of $C$ at distance at most one from $v$. We say that the code $C$ identifies the vertices of $G$ if the neighbouring sets $N(v,C), v\in V,$ are all nonempty and different. What is the smallest size of an identifying code $C$ ? We focus on the case when $G$ is the two-dimensional square lattice and improve previous upper and lower bounds on the minimum size of such a code.
An infinite Family of Non-embeddable Hadamard Designs
Authors: Mackenzie-Fleming K.
Published: January 2020

The parameters $2$ - $(2\lambda+2,\lambda+1,\lambda)$ are those of a residual Hadamard $2$ - $(4\lambda+3,2\lambda+1,\lambda)$ design. All $2$ - $(2\lambda+2,\lambda+1,\lambda)$ designs with $\lambda \le 4$ are embeddable. The existence of non-embeddable Hadamard $2$-designs has been determined for the cases $\lambda = 5$, $\lambda = 6$, and $\lambda = 7$. In this paper the existence of an infinite family of non-embeddable $2$ - $(2\lambda+2,\lambda+1,\lambda)$ designs, $\lambda = 3(2^m) - 1, m \ge 1$ is established.
Products of All Elements in a Loop and a Framework for Non-Associative Analogues of the Hall-Paige Conjecture
Authors: Pula Kyle
Published: January 2020

For a finite loop $Q$, let $P(Q)$ be the set of elements that can be represented as a product containing each element of $Q$ precisely once. Motivated by the recent proof of the Hall-Paige conjecture, we prove several universal implications between the following conditions: (A) $Q$ has a complete mapping, i.e. the multiplication table of $Q$ has a transversal, (B) there is no $N \trianglelefteq Q$ such that $|N|$ is odd and $Q/N \cong {\Bbb Z}_{2^m}$ for $m \geq 1$, and (C) $P(Q)$ intersects the associator subloop of $Q$. We prove $(A) \Longrightarrow (C)$ and $(B) \Longleftrightarrow (C)$ and show that when $Q$ is a group, these conditions reduce to familiar statements related to the Hall-Paige conjecture (which essentially says that in groups $(B) \Longrightarrow (A))$. We also establish properties of $P(Q)$, prove a generalization of the Dénes-Hermann theorem, and present an elementary proof of a weak form of the Hall-Paige conjecture.
Wilf-Equivalence on $k$-ary Words, Compositions, and Parking Functions
Authors: Jelínek Vít , Mansour Toufik
Published: January 2020

In this paper, we study pattern-avoidance in the set of words over the alphabet $[k]$. We say that a word $w\in[k]^n$ contains a pattern $\tau\in[\ell]^m$, if $w$ contains a subsequence order-isomorphic to $\tau$. This notion generalizes pattern-avoidance in permutations. We determine all the Wilf-equivalence classes of word patterns of length at most six. We also consider analogous problems within the set of integer compositions and the set of parking functions, which may both be regarded as special types of words, and which contain all permutations. In both these restricted settings, we determine the equivalence classes of all patterns of length at most five. As it turns out, the full classification of these short patterns can be obtained with only a few general bijective arguments, which are applicable to patterns of arbitrary size.
Stability of Kronecker Products of Irreducible Characters of the Symmetric Group
Authors: Vallejo Ernesto
Published: January 2020

F. Murnaghan observed a long time ago that the computation of the decompositon of the Kronecker product $\chi^{(n-a, \lambda_2, \dots )}\otimes \chi^{(n-b, \mu_2, \dots)}$ of two irreducible characters of the symmetric group into irreducibles depends only on $\overline\lambda=(\lambda_2,\dots )$ and $\overline\mu =(\mu_2,\dots )$, but not on $n$. In this note we prove a similar result: given three partitions $\lambda$, $\mu$, $\nu$ of $n$ we obtain a lower bound on $n$, depending on $\overline\lambda$, $\overline\mu$, $\overline\nu$, for the stability of the multiplicity $c(\lambda,\mu,\nu)$ of $\chi^\nu$ in $\chi^\lambda \otimes \chi^\mu$. Our proof is purely combinatorial. It uses a description of the $c(\lambda,\mu,\nu)$'s in terms of signed special rim hook tabloids and Littlewood-Richardson multitableaux.
List Edge-Colorings of Series-Parallel Graphs
Authors: Juvan Martin , Mohar Bojan , Thomas Robin
Published: January 2020

It is proved that for every integer $k\ge3$, for every (simple) series-parallel graph $G$ with maximum degree at most $k$, and for every collection $(L(e):e\in E(G))$ of sets, each of size at least $k$, there exists a proper edge-coloring of $G$ such that for every edge $e\in E(G)$, the color of $e$ belongs to $L(e)$.
A Note on the Symmetric Powers of the Standard Representation of $S_n$
Authors: Savitt D. , Stanley R. P.
Published: January 2020

In this paper, we prove that the dimension of the space span- ned by the characters of the symmetric powers of the standard $n$-dimensional representation of $S_n$ is asymptotic to $n^2 / 2$. This is proved by using generating functions to obtain formulas for upper and lower bounds, both asymptotic to $n^2/2$, for this dimension. In particular, for $n \ge 7$, these characters do not span the full space of class functions on $S_n$.
Counting Nondecreasing Integer Sequences that Lie Below a Barrier
Authors: Pemantle Robin , Wilf Herbert S.
Published: January 2020

Given a barrier $0 \leq b_0 \leq b_1 \leq \cdots$, let $f(n)$ be the number of nondecreasing integer sequences $0 \leq a_0 \leq a_1 \leq \cdots \leq a_n$ for which $a_j \leq b_j$ for all $0 \leq j \leq n$. Known formulæ for $f(n)$ include an $n \times n$ determinant whose entries are binomial coefficients (Kreweras, 1965) and, in the special case of $b_j = rj+s$, a short explicit formula (Proctor, 1988, p.320). A relatively easy bivariate recursion, decomposing all sequences according to $n$ and $a_n$, leads to a bivariate generating function, then a univariate generating function, then a linear recursion for $\{ f(n) \}$. Moreover, the coefficients of the bivariate generating function have a probabilistic interpretation, leading to an analytic inequality which is an identity for certain values of its argument.
Low Rank Co-Diagonal Matrices and Ramsey Graphs
Authors: Grolmusz Vince
Published: January 2020

We examine $n\times n$ matrices over $Z_m$, with 0's in the diagonal and nonzeros elsewhere. If $m$ is a prime, then such matrices have large rank (i.e., $n^{1/(p-1)}-O(1)$ ). If $m$ is a non-prime-power integer, then we show that their rank can be much smaller. For $m=6$ we construct a matrix of rank $\exp(c\sqrt{\log n\log \log n})$. We also show, that explicit constructions of such low rank matrices imply explicit constructions of Ramsey graphs.
An Improved Inequality Related to Vizing's Conjecture
Authors: Suen Stephen , Tarr Jennifer
Published: January 2020

Vizing conjectured in 1963 that $\gamma(G \Box H) \geq \gamma(G)\gamma(H)$ for any graphs $G$ and $H$. A graph $G$ is said to satisfy Vizing's conjecture if the conjectured inequality holds for $G$ and any graph $H$.  Vizing's conjecture has been proved for $\gamma(G) \le 3$, and it is known to hold for other classes of graphs. Clark and Suen in 2000 showed that $\gamma(G \Box H) \geq \frac{1}{2}\gamma(G)\gamma(H)$ for any graphs $G$ and $H$.   We give a slight improvement of this inequality by tightening their arguments.
A short proof of a partition relation for triples
Authors: Jones Albin L.
Published: January 2020

We provide a much shorter proof of the following partition theorem of P. Erdős and R. Rado: If $X$ is an uncountable linear order into which neither $\omega_1$ nor $\omega_1^{*}$ embeds, then $X \to (\alpha, 4)^{3}$ for every ordinal $\alpha < \omega + \omega$. We also provide two counterexamples to possible generalizations of this theorem, one of which answers a question of E. C. Milner and K. Prikry.
Harmonic Functions on Multiplicative Graphs and Interpolation Polynomials
Authors: Borodin Alexei , Olshanski Grigori
Published: January 2020

We construct examples of nonnegative harmonic functions on certain graded graphs: the Young lattice and its generalizations. Such functions first emerged in harmonic analysis on the infinite symmetric group. Our method relies on multivariate interpolation polynomials associated with Schur's S and P functions and with Jack symmetric functions. As a by–product, we compute certain Selberg–type integrals.
Symmetric Sum-Free Partitions and Lower Bounds for Schur Numbers
Authors: Fredricksen Harold , Sweet Melvin M.
Published: January 2020

We give new lower bounds for the Schur numbers $S(6)$ and $S(7)$. This will imply new lower bounds for the Multicolor Ramsey Numbers $R_6(3)$ and $R_7(3)$. We also make several observations concerning symmetric sum-free partitions into 5 sets.
Automorphisms and Enumeration of Switching Classes of Tournaments.
Authors: Babai L. , Cameron P. J.
Published: January 2020

Two tournaments $T_1$ and $T_2$ on the same vertex set $X$ are said to be switching equivalent if $X$ has a subset $Y$ such that $T_2$ arises from $T_1$ by switching all arcs between $Y$ and its complement $X\setminus Y$. The main result of this paper is a characterisation of the abstract finite groups which are full automorphism groups of switching classes of tournaments: they are those whose Sylow 2-subgroups are cyclic or dihedral. Moreover, if $G$ is such a group, then there is a switching class $C$, with Aut$(C)\cong G$, such that every subgroup of $G$ of odd order is the full automorphism group of some tournament in $C$. Unlike previous results of this type, we do not give an explicit construction, but only an existence proof. The proof follows as a special case of a result on the full automorphism group of random $G$-invariant digraphs selected from a certain class of probability distributions. We also show that a permutation group $G$, acting on a set $X$, is contained in the automorphism group of some switching class of tournaments with vertex set $X$ if and only if the Sylow 2-subgroups of $G$ are cyclic or dihedral and act semiregularly on $X$. Applying this result to individual permutations leads to an enumeration of switching classes, of switching classes admitting odd permutations, and of tournaments in a switching class. We conclude by remarking that both the class of switching classes of finite tournaments, and the class of "local orders" (that is, tournaments switching-equivalent to linear orders), give rise to countably infinite structures with interesting automorphism groups (by a theorem of Fraïssé).
A Note on the Asymptotic Behavior of the Heights in $b$-Tries for $b$ Large
Authors: Knessl Charles , Szpankowski Wojciech
Published: January 2020

We study the limiting distribution of the height in a generalized trie in which external nodes are capable to store up to $b$ items (the so called $b$-tries). We assume that such a tree is built from $n$ random strings (items) generated by an unbiased memoryless source. In this paper, we discuss the case when $b$ and $n$ are both large. We shall identify five regions of the height distribution that should be compared to three regions obtained for fixed $b$. We prove that for most $n$, the limiting distribution is concentrated at the single point $k_1=\lfloor \log_2 (n/b)\rfloor +1$ as $n,b\to \infty$. We observe that this is quite different than the height distribution for fixed $b$, in which case the limiting distribution is of an extreme value type concentrated around $(1+1/b)\log_2 n$. We derive our results by analytic methods, namely generating functions and the saddle point method. We also present some numerical verification of our results.
Quasi-Spectral Characterization of Strongly Distance-Regular Graphs
Authors: Fiol M. A.
Published: January 2020

A graph $\Gamma$ with diameter $d$ is strongly distance-regular if $\Gamma$ is distance-regular and its distance-$d$ graph $\Gamma _d$ is strongly regular. The known examples are all the connected strongly regular graphs (i.e. $d=2$), all the antipodal distance-regular graphs, and some distance-regular graphs with diameter $d=3$. The main result in this paper is a characterization of these graphs (among regular graphs with $d$ distinct eigenvalues), in terms of the eigenvalues, the sum of the multiplicities corresponding to the eigenvalues with (non-zero) even subindex, and the harmonic mean of the degrees of the distance-$d$ graph.
Evaluating a Weighted Graph Polynomial for Graphs of Bounded Tree-Width
Authors: Noble S. D.
Published: January 2020

We show that for any $k$ there is a polynomial time algorithm to evaluate the weighted graph polynomial $U$ of any graph with tree-width at most $k$ at any point. For a graph with $n$ vertices, the algorithm requires $O(a_k n^{2k+3})$ arithmetical operations, where $a_k$ depends only on $k$.
Large Equiangular Sets of Lines in Euclidean Space
Authors: De Caen D.
Published: January 2020

A construction is given of ${{2}\over {9}} (d+1)^2$ equiangular lines in Euclidean $d$-space, when $d = 3 \cdot 2^{2t-1}-1$ with $t$ any positive integer. This compares with the well known "absolute" upper bound of ${{1}\over {2}} d(d+1)$ lines in any equiangular set; it is the first known constructive lower bound of order $d^2$ .
Tight Upper Bounds for the Domination Numbers of Graphs with Given Order and Minimum Degree, II
Authors: Clark W. Edwin , Dunning Larry A. , Suen Stephen
Published: January 2020

Let $\gamma (n,\delta)$ denote the largest possible domination number for a graph of order $n$ and minimum degree $\delta$. This paper is concerned with the behavior of the right side of the sequence $$\gamma (n,0) \ge \gamma (n,1) \ge \cdots \ge \gamma (n,n-1) = 1. $$ We set $ \delta _k(n) = \max \{ \delta \, \vert \, \gamma (n,\delta) \ge k \}$, $k \ge 1.$ Our main result is that for any fixed $k \ge 2$ there is a constant $c_k$ such that for sufficiently large $n$, $$ n-c_kn^{(k-1)/k} \le \delta _{k+1}(n) \le n - n^{(k-1)/k}. $$ The lower bound is obtained by use of circulant graphs. We also show that for $n$ sufficiently large relative to $k$, $\gamma (n,\delta _k(n)) = k$. The case $k=3$ is examined in further detail. The existence of circulant graphs with domination number greater than 2 is related to a kind of difference set in ${\bf Z}_n$.
An Infinite Antichain of Permutations
Authors: Spielman Daniel A. , Bóna Miklós
Published: January 2020

We constructively prove that the partially ordered set of finite permutations ordered by deletion of entries contains an infinite antichain. In other words, there exists an infinite collection of permutations no one of which contains another as a pattern.
Note on Gy. Elekes's Conjectures Concerning Unavoidable Patterns in Proper Colorings
Authors: Rosta Vera
Published: January 2020

A counterexample is presented to Gy. Elekes's conjecture concerning the existence of long $2$-colored paths in properly colored graphs. A modified version of the conjecture is given and its connections to a problem of Erdős - Gyárfás and to Szemerédi's theorem are examined.
Maximum Exponent of Boolean Circulant Matrices with Constant Number of Nonzero Entries in their Generating Vector
Authors: Bueno M. I. , Furtado S. , Sherer N.
Published: January 2020

It is well-known that the maximum exponent that an $n$-by-$n$ boolean primitive circulant matrix can attain is $n-1$. In this paper, we find the maximum exponent attained by $n$-by-$n$ boolean primitive circulant matrices with constant number of nonzero entries in their generating vector. We also give matrices attaining such exponents. Solving this problem we also solve two equivalent problems: 1) find the maximum exponent attained by primitive Cayley digraphs on a cyclic group whose vertices have constant outdegree; 2) determine the maximum order of a basis for ${\Bbb Z}_{n}$ with fixed cardinality.
Applying Balanced Generalized Weighing Matrices to Construct Block Designs
Authors: Ionin Yury J.
Published: January 2020

Balanced generalized weighing matrices are applied for constructing a family of symmetric designs with parameters $(1+qr(r^{m+1}-1)/(r-1),r^{m},r^{m-1}(r-1)/q)$, where $m$ is any positive integer and $q$ and $r=(q^{d}-1)/(q-1)$ are prime powers, and a family of non-embeddable quasi-residual $2-((r+1)(r^{m+1}-1)/(r-1),r^{m}(r+1)/2,r^{m}(r-1)/2)$ designs, where $m$ is any positive integer and $r=2^{d}-1$, $3\cdot 2^{d}-1$ or $5\cdot 2^{d}-1$ is a prime power, $r\geq 11$.
Nowhere-zero $k$-flows of Supergraphs
Authors: Mohar Bojan , Škrekovski Riste
Published: January 2020

Let $G$ be a 2-edge-connected graph with $o$ vertices of odd degree. It is well-known that one should (and can) add $o \over 2$ edges to $G$ in order to obtain a graph which admits a nowhere-zero 2-flow. We prove that one can add to $G$ a set of $\le \lfloor{o \over 4}\rfloor$, $\lceil{1 \over 2}\lfloor{o \over 5}\rfloor\rceil$, and $\lceil{1 \over 2}\lfloor{o \over 7}\rfloor\rceil$ edges such that the resulting graph admits a nowhere-zero 3-flow, 4-flow, and 5-flow, respectively.
A Color-to-Spin Domino Schensted Algorithm
Authors: Shimozono Mark , White Dennis E.
Published: January 2020

We describe the domino Schensted algorithm of Barbasch, Vogan, Garfinkle and van Leeuwen. We place this algorithm in the context of Haiman's mixed and left-right insertion algorithms and extend it to colored words. It follows easily from this description that total color of a colored word maps to the sum of the spins of a pair of $2$-ribbon tableaux. Various other properties of this algorithm are described, including an alternative version of the Littlewood-Richardson bijection which yields the $q$-Littlewood-Richardson coefficients of Carré and Leclerc. The case where the ribbon tableau decomposes into a pair of rectangles is worked out in detail. This case is central in recent work by D. White on the number of even and odd linear extensions of a product of two chains.
Face Vectors of Two-Dimensional Buchsbaum Complexes
Authors: Murai Satoshi
Published: January 2020

In this paper, we characterize all possible $h$-vectors of $2$-dimensional Buchsbaum simplicial complexes.
A One–Sided Zimin Construction
Authors: Cummings L. J. , Mays M.
Published: January 2020

A string is Abelian square-free if it contains no Abelian squares; that is, adjacent substrings which are permutations of each other. An Abelian square-free string is maximal if it cannot be extended to the left or right by concatenating alphabet symbols without introducing an Abelian square. We construct Abelian square-free finite strings which are maximal by modifying a construction of Zimin. The new construction produces maximal strings whose length as a function of alphabet size is much shorter than that in the construction described by Zimin.
Asymptotically Optimal Tree-Packings in Regular Graphs
Authors: Kelmans Alexander , Mubayi Dhruv , Sudakov Benny
Published: January 2020

Let $T$ be a tree with $t$ vertices. Clearly, an $n$ vertex graph contains at most $n/t$ vertex disjoint trees isomorphic to $T$. In this paper we show that for every $\epsilon >0$, there exists a $D(\epsilon,t)>0$ such that, if $d>D(\epsilon,t)$ and $G$ is a simple $d$-regular graph on $n$ vertices, then $G$ contains at least $(1-\epsilon)n/t$ vertex disjoint trees isomorphic to $T$.
An Area-to-Inv Bijection Between Dyck Paths and 312-avoiding Permutations
Authors: Bandlow Jason , Killpatrick Kendra
Published: January 2020

The symmetric $q,t$-Catalan polynomial $C_n(q,t)$, which specializes to the Catalan polynomial $C_n(q)$ when $t=1$, was defined by Garsia and Haiman in 1994. In 2000, Garsia and Haglund described statistics $a(\pi)$ and $b(\pi)$ on Dyck paths such that $C_n(q,t) = \sum_{\pi} q^{a(\pi)}t^{b(\pi)}$ where the sum is over all $n \times n$ Dyck paths. Specializing $t=1$ gives the Catalan polynomial $C_n(q)$ defined by Carlitz and Riordan and further studied by Carlitz. Specializing both $t=1$ and $q=1$ gives the usual Catalan number $C_n$. The Catalan number $C_n$ is known to count the number of $n \times n$ Dyck paths and the number of $312$-avoiding permutations in $S_n$, as well as at least 64 other combinatorial objects. In this paper, we define a bijection between Dyck paths and $312$-avoiding permutations which takes the area statistic $a(\pi)$ on Dyck paths to the inversion statistic on $312$-avoiding permutations. The inversion statistic can be thought of as the number of $(21)$ patterns in a permutation $\sigma$. We give a characterization for the number of $(321)$, $(4321)$, $\dots$, $(k\cdots21)$ patterns that occur in $\sigma$ in terms of the corresponding Dyck path.
Gaps in the Chromatic Spectrum of Face-Constrained Plane Graphs
Authors: Kobler Daniel , Kündgen André
Published: January 2020

Let $G$ be a plane graph whose vertices are to be colored subject to constraints on some of the faces. There are 3 types of constraints: a $C$ indicates that the face must contain two vertices of a $C$ommon color, a $D$ that it must contain two vertices of a $D$ifferent color and a $B$ that $B$oth conditions must hold simultaneously. A coloring of the vertices of $G$ satisfying the facial constraints is a strict $k$-coloring if it uses exactly $k$ colors. The chromatic spectrum of $G$ is the set of all $k$ for which $G$ has a strict $k$-coloring. We show that a set of integers $S$ is the spectrum of some plane graph with face-constraints if and only if $S$ is an interval $\{s,s+1,\dots,t\}$ with $1\leq s\leq 4$, or $S=\{2,4,5,\dots,t\}$, i.e. there is a gap at 3.
Queens on Non-square Tori
Authors: Cairns Grant
Published: January 2020

We prove that for $m < n$, the maximum number of nonattacking queens that can be placed on the $n\times m$ rectangular toroidal chessboard is $\gcd(m,n)$, except in the case $m=3, n=6$.
The Polynomial Part of a Restricted Partition Function Related to the Frobenius Problem
Authors: Beck Matthias , Gessel Ira M. , Komatsu Takao
Published: January 2020

Given a set of positive integers $ A = \{ a_{1} , \dots , a_{n} \} $, we study the number $ p_{A} (t) $ of nonnegative integer solutions $ \left( m_{1} , \dots , m_{n} \right) $ to $ \sum_{j=1}^{n} m_{j} a_{j} = t $. We derive an explicit formula for the polynomial part of $p_A$.
About Division by 1
Authors: Lascoux Alain
Published: January 2020

The Euclidean division of two formal series in one variable produces a sequence of series that we obtain explicitly, remarking that the case where one of the two initial series is 1 is sufficiently generic. As an application, we define a Wronskian of symmetric functions.
Six Lonely Runners
Authors: Bohman Tom , Holzman Ron , Kleitman Dan
Published: January 2020

For $x$ real, let $ \{x\}$ be the fractional part of $x$ (i.e. $ \{x\} = x - \lfloor x \rfloor $). In this paper we prove the $k=5$ case of the following conjecture (the lonely runner conjecture): for any $k$ positive reals $ v_1, \dots , v_k $ there exists a real number $t$ such that $ 1/(k+1) \le \{v_it \} \le k/(k+1) $ for $ i= 1, \dots, k$.
Dartboard Arrangements
Authors: Cohen G. L. , Tonkes E.
Published: January 2020

This note considers possible arrangements of the sectors of a generalised dartboard. The sum of the $p$th powers of the absolute differences of the numbers on adjacent sectors is introduced as a penalty cost function and a string reversal algorithm is used to determine all arrangements that maximise the penalty, for any $p\ge1$. The maximum value of the penalty function for $p=1$ is well known in the literature, and has been previously stated without proof for $p=2$. We determine it also for $p=3$ and $p=4$.
A Finite Word Poset
Authors: Erdős Péter L. , Sziklai Péter , Torney David C.
Published: January 2020

Our word posets have finite words of bounded length as their elements, with the words composed from a finite alphabet. Their partial ordering follows from the inclusion of a word as a subsequence of another word. The elemental combinatorial properties of such posets are established. Their automorphism groups are determined (along with similar result for the word poset studied by Burosch, Frank and Röhl [4]) and a BLYM inequality is verified (via the normalized matching property).
Another Form of Matrix Nim
Authors: Ferguson Thomas S.
Published: January 2020

A new form of 2-dimensional nim is investigated. Positions are rectangular matrices of non-negative integers. Moves consist of chosing a positive integer and a row or column and subtracting the integer from every element of the chosen row or column. Last to move wins. The $2\times1$ case is just Wythoff's Game. The outcomes of all $2\times2$ positions are found in both the impartial and partizan cases. Some hope is given of being able to solve sums of $2\times2$ games in the partizan case.
Counting Abelian Squares
Authors: Richmond L. B. , Shallit Jeffrey
Published: January 2020

An abelian square is a nonempty string of length $2n$ where the last $n$ symbols form a permutation of the first $n$ symbols. Similarly, an abelian $r$'th power is a concatenation of $r$ blocks, each of length $n$, where each block is a permutation of the first $n$ symbols. In this note we point out that some familiar combinatorial identities can be interpreted in terms of abelian powers. We count the number of abelian squares and give an asymptotic estimate of this quantity.
Combinatorial Identities from the Spectral Theory of Quantum Graphs
Authors: Schanz Holger , Smilansky Uzy
Published: January 2020

The purpose of this paper is to present a newly discovered link between three seemingly unrelated subjects—quantum graphs, the theory of random matrix ensembles and combinatorics. We discuss the nature of this connection, and demonstrate it in a special case pertaining to simple graphs, and to the random ensemble of ${2\times 2}$ unitary matrices. The corresponding combinatorial problem results in a few identities, which, to the best of our knowledge, were not proven previously.
A Specht Module Analog for the Rook Monoid
Authors: Grood Cheryl
Published: January 2020

The wealth of beautiful combinatorics that arise in the representation theory of the symmetric group is well-known. In this paper, we analyze the representations of a related algebraic structure called the rook monoid from a combinatorial angle. In particular, we give a combinatorial construction of the irreducible representations of the rook monoid. Since the rook monoid contains the symmetric group, it is perhaps not surprising that the construction outlined in this paper is very similar to the classic combinatorial construction of the irreducible $S_n$-representations: namely, the Specht modules.
A Reformulation of Matrix Graph Grammars with Boolean Complexes
Authors: Velasco Pedro Pablo Pérez , De Lara Juan
Published: January 2020

Graph transformation is concerned with the manipulation of graphs by means of rules. Graph grammars have been traditionally studied using techniques from category theory. In previous works, we introduced Matrix Graph Grammars (MGG) as a purely algebraic approach for the study of graph dynamics, based on the representation of simple graphs by means of their adjacency matrices. The observation that, in addition to positive information, a rule implicitly defines negative conditions for its application (edges cannot become dangling, and cannot be added twice as we work with simple digraphs) has led to a representation of graphs as two matrices encoding positive and negative information. Using this representation, we have reformulated the main concepts in MGGs, while we have introduced other new ideas. In particular, we present (i) a new formulation of productions together with an abstraction of them (so called swaps), (ii) the notion of coherence, which checks whether a production sequence can be potentially applied, (iii) the minimal graph enabling the applicability of a sequence, and (iv) the conditions for compatibility of sequences (lack of dangling edges) and G-congruence (whether two sequences have the same minimal initial graph).
On the Number of Permutations Admitting an m-th Root
Authors: Pouyanne Nicolas
Published: January 2020

Let $m$ be a positive integer, and $p_n(m)$ the proportion of permutations of the symmetric group $S_n$ that admit an $m$-th root. Calculating the exponential generating function of these permutations, we show the following asymptotic formula $$p_n(m)\, \sim \, {{\pi _m}\over {n^{1-\varphi (m)/m}}},\;\; n\to \infty ,$$ where $\varphi$ is the Euler function and $\pi _m$ an explicit constant.
Computation of the Vertex Folkman Numbers $F(2,2,2,4;6)$ and $F(2,3,4;6)$
Authors: Nedialkov Evgeni , Nenov Nedyalko
Published: January 2020

In this note we show that the exact value of the vertex Folkman numbers $F(2,2,2,4;6)$ and $F(2,3,4;6)$ is 14.
Combinatorial Laplacian of the Matching Complex
Authors: Dong Xun , Wachs Michelle L.
Published: January 2020

A striking result of Bouc gives the decomposition of the representation of the symmetric group on the homology of the matching complex into irreducibles that are self-conjugate. We show how the combinatorial Laplacian can be used to give an elegant proof of this result. We also show that the spectrum of the Laplacian is integral.
MacWilliams Identities and Matroid Polynomials
Authors: Britz Thomas
Published: January 2020

We present generalisations of several MacWilliams type identities, including those by Kløve and Shiromoto, and of the theorems of Greene and Barg that describe how the Tutte polynomial of the vector matroid of a linear code determines the $r$th support weight enumerators of the code. One of our main tools is a generalisation of a decomposition theorem due to Brylawski.
Sparse Graphs Usually Have Exponentially Many Optimal Colorings
Authors: Krivelevich Michael
Published: January 2020

A proper coloring of a graph $G=(V,E)$ is called optimal if the number of colors used is the minimal possible; i.e., it coincides with the chromatic number of $G$. We investigate the typical behavior of the number of distinct optimal colorings of a random graph $G(n,p)$, for various values of the edge probability $p=p(n)$. Our main result shows that for every constant $1/3 < a < 2$, most of the graphs in the probability space $G(n,p)$ with $p=n^{-a}$ have exponentially many optimal colorings.
A Prolific Construction of Strongly Regular Graphs with the $n$-e.c. Property
Authors: Cameron Peter J. , Stark Dudley
Published: January 2020

A graph is $n$-e.c.$\,$ ($n$-existentially closed) if for every pair of subsets $U$, $W$ of the vertex set $V$ of the graph such that $U\cap W=\emptyset$ and $|U|+|W|=n$, there is a vertex $v\in V-(U\cup W)$ such that all edges between $v$ and $U$ are present and no edges between $v$ and $W$ are present. A graph is strongly regular if it is a regular graph such that the number of vertices mutually adjacent to a pair of vertices $v_1,v_2\in V$ depends only on whether or not $\{v_1,v_2\}$ is an edge in the graph. The only strongly regular graphs that are known to be $n$-e.c. for large $n$ are the Paley graphs. Recently D. G. Fon-Der-Flaass has found prolific constructions of strongly regular graphs using affine designs. He notes that some of these constructions were also studied by Wallis. By taking the affine designs to be Hadamard designs obtained from Paley tournaments, we use probabilistic methods to show that many non-isomorphic strongly regular $n$-e.c. graphs of order $(q+1)^2$ exist whenever $q\geq 16 n^2 2^{2n}$ is a prime power such that $q\equiv 3\!\!\!\pmod{4}$.
Catalan Traffic at the Beach
Authors: Niederhausen Heinrich
Published: January 2020

We design a lattice path problem in ${\bf Z}^{2}$ (the Catalan traffic) with step set $\{\rightarrow,\uparrow\}$ strictly above the line $y=( x-1) /2$, and with step set $\{\downarrow,\searrow\}$ below that same line, except for the gates at $(2y,y)$ (with $\{\uparrow,\downarrow ,\searrow\}$-steps) and the closed intersections at $( 2y+1,y) $ (no traffic). The step sets prevent any traffic from going below the diagonal $y=-x$ (the beach). If we denote by $t(n,m)$ the number of paths from the origin to $(n,m)$, then the ubiquitous Catalan numbers $C_{n}={{2n}\choose {n}}/ ( n+1) $ occur as $t( n,-n) $ along the beach. We prove this with the help of hypergeometric identities, and also by solving an equivalent lattice path problem. On the way we pick up several identities and discuss other known sequences of numbers occurring in the Catalan traffic scheme, like the Motzkin numbers in row $m=-1$, and the "Tri-Catalan numbers" $1,1,3,12,55,\dots$ at the gates.
Toida's Conjecture is True
Authors: Dobson Edward , Morris Joy
Published: January 2020

Let $S$ be a subset of the units in ${\bf Z_n}$. Let ${\Gamma}$ be a circulant graph of order $n$ (a Cayley graph of ${\bf Z_n}$) such that if $ij\in E({\Gamma})$, then $i - j$ (mod $n$) $\in S$. Toida conjectured that if $\Gamma'$ is another circulant graph of order $n$, then ${\Gamma}$ and ${\Gamma '}$ are isomorphic if and only if they are isomorphic by a group automorphism of ${\bf Z_n}$ In this paper, we prove that Toida's conjecture is true. We further prove that Toida's conjecture implies Zibin's conjecture, a generalization of Toida's conjecture.
A Concise Proof of the Littlewood-Richardson Rule
Authors: Stembridge John R.
Published: January 2020

We give a short proof of the Littlewood-Richardson rule using a sign-reversing involution.
A Note on the Number of Edges Guaranteeing a $C_4$ in Eulerian Bipartite Digraphs
Authors: Shen Jian , Yuster Raphael
Published: January 2020

Let $G$ be an Eulerian bipartite digraph with vertex partition sizes $m,n$. We prove the following Turán-type result: If $e(G) > 2mn/3$ then $G$ contains a directed cycle of length at most 4. The result is sharp. We also show that if $e(G)=2mn/3$ and no directed cycle of length at most 4 exists, then $G$ must be biregular. We apply this result in order to obtain an improved upper bound for the diameter of interchange graphs.
There Are Ternary Circular Square-Free Words of Length $n$ for $n\ge 18$
Authors: Currie James D.
Published: January 2020

There are circular square-free words of length $n$ on three symbols for $n\ge 18$. This proves a conjecture of R. J. Simpson.
Words Restricted by Patterns with at Most 2 Distinct Letters
Authors: Burstein Alexander , Mansour Toufik
Published: January 2020

We find generating functions for the number of words avoiding certain patterns or sets of patterns with at most 2 distinct letters and determine which of them are equally avoided. We also find exact numbers of words avoiding certain patterns and provide bijective proofs for the resulting formulae.
Counting 1324-Avoiding Permutations
Authors: Marinov Darko , Radoičić Radoš
Published: January 2020

We consider permutations that avoid the pattern 1324. By studying the generating tree for such permutations, we obtain a recurrence formula for their number. A computer program provides data for the number of 1324-avoiding permutations of length up to 20.
Profile Classes and Partial Well-Order for Permutations
Authors: Murphy Maximillian M. , Vatter Vincent R.
Published: January 2020

It is known that the set of permutations, under the pattern containment ordering, is not a partial well-order. Characterizing the partially well-ordered closed sets (equivalently: down sets or ideals) in this poset remains a wide-open problem. Given a $0/\pm1$ matrix $M$, we define a closed set of permutations called the profile class of $M$. These sets are generalizations of sets considered by Atkinson, Murphy, and Ruškuc. We show that the profile class of $M$ is partially well-ordered if and only if a related graph is a forest. Related to the antichains we construct to prove one of the directions of this result, we construct exotic fundamental antichains, which lack the periodicity exhibited by all previously known fundamental antichains of permutations.
Packing Patterns into Words
Authors: Burstein Alexander , Hästö Peter , Mansour Toufik
Published: January 2020

In this article we generalize packing density problems from permutations to patterns with repeated letters and generalized patterns. We are able to find the packing density for some classes of patterns and several other short patterns.
Switching of Edges in Strongly Regular Graphs I: A Family of Partial Difference Sets on 100 Vertices
Authors: Jørgensen L. K. , Klin M.
Published: January 2020

We present 15 new partial difference sets over 4 non-abelian groups of order 100 and 2 new strongly regular graphs with intransitive automorphism groups. The strongly regular graphs and corresponding partial difference sets have the following parameters: (100,22,0,6), (100,36,14,12), (100,45,20,20), (100,44,18,20). The existence of strongly regular graphs with the latter set of parameters was an open question. Our method is based on combination of Galois correspondence between permutation groups and association schemes, classical Seidel's switching of edges and essential use of computer algebra packages. As a by-product, a few new amorphic association schemes with 3 classes on 100 points are discovered.
Properties Determined by the Ihara Zeta Function of a Graph
Authors: Cooper Yaim
Published: January 2020

In this paper, we show how to determine several properties of a finite graph $G$ from its Ihara zeta function $Z_{G}(u)$. If $G$ is connected and has minimal degree at least 2, we show how to calculate the number of vertices of $G$. To do so we use a result of Bass, and in the case that $G$ is nonbipartite, we give an elementary proof of Bass' result. We further show how to determine whether $G$ is regular, and if so, its regularity and spectrum. On the other hand, we extend work of Czarneski to give several infinite families of pairs of non-isomorphic non-regular graphs with the same Ihara zeta function. These examples demonstrate that several properties of graphs, including vertex and component numbers, are not determined by the Ihara zeta function. We end with Hashimoto's edge matrix T. We show that any graph $G$ with no isolated vertices can be recovered from its $T$ matrix. Since graphs with the same Ihara zeta function are exactly those with isospectral T matrices, this relates again to the question of what information about $G$ can be recovered from its Ihara zeta function.
Regular Character Tables of Symmetric Groups
Authors: Olsson Jorn B.
Published: January 2020

We generalize a well-known result on the determinant of the character tables of finite symmetric groups.
Dynamic One-Pile Blocking Nim
Authors: Flammenkamp Achim , Holshouser Arthur , Reiter Harold
Published: January 2020

The purpose of this paper is to solve a class of combinatorial games consisting of one-pile counter pickup games for which the number of counters that can be removed on each successive turn changes during the play of the game. Both the minimum and the maximum number of counters that can be removed is dependent upon the move number. Also, on each move, the opposing player can block some of the moving player's options. This number of blocks also depends upon the move number.
Squishing Dimers on the Hexagon Lattice
Authors: Young Ben
Published: January 2020

We describe an operation on dimer configurations on the hexagon lattice, called "squishing", and use this operation to explain some of the properties of the Donaldson-Thomas partition function for the orbifold ${\Bbb C}^3 / {\Bbb Z}_2 \times {\Bbb Z}_2$ (a certain four-variable generating function for plane partitions which comes from algebraic geometry).
Strings with Maximally Many Distinct Subsequences and Substrings
Authors: Flaxman Abraham , Harrow Aram W. , Sorkin Gregory B.
Published: January 2020

A natural problem in extremal combinatorics is to maximize the number of distinct subsequences for any length-$n$ string over a finite alphabet $\Sigma$; this value grows exponentially, but slower than $2^n$. We use the probabilistic method to determine the maximizing string, which is a cyclically repeating string. The number of distinct subsequences is exactly enumerated by a generating function, from which we also derive asymptotic estimates. For the alphabet $\Sigma=\{1,2\}$, $\,(1,2,1,2,\dots)$ has the maximum number of distinct subsequences, namely ${\rm Fib}(n+3)-1 \sim \left((1+\sqrt5)/2\right)^{n+3} \! / \sqrt{5}$. We also consider the same problem with substrings in lieu of subsequences. Here, we show that an appropriately truncated de Bruijn word attains the maximum. For both problems, we compare the performance of random strings with that of the optimal ones.
Bounds on the Distinguishing Chromatic Number
Authors: Collins Karen L. , Hovey Mark , Trenk Ann N.
Published: January 2020

Collins and Trenk define the distinguishing chromatic number $\chi_D(G)$ of a graph $G$ to be the minimum number of colors needed to properly color the vertices of $G$ so that the only automorphism of $G$ that preserves colors is the identity. They prove results about $\chi_D(G)$ based on the underlying graph $G$. In this paper we prove results that relate $\chi_D(G)$ to the automorphism group of $G$. We prove two upper bounds for $\chi_D(G)$ in terms of the chromatic number $\chi(G)$ and show that each result is tight: (1) if Aut$(G)$ is any finite group of order $p_1^{i_1} p_2^{i_2} \cdots p_k^{i_k}$ then $\chi_D(G) \le \chi(G) + i_1 + i_2 \cdots + i_k$, and (2) if Aut$(G)$ is a finite and abelian group written Aut$(G) = {\Bbb Z}_{p_{1}^{i_{1}}}\times \cdots \times {\Bbb Z}_{p_{k}^{i_{k}}}$ then we get the improved bound $\chi_D(G) \le \chi(G) + k$. In addition, we characterize automorphism groups of graphs with $\chi_D(G) = 2$ and discuss similar results for graphs with $\chi_D(G)=3$.
A Card Shuffling Analysis of Deformations of the Plancherel Measure of the Symmetric Group
Authors: Fulman Jason
Published: January 2020

This paper finds and analyzes a formula for the total variation distance between iterations of riffle shuffles and iterations of "cut and then riffle shuffle". This allows one to obtain information about the convergence rate of permutation statistics (such as the length of the longest increasing subsequence or position of a given card) under these processes. Similar results are given for affine shuffles, which allow us to determine their convergence rate to randomness.
Coloring with no $2$-Colored $P_4$'s
Authors: Albertson Michael O. , Chappell Glenn G. , Kierstead H. A. , Kündgen André , Ramamurthi Radhika
Published: January 2020

A proper coloring of the vertices of a graph is called a star coloring if every two color classes induce a star forest. Star colorings are a strengthening of acyclic colorings, i.e., proper colorings in which every two color classes induce a forest. We show that every acyclic $k$-coloring can be refined to a star coloring with at most $(2k^2-k)$ colors. Similarly, we prove that planar graphs have star colorings with at most 20 colors and we exhibit a planar graph which requires 10 colors. We prove several other structural and topological results for star colorings, such as: cubic graphs are $7$-colorable, and planar graphs of girth at least $7$ are $9$-colorable. We provide a short proof of the result of Fertin, Raspaud, and Reed that graphs with tree-width $t$ can be star colored with ${t+2\choose2}$ colors, and we show that this is best possible.
On the Livingstone-Wagner Theorem
Authors: Mnukhin V. B. , Siemons I. J.
Published: January 2020

Let $G$ be a permutation group on the set $\Omega$ and let ${\cal S}$ be a collection of subsets of $\Omega,$ all of size $\geq m$ for some integer $m$. For $s\leq m$ let $n_{s}(G,\,{\cal S})$ be the number of $G$-orbits on the subsets of $\Omega$ which have a representative $y\subseteq x$ with $|y|=s$ and $y\subseteq x$ for some $x\in {\cal S}$. We prove that if $s < t$ with $s+t\leq m$ then $n_{s}(G,\,{\cal S})\leq n_{t}(G,\,{\cal S})$. A special case of this theorem is the Livingstone-Wagner Theorem when ${\cal S}=\{\Omega\}$. We show how the result can be applied to estimate orbit numbers for simplicial complexes, sequences, graphs and amalgamation classes. It is also shown how this theorem can be extended to orbit theorems on more general partially ordered sets.
On the Combinatorial Structure of Arrangements of Oriented Pseudocircles
Authors: Linhart Johann , Ortner Ronald
Published: January 2020

We introduce intersection schemes (a generalization of uniform oriented matroids of rank 3) to describe the combinatorial properties of arrangements of pseudocircles in the plane and on closed orientable surfaces. Similar to the Folkman-Lawrence topological representation theorem for oriented matroids we show that there is a one-to-one correspondence between intersection schemes and equivalence classes of arrangements of pseudocircles. Furthermore, we consider arrangements where the pseudocircles separate the surface into two components. For these strict arrangements there is a one-to-one correspondence to a quite natural subclass of consistent intersection schemes.
Enumerative Problems Inspired by Mayer's Theory of Cluster Integrals
Authors: Leroux Pierre
Published: January 2020

The basic functional equations for connected and 2-connnected graphs can be traced back to the statistical physicists Mayer and Husimi. They play an essential role in establishing rigorously the virial expansion for imperfect gases. We first review these functional equations, putting the emphasis on the structural relationships between the various classes of graphs. We then investigate the problem of enumerating some classes of connected graphs all of whose 2-connected components (blocks) are contained in a given class $B$. Included are the species of Husimi graphs ($B =$ "complete graphs"), cacti ($B =$ "unoriented cycles"), and oriented cacti ($B =$ "oriented cycles"). For each of these, we address the question of their labelled and unlabelled enumeration, according (or not) to their block-size distributions. Finally we discuss the molecular expansion of these species. It consists of a descriptive classification of the unlabelled structures in terms of elementary species, from which all their symmetries can be deduced.
$q$-Exponential Families
Authors: Morrison Kent E.
Published: January 2020

We develop an analog of the exponential families of Wilf in which the label sets are finite dimensional vector spaces over a finite field rather than finite sets of positive integers. The essential features of exponential families are preserved, including the exponential formula relating the deck enumerator and the hand enumerator.
Even Astral Configurations
Authors: Berman Leah Wrenn
Published: January 2020

A configuration $(p_q, n_k)$ is a collection of $p$ points and $n$ straight lines in the Euclidean plane so that every point has $q$ straight lines passing through it and every line has $k$ points lying on it. A configuration is astral if it has precisely $\lfloor {q+1\over2} \rfloor$ symmetry classes (transitivity classes) of lines and $\lfloor{k+1\over2} \rfloor$ symmetry classes of points. An even astral configuration is an astral configuration configuration where $q$ and $k$ are both even. This paper completes the classification of all even astral configurations.
On the Associative Nijenhuis Relation
Authors: Ebrahimi-Fard Kurusch
Published: January 2020

We give the construction of a free commutative unital associative Nijenhuis algebra on a commutative unital associative algebra based on an augmented modified quasi-shuffle product.
Degree Powers in Graphs with Forbidden Subgraphs
Authors: Bollobás Béla , Nikiforov Vladimir
Published: January 2020

For every real $p>0$ and simple graph $G,$ set $$ f\left( p,G\right) =\sum_{u\in V\left( G\right) }d^{p}\left( u\right) , $$ and let $\phi\left( r,p,n\right) $ be the maximum of $f\left( p,G\right) $ taken over all $K_{r+1}$-free graphs $G$ of order $n.$ We prove that, if $0 < p < r,$ then$$ \phi\left( r,p,n\right) =f\left( p,T_{r}\left( n\right) \right) , $$ where $T_{r}\left( n\right) $ is the $r$-partite Turan graph of order $n$. For every $p\geq r+\left\lceil \sqrt{2r}\right\rceil $ and $n$ large, we show that$$ \phi\left( p,n,r\right) >\left( 1+\varepsilon\right) f\left( p,T_{r}\left( n\right) \right) $$ for some $\varepsilon=\varepsilon\left( r\right) >0.$ Our results settle two conjectures of Caro and Yuster.