bluuebunny/crossref_metadata_2025 huggingface dataset:
Two-Stage Allocations and the Double $Q$-Function
Authors: Agievich Sergey
Published: January 2020

Let $m+n$ particles be thrown randomly, independently of each other into $N$ cells, using the following two-stage procedure.1. The first $m$ particles are allocated equiprobably, that is, the probability of a particle falling into any particular cell is $1/N$. Let the $i$th cell contain $m_i$ particles on completion. Then associate with this cell the probability $a_i=m_i/m$ and withdraw the particles.2. The other $n$ particles are then allocated polynomially, that is, the probability of a particle falling into the $i$th cell is $a_i$.Let $\nu=\nu(m,N)$ be the number of the first particle that falls into a non-empty cell during the second stage. We give exact and asymptotic expressions for the expectation ${\bf E}\nu$.
Short Cycles in Digraphs with Local Average Outdegree at Least Two
Authors: Shen Jian
Published: January 2020

Suppose $G$ is a strongly connected digraph with order $n$ girth $g$ and diameter $d$. We prove that $d +g \le n$ if $G$ contains no arcs $(u,v)$ with $\deg^+(u)=1$ and $\deg^+(v) \le 2$.Caccetta and H${\rm\ddot{a}}$ggkvist showed in 1978 that any digraph of order $n$ with minimum outdegree $2$ contains a cycle of length at most $\lceil n/2 \rceil$. Applying the above-mentioned result, we improve their result by replacing the minimum outdegree condition by some weaker conditions involving the local average outdegree. In particular, we prove that, for any digraph $G$ of order $n$, if either(1) $G$ has minimum outdegree $1$ and $\deg^+(u) +\deg^+(v) \ge 4$ for all arcs $(u,v)$, or(2) $\deg^+(u) +\deg^+(v) \ge 3$ for all pairs of distinct vertices $u,v$,then $G$ contains a cycle of length at most $\lceil n/2 \rceil$.
Anti-Ramsey Numbers for Graphs with Independent Cycles
Authors: Jin Zemin , Li Xueliang
Published: January 2020

An edge-colored graph is called rainbow if all the colors on its edges are distinct. Let ${\cal G}$ be a family of graphs. The anti-Ramsey number $AR(n,{\cal G})$ for ${\cal G}$, introduced by Erdős et al., is the maximum number of colors in an edge coloring of $K_n$ that has no rainbow copy of any graph in ${\cal G}$. In this paper, we determine the anti-Ramsey number $AR(n,\Omega_2)$, where $\Omega_2$ denotes the family of graphs that contain two independent cycles.
Descents in Noncrossing Trees
Authors: Hough David S.
Published: January 2020

The generating function for descents in noncrossing trees is found. A bijection shows combinatorially why the descent generating function with descents set equal to $2$ is the generating function for connected noncrossing graphs.
Spherical f-Tilings by Scalene Triangles and Isosceles Trapezoids III
Authors: Avelino Catarina P. , Santos Altino F.
Published: January 2020

The study of the dihedral f-tilings of the sphere $S^2$ whose prototiles are a scalene triangle and an isosceles trapezoid was initiated in parts I and II. In this paper we complete this classification presenting the study of all dihedral spherical f-tilings by scalene triangles and isosceles trapezoids in the remaining case of adjacency. A list containing all the f-tilings obtained in this paper is presented. It is composed by isolated tilings as well as discrete and continuous families of tilings. The combinatorial structure is also achieved.
Secret Sharing Schemes on Sparse Homogeneous Access Structures with Rank Three
Authors: Martí-Farré Jaume , Padró Carles
Published: January 2020

One of the main open problems in secret sharing is the characterization of the ideal access structures. This problem has been studied for several families of access structures with similar results. Namely, in all these families, the ideal access structures coincide with the vector space ones and, besides, the optimal information rate of a non-ideal access structure is at most $2/3$. An access structure is said to be $r$-homogeneous if there are exactly $r$ participants in every minimal qualified subset. A first approach to the characterization of the ideal $3$-homogeneous access structures is made in this paper. We show that the results in the previously studied families can not be directly generalized to this one. Nevertheless, we prove that the equivalences above apply to the family of the sparse $3$-homogeneous access structures, that is, those in which any subset of four participants contains at most two minimal qualified subsets. Besides, we give a complete description of the ideal sparse $3$-homogeneous access structures.
$q$-Counting Descent Pairs with Prescribed Tops and Bottoms
Authors: Hall John , Liese Jeffrey , Remmel Jeffrey B.
Published: January 2020

Given sets $X$ and $Y$ of positive integers and a permutation $\sigma = \sigma_1 \sigma_2 \cdots \sigma_n \in S_n$, an $(X,Y)$-descent of $\sigma$ is a descent pair $\sigma_i > \sigma_{i+1}$ whose "top" $\sigma_i$ is in $X$ and whose "bottom" $\sigma_{i+1}$ is in $Y$. Recently Hall and Remmel proved two formulas for the number $P_{n,s}^{X,Y}$ of $\sigma \in S_n$ with $s$ $(X,Y)$-descents, which generalized Liese's results in [1]. We define a new statistic ${\rm stat}_{X,Y}(\sigma)$ on permutations $\sigma$ and define $P_{n,s}^{X,Y}(q)$ to be the sum of $q^{{\rm stat}_{X,Y}(\sigma)}$ over all $\sigma \in S_n$ with $s$ $(X,Y)$-descents. We then show that there are natural $q$-analogues of the Hall-Remmel formulas for $P_{n,s}^{X,Y}(q)$.
On Rowland's Sequence
Authors: Chamizo Fernando , Raboso Dulcinea , Ruiz-Cabello Serafín
Published: January 2020

E. S. Rowland proved that $a_k= a_{k-1}+ \gcd(k,a_{k-1})$, $a_1= 7$ implies that $a_{k}-a_{k-1}$ is always 1 or prime. Conjecturally this property also holds for any $a_1>3$ from a certain $k$ onwards. We state some properties of this sequence for arbitrary values of $a_1$. Namely, we prove that some specific sequences contain infinitely many primes and we characterize the possible finite subsequences of primes.
The Identities of Additive Binary Arithmetics
Authors: Klyachko Anton A. , Menshova Ekaterina V.
Published: January 2020

Operations of arbitrary arity expressible via addition modulo $2^n$ and bitwise addition modulo $2$ admit a simple description.  The identities connecting these two additions have a finite basis. Moreover, the universal algebra $\mathbb{Z}/2^n\mathbb{Z}$ with these two operations is rationally equivalent to a nilpotent ring and, therefore, generates a Specht variety.
Rainbow-free $3$-colorings of Abelian Groups
Authors: Montejano Amanda , Serra Oriol
Published: January 2020

A $3$-coloring of the elements of an abelian group is said to be rainbow-free if there is no $3$-term arithmetic progression with its members having pairwise distinct colors. We give a structural characterization of rainbow-free colorings of abelian groups. This characterization proves a conjecture of Jungić et al. on the size of the smallest chromatic class of a rainbow-free $3$-coloring of cyclic groups.
Tetravalent Non-Normal Cayley Graphs of Order $4p$
Authors: Zhou Jin-Xin
Published: January 2020

A Cayley graph ${\rm Cay}(G,S)$ on a group $G$ is said to be normal if the right regular representation $R(G)$ of $G$ is normal in the full automorphism group of ${\rm Cay}(G,S)$. In this paper, all connected tetravalent non-normal Cayley graphs of order $4p$ are constructed explicitly for each prime $p$. As a result, there are fifteen sporadic and eleven infinite families of tetravalent non-normal Cayley graphs of order $4p$.
Cubic Vertex-Transitive Non-Cayley Graphs of Order $8p$
Authors: Zhou Jin-Xin , Feng Yan-Quan
Published: January 2020

A graph is vertex-transitive if its automorphism group acts transitively on its vertices. A vertex-transitive graph is a Cayley graph if its automorphism group contains a subgroup acting regularly on its vertices. In this paper, the cubic vertex-transitive non-Cayley graphs of order $8p$ are classified for each prime $p$. It follows from this classification that there are two sporadic and two infinite families of such graphs, of which the sporadic ones have order $56$,  one infinite family exists for every prime $p>3$ and the other family exists if and only if $p\equiv 1\mod 4$. For each family there is a unique graph for a given order.
Counting Fixed-Height Tatami Tilings
Authors: Ruskey Frank , Woodcock Jennifer
Published: January 2020

A tatami tiling is an arrangement of $1 \times 2$ dominoes (or mats) in a rectangle with $m$ rows and $n$ columns, subject to the constraint that no four corners meet at a point. For fixed $m$ we present and use Dean Hickerson's combinatorial decomposition of the set of tatami tilings — a decomposition that allows them to be viewed as certain classes of restricted compositions when $n \ge m$. Using this decomposition we find the ordinary generating functions of both unrestricted and inequivalent tatami tilings that fit in a rectangle with $m$ rows and $n$ columns, for fixed $m$ and $n \ge m$. This allows us to verify a modified version of a conjecture of Knuth. Finally, we give explicit solutions for the count of tatami tilings, in the form of sums of binomial coefficients.
Largest and Smallest Minimal Percolating Sets in Trees
Authors: Riedl Eric
Published: January 2020

Originally introduced by Chalupa, Leath and Reich for use in modeling disordered magnetic systems, $r$-bootstrap percolation is the following deterministic process on a graph.  Given an initial infected set, vertices with at least $r$ infected neighbors are infected until no new vertices can be infected.  A set percolates if it infects all the vertices of the graph, and a percolating set is minimal if no proper subset percolates.  We consider minimal percolating sets in finite trees.  We show that if $A$ is a minimal percolating set on a tree $T$ with $n$ vertices and $\ell$ vertices of degree less than $r$ (leaves in the case $r=2$), then $\frac{(r-1)n+1}{r} \leq |A| \leq \frac{rn+\ell}{r+1}$.  Moreover, we show that the difference between the sizes of a largest and smallest minimal percolating sets is at most $\frac{(r-1)(n-1)}{r^2}$.  Finally, we describe $O(n)$ algorithms for computing the largest (for $r=2$) and smallest (for $r \geq 2$) minimal percolating sets.
Symmetric Functions for the Generating Matrix of the Yangian of $\mathfrak{gl}_n({\Bbb C})$
Authors: Rozhkovskaya Natasha
Published: January 2020

Analogues of classical combinatorial identities for elementary and homogeneous symmetric functions with coefficients in the Yangian are proved. As a corollary, similar relations are deduced for shifted Schur polynomials.
On Cross-Intersecting Families of Set Partitions
Authors: Ku Cheng Yeaw , Wong Kok Bin
Published: January 2020

Let $\mathcal{B}(n)$ denote the collection of all set partitions of $[n]$. Suppose $\mathcal A_1,\mathcal A_2\subseteq \mathcal{B}(n)$ are cross-intersecting i.e. for all $A_1\in \mathcal A_1$ and $A_2\in \mathcal A_2$, we have $A_1\cap A_2\neq\varnothing$. It is proved that for sufficiently large $n$,\[ \vert \mathcal A_1\vert\vert \mathcal A_2\vert\leq B_{n-1}^2\]where $B_{n}$ is the $n$-th Bell number. Moreover, equality holds if and only if $\mathcal{A}_1=\mathcal A_2$ and $\mathcal A_1$ consists of all set partitions with a fixed singleton.
Combinatorial Games: Selected Bibliography with a Succinct Gourmet Introduction
Authors: Fraenkel Aviezri
Published: January 2020

Roughly speaking, the family of combinatorial games consists of two-player games with perfect information (no hidden information as in some card games), no chance moves (no dice) and outcome restricted to (lose, win), (tie, tie) and (draw, draw) for the two players who move alternately. Tie is an end position such as in tic-tac-toe, where no player wins, whereas draw is a dynamic tie: any position from which a player has a nonlosing move, but cannot force a win. Both the easy game of Nim and the seemingly difficult chess are examples of combinatorial games. And so is go. The shorter terminology game, games is used below to designate combinatorial games.
Self-Dual Interval Orders and Row-Fishburn Matrices
Authors: Yan Sherry H. F. , Xu Yuexiao
Published: January 2020

Recently, Jelínek derived  that the number of self-dual interval orders of reduced size $n$ is twice the number of row-Fishburn matrices of size $n$ by using generating functions. In this paper, we present a bijective proof of this relation by establishing a bijection between two variations of upper-triangular matrices of nonnegative integers. Using the bijection, we provide a combinatorial proof  of the refined relations between self-dual Fishburn matrices and row-Fishburn matrices in answer to a problem proposed by Jelínek.
Graph Labelings and Continuous Factors of Dynamical Systems
Authors: Shea Stephen M.
Published: January 2020

A labeling of a graph is a function from the vertex set of the graph to some finite set.  Certain dynamical systems (such as topological Markov shifts) can be defined by directed graphs.  In these instances, a labeling of the graph defines a continuous, shift-commuting factor of the dynamical system.  We find sufficient conditions on the labeling to imply classification results for the factor dynamical system.  We define the topological entropy of a (directed or undirected) graph and its labelings in a way that is analogous to the definition of topological entropy for a shift space in symbolic dynamics.  We show, for example, if $G$ is a perfect graph, all proper $\chi(G)$-colorings of $G$ have the same entropy, where $\chi(G)$ is the chromatic number of $G$.
Lower Bounds for $q$-ary Codes with Large Covering Radius
Authors: Haas Wolfgang , Halupczok Immanuel , Schlage-Puchta Jan-Christoph
Published: January 2020

Let $K_q(n,R)$ denote the minimal cardinality of a $q$-ary code of length $n$ and covering radius $R$. Recently the authors gave a new proof of a classical lower bound of Rodemich on $K_q(n,n-2)$ by the use of partition matrices and their transversals. In this paper we show that, in contrast to Rodemich's original proof, the method generalizes to lower-bound $K_q(n,n-k)$ for any $k>2$. The approach is best-understood in terms of a game where a winning strategy for one of the players implies the non-existence of a code. This proves to be by far the most efficient method presently known to lower-bound $K_q(n,R)$ for large $R$ (i.e. small $k$). One instance: the trivial sphere-covering bound $K_{12}(7,3)\geq 729$, the previously best bound $K_{12}(7,3)\geq 732$ and the new bound $K_{12}(7,3)\geq 878$.
Bounds for the Hückel Energy of a Graph
Authors: Ghorbani Ebrahim , Koolen Jack H. , Yang Jae Young
Published: January 2020

Let $G$ be a graph on $n$ vertices with $r := \lfloor n/2 \rfloor$ and let $\lambda _1 \geq\cdots\geq \lambda _{n} $ be adjacency eigenvalues of $G$. Then the Hückel energy of $G$, HE($G$), is defined as $${\rm HE}(G) = \cases{ \displaystyle \; 2\sum_{i=1}^{r} \lambda_i, & \hbox{if $n= 2r$;} \cr \displaystyle \; 2\sum_{i=1}^{\phantom{l}r\phantom{l}} \lambda_i + \lambda_{r+1}, & \hbox{if $n= 2r+1$.}\cr } $$ The concept of Hückel energy was introduced by Coulson as it gives a good approximation for the $\pi$-electron energy of molecular graphs. We obtain two upper bounds and a lower bound for HE$(G)$. When $n$ is even, it is shown that equality holds in both upper bounds if and only if $G$ is a strongly regular graph with parameters $(n, k, \lambda, \mu) = (4t^2 +4t +2,\, 2t^2 +3t +1,\, t^2 +2t,\, t^2 + 2t +1),$ for positive integer $t$. Furthermore, we will give an infinite family of these strongly regular graph whose construction was communicated by Willem Haemers to us. He attributes the construction to J.$\,$J. Seidel.
Block Designs with SDP Parameters
Authors: Ward Harold
Published: January 2020

It is traditional to call a quasi-symmetric design with certain parameters an SDP design if the symmetric difference of two different blocks is either a block or a block complement. In this note, we delete the requirements on the parameters and demand just that the symmetric difference of two blocks be a block, a block complement, or either the empty set or the whole point set. We obtain the parameters of such designs and use the result to prove Kantor's theorem on the parameters of a symmetric SDP design. A spin-off of an exponential Diophantine equation considered by Ramanujan is at the core.
A Short Proof of the Odd-Girth Theorem
Authors: Van Dam Edwin R. , Fiol Miquel Angel
Published: January 2020

Recently, it has been shown that a connected graph $\Gamma$ with $d+1$ distinct eigenvalues and odd-girth $2d+1$ is distance-regular. The proof of this result was based on the spectral excess theorem. In this note we present an alternative and more direct proof which does not rely on the spectral excess theorem, but on a known characterization of distance regular graphs in terms of the predistance polynomial of degree $d$.
Structure of Colored Complete Graphs Free of Proper Cycles
Authors: Coll Vincent , Magnant Colton , Ryan Kathleen
Published: January 2020

For a fixed integer $m$, we consider edge colorings of complete graphs which contain no properly edge colored cycle $C_{m}$ as a subgraph.  Within colorings free of these subgraphs, we establish global structure by bounding the number of colors that can induce a spanning and connected subgraph.  In the case of smaller cycles, namely $C_4,C_5$, and $C_6$, we show that our bounds are sharp.
Improving the Use of Cyclic Zippers in Finding Lower Bounds for van der Waerden Numbers
Authors: Rabung John , Lotts Mark
Published: January 2020

For integers $k$ and $l$, each greater than $1$, suppose that $p$ is a prime with $p\equiv1\,(\textrm{mod}\, k)$ and that the $k^{\rm th}$-power classes $\textrm{mod}\, p$ induce a coloring of the integer segment $[0,\, p-1]$ that admits no monochromatic occurrence of $l$ consecutive members of an arithmetic progression. Such a coloring can lead to a coloring of $[0,\,(l-1)p]$ that is similarly free of monochromatic $l$-progressions, and, hence, can give directly a lower bound for the van der Waerden number $W(k,l)$. P. R. Herwig, M. J. H. Heule, P. M. van Lambalgen, and H. van Maaren have devised a technique for splitting and "zipping" such a coloring of $[0,\, p-1]$ to yield a coloring of $[0,\,2p-1]$ which, for even values of $k$, is sometimes extendable to a coloring of $[0,\,2(l-1)p]$ where both new colorings still admit no monochromatic $l$-progressions. Here we derive a fast procedure for checking whether such a zipped coloring remains free of monochromatic $l$-progressions, effectively reducing a quadratic-time check to a linear-time check. Using this procedure we find some new lower bounds for van der Waerden numbers.
Distance Powers and Distance Matrices of Integral Cayley Graphs over Abelian Groups
Authors: Klotz Walter , Sander Torsten
Published: January 2020

It is shown that distance powers of an integral Cayley graph over an abelian group $\Gamma$ are again integral Cayley graphs over $\Gamma$. Moreover, it is proved that distance matrices of integral Cayley graphs over abelian groups have integral spectrum.
Modular Schur Numbers
Authors: Chappelon Jonathan , Revuelta Marchena María Pastora , Sanz Domínguez María Isabel
Published: January 2020

For any positive integers $l$ and $m$, a set of integers is said to be (weakly) $l$-sum-free modulo $m$ if it contains no (pairwise distinct) elements $x_1,x_2,\ldots,x_l,y$ satisfying the congruence $x_1+\ldots+x_l\equiv y\bmod{m}$. It is proved that, for any positive integers $k$ and $l$, there exists a largest integer $n$ for which the set of the first $n$ positive integers $\{1,2,\ldots,n\}$ admits a partition into $k$ (weakly) $l$-sum-free sets modulo $m$. This number is called the generalized (weak) Schur number modulo $m$, associated with $k$ and $l$. In this paper, for all positive integers $k$ and $l$, the exact value of these modular Schur numbers are determined for $m=1$, $2$ and $3$.
Sum and Shifted-Product Subsets of Product-Sets over Finite Rings
Authors: Le Anh Vinh
Published: January 2020

For sufficiently large subsets $\mathcal{A}, \mathcal{B}, \mathcal{C}, \mathcal{D}$ of $\mathbb{F}_q$, Gyarmati and Sárközy (2008)  showed the solvability of the equations $a + b= c d$ and $a b + 1 = c d$ with $a \in \mathcal{A}$, $b \in\mathcal{B}$, $c \in \mathcal{C}$, $d \in \mathcal{D}$. They asked whether one can extend these results to every $k \in \mathbb{N}$ in the following way: for large subsets $\mathcal{A}, \mathcal{B}, \mathcal{C}, \mathcal{D}$ of $\mathbb{F}_q$,  there are $a_1, \ldots, a_k, a_1', \ldots, a_k' \in\mathcal{A}$, $b_1, \ldots, b_k, b_1', \ldots, b_k' \in \mathcal{B}$ with $a_i + b_j, a_i' b_j' + 1 \in \mathcal{C}\mathcal{D}$ (for $1 \leq i, j\leq k)$. The author (2010) gave an affirmative answer to this question using Fourier analytic methods. In this paper, we will extend this result to the setting of finite cyclic rings using tools from spectral graph theory.
Extremal Hypergraphs for the Biased Erdős-Selfridge Theorem
Authors: Sundberg Eric Lars
Published: January 2020

A positional game is essentially a generalization of Tic-Tac-Toe played on a hypergraph $(V,{\cal F}).$  A pivotal result in the study of positional games is the Erdős–Selfridge theorem, which gives a simple criterion for the existence of a Breaker's winning strategy on a finite hypergraph ${\cal F}$.  It has been shown that the bound in the Erdős–Selfridge theorem can be tight and that numerous extremal hypergraphs exist that demonstrate the tightness of the bound. We focus on a generalization of the Erdős–Selfridge theorem proven by Beck for biased $(p:q)$ games, which we call the $(p:q)$–Erdős–Selfridge theorem.  We show that for $pn$-uniform hypergraphs there is a unique extremal hypergraph for the $(p:q)$–Erdős–Selfridge theorem when $q\geq 2$.
Hopf Algebra of Building Sets
Authors: Grujić Vladimir , Stojadinović Tanja
Published: January 2020

The combinatorial Hopf algebra on building sets $BSet$ extends the chromatic Hopf algebra of simple graphs. The image of a building set under canonical morphism to quasi-symmetric functions is the chromatic symmetric function of the corresponding hypergraph. By passing from graphs to building sets, we construct a sequence of symmetric functions associated to a graph. From the generalized Dehn-Sommerville relations for the Hopf algebra $BSet$, we define a class of building sets called eulerian and show that eulerian building sets satisfy Bayer-Billera relations. We show the existence of the $\mathbf{c}\mathbf{d}-$index, the polynomial in two noncommutative variables associated to an eulerian building set. The complete characterization of eulerian building sets is given in terms of combinatorics of intersection posets of antichains of finite sets.
Statistics of Blocks in k-Divisible Non-Crossing Partitions
Authors: Arizmendi Octavio
Published: January 2020

We derive a formula for the expected number of blocks of a given size from a non-crossing partition chosen uniformly at random. Moreover, we refine this result subject to the restriction of having a number of blocks given.Furthermore, we generalize to $k$-divisible partitions. In particular, we find that, asymptotically, the expected number of blocks of size $t$ of a $k$-divisible non-crossing partition of $nk$ elements chosen uniformly at random is $\frac{kn+1}{(k+1)^{t+1}}$. Similar results are obtained for type $B$ and type $D$ non-crossing partitions of Armstrong.
Alternating, Pattern-Avoiding Permutations
Authors: Lewis Joel Brewster
Published: January 2020

We study the problem of counting alternating permutations avoiding collections of permutation patterns including $132$. We construct a bijection between the set $S_n(132)$ of $132$-avoiding permutations and the set $A_{2n + 1}(132)$ of alternating, $132$-avoiding permutations. For every set $p_1, \ldots, p_k$ of patterns and certain related patterns $q_1, \ldots, q_k$, our bijection restricts to a bijection between $S_n(132, p_1, \ldots, p_k)$, the set of permutations avoiding $132$ and the $p_i$, and $A_{2n + 1}(132, q_1, \ldots, q_k)$, the set of alternating permutations avoiding $132$ and the $q_i$. This reduces the enumeration of the latter set to that of the former.
The Maximal Number of Runs in Standard Sturmian Words
Authors: Baturo Paweł , Piątkowski Marcin , Rytter Wojciech
Published: January 2020

We investigate some repetition problems for a very special class $\mathcal{S}$ of strings called the standard Sturmian words, which  have very compact representations in terms of sequences of integers. Usually the size of this word is exponential with respect to the size of its integer sequence, hence we are dealing with repetition problems in compressed strings. An explicit formula is given for the number $\rho(w)$ of runs in a standard word $w$. We show that $\rho(w)/|w|\le 4/5$ for each $w\in S$, and  there is an infinite sequence of strictly growing words $w_k\in {\mathcal{S}}$ such that $\lim_{k\rightarrow \infty} \frac{\rho(w_k)}{|w_k|} = \frac{4}{5}$. Moreover, we show how to compute the number of runs in a standard Sturmian word in linear time with respect to the size of its compressed representation.
Multigraphs (Only) Satisfy a Weak Triangle Removal Lemma
Authors: Shapira Asaf , Yuster Raphael
Published: January 2020

The triangle removal lemma states that a simple graph with $o(n^3)$ triangles can be made triangle-free by removing $o(n^2)$ edges. It is natural to ask if this widely used result can be extended to multi-graphs. In this short paper we rule out the possibility of such an extension by showing that there are multi-graphs with only $n^{2+o(1)}$ triangles that are still far from being triangle-free. On the other hand, we show that for some slowly growing function $g(n)=\omega(1)$, if a multi-graph has only $g(n)n^2$ triangles then it must be close to being triangle-free. The proof relies on variants of the Ruzsa-Szemerédi theorem.
Expected Patterns in Permutation Classes
Authors: Homberger Cheyne
Published: January 2020

Each length $k$ pattern occurs equally often in the set $S_n$ of all permutations of length $n$, but the same is not true in general for a proper subset of $S_n$. Miklós Bóna recently proved that if we consider the set of $n$-permutations avoiding the pattern 132, all other non-monotone patterns of length 3 are equally common. In this paper we focus on the set $\operatorname{Av}_n (123)$ of $n$-permutations avoiding $123$, and give exact formulae for the occurrences of each length 3 pattern. While this set does not have the same symmetries as $\operatorname{Av}_n (132)$, we find several similarities between the two and prove that the number of 231 patterns is the same in each.
Bounding Tree-Width via Contraction on the Projective Plane and Torus.
Authors: Morgan Evan , Oporowski Bogdan
Published: January 2020

If $X$ is a collection of edges in a graph $G$, let $G/X$ denote the contraction of $X$. Following a question of Oxley and a conjecture of Oporowski, we prove that every projective planar graph $G$ admits an edge partition $\{X,Y\}$ such that $G/X$ and $G/Y$ have tree-width at most three. We prove that every toroidal graph $G$ admits an edge partition $\{X,Y\}$ such that $G/X$ and $G/Y$ have tree-width at most three and four, respectively.
A Note on Edge-Colourings Avoiding Rainbow $K_4$ and Monochromatic $K_m$
Authors: Jungić Veselin , Kaiser Tomáš , Král' Daniel
Published: January 2020

We study the mixed Ramsey number $maxR(n,{K_m},{K_r})$, defined as the maximum number of colours in an edge-colouring of the complete graph $K_n$, such that $K_n$ has no monochromatic complete subgraph on $m$ vertices and no rainbow complete subgraph on $r$ vertices. Improving an upper bound of Axenovich and Iverson, we show that $maxR(n,{K_m},{K_4}) \leq n^{3/2}\sqrt{2m}$ for all $m\geq 3$. Further, we discuss a possible way to improve their lower bound on $maxR(n,{K_4},{K_4})$ based on incidence graphs of finite projective planes.
Planar Graphs of Maximum Degree Six without 7-cycles are Class One
Authors: Huang Danjun , Wang Weifan
Published: January 2020

In this paper, we prove that every planar graph of maximum degree six without 7-cycles is class one.
Biregular Cages of Girth Five
Authors: Abreu Marién , Araujo-Pardo Gabriela , Balbuena Camino , Labbate Domenico , López-Chávez Gloria
Published: January 2020

Let $2 \le r < m$ and $g$ be positive integers. An $(\{r,m\};g)$-graph (or biregular graph) is a graph with degree set $\{r,m\}$ and girth $g$, and an $(\{r,m\};g)$-cage (or biregular cage) is an $(\{r,m\};g)$-graph of minimum order $n(\{r,m\};g)$. If $m=r+1$, an $(\{r,m\};g)$-cage is said to be a semiregular cage.In this paper we generalize the reduction and graph amalgam operations from [M. Abreu,  G. Araujo-Pardo, C. Balbuena, D. Labbate. Families of Small Regular Graphs of Girth $5$. Discrete Math. 312 (2012) 2832--2842] on the incidence graphs of an affine and a biaffine plane obtaining two new infinite families of biregular cages and two new semiregular cages. The constructed new families are $(\{r,2r-3\};5)$-cages for all $r=q+1$ with $q$ a prime power, and $(\{r,2r-5\};5)$-cages for all $r=q+1$ with $q$ a prime. The new semiregular cages are constructed for $r=5$ and $6$ with $31$ and $43$ vertices respectively.
Baxter Permutations, Maj-Balances, and Positive Braids
Authors: Eu Sen-Peng , Fu Tung-Shan , Pan Yeh-Jong , Ting Chien-Tai
Published: January 2020

In this paper we present two interesting properties of 321-avoiding Baxter permutations. The first one is a variant of refined major-balance identity for the 321-avoiding Baxter permutations, respecting the number of fixed points and descents. The second one is a bijection between the 321-avoiding Baxter permutations with the entry 1 preceding the entry 2 and the positive braid words on four strands.
Matchings in Random Biregular Bipartite Graphs
Authors: Perarnau Guillem , Petridis Giorgis
Published: January 2020

We study the existence of perfect matchings in suitably chosen induced subgraphs of random biregular bipartite graphs. We prove a result similar to a classical theorem of Erdös and Rényi about perfect matchings in random bipartite graphs. We also present an application to commutative graphs, a class of graphs that are featured in additive number theory.
Graph Labeling
Authors: Gallian Joseph A.
Published: January 2020

A graph labeling is an assignment of integers to the vertices or edges, or both, subject to certain conditions. Graph labelings were first introduced in the mid 1960s. In the intervening 50 years nearly 200 graph labelings techniques have been studied in over 2000 papers. Finding out what has been done for any particular kind of labeling and keeping up with new discoveries is difficult because of the sheer number of papers and because many of the papers have appeared in journals that are not widely available. In this survey I have collected everything I could find on graph labeling. For the convenience of the reader the survey includes a detailed table of contents and index.
Some Constant Weight Codes from Primitive Permutation Groups
Authors: Smith Derek H. , Montemanni Roberto
Published: January 2020

In recent years the detailed study of the construction of constant weight codes has been extended from length at most 28 to lengths less than 64. Andries Brouwer maintains web pages with tables of the best known constant weight codes of these lengths. In many cases the codes have more codewords than the best code in the literature, and are not particularly easy to improve. Many of the codes are constructed using a specified permutation group as automorphism group. The groups used include cyclic, quasi-cyclic, affine general linear groups etc. sometimes with fixed points. The precise rationale for the choice of groups is not clear.In this paper the choice of groups is made systematic by the use of the classification of primitive permutation groups. Together with several improved techniques for finding a maximum clique, this has led to the construction of 39 improved constant weight codes.
Directed Animals, Quadratic Systems and Rewriting Systems
Authors: Marckert Jean-François
Published: January 2020

A directed animal is a percolation cluster in the directed site percolation model. The aim of this paper is to exhibit a strong relation between the problem of computing the generating function G of directed animals on the square lattice, counted according to the area and the perimeter, and the problem of solving a system of quadratic equations involving unknown matrices. We present some solid evidence that some infinite explicit matrices, the fixed points of a rewriting like system are the natural solutions to this system of equations: some strong evidence is given that the problem of finding G reduces to the problem of finding an eigenvector to an explicit infinite matrix.  Similar properties are shown for other combinatorial questions concerning directed animals, and for different lattices.
A Note on Automorphisms of the Infinite-Dimensional Hypercube Graph
Authors: Pankov Mark
Published: January 2020

We define the infinite-dimensional hypercube graph $H_{{\aleph}_{0}}$ as a graph whose vertex set is formed by the so-called singular subsets of ${\mathbb Z}\setminus\{0\}$. This graph is not connected, but it has isomorphic connected components. We show that the restrictions of its automorphisms to the connected components  are induced by permutations on ${\mathbb Z}\setminus\{0\}$ preserving the family of singular subsets. As an application, we describe the automorphism group of the connected components.
On Universal Cycles of Labeled Graphs
Authors: Brockman Greg , Kay Bill , Snively Emma E.
Published: January 2020

A universal cycle is a compact listing of a class of combinatorial objects. In this paper, we prove the existence of universal cycles of classes of labeled graphs, including simple graphs, trees, graphs with $m$ edges, graphs with loops, graphs with multiple edges (with up to $m$ duplications of each edge), directed graphs, hypergraphs, and $k$-uniform hypergraphs.
Enumeration of (16,4,16,4) Relative Difference Sets
Authors: Clark David , Tonchev Vladimir D.
Published: January 2020

A complete enumeration of relative difference sets (RDS) with parameters $(16,4,16,4)$ in a group of order 64 with a normal subgroup $N$ of order 4 is given. If $N=Z_4$, three of the 11 abelian groups of order 64, and 23 of the 256 nonabelian groups of order 64 contain  $(16,4,16,4)$ RDSs. If $N=Z_2 \times Z_2$, nine of the abelian groups and 194 of the non-abelian groups of order 64 contain  $(16,4,16,4)$  RDSs.
Generalized Alcuin's Sequence
Authors: Panario Daniel , Sahin Murat , Wang Qiang
Published: January 2020

We introduce a new family of sequences $\{t_k(n)\}_{n=-\infty}^{\infty}$ for given positive integer $k$. We call these new sequences asgeneralized Alcuin's sequences because we get Alcuin's sequence which has several interesting properties when $k=3$. Also, $\{t_k(n)\}_{n=0}^{\infty}$ counts the number of partitions of $n-k$ with parts being $k, \left(k-1\right), 2\left(k-1\right),$ $3\left(k-1\right)$, $\ldots, \left(k-1\right)\left(k-1\right)$. We find an explicit linear recurrence equation and the generating function for $\{t_k(n)\}_{n=-\infty}^{\infty}$. For the special case $k=4$ and $k=5$, we get a simpler formula for $\{t_k(n)\}_{n=-\infty}^{\infty}$ and investigate the period of $\{t_k(n)\}_{n=-\infty}^{\infty}$ modulo a fixed integer. Also, we get a formula for $p_{5}\left(n\right)$ which is the number of partitions of $n$ into exactly $5$ parts.
Edge-Disjoint Induced Subgraphs with Given Minimum Degree
Authors: Yuster Raphael
Published: January 2020

Let $h$ be a given positive integer. For a graph with $n$ vertices and $m$ edges, what is the maximum number of pairwise edge-disjoint {\em induced} subgraphs, each having  minimum degree at least $h$? There are examples for which this number is $O(m^2/n^2)$. We prove that this bound is achievable for all graphs with polynomially many edges. For all $\epsilon > 0$, if $m \ge n^{1+\epsilon}$, then there are always $\Omega(m^2/n^2)$ pairwise edge-disjoint induced subgraphs, each having  minimum degree at least $h$. Furthermore, any two subgraphs intersect in an independent set of size at most $1+ O(n^3/m^2)$, which is shown to be asymptotically optimal.
Forcing Finite Minors in Sparse Infinite Graphs by Large-Degree Assumptions
Authors: Diestel Reinhard
Published: January 2020

Developing further Stein's recent notion of relative end degrees in infinite graphs, we investigate which degree assumptions can force a locally finite graph to contain a given finite minor, or a finite subgraph of given minimum or average degree. This is part of a wider project which seeks to develop an extremal theory of sparse infinite graphs.
On the Relationship between Pipe Dreams and Permutation Words
Authors: Marcott Cameron
Published: January 2020

Pipe dreams represent permutations pictorially as a series of crossing pipes. Recent applications of pipe dreams include the calculation of Schubert polynomials, fillings of moon polyominoes, and in the combinatorics of antidiagonal simplicial complexes. These applications associate pipe dreams to words of elementary symmetric transpositions via a canonical mapping. However, this canonical mapping is by no means the only way of mapping pipe dreams to permutation words. We define sensical mappings from pipe dreams to words and prove sensical mappings are in bijection with standard shifted tableaux of triangular shape. We characterize the set of pipe dreams associated to a given word (under any sensical map) using step ladder moves. These moves induce a partial order on the set of pipe dreams mapping to a given word, yielding a distributive lattice.
Extremal Values of Ratios: Distance Problems vs. Subtree Problems in Trees
Authors: Székely László , Wang Hua
Published: January 2020

The authors discovered a dual behaviour of two tree indices, the Wiener index and the number of subtrees, for a number of extremal problems  [Discrete Appl. Math. 155 (3) 2006, 374-385;  Adv. Appl. Math. 34 (2005), 138-155]. Barefoot, Entringer and Székely [Discrete Appl. Math. 80 (1997), 37-56] determined extremal values of $\sigma_T(w)/\sigma_T(u)$,   $\sigma_T(w)/\sigma_T(v)$, $\sigma(T)/\sigma_T(v)$, and $\sigma(T)/\sigma_T(w)$, where $T$ is a tree on $n$ vertices, $v$ is in the centroid of the tree $T$, and $u,w$ are leaves in $T$.In this paper  we test how far the negative correlation between distances and subtrees go if we look for the   extremal values of $F_T(w)/F_T(u)$, $F_T(w)/F_T(v)$, $F(T)/F_T(v)$, and $F(T)/F_T(w)$, where $T$ is a tree on $n$ vertices, $v$ is in the subtree core of the tree $T$, and $u,w$ are leaves in $T$-the complete analogue of  [Discrete Appl. Math. 80 (1997), 37-56], changing distances to the number of subtrees.  We include a number of open problems, shifting the interest towards the number of subtrees in graphs.
Which Exterior Powers are Balanced?
Authors: Mallory Devlin , Raz Abigail , Tamon Christino , Zaslavsky Thomas
Published: January 2020

A signed graph is a graph whose edges are given $\pm 1$ weights. In such a graph, the sign of a cycle is the product of the signs of its edges. A signed graph is called balanced if its adjacency matrix is similar to the adjacency matrix of an unsigned graph via conjugation by a diagonal $\pm 1$ matrix. For a signed graph $\Sigma$ on $n$ vertices, its exterior $k$th power, where $k=1,\ldots,n-1$, is a graph $\bigwedge^{k} \Sigma$ whose adjacency matrix is given by\[ A(\mbox{$\bigwedge^{k} \Sigma$}) = P_{\wedge}^{\dagger} A(\Sigma^{\Box k}) P_{\wedge}, \]where $P_{\wedge}$ is the projector onto the anti-symmetric subspace of the $k$-fold tensor product space $(\mathbb{C}^{n})^{\otimes k}$ and $\Sigma^{\Box k}$ is the $k$-fold Cartesian product of $\Sigma$ with itself. The exterior power creates a signed graph from any graph, even unsigned. We prove sufficient and necessary conditions so that $\bigwedge^{k} \Sigma$ is balanced. For $k=1,\ldots,n-2$, the condition is that either $\Sigma$ is a signed path or $\Sigma$ is a signed cycle that is balanced for odd $k$ or is unbalanced for even $k$; for $k=n-1$, the condition is that each even cycle in $\Sigma$ is positive and each odd cycle in $\Sigma$ is negative.
Nested Recursions, Simultaneous Parameters and Tree Superpositions
Authors: Isgur Abraham , Kuznetsov Vitaly , Rahman Mustazee , Tanny Stephen
Published: January 2020

We apply a tree-based methodology to solve new, very broadly defined families of nested recursions of the general form $R(n)=\sum_{t=1}^k R(n-a_t-\sum_{i=1}^{p}R(n-b_{ti}))$, where $a_t$ are integers, $b_{ti}$ are natural numbers, and $k,p$ are natural numbers that we use to denote "arity" and "order," respectively, and with some specified initial conditions. The key idea of the tree-based solution method is to associate such recursions with infinite labelled trees in a natural way so that the solution to the recursions solves a counting question relating to the corresponding trees. We characterize certain recursion families within $R(n)$ by introducing "simultaneous parameters" that appear both within the recursion itself and that also specify structural properties of the corresponding tree. First, we extend and unify recently discovered results concerning two families of arity $k=2$, order $p=1$ recursions. Next, we investigate the solution of nested recursion families by taking linear combinations of solution sequence frequencies for simpler nested recursions, which correspond to superpositions of the associated trees; this leads us to identify and solve two new recursion families for arity $k=2$ and general order $p$. Finally, we extend these results to general arity $k>2$. We conclude with several related open problems.
Medial Symmetry Type Graphs
Authors: Hubard Isabel , Del Río Francos María , Orbanić Alen , Pisanski Tomaž
Published: January 2020

A $k$-orbit map is a map with its automorphism group partitioning the set of flags into $k$ orbits. Recently $k$-orbit maps were studied by Orbanić, Pellicer and Weiss, for $k \leq 4$. In this paper we use symmetry type graphs to extend such study and classify all the types of $5$-orbit maps, as well as all self-dual, properly and improperly, symmetry type of $k$-orbit maps with $k\leq 7$. Moreover, we determine, for small values of $k$, all types of $k$-orbits maps that are medial maps. Self-dualities constitute an important tool in this quest.
On the Number of Nonequivalent Propelinear Extended Perfect Codes
Authors: Borges Joaquim , Mogilnykh Ivan Yu. , Rifà Josep , Solov'eva Faina I.
Published: January 2020

The paper proves that there exists an exponential number of nonequivalent propelinear extended perfect binary codes of length growing to infinity. Specifically, it is proved that all transitive extended perfect binary codes found by Potapov (2007) are propelinear. All such codes have small rank, which is one more than the rank of the extended Hamming code of the same length. We investigate the properties of these codes and show that any of them has a normalized propelinear representation.
Distance-Regular Graphs with an Eigenvalue $-k < \theta \leq 2-k$
Authors: Bang Sejeong
Published: January 2020

It is known that bipartite distance-regular graphs with diameter $D\geq 3$, valency $k\geq 3$, intersection number $c_2\geq 2$ and eigenvalues $k = \theta_0 > \theta_1 > \cdots > \theta_D$ satisfy $\theta_1\leq  k-2$ and thus $\theta_{D-1}\geq 2-k$. In this paper we classify non-complete distance-regular graphs with valency $k\geq 2$, intersection number $c_2\geq 2$ and an eigenvalue $\theta$ satisfying $-k< \theta \leq 2-k$. Moreover, we give a lower bound for valency $k$ which implies $\theta_D \geq 2-k$ for distance-regular graphs with girth $g\geq 5$ satisfying $g=5$ or $ g \equiv 3~(\operatorname{mod}~4)$.
Nonexistence of a Class of Distance-Regular Graphs
Authors: Huang Yu-pei , Pan Yeh-jong , Weng Chih-wen
Published: January 2020

Let $\Gamma$ denote a distance-regular graph with diameter $D \geq 3$ and intersection numbers $a_1=0, a_2 \neq 0$, and $c_2=1$. We show a connection between the $d$-bounded property and the nonexistence of parallelograms of any length up to $d+1$. Assume further that $\Gamma$ is with classical parameters $(D, b, \alpha, \beta)$, Pan and Weng (2009) showed that $(b, \alpha, \beta)= (-2, -2, ((-2)^{D+1}-1)/3).$ Under the assumption $D \geq 4$, we exclude this class of graphs by an application of the above connection.
Linked Partitions and Permutation Tableaux
Authors: Chen William Y.C. , Liu Lewis H. , Wang Carol J.
Published: January 2020

Linked partitions were introduced by Dykema in the study of transforms in free probability theory, whereas permutation tableaux were introduced by Steingrímsson and Williams in the study of totally positive Grassmannian cells. Let $[n]=\{1,2,\ldots,n\}$. Let $L(n,k)$ denote the set of  linked partitions of $[n]$ with $k$ blocks, let $P(n,k)$ denote the set of  permutations of $[n]$ with $k$ descents, and let $T(n,k)$ denote the set of permutation tableaux of length $n$ with $k$ rows. Steingrímsson and Williams found a bijection between the set of permutation tableaux of length $n$ with $k$ rows and the set of permutations of $[n]$ with $k$ weak excedances. Corteel and Nadeau gave a bijection between the set of permutation tableaux of length $n$ with $k$ columns and the set of permutations of $[n]$ with $k$ descents. In this paper, we establish a bijection between $L(n,k)$ and $P(n,k-1)$ and a bijection between $L(n,k)$ and $T(n,k)$. Restricting the latter bijection to  noncrossing linked partitions and nonnesting linked partitions, we find that the corresponding  permutation tableaux can be characterized by pattern avoidance.
Counting $k$-Convex Polyominoes
Authors: Micheli Anne , Rossin Dominique
Published: January 2020

We compute an asymptotic estimate of a lower bound of the number of $k$-convex polyominoes of semiperimeter $p$. This approximation can be written as $\mu(k) p 4^p$ where $\mu(k)$ is a rational fraction of $k$ which up to $\mu(k)$ is the asymptotics of convex polyominoes.
Extremal Problems for Subset Divisors
Authors: Huynh Tony
Published: January 2020

Let $A$ be a set of $n$ positive integers. We say that a subset $B$ of $A$ is a divisor of $A$, if the sum of the elements in $B$ divides the sum of the elements in $A$. We are interested in the following extremal problem. For each $n$, what is the maximum number of divisors a set of $n$ positive integers can have? We determine this function exactly for all values of $n$. Moreover, for each $n$ we characterize all sets that achieve the maximum. We also prove results for the $k$-subset analogue of our problem. For this variant, we determine the function exactly in the special case that $n=2k$. We also characterize all sets that achieve this bound when $n=2k$.
On the Number of Colored Birch and Tverberg Partitions
Authors: Hell Stephan
Published: January 2020

In 2009, Blagojević, Matschke, and Ziegler established the first tight colored Tverberg theorem. We develop a colored version of our previous results (2008): Evenness and non-trivial lower bounds for the number of colored Tverberg partitions. Both properties follow from similar results on the number of colored Birch partitions.
Sharply Transitive $1$-Factorizations of Complete Multipartite Graphs
Authors: Mazzuoccolo Giuseppe , Rinaldi Gloria
Published: January 2020

Given a finite group $G$ of even order, which graphs $\Gamma$ have a $1$-factorization admitting $G$ as automorphism group with a sharply transitive action on the vertex-set? Starting from this question, we prove some general results and develop an exhaustive analysis when $\Gamma$ is a complete multipartite graph and $G$ is cyclic.
On the Kirchhoff and the Wiener Indices of Graphs and Block Decomposition
Authors: Nikseresht Ashkan , Sepasdar Zahra
Published: January 2020

In this article we state a relation between the Kirchhoff and Wiener indices of a simple connected graph $G$ and the Kirchhoff and Wiener indices of those subgraphs of $G$ which are induced by its blocks. Then as an application, we define a composition of a rooted tree $T$ and a graph $G$ and calculate its Kirchhoff index in terms of parameters of $T$ and $G$. Finally, we present an algorithm for computing the resistance distances and the Kirchhoff index and a similar one for computing the weighted distances and the Wiener index of a graph. These algorithms are asymptotically faster than the previously known algorithms, on graphs in which the order of the subgraphs induced by blocks is small with respect to the order of the graph.