bluuebunny/crossref_metadata_2025 huggingface dataset:
A Laurent Series Proof of the Habsieger-Kadell $q$-Morris Identity
Authors: Guoce Xin , Yue Zhou
Published: January 2020

We give a Laurent series proof of the Habsieger-Kadell $q$-Morris identity, which is a common generalization of the $q$-Morris identity and the Aomoto constant term identity. The proof allows us to extend the theorem for some additional parameter cases.
Enumerating Permutations by their Run Structure
Authors: Fewster Christopher J. , Siemssen Daniel
Published: January 2020

Motivated by a problem in quantum field theory, we study the up and down structure of circular and linear permutations. In particular, we count the length of the (alternating) runs of permutations by representing them as monomials and find that they can always be decomposed into so-called 'atomic' permutations introduced in this work. This decomposition allows us to enumerate the (circular) permutations of a subset of $\mathbb{N}$ by the length of their runs. Furthermore, we rederive, in an elementary way and using the methods developed here, a result due to Kitaev on the enumeration of valleys.
On the Typical Structure of Graphs in a Monotone Property
Authors: Janson Svante , Uzzell Andrew J.
Published: January 2020

Given a graph property $\mathcal{P}$, it is interesting to determine the typical structure of graphs that satisfy $\mathcal{P}$.  In this paper, we consider monotone properties, that is, properties that are closed under taking subgraphs.  Using results from the theory of graph limits, we show that if $\mathcal{P}$ is a monotone property and $r$ is the largest integer for which every $r$-colorable graph satisfies $\mathcal{P}$, then almost every graph with $\mathcal{P}$ is close to being a balanced $r$-partite graph.
The Combinatorial Nullstellensätze Revisited
Authors: Clark Pete L.
Published: January 2020

We revisit and further explore the celebrated Combinatorial Nullstellensätze of N. Alon in several different directions.
Disjoint Compatibility Graph of Non-Crossing Matchings of Points in Convex Position
Authors: Aichholzer Oswin , Asinowski Andrei , Miltzow Tillmann
Published: January 2020

Let $X_{2k}$ be a set of $2k$ labeled points in convex position in the plane. We consider geometric non-intersecting straight-line perfect matchings of $X_{2k}$. Two such matchings, $M$ and $M'$, are disjoint compatible if they do not have common edges, and no edge of $M$ crosses an edge of $M'$. Denote by $\rm{DCM}_k$ the graph whose vertices correspond to such matchings, and two vertices are adjacent if and only if the corresponding matchings are disjoint compatible. We show that for each $k \geq 9$, the connected components of $\rm{DCM}_k$ form exactly three isomorphism classes - namely, there is a certain number of isomorphic small components, a certain number of isomorphic medium components, and one big component. The number and the structure of small and medium components is determined precisely.
On $m$-Closed Graphs
Authors: Sharifan Leila , Javanbakht Masoumeh
Published: January 2020

A graph is closed when its vertices have a labeling by $[n]$ such that the binomial edge ideal $J_G$ has a quadratic Gröbner basis with respect to the lexicographic order induced by $x_1 > \ldots > x_n > y_1> \ldots > y_n$. In this paper, we generalize this notion and study the so called $m$-closed graphs. We find equivalent condition to $3$-closed property of an arbitrary tree $T$. Using it, we classify a class of $3$-closed trees. The primary decomposition of this class of graphs is also studied.
An Extremal Property of Turán Graphs
Authors: Lazebnik Felix , Tofts Spencer
Published: January 2020

Let ${\cal F}_{n,t_r(n)}$ denote the family of all graphs on $n$ vertices and $t_r(n)$ edges, where $t_r(n)$ is the number of edges in the Turán's graph $T_r(n)$ – the complete $r$-partite graph on $n$ vertices with partition sizes as equal as possible. For a graph $G$ and a positive integer $\lambda$, let $P_G(\lambda)$ denote the number of proper vertex colorings of $G$ with at most $\lambda$ colors, and let $f(n,t_r(n),\lambda) = \max\{P_G(\lambda):G \in {\cal F}_{n,t_r(n)}\}$. We prove that for all $n\ge r\ge 2$, $f(n,t_r(n),r+1) = P_{T_r(n)}(r+1)$ and that $T_r(n)$ is the only extremal graph.
New Results about Set Colorings of Graphs
Authors: Boutin J. P. , Duchêne E. , Effantin B. , Kheddouci H. , Seba H.
Published: January 2020

The set coloring problem is a new kind of both vertex and edge coloring of a graph introduced by Suresh Hegde in 2009. Only large bounds have been given on the chromatic number for general graphs. In this paper, we consider the problem on paths and complete binary trees, and show that it can be reduced to the computation of a transversal in a special Latin square, i.e., the XOR table. We then investigate a variation of the problem called strong set coloring, and we provide an exhaustive list of all graphs being strongly set colorable with at most 4 colors.
On a Refinement of Wilf-equivalence for Permutations
Authors: Yan Sherry  H.F. , Ge Huiyun , Zhang Yaqiu
Published: January 2020

Recently, Dokos et al. conjectured that for all $k, m\geq 1$, the patterns $ 12\ldots k(k+m+1)\ldots (k+2)(k+1) $ and $(m+1)(m+2)\ldots  (k+m+1)m\ldots 21$ are $maj$-Wilf-equivalent. In this paper, we confirm this conjecture for all $k\geq 1$ and $m=1$. In fact, we construct a descent set preserving bijection between $ 12\ldots k (k-1) $-avoiding permutations and $23\ldots k1$-avoiding permutations for all $k\geq 3$. As a corollary, our bijection enables us to settle a conjecture of  Gowravaram and Jagadeesan concerning the Wilf-equivalence for  permutations with given descent sets.
A New Approach to the 2-Regularity of the $\ell$-Abelian Complexity of 2-Automatic Sequences
Authors: Parreau Aline , Rigo Michel , Rowland Eric , Vandomme Élise
Published: January 2020

We prove that a sequence satisfying a certain symmetry property is $2$-regular in the sense of Allouche and Shallit, i.e., the $\mathbb{Z}$-module generated by its $2$-kernel is finitely generated. We apply this theorem to develop a general approach for studying the $\ell$-abelian complexity of $2$-automatic sequences. In particular, we prove that the period-doubling word and the Thue-Morse word have $2$-abelian complexity sequences that are $2$-regular. Along the way, we also prove that the $2$-block codings of these two words have $1$-abelian complexity sequences that are $2$-regular.
A Note on Goldbach Partitions of Large Even Integers
Authors: Mutafchiev Ljuben
Published: January 2020

Let $\Sigma_{2n}$ be the set of all partitions of the even integers from the interval $(4,2n], n>2,$ into two odd prime parts. We show that $|\Sigma_{2n}| \sim 2n^2/\log^2{n}$ as $n\to\infty$. We also assume that a partition is selected uniformly at random from the set $\Sigma_{2n}$. Let $2X_n\in (4,2n]$ be the size of this partition. We prove a limit theorem which establishes that $X_n/n$ converges weakly to the maximum of two random variables which are independent copies of a uniformly distributed random variable in the interval $(0,1)$. Our method of proof is based on a classical Tauberian theorem due to Hardy, Littlewood and Karamata. We also show that the same asymptotic approach can be applied to partitions of integers into an arbitrary and fixed number of odd prime parts.
Some Symmetric Identities involving a Sequence of Polynomials
Authors: He Yuan , Zhang Wenpeng
Published: January 2020

In this paper we establish some symmetric identities on a sequence of polynomials in an elementary way, and some known identities involving Bernoulli and Euler numbers and polynomials are obtained as particular cases.
Computing the Tutte Polynomial of a Matroid from its Lattice of Cyclic Flats
Authors: Eberhardt Jens Niklas
Published: January 2020

We show how the Tutte polynomial of a matroid $M$ can be computed from its condensed configuration, which is a statistic of its lattice of cyclic flats. The results imply that the Tutte polynomial of $M$ is already determined by the abstract lattice of its cyclic flats together with their cardinalities and ranks. They furthermore generalize similiar statements for perfect matroid designs and near designs due to Brylawski (1980) and help to understand families of matroids with identical Tutte polynomials as constructed by Giménez and later improved by Shoda (2012).
Density of Gallai Multigraphs
Authors: Magnant Colton
Published: January 2020

Diwan and Mubayi asked how many edges of each color could be included in a $3$-edge-colored multigraph containing no rainbow triangle.  We answer this question under the modest assumption that the multigraphs in question contain at least one edge between every pair of vertices.  We also conjecture that this assumption is, in fact, without loss of generality.
Counting Permutations by Alternating Descents
Authors: Gessel Ira M. , Zhuang Yan
Published: January 2020

We find the exponential generating function for permutations with all valleys even and all peaks odd, and use it to determine the asymptotics for its coefficients, answering a question posed by Liviu Nicolaescu. The generating function can be expressed as the reciprocal of a sum involving Euler numbers: \[\left(1-E_1x+E_{3}\frac{x^{3}}{3!}-E_{4}\frac{x^{4}}{4!}+E_{6}\frac{x^{6}}{6!}-E_{7}\frac{x^{7}}{7!}+\cdots\right)^{-1},\tag{$*$}\]where $\sum_{n=0}^\infty E_n x^n\!/n! = \sec x + \tan x$. We give two proofs of this formula. The first uses a system of differential equations whose solution gives the generating function\begin{equation*}\frac{3\sin\left(\frac{1}{2}x\right)+3\cosh\left(\frac{1}{2}\sqrt{3}x\right)}{3\cos\left(\frac{1}{2}x\right)-\sqrt{3}\sinh\left(\frac{1}{2}\sqrt{3}x\right)},\end{equation*} which we then show is equal to $(*)$. The second proof derives $(*)$ directly from general permutation enumeration techniques, using noncommutative symmetric functions. The generating function $(*)$ is an "alternating" analogue of David and Barton's generating function \[\left(1-x+\frac{x^{3}}{3!}-\frac{x^{4}}{4!}+\frac{x^{6}}{6!}-\frac{x^{7}}{7!}+\cdots\right)^{-1},\]for permutations with no increasing runs of length 3 or more. Our general results give further alternating analogues of permutation enumeration formulas, including results of Chebikin and Remmel.
Asymptotic Expansion of the Multi-Orientable Random Tensor Model
Authors: Fusy Eric , Tanasa Adrian
Published: January 2020

Three-dimensional random tensor models are a natural generalization of the celebrated matrix models. The associated tensor graphs, or 3D maps, can be classified with respect to a particular integer or half-integer, the degree of the respective graph. In this paper we analyze the general term of the asymptotic expanion in $N$, the size of the tensor, of a particular random tensor model, the multi-orientable tensor model. We perform their enumeration and we establish which are the dominant configurations of a given degree.
Induced and Non-induced Forbidden Subposet Problems
Authors: Patkós Balázs
Published: January 2020

The problem of determining the maximum size $La(n,P)$ that a $P$-free subposet of the Boolean lattice $B_n$ can have, attracted the attention of many researchers, but little is known about the induced version of these problems. In this paper we determine the asymptotic behavior of $La^*(n,P)$, the maximum size that an induced $P$-free subposet of the Boolean lattice $B_n$ can have for the case when $P$ is the complete two-level poset $K_{r,t}$ or the complete multi-level poset $K_{r,s_1,\dots,s_j,t}$ when all $s_i$'s either equal 4 or are large enough and satisfy an extra condition. We also show lower and upper bounds for the non-induced problem in the case when $P$ is the complete three-level poset $K_{r,s,t}$. These bounds determine the asymptotics of $La(n,K_{r,s,t})$ for some values of $s$ independently of the values of $r$ and $t$.
Maximal Clades in Random Binary Search Trees
Authors: Janson Svante
Published: January 2020

We study maximal clades in random phylogenetic trees with the Yule-Harding model or, equivalently, in binary search trees. We use probabilistic methods to reprove and extend earlier results on moment asymptotics and asymptotic normality. In particular, we give an explanation of the curious phenomenon observed by Drmota, Fuchs and Lee (2014) that asymptotic normality holds, but one should normalize using half the variance.
Traces Without Maximal Chains
Authors: Tan Ta Sheng
Published: January 2020

The trace of a family of sets ${\cal A}$ on a set $X$ is ${\cal A}|_X=\{A\cap X:A\in {\cal A}\}$. If ${\cal A}$ is a family of $k$-sets from an $n$-set such that for any $r$-subset $X$ the trace ${\cal A}|_X$ does not contain a maximal chain, then how large can ${\cal A}$ be? Patkós conjectured that, for $n$ sufficiently large, the size of ${\cal A}$ is at most ${n-k+r-1\choose r-1}$. Our aim in this paper is to prove this conjecture.
Flag-Transitive Non-Symmetric 2-Designs with $(r,\lambda)=1$ and Alternating Socle
Authors: Zhou Shenglin , Wang Yajie
Published: January 2020

This paper deals with flag-transitive non-symmetric 2-designs with $(r,\lambda)=1$. We prove that if $\mathcal D$ is a non-trivial non-symmetric $2$-$(v,k,\lambda)$ design with $(r,\lambda)=1$ and $G\leq Aut(\mathcal D)$ is flag-transitive with $Soc(G)=A_n$ for $n\geq 5$, then $\mathcal D$ is a $2$-$(6,3,2)$ design, the projective space $PG(3,2)$, or a $2$-$(10,6,5)$ design.
A Simple Bijection between Binary Trees and Colored Ternary Trees
Authors: Sun Yidong
Published: January 2020

In this short note, we first present a simple bijection between binary trees and colored ternary trees and then derive a new identity related to generalized Catalan numbers.
Most Probably Intersecting Hypergraphs
Authors: Das Shagnik , Sudakov Benny
Published: January 2020

The celebrated Erdős-Ko-Rado theorem shows that for $n \ge 2k$ the largest intersecting $k$-uniform set family on $[n]$ has size $\binom{n-1}{k-1}$. It is natural to ask how far from intersecting larger set families must be. Katona, Katona and Katona introduced the notion of most probably intersecting families, which maximise the probability of random subfamilies being intersecting.We consider the most probably intersecting problem for $k$-uniform set families. We provide a rough structural characterisation of the most probably intersecting families and, for families of particular sizes, show that the initial segment of the lexicographic order is optimal.
Growth Rates of Geometric Grid Classes of Permutations
Authors: Bevan David
Published: January 2020

Geometric grid classes of permutations have proven to be key in investigations of classical permutation pattern classes. By considering the representation of gridded permutations as words in a trace monoid, we prove that every geometric grid class has a growth rate which is given by the square of the largest root of the matching polynomial of a related graph. As a consequence, we characterise the set of growth rates of geometric grid classes in terms of the spectral radii of trees, explore the influence of “cycle parity” on the growth rate, compare the growth rates of geometric grid classes against those of the corresponding monotone grid classes, and present new results concerning the effect of edge subdivision on the largest root of the matching polynomial.
Convex-Ear Decompositions and the Flag h-Vector
Authors: Schweig Jay
Published: January 2020

We prove a theorem allowing us to find convex-ear decompositions for rank-selected subposets of posets that are unions of Boolean sublattices in a coherent fashion. We then apply this theorem to geometric lattices and face posets of shellable complexes, obtaining new inequalities for their h-vectors. Finally, we use the latter decomposition to give a new interpretation to inequalities satisfied by the flag h-vectors of face posets of Cohen-Macaulay complexes.
Solution to a Conjecture on the Maximum Skew-Spectral Radius of Odd-Cycle Graphs
Authors: Chen Xiaolin , Li Xueliang , Lian Huishu
Published: January 2020

Let $G$ be a simple graph with no even cycle, called an odd-cycle graph. Cavers et al. [Linear Algebra Appl. 436(12):4512-1829, 2012] showed that the spectral radius of $G^\sigma$ is the same for every orientation $\sigma$ of $G$, and equals the maximum matching root of $G$. They proposed a conjecture that the graphs which attain the maximum skew spectral radius among the odd-cycle graphs $G$ of order $n$ are isomorphic to the odd-cycle graph with one vertex degree $n-1$ and size $m=\lfloor 3(n-1)/2\rfloor$. By using the Kelmans transformation, we give a proof to the conjecture. Moreover, sharp upper bounds of the maximum matching roots of the odd-cycle graphs with given order $n$ and size $m$ are given and extremal graphs are characterized.
The Number of Positions Starting a Square in Binary Words
Authors: Harju Tero , Kärki Tomi , Nowotka Dirk
Published: January 2020

We consider the number $\sigma(w)$ of positions that do not start a square in binary words $w$. Letting $\sigma(n)$ denote the maximum of $\sigma(w)$ for length $|w|=n$, we show that $\lim \sigma(n)/n = 15/31$.
Schubert Calculus and the Homology of the Peterson Variety
Authors: Insko Erik
Published: January 2020

We use the tight correlation between the geometry of the Peterson variety and the combinatorics the symmetric group to prove that homology of the Peterson variety injects into the homology of the flag variety. Our proof counts the points of intersection between certain Schubert varieties in the full flag variety and the Peterson variety, and shows that these intersections are proper and transverse.
A Deza–Frankl Type Theorem for Set Partitions
Authors: Ku Cheng Yeaw , Wong Kok Bin
Published: January 2020

A set partition of $[n]$ is a collection of pairwise disjoint nonempty subsets (called blocks) of $[n]$ whose union is $[n]$. Let $\mathcal{B}(n)$ denote the family of all set partitions of $[n]$. A family $\mathcal{A} \subseteq \mathcal{B}(n)$ is said to be $m$-intersecting if any two of its members have at least $m$ blocks in common. For any set partition $P \in \mathcal{B}(n)$, let $\tau(P) = \{x: \{x\} \in P\}$ denote the union of its singletons. Also, let $\mu(P) = [n] -\tau(P)$ denote the set of elements that do not appear as a singleton in $P$. Let \begin{align*} {\mathcal F}_{2t} & =\left\{P \in \mathcal{B}(n)\ : \ \vert \mu (P)\vert\leq t\right\};\\{\mathcal F}_{2t+1}(i_0) & =\left\{P \in \mathcal{B}(n)\ : \ \vert\mu (P)\cap ([n]\setminus \{i_0\})\vert\leq t\right\}.\end{align*} In this paper, we show that for $r\geq 3$, there exists a $n_0=n_0(r)$ depending on $r$ such that for all $n\geq n_0$, if $\mathcal{A} \subseteq\mathcal{B}(n)$ is $(n-r)$-intersecting, then \[ |\mathcal{A}| \leq \begin{cases} \vert {\mathcal F}_{2t} \vert, & \text{if $r=2t$};\\ \vert {\mathcal F}_{2t+1}(1) \vert, & \text{if $r=2t+1$}.\end{cases}\]Moreover, equality holds if and only if \[ \mathcal{A}= \begin{cases} {\mathcal F}_{2t}, & \text{if $r=2t$};\\ {\mathcal F}_{2t+1}(i_0), & \text{if $r=2t+1$},\end{cases}\]for some $i_0\in [n]$.
Output Sum of Transducers: Limiting Distribution and Periodic Fluctuation
Authors: Heuberger Clemens , Kropf Sara , Prodinger Helmut
Published: January 2020

As a generalization of the sum of digits function and other digital sequences, sequences defined as the sum of the output of a transducer are asymptotically analyzed. The input of the transducer is a random integer in $[0, N)$. Analogues in higher dimensions are also considered. Sequences defined by a certain class of recursions can be written in this framework.Depending on properties of the transducer, the main term, the periodic fluctuation and an error term of the expected value and the variance of this sequence are established. The periodic fluctuation of the expected value is Hölder continuous and, in many cases, nowhere differentiable. A general formula for the Fourier coefficients of this periodic function is derived. Furthermore, it turns out that the sequence is asymptotically normally distributed for many transducers. As an example, the abelian complexity function of the paperfolding sequence is analyzed. This sequence has recently been studied by Madill and Rampersad.
On Optimal Linear Codes over ${\mathbb{F}}_8$
Authors: Kanazawa Rie , Maruta Tatsuya
Published: January 2020

Let $n_q(k,d)$ be the smallest integer $n$ for which there exists an $[n,k,d]_q$ code for given $q,k,d$. It is known that $n_8(4,d) = \sum_{i=0}^{3} \left\lceil d/8^i \right\rceil$ for all $d \ge 833$. As a continuation of Jones et al. [Electronic J. Combinatorics 13 (2006), #R43], we determine $n_8(4,d)$ for 117 values of $d$ with $113 \le d \le 832$ and give upper and lower bounds on $n_8(4,d)$ for other $d$ using geometric methods and some extension theorems for linear codes.
Improved Upper Bounds for the Laplacian Spectral Radius of a Graph
Authors: Wang Tianfei , Yang Jin , Li Bin
Published: January 2020

In this paper, we present three improved upper bounds for the Laplacian spectral radius of graphs. Moreover, we determine all extremal graphs which achieve these upper bounds. Finally, some examples illustrate that the results are best in all known upper bounds in some sense.
Sharp Threshold Functions for Random Intersection Graphs via a Coupling Method
Authors: Rybarczyk Katarzyna
Published: January 2020

We present a new method which enables us to find threshold functions for many properties in random intersection graphs. This method is used to establish sharp threshold functions in random intersection graphs for $k$–connectivity, perfect matching containment and Hamilton cycle containment.
On Generalized Dyck Paths
Authors: Rukavicka Josef
Published: January 2020

We generalize the elegant bijective proof of the Chung Feller theorem from a paper of Young-Ming Chen [The Chung-Feller theorem revisited, Disc. Math. 308 (2008), 1328–1329].
Loose Hamilton Cycles in Random Uniform Hypergraphs
Authors: Dudek Andrzej , Frieze Alan
Published: January 2020

In the random $k$-uniform hypergraph $H_{n,p;k}$ of order $n$ each possible $k$-tuple appears independently with probability $p$. A loose Hamilton cycle is a cycle of order $n$ in which every pair of adjacent edges intersects in a single vertex. We prove that if $p n^{k-1}/\log n$ tends to infinity with $n$ then $$\lim_{\substack{n\to \infty\\ 2(k-1) |n}}\Pr(H_{n,p;k}\text{ contains a loose Hamilton cycle})=1.$$ This is asymptotically best possible.
The Bipartite Ramsey Numbers $b(C_{2m};K_{2,2})$
Authors: Rui Zhang , Yongqi Sun
Published: January 2020

Given bipartite graphs $H_1$ and $H_2$, the bipartite Ramsey number $b(H_1; H_2)$ is the smallest integer $b$ such that any subgraph $G$ of the complete bipartite graph $K_{b,b}$, either $G$ contains a copy of $H_1$ or its complement relative to $K_{b,b}$ contains a copy of $H_2$. It is known that $b(K_{2,2};K_{2,2})=5, b(K_{2,3};K_{2,3})=9, b(K_{2,4};K_{2,4})=14$ and $b(K_{3,3};K_{3,3})=17$. In this paper we study the case $H_1$ being even cycles and $H_2$ being $K_{2,2}$, prove that $b(C_6;K_{2,2})=5$ and $b(C_{2m};K_{2,2})=m+1$ for $m\geq 4$.
Perfect Matchings in Claw-free Cubic Graphs
Authors: Oum Sang-il
Published: January 2020

Lovász and Plummer conjectured that there exists a fixed positive constant $c$ such that every cubic $n$-vertex graph with no cutedge has at least $2^{cn}$ perfect matchings. Their conjecture has been verified for bipartite graphs by Voorhoeve and planar graphs by Chudnovsky and Seymour. We prove that every claw-free cubic $n$-vertex graph with no cutedge has more than $2^{n/12}$ perfect matchings, thus verifying the conjecture for claw-free graphs.
On the Automorphism Group of Integral Circulant Graphs
Authors: Bašić Milan , Ilić Aleksandar
Published: January 2020

The integral circulant graph $X_n (D)$ has the vertex set $Z_n = \{0, 1,\ldots$, $n{-}1\}$ and vertices $a$ and $b$ are adjacent, if and only if $\gcd(a{-}b$, $n)\in D$, where $D = \{d_1,d_2, \ldots, d_k\}$ is a set of divisors of $n$. These graphs play an important role in modeling quantum spin networks supporting the perfect state transfer and also have applications in chemical graph theory. In this paper, we deal with the automorphism group of integral circulant graphs and investigate a problem proposed in [W. Klotz, T. Sander, Some properties of unitary Cayley graphs, Electr. J. Comb. 14 (2007), #R45]. We determine the size and the structure of the automorphism group of the unitary Cayley graph $X_n (1)$ and the disconnected graph $X_n (d)$. In addition, based on the generalized formula for the number of common neighbors and the wreath product, we completely characterize the automorphism groups $Aut (X_n (1, p))$ for $n$ being a square-free number and $p$ a prime dividing $n$, and $Aut (X_n (1, p^k))$ for $n$ being a prime power.
On a New Family of Generalized Stirling and Bell Numbers
Authors: Mansour Toufik , Schork Matthias , Shattuck Mark
Published: January 2020

A new family of generalized Stirling and Bell numbers is introduced by considering powers $(VU)^n$ of the noncommuting variables $U,V$ satisfying $UV=VU+hV^s$. The case $s=0$ (and $h=1$) corresponds to the conventional Stirling numbers of second kind and Bell numbers. For these generalized Stirling numbers, the recursion relation is given and explicit expressions are derived. Furthermore, they are shown to be connection coefficients and a combinatorial interpretation in terms of statistics is given. It is also shown that these Stirling numbers can be interpreted as $s$-rook numbers introduced by Goldman and Haglund. For the associated generalized Bell numbers, the recursion relation as well as a closed form for the exponential generating function is derived. Furthermore, an analogue of Dobinski's formula is given for these Bell numbers.
Growth of Graph Powers
Authors: Pokrovskiy A.
Published: January 2020

For a graph $G$, its $r$th power is constructed by placing an edge between two vertices if they are within distance $r$ of each other. In this note we study the amount of edges added to a graph by taking its $r$th power. In particular we obtain that, for $r\geq 3$, either the $r$th power is complete or "many" new edges are added. In this direction, Hegarty showed that there is a constant $\epsilon > 0$ such $e(G^3)\geq (1+\epsilon)e(G)$. We extend this result in two directions. We give an alternative proof of Hegarty's result with an improved constant of $\epsilon = \frac{1}{6}$. We also show that for general $r$, $e(G^{r}) \geq \left( \left\lceil \frac{r}{3} \right\rceil -1 \right)e(G).$
Integral Cayley Graphs Defined by Greatest Common Divisors
Authors: Klotz Walter , Sander Torsten
Published: January 2020

An undirected graph is called integral, if all of its eigenvalues are integers. Let $\Gamma =Z_{m_1}\otimes \ldots \otimes Z_{m_r}$ be an abelian group represented as the direct product of cyclic groups $Z_{m_i}$ of order $m_i$ such that all greatest common divisors $\gcd(m_i,m_j)\leq 2$ for $i\neq j$. We prove that a Cayley graph $Cay(\Gamma,S)$ over $\Gamma$ is integral, if and only if $S\subseteq \Gamma$ belongs to the the Boolean algebra $B(\Gamma)$ generated by the subgroups of $\Gamma$. It is also shown that every $S\in B(\Gamma)$ can be characterized by greatest common divisors.
Reduced Decompositions of Matchings
Authors: Lv Lun , Pang Sabrina X. M.
Published: January 2020

We give a characterization of matchings in terms of the canonical reduced decompositions. As an application, the canonical reduced decompositions of $12312$-avoiding matchings are obtained. Based on such decompositions, we find a bijection between $12312$-avoiding matchings and ternary paths.
Total Weight Choosability of Graphs
Authors: Przybyło Jakub , Woźniak Mariusz
Published: January 2020

Suppose the edges and the vertices of a simple graph $G$ are assigned $k$-element lists of real weights. By choosing a representative of each list, we specify a vertex colouring, where for each vertex its colour is defined as the sum of the weights of its incident edges and the weight of the vertex itself. How long lists ensures a choice implying a proper vertex colouring for any graph? Is there any finite bound or maybe already lists of length two are sufficient? We prove that $2$-element lists are enough for trees, wheels, unicyclic and complete graphs, while the ones of length $3$ are sufficient for complete bipartite graphs. Our main tool is an algebraic theorem by Alon called Combinatorial Nullstellensatz.
Independence Complexes of Stable Kneser Graphs
Authors: Braun Benjamin
Published: January 2020

For integers $n\geq 1$, $k\geq 0$, the stable Kneser graph $SG_{n,k}$ (also called the Schrijver graph) has as vertex set the stable $n$-subsets of $[2n+k]$ and as edges disjoint pairs of $n$-subsets, where a stable $n$-subset is one that does not contain any $2$-subset of the form $\{i,i+1\}$ or $\{1,2n+k\}$. The stable Kneser graphs have been an interesting object of study since the late 1970's when A. Schrijver determined that they are a vertex critical class of graphs with chromatic number $k+2$. This article contains a study of the independence complexes of $SG_{n,k}$ for small values of $n$ and $k$. Our contributions are two-fold: first, we prove that the homotopy type of the independence complex of $SG_{2,k}$ is a wedge of spheres of dimension two. Second, we determine the homotopy types of the independence complexes of certain graphs related to $SG_{n,2}$.
On the Number of Subsequences with a Given Sum in a Finite Abelian Group
Authors: Chang Gerard Jennhwa , Chen Sheng-Hua , Qu Yongke , Wang Guoqing , Zhang Haiyan
Published: January 2020

Suppose $G$ is a finite abelian group and $S$ is a sequence of elements in $G$. For any element $g$ of $G$, let $N_g(S)$ denote the number of subsequences of $S$ with sum $g$. The purpose of this paper is to investigate the lower bound for $N_g(S)$. In particular, we prove that either $N_g(S)=0$ or $N_g(S)\ge2^{|S|-D(G)+1}$, where $D(G)$ is the smallest positive integer $\ell$ such that every sequence over $G$ of length at least $\ell$ has a nonempty zero-sum subsequence. We also characterize the structures of the extremal sequences for which the equality holds for some groups.
On-line Ramsey Theory for Bounded Degree Graphs
Authors: Butterfield Jane , Grauman Tracy , Kinnersley William B. , Milans Kevin G. , Stocker Christopher , West Douglas B.
Published: January 2020

When graph Ramsey theory is viewed as a game, "Painter" 2-colors the edges of a graph presented by "Builder". Builder wins if every coloring has a monochromatic copy of a fixed graph $G$. In the on-line version, iteratively, Builder presents one edge and Painter must color it. Builder must keep the presented graph in a class ${\cal H}$. Builder wins the game $(G,{\cal H})$ if a monochromatic copy of $G$ can be forced. The on-line degree Ramsey number $\mathring {R}_\Delta(G)$ is the least $k$ such that Builder wins $(G,{\cal H})$ when ${\mathcal H}$ is the class of graphs with maximum degree at most $k$. Our results include: 1) $\mathring {R}_\Delta(G)\!\le\!3$ if and only if $G$ is a linear forest or each component lies inside $K_{1,3}$. 2) $\mathring {R}_\Delta(G)\ge \Delta(G)+t-1$, where $t=\max_{uv\in E(G)}\min\{d(u),d(v)\}$. 3) $\mathring {R}_\Delta(G)\le d_1+d_2-1$ for a tree $G$, where $d_1$ and $d_2$ are two largest vertex degrees. 4) $4\le \mathring {R}_\Delta(C_n)\le 5$, with $\mathring {R}_\Delta(C_n)=4$ except for finitely many odd values of $n$. 5) $\mathring {R}_\Delta(G)\le6$ when $\Delta(G)\le 2$. The lower bounds come from strategies for Painter that color edges red whenever the red graph remains in a specified class. The upper bounds use a result showing that Builder may assume that Painter plays "consistently".
Computing the Domination Number of Grid Graphs
Authors: Alanko Samu , Crevals Simon , Isopoussu Anton , Östergård Patric , Pettersson Ville
Published: January 2020

Let $\gamma_{m,n}$ denote the size of a minimum dominating set in the $m \times n$ grid graph. For the square grid graph, exact values for $\gamma_{n,n}$ have earlier been published for $n \leq 19$. By using a dynamic programming algorithm, the values of $\gamma_{m,n}$ for $m,n \leq 29$ are here obtained. Minimum dominating sets for square grid graphs up to size $29 \times 29$ are depicted.
A Note on Naturally Embedded Ternary Trees
Authors: Kuba Markus
Published: January 2020

In this note we consider ternary trees naturally embedded in the plane in a deterministic way. The root has position zero, or in other words label zero, and the three children of a node with position $j\in\mathbb{Z}$ have positions $j-1$, $j$, and $j+1$. We derive the generating function of embedded ternary trees where all internal nodes have labels less than or equal to $j$, with $j\in\mathbb{N}$. Furthermore, we study the generating function of the number of ternary trees of size $n$ with a given number of internal nodes with label $j$. Moreover, we discuss generalizations of this counting problem to several labels at the same time. We also study a refinement of the depth of the external node of rank $s$, with $0\le s\le 2n$, by keeping track of the left, center, and right steps on the unique path from the root to the external node. The $2n+1$ external nodes of a ternary tree are ranked from the left to the right according to an inorder traversal of the tree. Finally, we discuss generalizations of the considered enumeration problems to embedded $d$-ary trees.
Exponential Triples
Authors: Sisto Alessandro
Published: January 2020

Using ultrafilter techniques we show that in any partition of $\mathbb{N}$ into 2 cells there is one cell containing infinitely many exponential triples, i.e. triples of the kind $a,b,a^b$ (with $a,b>1$). Also, we will show that any multiplicative $IP^*$ set is an "exponential $IP$ set", the analogue of an $IP$ set with respect to exponentiation.
The $t$-Pebbling Number is Eventually Linear in $t$
Authors: Hoffmann Michael , Matoušek Jiří , Okamoto Yoshio , Zumstein Philipp
Published: January 2020

In graph pebbling games, one considers a distribution of pebbles on the vertices of a graph, and a pebbling move consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The $t$-pebbling number $\pi_t(G)$ of a graph $G$ is the smallest $m$ such that for every initial distribution of $m$ pebbles on $V(G)$ and every target vertex $x$ there exists a sequence of pebbling moves leading to a distibution with at least $t$ pebbles at $x$. Answering a question of Sieben, we show that for every graph $G$, $\pi_t(G)$ is eventually linear in $t$; that is, there are numbers $a,b,t_0$ such that $\pi_t(G)=at+b$ for all $t\ge t_0$. Our result is also valid for weighted graphs, where every edge $e=\{u,v\}$ has some integer weight $\omega(e)\ge 2$, and a pebbling move from $u$ to $v$ removes $\omega(e)$ pebbles at $u$ and adds one pebble to $v$.
On Multivariate Chromatic Polynomials of Hypergraphs and Hyperedge Elimination
Authors: White Jacob A.
Published: January 2020

In this paper we introduce multivariate hyperedge elimination polynomials and multivariate chromatic polynomials for hypergraphs. The first set of polynomials is defined in terms of a deletion-contraction-extraction recurrence, previously investigated for graphs by Averbouch, Godlin, and Makowsky. The multivariate chromatic polynomial is an equivalent polynomial defined in terms of colorings, and generalizes the coboundary polynomial of Crapo, and the bivariate chromatic polynomial of Dohmen, Pönitz and Tittman. We prove that specializations of these new polynomials recover polynomials which enumerate hyperedge coverings, matchings, transversals, and section hypergraphs, all weighted according to certain statistics. We also prove that the polynomials can be defined in terms of Möbius inversion on the partition lattice of a hypergraph, and we compute these polynomials for various classes of hypergraphs. We also consider trivariate polynomials, which we call the hyperedge elimination polynomial and the trivariate chromatic polynomial.
List-Distinguishing Colorings of Graphs
Authors: Ferrara Michael , Flesch Breeann , Gethner Ellen
Published: January 2020

A coloring of the vertices of a graph $G$ is said to be distinguishing provided that no nontrivial automorphism of $G$ preserves all of the vertex colors. The distinguishing number of $G$, denoted $D(G)$, is the minimum number of colors in a distinguishing coloring of $G$. The distinguishing number, first introduced by Albertson and Collins in 1996, has been widely studied and a number of interesting results exist throughout the literature. In this paper, the notion of distinguishing colorings is extended to that of list-distinguishing colorings. Given a family $L=\{L(v)\}_{v\in V(G)}$ of lists assigning available colors to the vertices of $G$, we say that $G$ is $L$-distinguishable if there is a distinguishing coloring $f$ of $G$ such that $f(v)\in L(v)$ for all $v$. The list-distinguishing number of $G$, $D_{\ell}(G)$, is the minimum integer $k$ such that $G$ is $L$-distinguishable for any assignment $L$ of lists with $|L(v)|=k$ for all $v$. Here, we determine the list-distinguishing number for several families of graphs and highlight a number of distinctions between the problems of distinguishing and list-distinguishing a graph.
Trees with an On-Line Degree Ramsey Number of Four
Authors: Rolnick David
Published: January 2020

On-line Ramsey theory studies a graph-building game between two players. The player called Builder builds edges one at a time, and the player called Painter paints each new edge red or blue after it is built. The graph constructed is called the background graph. Builder's goal is to cause the background graph to contain a monochromatic copy of a given goal graph, and Painter's goal is to prevent this. In the $S_k$-game variant of the typical game, the background graph is constrained to have maximum degree no greater than $k$. The on-line degree Ramsey number $\mathring{R}_{\Delta}(G)$ of a graph $G$ is the minimum $k$ such that Builder wins an $S_k$-game in which $G$ is the goal graph. Butterfield et al. previously determined all graphs $G$ satisfying $\mathring{R}_{\Delta}(G)\le 3$. We provide a complete classification of trees $T$ satisfying $\mathring{R}_{\Delta}(T)=4$.
Some Results for the Periodicity and Perfect State Transfer
Authors: Zhou Jiang , Bu Changjiang , Shen Jihong
Published: January 2020

Let $G$ be a graph with adjacency matrix $A$, let $H(t)=\exp(itA)$. $G$ is called a periodic graph if there exists a time $\tau$ such that $H(\tau)$ is diagonal. If $u$ and $v$ are distinct vertices in $G$, we say that perfect state transfer occurs from $u$ to $v$ if there exists a time $\tau$ such that $|H(\tau)_{u,v}|=1$. A necessary and sufficient condition for $G$ is periodic is given. We give the existence for the perfect state transfer between antipodal vertices in graphs with extreme diameter.
Spherical Venn Diagrams with Involutory Isometries
Authors: Ruskey Frank , Weston Mark
Published: January 2020

In this paper we give a construction, for any $n$, of an $n$-Venn diagram on the sphere that has antipodal symmetry; that is, the diagram is fixed by the map that takes a point on the sphere to the corresponding antipodal point. Thus, along with certain diagrams due to Anthony Edwards which can be drawn with rotational and reflective symmetry, for any isometry of the sphere that is an involution, there exists an $n$-Venn diagram on the sphere invariant under that involution. Our construction uses a recursively defined chain decomposition of the Boolean lattice.
A New Upper Bound on the Global Defensive Alliance Number in Trees
Authors: Chen Xue-gang , Shiu Wai Chee
Published: January 2020

A global defensive alliance in a graph $G=(V,E)$ is a dominating set $S$ satisfying the condition that for every vertex $v\in S$, $|N[v]\cap S|\geq |N(v)\cap(V-S)|$. In this note, a new upper bound on the global defensive alliance number of a tree is given in terms of its order and the number of support vertices. Moreover, we characterize trees attaining this upper bound.
Hamiltonian Cycles in the Square of a Graph
Authors: Ekstein Jan
Published: January 2020

We show that under certain conditions the square of the graph obtained by identifying a vertex in two graphs with hamiltonian square is also hamiltonian. Using this result, we prove necessary and sufficient conditions for hamiltonicity of the square of a connected graph such that every vertex of degree at least three in a block graph corresponds to a cut vertex and any two these vertices are at distance at least four.
On the Hyperbolicity Constant of Line Graphs
Authors: Carballosa Walter , Rodríguez José M. , Sigarreta José M. , Villeta María
Published: January 2020

If X is a geodesic metric space and $x_1,x_2,x_3\in X$, a geodesic triangle $T=\{x_1,x_2,x_3\}$ is the union of the three geodesics $[x_1x_2]$, $[x_2x_3]$ and $[x_3x_1]$ in $X$. The space $X$ is $\delta$-hyperbolic $($in the Gromov sense$)$ if any side of $T$ is contained in a $\delta$-neighborhood of the union of the two other sides, for every geodesic triangle $T$ in $X$. We denote by $\delta(X)$ the sharp hyperbolicity constant of $X$, i.e., $\delta(X):=\inf\{\delta\ge 0: X \text{ is }\delta\text{-hyperbolic}\}$. The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it. The main aim of this paper is to obtain information about the hyperbolicity constant of the line graph $\mathcal{L}(G)$ in terms of parameters of the graph $G$. In particular, we prove qualitative results as the following: a graph $G$ is hyperbolic if and only if $\mathcal{L}(G)$ is hyperbolic; if $\{G_n\}$ is a T-decomposition of $G$ ($\{G_n\}$ are simple subgraphs of $G$), the line graph $\mathcal{L}(G)$ is hyperbolic if and only if $\sup_n \delta(\mathcal{L}(G_n))$ is finite. Besides, we obtain quantitative results. Two of them are quantitative versions of our qualitative results. We also prove that $g(G)/4 \le \delta(\mathcal{L}(G)) \le c(G)/4+2$, where $g(G)$ is the girth of $G$ and $c(G)$ is its circumference. We show that $\delta(\mathcal{L}(G)) \ge \sup \{L(g):\, g \,\text{ is an isometric cycle in }\,G\,\}/4$. Furthermore, we characterize the graphs $G$ with $\delta(\mathcal{L}(G)) < 1$.
Dot Product Representations of Planar Graphs
Authors: Kang Ross J. , Lovász László , Müller Tobias , Scheinerman Edward R.
Published: January 2020

A graph $G$ is a $k$-dot product graph if there exists a vector labelling $u: V(G) \to \mathbb{R}^k$ such that $u(i)^{T}u(j) \geq 1$ if and only if $ij \in E(G)$. Fiduccia, Scheinerman, Trenk and Zito [Discrete Math., 1998] asked whether every planar graph is a $3$-dot product graph. We show that the answer is "no". On the other hand, every planar graph is a $4$-dot product graph. We also answer the corresponding questions for planar graphs of prescribed girth and for outerplanar graphs.
$q$-Eulerian Polynomials and Polynomials with Only Real Zeros
Authors: Ma Shi-Mei , Wang Yi
Published: January 2020

Let $f$ and $F$ be two polynomials satisfying $F(x)=u(x)f(x)+v(x)f'(x)$. We characterize the relation between the location and multiplicity of the real zeros of $f$ and $F$, which generalizes and unifies many known results, including the results of Brenti and Brändén about the $q$-Eulerian polynomials.
Minimum Rank of Matrices Described by a Graph or Pattern over the Rational, Real and Complex Numbers
Authors: Berman Avi , Friedland Shmuel , Hogben Leslie , Rothblum Uriel G. , Shader Bryan
Published: January 2020

We use a technique based on matroids to construct two nonzero patterns $Z_1$ and $Z_2$ such that the minimum rank of matrices described by $Z_1$ is less over the complex numbers than over the real numbers, and the minimum rank of matrices described by $Z_2$ is less over the real numbers than over the rational numbers. The latter example provides a counterexample to a conjecture by Arav, Hall, Koyucu, Li and Rao about rational realization of minimum rank of sign patterns. Using $Z_1$ and $Z_2$, we construct symmetric patterns, equivalent to graphs $G_1$ and $G_2$, with the analogous minimum rank properties. We also discuss issues of computational complexity related to minimum rank.
An Elementary Proof of the Hook Formula
Authors: Bandlow Jason
Published: January 2020

The hook-length formula is a well known result expressing the number of standard tableaux of shape $\lambda$ in terms of the lengths of the hooks in the diagram of $\lambda$. Many proofs of this fact have been given, of varying complexity. We present here an elementary new proof which uses nothing more than the fundamental theorem of algebra. This proof was suggested by a $q,t$-analog of the hook formula given by Garsia and Tesler, and is roughly based on the inductive approach of Greene, Nijenhuis and Wilf. We also prove the hook formula in the case of shifted Young tableaux using the same technique.
Chromatic Graphs, Ramsey Numbers and the Flexible Atom Conjecture
Authors: Alm Jeremy F. , Maddux Roger D. , Manske Jacob
Published: January 2020

Let $K_{N}$ denote the complete graph on $N$ vertices with vertex set $V = V(K_{N})$ and edge set $E = E(K_{N})$. For $x,y \in V$, let $xy$ denote the edge between the two vertices $x$ and $y$. Let $L$ be any finite set and ${\cal M} \subseteq L^{3}$. Let $c : E \rightarrow L$. Let $[n]$ denote the integer set $\{1, 2, \ldots, n\}$. For $x,y,z \in V$, let $c(xyz)$ denote the ordered triple $\big(c(xy)$, $c(yz), c(xz)\big)$. We say that $c$ is good with respect to ${\cal M}$ if the following conditions obtain: 1. $\forall x,y \in V$ and $\forall (c(xy),j,k) \in {\cal M}$, $\exists z \in V$ such that $c(xyz) = (c(xy),j,k)$; 2. $\forall x,y,z \in V$, $c(xyz) \in {\cal M}$; and 3. $\forall x \in V \ \forall \ell\in L \ \exists \, y\in V$ such that $ c(xy)=\ell $. We investigate particular subsets ${\cal M}\subseteq L^{3}$ and those edge colorings of $K_{N}$ which are good with respect to these subsets ${\cal M}$. We also remark on the connections of these subsets and colorings to projective planes, Ramsey theory, and representations of relation algebras. In particular, we prove a special case of the flexible atom conjecture.
On Rainbow Trees and Cycles
Authors: Frieze Alan , Krivelevich Michael
Published: January 2020

We derive sufficient conditions for the existence of rainbow cycles of all lengths in edge colourings of complete graphs. We also consider rainbow colorings of a certain class of trees.
$f$-Vectors of $3$-Manifolds
Authors: Lutz Frank H. , Sulanke Thom , Swartz Ed
Published: January 2020

In 1970, Walkup completely described the set of $f$-vectors for the four $3$-manifolds $S^3$, $S^2\rlap{\times}\_\;S^1$, $S^2\!\times\!S^1$, and ${\Bbb R}{\bf P}^{\,3}$. We improve one of Walkup's main restricting inequalities on the set of $f$-vectors of $3$-manifolds. As a consequence of a bound by Novik and Swartz, we also derive a new lower bound on the number of vertices that are needed for a combinatorial $d$-manifold in terms of its $\beta_1$-coefficient, which partially settles a conjecture of Kühnel. Enumerative results and a search for small triangulations with bistellar flips allow us, in combination with the new bounds, to completely determine the set of $f$-vectors for twenty further $3$-manifolds, that is, for the connected sums of sphere bundles $(S^2\!\times\!S^1)^{\# k}$ and twisted sphere bundles $(S^2\rlap{\times}\_\;S^1)^{\# k}$, where $k=2,3,4,5,6,7,8,10,11,14$. For many more $3$-manifolds of different geometric types we provide small triangulations and a partial description of their set of $f$-vectors. Moreover, we show that the $3$-manifold ${\Bbb R}{\bf P}^{\,3}\#\,{\Bbb R}{\bf P}^{\,3}$ has (at least) two different minimal $g$-vectors.