bluuebunny/crossref_metadata_2025 huggingface dataset:
The Range of a Random Walk on a Comb
Authors: Pach János , Tardos Gábor
Published: January 2020

The graph obtained from the integer grid $\mathbb{Z}\times\mathbb{Z}$ by the removal of all horizontal edges that do not belong to the $x$-axis is called a comb. In a random walk on a graph, whenever a walker is at a vertex $v$, in the next step it will visit one of the neighbors of $v$, each with probability $1/d(v)$, where $d(v)$ denotes the degree of $v$. We answer a question of Csáki, Csörgő, Földes, Révész, and Tusnády by showing that the expected number of vertices visited by a random walk on the comb after $n$ steps is $(\frac1{2\sqrt{2\pi}}+o(1))\sqrt{n}\log n.$ This contradicts a claim of Weiss and Havlin.
Revstack Sort, Zigzag Patterns, Descent Polynomials of $t$-Revstack Sortable Permutations, and Steingrímsson's Sorting Conjecture
Authors: Dukes Mark
Published: January 2020

In this paper we examine the sorting operator $\mathcal{T}(LnR)=\mathcal{T}(R)\mathcal{T}(L)n$. Applying this operator to a permutation is equivalent to passing the permutation reversed through a stack. We prove theorems that characterise $t$-revstack sortability in terms of patterns in a permutation that we call zigzag patterns. Using these theorems we characterise those permutations of length $n$ which are sorted by $t$ applications of $\mathcal{T}$ for $t=0,1,2,n-3,n-2,n-1$. We derive expressions for the descent polynomials of these six classes of permutations and use this information to prove Steingrímsson's sorting conjecture for those six values of $t$. Symmetry and unimodality of the descent polynomials for general $t$-revstack sortable permutations is also proven and three conjectures are given.
Double-Critical Graphs and Complete Minors
Authors: Kawarabayashi Ken-ichi , Pedersen Anders Sune , Toft Bjarne
Published: January 2020

A connected $k$-chromatic graph $G$ is double-critical if for all edges $uv$ of $G$ the graph $G - u - v$ is $(k-2)$-colourable. The only known double-critical $k$-chromatic graph is the complete $k$-graph $K_k$. The conjecture that there are no other double-critical graphs is a special case of a conjecture from 1966, due to Erdős and Lovász. The conjecture has been verified for $k$ at most $5$. We prove for $k=6$ and $k=7$ that any non-complete double-critical $k$-chromatic graph is $6$-connected and contains a complete $k$-graph as a minor.
Extensions to 2-Factors in Bipartite Graphs
Authors: Vandenbussche Jennifer , West Douglas B.
Published: January 2020

A graph is $d$-bounded if its maximum degree is at most $d$.  We apply the Ore-Ryser Theorem on $f$-factors in bipartite graphs to obtain conditions for the extension of a $2$-bounded subgraph to a $2$-factor in a bipartite graph.  As consequences, we prove that every matching in the $5$-dimensional hypercube extends to a $2$-factor, and we obtain conditions for this property in general regular bipartite graphs.  For example, to show that every matching in a regular $n$-vertex bipartite graph extends to a $2$-factor, it suffices to show that all matchings with fewer than $n/3$ edges extend to $2$-factors.
Coloring 2-Intersecting Hypergraphs
Authors: Colucci Lucas , Gyárfás András
Published: January 2020

A hypergraph is 2-intersecting if any two edges intersect in at least two vertices. Blais, Weinstein and Yoshida asked (as a first step to a more general problem) whether every 2-intersecting hypergraph has a vertex coloring with a constant number of colors so that each hyperedge has at least $\min(|e|,3)$ colors. We show that there is such a coloring with at most 5 colors (which is best possible).
Some Results on the Structure of Multipoles in the Study of Snarks
Authors: Fiol M. A. , Vilaltella J.
Published: January 2020

Multipoles are the pieces we obtain by cutting some edges of a cubic graph in one or more points. As a result of the cut, a multipole $M$ has vertices attached to a dangling edge with one free end, and isolated edges with two free ends. We refer to such free ends as semiedges, and to isolated edges as free edges. Every 3-edge-coloring of a multipole induces a coloring or state of its semiedges, which satisfies the Parity Lemma. Multipoles have been extensively used in the study of snarks, that is, cubic graphs which are not 3-edge-colorable. Some results on the states and structure of the so-called color complete and color closed multipoles are presented. In particular, we give lower and upper linear bounds on the minimum order of a color complete multipole, and compute its exact number of states. Given two multipoles $M_1$ and $M_2$ with the same number of semiedges, we say that $M_1$ is reducible to $M_2$ if the state set of $M_2$ is a non-empty subset of the state set of $M_1$ and $M_2$ has less vertices than $M_1$. The function $v(m)$ is defined as the maximum number of vertices of an irreducible multipole with $m$ semiedges. The exact values of  $v(m)$ are only known for $m\le 5$. We prove that tree and cycle multipoles are irreducible and, as a byproduct, that $v(m)$ has a linear lower bound.
How Frequently is a System of $2$-Linear Boolean Equations Solvable?
Authors: Pittel Boris , Yeum Ji-A
Published: January 2020

We consider a random system of equations $x_i+x_j=b_{(i,j)} ({\rm mod }2)$, $(x_u\in \{0,1\},\, b_{(u,v)}=b_{(v,u)}\in\{0,1\})$, with the pairs $(i,j)$ from $E$, a symmetric subset of $[n]\times [n]$. $E$ is chosen uniformly at random among all such subsets of a given cardinality $m$; alternatively $(i,j)\in E$ with a given probability $p$, independently of all other pairs. Also, given $E$, ${\rm Pr}\{b_{e}=0\}={\rm Pr}\{b_e=1\}$ for each $e\in E$, independently of all other $b_{e\prime}$. It is well known that, as $m$ passes through $n/2$ ($p$ passes through $1/n$, resp.), the underlying random graph $G(n,\#{\rm edges}=m)$, ($G(n,{\rm Pr}({\rm edge})=p)$, resp.) undergoes a rapid transition, from essentially a forest of many small trees to a graph with one large, multicyclic, component in a sea of small tree components. We should expect then that the solvability probability decreases precipitously in the vicinity of $m\sim n/2$ ($p\sim 1/n$), and indeed this probability is of order $(1-2m/n)^{1/4}$, for $m < n/2$ ($(1-pn)^{1/4}$, for $p < 1/n$, resp.). We show that in a near-critical phase $m=(n/2)(1+\lambda n^{-1/3})$ ($p=(1+\lambda n^{-1/3})/n$, resp.), $\lambda=o(n^{1/12})$, the system is solvable with probability asymptotic to $c(\lambda)n^{-1/12}$, for some explicit function $c(\lambda)>0$. Mike Molloy noticed that the Boolean system with $b_e\equiv 1$ is solvable iff the underlying graph is $2$-colorable, and asked whether this connection might be used to determine an order of probability of $2$-colorability in the near-critical case. We answer Molloy's question affirmatively and show that, for $\lambda=o(n^{1/12})$, the probability of $2$-colorability is ${}\lesssim 2^{-1/4}e^{1/8}c(\lambda)n^{-1/12}$, and asymptotic to $2^{-1/4}e^{1/8}c(\lambda)n^{-1/12}$ at a critical phase $\lambda=O(1)$, and for $\lambda\to -\infty$.
Symmetric Alcoved Polytopes
Authors: Werner Annette , Yu Josephine
Published: January 2020

Generalized alcoved polytopes are polytopes whose facet normals are roots in a given root system.  We call a set of points in an alcoved polytope a generating set if there does not exist a strictly smaller alcoved polytope containing it.  The type $A$ alcoved polytopes are precisely the tropical polytopes that are also convex in the usual sense. In this case the tropical generators form a generating set.  We show that for any root system other than $F_4$, every alcoved polytope invariant under the natural Weyl group action has a generating set of cardinality equal to the Coxeter number of the root system.
Maxmaxflow and Counting Subgraphs
Authors: Jackson Bill , Sokal Alan D.
Published: January 2020

We introduce a new graph invariant $\Lambda(G)$ that we call maxmaxflow, and put it in the context of some other well-known graph invariants, notably maximum degree and its relatives. We prove the equivalence of two "dual" definitions of maxmaxflow: one in terms of flows, the other in terms of cocycle bases. We then show how to bound the total number (or more generally, total weight) of various classes of subgraphs of $G$ in terms of either maximum degree or maxmaxflow. Our results are motivated by a conjecture that the modulus of the roots of the chromatic polynomial of $G$ can be bounded above by a function of $\Lambda(G)$.
Progress on Dirac's Conjecture
Authors: Payne Michael S. , Wood David R.
Published: January 2020

In 1951, Gabriel Dirac conjectured that every non-collinear set $P$ of $n$ points in the plane contains a point incident to at least $\frac{n}{2}-c$ of the lines determined by $P$, for some constant $c$. The following weakened conjecture was proved by Beck and by Szemerédi and Trotter: every non-collinear set $P$ of $n$ points in the plane contains a point in at least $\frac{n}{c'}$ lines determined by $P$, for some constant $c'$. We prove this result with $c'= 37$. We also give the best known constant for Beck's Theorem, proving that every set of $n$ points with at most $\ell$ collinear determines at least $\frac{1}{98} n(n-\ell)$ lines.
On the Number of Spanning Trees in Random Regular Graphs
Authors: Greenhill Catherine , Kwan Matthew , Wind David
Published: January 2020

Let $d\geq 3$ be a fixed integer.   We give an asympotic formula for the expected number of spanning trees in a uniformly random $d$-regular graph with $n$ vertices. (The asymptotics are as $n\to\infty$, restricted to even $n$ if $d$ is odd.) We also obtain the asymptotic distribution of the number of spanning trees in a uniformly random cubic graph, and conjecture that the corresponding result holds for arbitrary (fixed) $d$. Numerical evidence is presented which supports our conjecture.
A Counterexample to a Question of Hof, Knill and Simon
Authors: Labbé Sébastien
Published: January 2020

In this article, we give a negative answer to a question of Hof, Knill and Simon (1995) concerning purely morphic sequences obtained from primitive morphism containing an infinite number of palindromes. Their conjecture states that such palindromic sequences arise from substitutions that are in class $\mathcal{P}$. The conjecture was proven for the binary alphabet by B. Tan in 2007. We give here a counterexample for a ternary alphabet.
A Conjectured Formula for Fully Packed Loop Configurations in a Triangle
Authors: Zinn-Justin Paul
Published: January 2020

We describe a new conjecture involving Fully Packed Loop counting which relates (via the Razumov–Stroganov conjecture) recent observations of Thapper to formulae in the Temperley–Lieb model of loops.
Monomial Ideals with Primary Components given by Powers of Monomial Prime Ideals
Authors: Herzog Jürgen , Vladoiu Marius
Published: January 2020

We characterize monomial ideals which are intersections of powers of monomial prime ideals and study classes of ideals with this property, among them polymatroidal ideals.
On Graphs Having no Flow Roots in the Interval $(1,2)$
Authors: Dong F.M.
Published: January 2020

For any graph $G$, let $W(G)$ be the set of vertices in $G$ of degrees larger than 3. We show that for any bridgeless graph $G$, if $W(G)$ is dominated by some component of $G - W(G)$, then $F(G,\lambda)$ has no roots in the interval (1,2), where $F(G,\lambda)$ is the flow polynomial of $G$. This result generalizes the known result that $F(G,\lambda)$ has no roots in (1,2) whenever $|W(G)| \leq 2$. We also give some constructions to generate graphs whose flow polynomials have no roots in $(1,2)$.
Recognizing Graph Theoretic Properties with Polynomial Ideals
Authors: De Loera Jesús A. , Hillar Christopher J. , Malkin Peter N. , Omar Mohamed
Published: January 2020

Many hard combinatorial problems can be modeled by a system of polynomial equations. N. Alon coined the term polynomial method to describe the use of nonlinear polynomials when solving combinatorial problems. We continue the exploration of the polynomial method and show how the algorithmic theory of polynomial ideals can be used to detect $k$-colorability, unique Hamiltonicity, and automorphism rigidity of graphs. Our techniques are diverse and involve Nullstellensatz certificates, linear algebra over finite fields, Gröbner bases, toric algebra, convex programming, and real algebraic geometry.
Total Transversals and Total Domination in Uniform Hypergraphs
Authors: Bujtás Csilla , Henning Michael , Tuza Zsolt , Yeo Anders
Published: January 2020

In 2012, the first three authors established a relationship between the transversal number and the domination number of uniform hypergraphs. In this paper, we establish a relationship between the total transversal number and the total domination number of uniform hypergraphs. We prove tight asymptotic upper bounds on the total transversal number in terms of the number of vertices, the number of edges, and the edge size.
Characterization of $(2m,m)$-Paintable Graphs
Authors: Mahoney Thomas , Meng Jixian , Zhu Xuding
Published: January 2020

In this paper, we prove that for any graph $G$ and any positive integer $m$, $G$ is $(2m,m)$-paintable if and only if $G$ is 2-paintable. It was asked by Zhu in 2009 whether $k$-paintable graphs are $(km,m)$-paintable for any positive integer $m$. Our result answers this question in the affirmative for $k=2$.
Cyclic Permutations of Sequences and Uniform Partitions
Authors: Huang Po-Yi , Ma Jun , Yeh Yeong-Nan
Published: January 2020

Let $\vec{r}=(r_i)_{i=1}^n$ be a sequence of real numbers of length $n$ with sum $s$. Let $s_0=0$ and $s_i=r_1+\ldots +r_i$ for every $i\in\{1,2,\ldots,n\}$. Fluctuation theory is the name given to that part of probability theory which deals with the fluctuations of the partial sums $s_i$. Define $p(\vec{r})$ to be the number of positive sum $s_i$ among $s_1,\ldots,s_n$ and $m(\vec{r})$ to be the smallest index $i$ with $s_i=\max\limits_{0\leq k\leq n}s_k$. An important problem in fluctuation theory is that of showing that in a random path the number of steps on the positive half-line has the same distribution as the index where the maximum is attained for the first time. In this paper, let $\vec{r}_i=(r_i,\ldots,r_n,r_1,\ldots,r_{i-1})$ be the $i$-th cyclic permutation of $\vec{r}$. For $s>0$, we give the necessary and sufficient conditions for $\{ m(\vec{r}_i)\mid 1\leq i\leq n\}=\{1,2,\ldots,n\}$ and $\{ p(\vec{r}_i)\mid 1\leq i\leq n\}=\{1,2,\ldots,n\}$; for $s\leq 0$, we give the necessary and sufficient conditions for $\{ m(\vec{r}_i)\mid 1\leq i\leq n\}=\{0,1,\ldots,n-1\}$ and $\{ p(\vec{r}_i)\mid 1\leq i\leq n\}=\{0,1,\ldots,n-1\}$. We also give an analogous result for the class of all permutations of $\vec{r}$.
From Clutters to Matroids
Authors: Martí-Farré Jaume
Published: January 2020

This paper deals with the question of completing a monotone increasing family of subsets $\Gamma$ of a finite set $\Omega$ to obtain the dependent sets of a matroid. Specifically, we provide several natural processes for transforming the clutter $\Lambda$ of the inclusion-minimal subsets of the family $\Gamma$ into the set of circuits ${\cal C}({\cal M})$ of a matroid ${\cal M}$ with ground set $\Omega$. In addition, by combining these processes, we prove that all the minimal matroidal completions of the family can be obtained.
A Combinatorial Identity of Multiple Zeta Values with Even Arguments
Authors: Ding Shifeng , Feng Lihua , Liu Weijun
Published: January 2020

Let $\zeta(s_1,s_2,\cdots,s_k;\alpha)$ be the multiple Hurwitz zeta function. Given two positive integers $k$ and $n$ with $k\leq n$, let $E(2n, k;\alpha)$ be the sum of all multiple zeta values with even arguments whose weight is $2n$ and whose depth is $k$.  In this note we present some generating series for the numbers $E(2n,k;\alpha)$.
Minimal Crystallizations of 3-Manifolds
Authors: Basak Biplab , Datta Basudeb
Published: January 2020

We have introduced the weight of a group which has a presentation with number of relations is at most the number of generators. We have shown that the number of facets of any contracted pseudotriangulation of a connected closed 3-manifold $M$ is at least the weight of the fundamental group of $M$. This lower bound is sharp for the 3-manifolds $\mathbb{RP}^3$, $L(3,1)$, $L(5,2)$, $S^1\times S^1 \times S^1$, $S^2 \times S^1$, twisted product of $S^2$ and $S^1$ and $S^3/Q_8$, where $Q_8$ is the quaternion group. Moreover, there is a unique such facet minimal pseudotriangulation in each of these seven cases. We have also constructed contracted pseudotriangulations of $L(kq-1,q)$ with $4(q+k-1)$ facets for $q \geq 3$, $k \geq 2$ and $L(kq+1,q)$ with $4(q+k)$ facets for $q\geq 4$, $k\geq 1$. By a recent result of Swartz, our pseudotriangulations of $L(kq+1, q)$ are facet minimal when $kq+1$ are even. In 1979, Gagliardi found presentations of the fundamental group of a manifold $M$ in terms of a contracted pseudotriangulation of $M$. Our construction is the converse of this, namely, given a presentation of the fundamental group of a 3-manifold $M$, we construct a contracted pseudotriangulation of $M$. So, our construction of a contracted pseudotriangulation of a 3-manifold $M$ is based on a presentation of the fundamental group of $M$ and it is computer-free.
Equicovering Subgraphs of Graphs and Hypergraphs
Authors: Choi Ilkyoo , Kim Jaehoon , Tebbe Amelia , West Douglas B.
Published: January 2020

As a variation on the $t$-Equal Union Property ($t$-EUP) introduced by Lindström, we introduce the $t$-Equal Valence Property ($t$-EVP) for hypergraphs: a hypergraph satisfies the $t$-EVP if there are $t$ pairwise edge-disjoint subhypergraphs such that for each vertex $v$, the degree of $v$ in all $t$ subhypergraphs is the same.  In the $t$-EUP, the subhypergraphs just have the same sets of vertices with positive degree.  For both the $2$-EUP and the $2$-EVP, we characterize the graphs satisfying the property and determine the maximum number of edges in a graph not satisfying it.  We also study the maximum number of edges in both $k$-uniform and general hypergraphs not satisfying the $t$-EVP.
Additional Constructions to Solve the Generalized Russian Cards Problem using Combinatorial Designs
Authors: Swanson Colleen M. , Stinson Douglas R.
Published: January 2020

In the generalized Russian cards problem, we have a card deck $X$ of $n$ cards and three participants, Alice, Bob, and Cathy, dealt $a$, $b$, and $c$ cards, respectively. Once the cards are dealt, Alice and Bob wish to privately communicate their hands to each other via public announcements, without the advantage of a shared secret or public key infrastructure. Cathy, for her part, should remain ignorant of all but her own cards after Alice and Bob have made their announcements. Notions for Cathy's ignorance in the literature range from Cathy not learning the fate of any individual card with certainty (weak $1$-security) to not gaining any probabilistic advantage in guessing the fate of some set of $\delta$ cards (perfect $\delta$-security). As we demonstrate in this work, the generalized Russian cards problem has close ties to the field of combinatorial designs, on which we rely heavily, particularly for perfect security notions. Our main result establishes an equivalence between perfectly $\delta$-secure strategies and $(c+\delta)$-designs on $n$ points with block size $a$, when announcements are chosen uniformly at random from the set of possible announcements. We also provide construction methods and example solutions, including a construction that yields perfect $1$-security against Cathy when $c=2$. Drawing on our equivalence results, we are able to use a known combinatorial design to construct a strategy with $a=8$, $b=13$, and $c=3$ that is perfectly $2$-secure. Finally, we consider a variant of the problem that yields solutions that are easy to construct and optimal with respect to both the number of announcements and level of security achieved. Moreover, this is the first method obtaining weak $\delta$-security that allows Alice to hold an arbitrary number of cards and Cathy to hold a set of $c = \lfloor \frac{a-\delta}{2} \rfloor$ cards. Alternatively, the construction yields solutions for arbitrary $\delta$, $c$ and any $a \geq \delta + 2c$.
An Erdős-Ko-Rado Theorem for Permutations with Fixed Number of Cycles
Authors: Ku Cheng Yeaw , Wong Kok Bin
Published: January 2020

Let $S_{n}$ denote the set of permutations of $[n]=\{1,2,\dots, n\}$. For a positive integer $k$, define $S_{n,k}$ to be the set of all permutations of $[n]$ with exactly $k$ disjoint cycles, i.e.,\[ S_{n,k} = \{\pi \in S_{n}: \pi = c_{1}c_{2} \cdots c_{k}\},\] where $c_1,c_2,\dots ,c_k$ are disjoint cycles. The size of $S_{n,k}$ is $\left [ \begin{matrix}n\\ k \end{matrix}\right]=(-1)^{n-k}s(n,k)$, where $s(n,k)$ is the Stirling number of the first kind. A family $\mathcal{A} \subseteq S_{n,k}$ is said to be $t$-cycle-intersecting if any two elements of $\mathcal{A}$ have at least $t$ common cycles. In this paper we show that, given any positive integers $k,t$ with $k\geq t+1$, if $\mathcal{A} \subseteq S_{n,k}$ is $t$-cycle-intersecting and $n\ge n_{0}(k,t)$ where $n_{0}(k,t) = O(k^{t+2})$, then \[ |\mathcal{A}| \le \left [ \begin{matrix}n-t\\ k-t \end{matrix}\right],\]with equality if and only if $\mathcal{A}$ is the stabiliser of $t$ fixed points.
A Criterion for a Monomial Ideal to have a Linear Resolution in Characteristic 2
Authors: Connon E. , Faridi Sara
Published: January 2020

In this paper we give a necessary and sufficient combinatorial condition for a monomial ideal to have a linear resolution over fields of characteristic 2.
Permutation Reconstruction from Differences
Authors: De Biasi Marzio
Published: January 2020

We prove that the problem of reconstructing a permutation $\pi_1,\dotsc,\pi_n$ of the integers $[1\dotso n]$ given the absolute differences $|\pi_{i+1}-\pi_i|$, $i = 1,\dotsc,n-1$ is $\sf{NP}$-complete. As an intermediate step we first prove the $\sf{NP}$-completeness of the decision version of a new puzzle game that we call Crazy Frog Puzzle. The permutation reconstruction from differences is one of the simplest combinatorial problems that have been proved to be computationally intractable.An addendum was added to this paper on the 9th of December 2015.
Proof of a Conjecture of Amdeberhan and Moll on a Divisibility Property of Binomial Coefficients
Authors: Yang Quan-Hui
Published: January 2020

Let $a,b$ and $n$ be positive integers with $a>b$. In this note, we prove that $$(2bn+1)(2bn+3){2bn \choose bn}\bigg|3(a-b)(3a-b){2an \choose an}{an\choose bn}.$$ This confirms a recent conjecture of Amdeberhan and Moll.
Isometric Embeddings of Half-Cube Graphs in Half-Spin Grassmannians
Authors: Pankov Mark
Published: January 2020

Let $\Pi$ be a polar space of type $\textsf{D}_{n}$. Denote by ${\mathcal G}_{\delta}(\Pi)$, $\delta\in \{+,-\}$ the associated half-spin Grassmannians and write $\Gamma_{\delta}(\Pi)$ for the corresponding half-spin Grassmann graphs. In the case when $n\ge 4$ is even, the apartments of ${\mathcal G}_{\delta}(\Pi)$ will be characterized as the images of isometric embeddings of  the half-cube graph $\frac{1}{2}H_n$ in $\Gamma_{\delta}(\Pi)$. As an application, we describe all isometric embeddings of $\Gamma_{\delta}(\Pi)$ in the half-spin Grassmann graphs associated to a polar space of type $\textsf{D}_{n'}$ under the assumption that $n\ge 6$ is even.
Extremal Problems for the $p$-Spectral Radius of Graphs
Authors: Kang Liying , Nikiforov Vladimir
Published: January 2020

The $p$-spectral radius of a graph $G\ $of order $n$ is defined for any real number $p\geq1$ as$$\lambda^{(p)}(G) =\max\{ 2\sum_{\{i,j\}\in E(G)} x_ix_j:x_1,\ldots,x_n\in\mathbb{R}\text{ and }\vert x_{1}\vert ^{p}+\cdots+\vert x_n\vert^{p}=1\} .$$The most remarkable feature of $\lambda^{(p)}$ is that it seamlessly joins several other graph parameters, e.g., $\lambda^{(1)}$ is the Lagrangian, $\lambda^{(2)  }$ is the spectral radius and $\lambda^{(\infty)  }/2$ is the number of edges. This paper presents solutions to some extremal problems about $\lambda^{(p)}$, which are common generalizations of corresponding edge and spectral extremal problems.Let $T_{r}\left(  n\right)  $ be the $r$-partite Turán graph of order $n$. Two of the main results in the paper are:(I) Let $r\geq2$ and $p>1.$ If $G$ is a $K_{r+1}$-free graph of order $n$, then$$\lambda^{(p)}(G)  <\lambda^{(p)}(T_{r}(n)),$$ unless $G=T_{r}(n)$.(II) Let $r\geq2$ and $p>1.$ If $G\ $is a graph of order $n,$ with$$\lambda^{(p)}(G)>\lambda^{(p)}(  T_{r}(n))  ,$$then $G$ has an edge contained in at least $cn^{r-1}$ cliques of order $r+1$, where $c$ is a positive number depending only on $p$ and $r.$
Operators of Equivalent Sorting Power and Related Wilf-equivalences
Authors: Albert Michael , Bouvel Mathilde
Published: January 2020

We study sorting operators $\mathbf{A}$ on permutations that are obtained composing Knuth's stack sorting operator $\mathbf{S}$ and the reversal operator $\mathbf{R}$, as many times as desired. For any such operator $\mathbf{A}$, we provide a size-preserving bijection between the set of permutations sorted by $\mathbf{S} \circ \mathbf{A}$ and the set of those sorted by $\mathbf{S} \circ \mathbf{R} \circ \mathbf{A}$, proving that these sets are enumerated by the same sequence, but also that many classical permutation statistics are equidistributed across these two sets. The description of this family of bijections is based on a bijection between the set of permutations avoiding the pattern $231$ and the set of those avoiding $132$ which preserves many permutation statistics. We also present other properties of this bijection, in particular for finding pairs of Wilf-equivalent permutation classes.
Schubert Polynomials and $k$-Schur Functions
Authors: Benedetti Carolina , Bergeron Nantel
Published: January 2020

The main purpose of this paper is to show that the multiplication of a Schubert polynomial of finite type $A$ by a Schur function, which we refer to as Schubert vs. Schur problem, can be understood combinatorially from the multiplication in the space of dual $k$-Schur functions. Using earlier work by the second author, we encode both problems by means of quasisymmetric functions. On the Schubert vs. Schur side, we study the poset given by the Bergeron-Sottile's $r$-Bruhat order, along with certain operators associated to this order. Then, we connect this poset with a graph on dual $k$-Schur functions given by studying the affine grassmannian order of  Lam-Lapointe-Morse-Shimozono. Also, we define operators associated to the graph on dual $k$-Schur functions which are analogous to the ones given for the Schubert vs. Schur problem. This is the first step of our more general program of showing combinatorially  the positivity of the multiplication of a dual $k$-Schur function by a Schur function.
On Graphs with Cyclic Defect or Excess
Authors: Delorme Charles , Pineda-Villavicencio Guillermo
Published: January 2020

The Moore bound constitutes both an upper bound on the order of a graph of maximum degree $d$ and diameter $D=k$ and a lower bound on the order of a graph of minimum degree $d$ and odd girth $g=2k+1$. Graphs missing or exceeding the Moore bound by $\epsilon$ are called graphs with defect or excess $\epsilon$, respectively. While Moore graphs (graphs with $\epsilon=0$) and graphs with defect or excess 1 have been characterized almost completely, graphs with defect or excess 2 represent a wide unexplored area. Graphs with defect (excess) 2 satisfy the equation $G_{d,k}(A) = J_n + B$ ($G_{d,k}(A) = J_n - B$), where $A$ denotes the adjacency matrix of the graph in question, $n$ its order, $J_n$ the $n\times n$ matrix whose entries are all 1's, $B$ the adjacency matrix of a union of vertex-disjoint cycles, and $G_{d,k}(x)$ a polynomial with integer coefficients such that the matrix $G_{d,k}(A)$ gives the number of paths of length at most $k$ joining each pair of vertices in the graph. In particular, if $B$ is the adjacency matrix of a cycle of order $n$ we call the corresponding graphs graphs with cyclic defect or excess; these graphs are the subject of our attention in this paper. We prove the non-existence of infinitely many such graphs. As the highlight of the paper we provide the asymptotic upper bound of $O(\frac{64}3d^{3/2})$ for the number of graphs of odd degree $d\ge3$ and cyclic defect or excess. This bound is in fact quite generous, and as a way of illustration, we show the non-existence of some families of graphs of odd degree $d\ge3$ and cyclic defect or excess. Actually, we conjecture that, apart from the Möbius ladder on 8 vertices, no non-trivial graph of any degree $\ge 3$ and cyclic defect or excess exists.
Lower Bounds for the Average Genus of a CF-graph
Authors: Chen Yichao
Published: January 2020

CF-graphs form a class of multigraphs that contains all simple graphs. We prove a lower bound for the average genus of a CF-graph which is a linear function of its Betti number. A lower bound for average genus in terms of the maximum genus and some structure theorems for graphs with a given average genus are also provided.
Enumeration of Tilings of Quartered Aztec Rectangles
Authors: Lai Tri
Published: January 2020

We generalize a theorem of W. Jockusch and J. Propp on quartered Aztec diamonds by enumerating the tilings of quartered Aztec rectangles. We use subgraph replacement method to transform the dual graph of a quartered Aztec rectangle to the dual graph of a quartered lozenge hexagon, and then use Lindström-Gessel-Viennot methodology to find the number of tilings of a quartered lozenge hexagon.
Maximum 4-Degenerate Subgraph of a Planar Graph
Authors: Lukot'ka Robert , Mazák Ján , Zhu Xuding
Published: January 2020

A graph $G$ is $k$-degenerate if it can be transformed into an empty graph by subsequent removals of vertices of degree $k$ or less. We prove that every connected planar graph with average degree $d \ge  2$ has a $4$-degenerate induced subgraph containing at least $ (38 - d)/36$ of its vertices. This shows that every planar graph of order $n$ has a $4$-degenerate induced subgraph of order more than $8/9 \cdot n$. We also consider a local variation of this problem and show that in every planar graph with at least 7 vertices, deleting a suitable vertex allows us to subsequently remove at least 6 more vertices of degree four or less.
Mutations of Fake Weighted Projective Spaces
Authors: Coates Tom , Gonshaw Samuel , Kasprzyk Alexander , Nabijou Navid
Published: January 2020

We characterise mutations between fake weighted projective spaces, and give explicit formulas for how the weights and multiplicity change under mutation. In particular, we prove that multiplicity-preserving  mutations between fake weighted projective spaces are mutations over edges of the corresponding simplices. As an application, we analyse the canonical and terminal fake weighted projective spaces of maximal degree.
The Orderings of Bicyclic Graphs and Connected Graphs by Algebraic Connectivity
Authors: Li Jianxi , Guo Ji-Ming , Shiu Wai Chee
Published: January 2020

The algebraic connectivity of a graph $G$ is the second smallest eigenvalue of its Laplacian matrix. Let $\mathscr{B}_n$ be the set of all bicyclic graphs of order $n$. In this paper, we determine the last four bicyclic graphs (according to their smallest algebraic connectivities) among all graphs in $\mathscr{B}_n$ when $n\geq 13$. This result, together with our previous results on trees and unicyclic graphs, can be used to further determine the last sixteen graphs among all connected graphs of order $n$. This extends the results of Shao et al. [The ordering of trees and connected graphs by their algebraic connectivity, Linear Algebra Appl. 428 (2008) 1421-1438].
The Game Chromatic Number of Dense Random Graphs
Authors: Keusch Ralph , Steger Angelika
Published: January 2020

Suppose that two players take turns coloring the vertices of a given graph G with k colors. In each move the current player colors a vertex such that neighboring vertices get different colors. The first player wins this game if and only if at the end, all vertices are colored. The game chromatic number χg(G) is defined as the smallest k for which the first player has a winning strategy.Recently, Bohman, Frieze and Sudakov [Random Structures and Algorithms 2008] analysed the game chromatic number of random graphs and obtained lower and upper bounds of the same order of magnitude. In this paper we improve existing results and show that with high probability, the game chromatic number χg(Gn,p) of dense random graphs with p ≥ e-o(log n) is asymptotically twice as large as the ordinary chromatic number χ(Gn,p).
On Maltsev Digraphs
Authors: Carvalho Catarina , Egri Laszlo , Jackson Marcel , Niven Todd
Published: January 2020

We study digraphs preserved by a Maltsev operation: Maltsev digraphs. We show that these digraphs retract either onto a directed path or to the disjoint union of directed cycles, showing in this way that the constraint satisfaction problem for Maltsev digraphs is in logspace, L. We then generalize results from Kazda (2011) to show that a Maltsev digraph is preserved not only by a majority operation, but by a class of other operations (e.g., minority, Pixley) and obtain a $O(|V_G|^4)$-time algorithm to recognize Maltsev digraphs. We also prove analogous results for digraphs preserved by conservative Maltsev operations which we use to establish that the list homomorphism problem for Maltsev digraphs is in L. We then give a polynomial time characterisation of Maltsev digraphs admitting a conservative 2-semilattice operation. Finally, we give a simple inductive construction of directed acyclic digraphs preserved by a Maltsev operation, and relate them with series parallel digraphs.
Wieland Drift for Triangular Fully Packed Loop Configurations
Authors: Beil Sabine , Fischer Ilse , Nadeau Philippe
Published: January 2020

Triangular fully packed loop configurations (TFPLs) emerged as auxiliary objects in the study of fully packed loop configurations on a square (FPLs) corresponding to link patterns with a large number of nested arches. Wieland gyration, on the other hand, was invented to show the rotational invariance of the numbers $A_\pi$ of FPLs corresponding to a given link pattern $\pi$. The focus of this article is the definition and study of Wieland drift on TFPLs. We show that the repeated application of this operation eventually leads to a configuration that is left invariant. We also provide a characterization of such stable configurations. Finally we apply Wieland drift to the study of TFPL configurations, in particular giving new and simple proofs of several results.
Counting the Palstars
Authors: Richmond L. Bruce , Shallit Jeffrey O
Published: January 2020

A palstar (after Knuth, Morris, and Pratt) is a concatenation of even-length palindromes.  We show that, asymptotically, there are $\Theta(\alpha_k^n)$ palstars of length $2n$ over a $k$-letter alphabet, where $\alpha_k$ is a constant such that $2k-1 < \alpha_k < 2k-{1 \over 2}$.  In particular, $\alpha_2\doteq 3.33513193$.
On the Longest $k$-Alternating Subsequence
Authors: Pak Igor , Pemantle Robin
Published: January 2020

We show that the longest $k$-alternating substring of a random permutation has length asymptotic to $2(n-k)/3$.
A Colorful Involution for the Generating Function for Signed Stirling Numbers of the First Kind
Authors: Levande Paul
Published: January 2020

We show how the generating function for signed Stirling numbers of the first kind can be proved using the involution principle and a natural combinatorial interpretation based on cycle-colored permuations.
Locating-Dominating Sets and Identifying Codes in Graphs of Girth at least 5
Authors: Balbuena Camino , Foucaud Florent , Hansberg Adriana
Published: January 2020

Locating-dominating sets and identifying codes are two closely related notions in the area of separating systems. Roughly speaking, they consist in a dominating set of a graph such that every vertex is uniquely identified by its neighbourhood within the dominating set. In this paper, we study the size of a smallest locating-dominating set or identifying code for graphs of girth at least 5 and of given minimum degree. We use the technique of vertex-disjoint paths to provide upper bounds on the minimum size of such sets, and construct graphs who come close to meeting these bounds.
Summation of Rational Series Twisted by Strongly $B$-multiplicative Coefficients
Authors: Allouche Jean-Paul , Sondow Jonathan
Published: January 2020

We evaluate in closed form series of the type $\sum u(n) R(n)$, with $(u(n))_n$ a strongly $B$-multiplicative sequence and $R(n)$ a (well-chosen) rational function. A typical example is:$$\sum_{n \geq 1} (-1)^{s_2(n)} \frac{4n+1}{2n(2n+1)(2n+2)} = -\frac{1}{4}$$where $s_2(n)$ is the sum of the binary digits of the integer $n$. Furthermore closed formulas for series involving automatic sequences that are not strongly $B$-multiplicative, such as the regular paperfolding and Golay-Shapiro-Rudin sequences, are obtained; for example, for integer $d \geq 0$:$$\sum_{n \geq 0} \frac{v(n)}{(n+1)^{2d+1}} = \frac{\pi^{2d+1} |E_{2d}|}{(2^{2d+2}-2)(2d)!}$$where $(v(n))_n$ is the $\pm 1$ regular paperfolding sequence and $E_{2d}$ is an Euler number.
Random Subnetworks of Random Sorting Networks
Authors: Angel Omer , Holroyd Alexander E.
Published: January 2020

A sorting network is a shortest path from $12\cdots n$ to $n\cdots21$ in the Cayley graph of $S_n$ generated by nearest-neighbor swaps. For $m\leq n$, consider the random $m$-particle sorting network obtained by choosing an $n$-particle sorting network uniformly at random and then observing only the relative order of $m$ particles chosen uniformly at random. We prove that the expected number of swaps in location $j$ in the subnetwork does not depend on $n$, and we provide a formula for it. Our proof is probabilistic, and involves a Pólya urn with non-integer numbers of balls. From the case $m=4$ we obtain a proof of a conjecture of Warrington. Our result is consistent with a conjectural limiting law of the subnetwork as $n\to\infty$ implied by the great circle conjecture of Angel, Holroyd, Romik and Virág.
Power Sum Expansion of Chromatic Quasisymmetric Functions
Authors: Athanasiadis Christos A.
Published: January 2020

The chromatic quasisymmetric function of a graph was introduced by Shareshian and Wachs as a refinement of Stanley's chromatic symmetric function. An explicit combinatorial formula, conjectured by Shareshian and Wachs, expressing the chromatic quasisymmetric function of the incomparability graph of a natural unit interval order in terms of power sum symmetric functions, is proven. The proof uses a formula of Roichman for the irreducible characters of the symmetric group.
A Classification of Ramanujan Unitary Cayley Graphs
Authors: Droll Andrew
Published: January 2020

The unitary Cayley graph on $n$ vertices, $X_n$, has vertex set ${\Bbb Z}/{n\Bbb Z}$, and two vertices $a$ and $b$ are connected by an edge if and only if they differ by a multiplicative unit modulo $n$, i.e. ${\rm gcd}(a-b,n) = 1$. A $k$-regular graph $X$ is Ramanujan if and only if $\lambda(X) \leq 2\sqrt{k-1}$ where $\lambda(X)$ is the second largest absolute value of the eigenvalues of the adjacency matrix of $X$. We obtain a complete characterization of the cases in which the unitary Cayley graph $X_n$ is a Ramanujan graph.
Motzkin Paths, Motzkin Polynomials and Recurrence Relations
Authors: Oste Roy , Van der Jeugt Joris
Published: January 2020

We consider the Motzkin paths which are simple combinatorial objects appearing in many contexts. They are counted by the Motzkin numbers, related to the well known Catalan numbers.  Associated with the Motzkin paths, we introduce the Motzkin polynomial, which is a multi-variable polynomial "counting" all Motzkin paths of a certain type. Motzkin polynomials (also called Jacobi-Rogers polynomials) have been studied before, but here we deduce some properties based on recurrence relations. The recurrence relations proved here also allow an efficient computation of the Motzkin polynomials. Finally, we show that the matrix entries of powers of an arbitrary tridiagonal matrix are essentially given by Motzkin polynomials, a property commonly known but usually stated without proof.
Roudneff's Conjecture for Lawrence Oriented Matroids
Authors: Montejano Luis Pedro , Ramírez-Alfonsín Jorge Luis
Published: January 2020

J.-P. Roudneff has conjectured that every arrangement of $n\ge 2d+1\ge 5$ (pseudo) hyperplanes in the real projective space $\mathbb{P}^d$ has at most $\sum_{i=0}^{d-2} \binom{n-1}{i}$ cells bounded by each hyperplane. In this note, we show the validity of this conjecture for arrangements arising from Lawrence oriented matroids.
Upper and lower bounds for $F_v(4,4;5)$
Authors: Xu Xiaodong , Luo Haipeng , Shao Zehui
Published: January 2020

In this note we give a computer assisted proof showing that the unique $(5,3)$-Ramsey graph is the unique $K_5$-free graph of order 13 giving $F_v(3,4;5) \leq 13$, then we prove that $17 \leq F_v(2,2,2, 4; 5) \leq F_v(4, 4; 5) \leq 23$. This improves the previous best bounds $16 \leq F_v(4, 4; 5) \leq 25$ provided by Nenov and Kolev.
A Tight Lower Bound for Convexly Independent Subsets of the Minkowski Sums of Planar Point Sets
Authors: Bílka Ondřej , Buchin Kevin , Fulek Radoslav , Kiyomi Masashi , Okamoto Yoshio , Tanigawa Shin-ichi , Tóth Csaba D.
Published: January 2020

Recently, Eisenbrand, Pach, Rothvoß, and Sopher studied the function $M(m, n)$, which is the largest cardinality of a convexly independent subset of the Minkowski sum of some planar point sets $P$ and $Q$ with $|P| = m$ and $|Q| = n$. They proved that $M(m,n)=O(m^{2/3}n^{2/3}+m+n)$, and asked whether a superlinear lower bound exists for $M(n,n)$. In this note, we show that their upper bound is the best possible apart from constant factors.
Intersections of Shifted Sets
Authors: Di Nasso Mauro
Published: January 2020

We consider shifts of a set $A\subseteq\mathbb{N}$ by elements from another set $B\subseteq\mathbb{N}$, and prove intersection properties according to the relative asymptotic size of $A$ and $B$. A consequence of our main theorem is the following: If $A=\{a_n\}$ is such that $a_n=o(n^{k/k-1})$, then the $k$-recurrence set $R_k(A)=\{x\mid |A\cap(A+x)|\ge k\}$ contains the distance sets  of arbitrarily large finite sets.
Distributions Defined by $q$-Supernomials, Fusion Products, and Demazure Modules
Authors: Kousidis Stavros , Schulte-Geers Ernst
Published: January 2020

We prove asymptotic normality of the distributions defined by $q$-supernomials, which implies asymptotic normality of the distributions given by the central string functions and the basic specialization of fusion modules of the current algebra of $\frak{sl}_2$. The limit is taken over linearly scaled fusion powers of a fixed collection of irreducible representations. This includes as special instances all Demazure modules of the affine Kac-Moody algebra associated to $\frak{sl}_2$. Along with an available complementary result on the asymptotic normality of the basic specialization of graded tensors of the type $A$ standard representation, our result is a central limit theorem for a serious class of graded tensors. It therefore serves as an indication towards universal behavior: The central string functions and the basic specialization of fusion and, in particular, Demazure modules behave asymptotically normal, as the number of fusions scale linearly in an asymptotic parameter, $N$ say.
Graphs with Four Boundary Vertices
Authors: Müller Tobias , Pór Attila , Sereni Jean-Sébastien
Published: January 2020

A vertex $v$ of a graph $G$ is a boundary vertex if there exists a vertex $u$ such that the distance in $G$ from $u$ to $v$ is at least the distance from $u$ to any neighbour of $v$. We give a full description of all graphs that have exactly four boundary vertices, which answers a question of Hasegawa and Saito. To this end, we introduce the concept of frame of a graph. It allows us to construct, for every positive integer $b$ and every possible "distance-vector" between $b$ points, a graph $G$ with exactly $b$ boundary vertices such that every graph with $b$ boundary vertices and the same distance-vector between them is an induced subgraph of $G$.
Counting Connected Set Partitions of Graphs
Authors: Simon Frank , Tittmann Peter , Trinks Martin
Published: January 2020

Let $G=(V,E)$ be a simple undirected graph with $n$ vertices then a set partition $\pi=\{V_1, \ldots, V_k\}$ of the vertex set of $G$ is a connected set partition if each subgraph $G[V_j]$ induced by the blocks $V_j$ of $\pi$ is connected for $1\le j\le k$. Define $q_{i}(G)$ as the number of connected set partitions in $G$ with $i$ blocks. The partition polynomial is $Q(G, x)=\sum_{i=0}^n q_{i}(G)x^i$. This paper presents a splitting approach to the partition polynomial on a separating vertex set $X$ in $G$ and summarizes some properties of the bond lattice. Furthermore the bivariate partition polynomial $Q(G,x,y)=\sum_{i=1}^n \sum_{j=1}^m q_{ij}(G)x^iy^j$ is briefly discussed, where $q_{ij}(G)$ counts the number of connected set partitions with $i$ blocks and $j$ intra block edges. Finally the complexity for the bivariate partition polynomial is proven to be $\sharp P$-hard.
Weighted Spanning Trees on some Self-Similar Graphs
Authors: D'Angeli Daniele , Donno Alfredo
Published: January 2020

We compute the complexity of two infinite families of finite graphs: the Sierpiński graphs, which are finite approximations of the well-known Sierpiński gasket, and the Schreier graphs of the Hanoi Towers group $H^{(3)}$ acting on the rooted ternary tree. For both of them, we study the weighted generating functions of the spanning trees, associated with several natural labellings of the edge sets.
Digraphs are $2$-Weight Choosable
Authors: Khatirinejad Mahdad , Naserasr Reza , Newman Mike , Seamone Ben , Stevens Brett
Published: January 2020

An edge-weighting vertex colouring of a graph is an edge-weight assignment such that the accumulated weights at the vertices yield a proper vertex colouring. If such an assignment from a set $S$ exists, we say the graph is $S$-weight colourable. We consider the $S$-weight colourability of digraphs by defining the accumulated weight at a vertex to be the sum of the inbound weights minus the sum of the outbound weights. Bartnicki et al. showed that every digraph is $S$-weight colourable for any set $S$ of size $2$ and asked whether one could show the same result using an algebraic approach. Using the Combinatorial Nullstellensatz and a classical theorem of Schur, we provide such a solution.
Combinatorics of the Three-Parameter PASEP Partition Function
Authors: Josuat-Vergès Matthieu
Published: January 2020

We consider a partially asymmetric exclusion process (PASEP) on a finite number of sites with open and directed boundary conditions. Its partition function was calculated by Blythe, Evans, Colaiori, and Essler. It is known to be a generating function of permutation tableaux by the combinatorial interpretation of Corteel and Williams. We prove bijectively two new combinatorial interpretations. The first one is in terms of weighted Motzkin paths called Laguerre histories and is obtained by refining a bijection of Foata and Zeilberger. Secondly we show that this partition function is the generating function of permutations with respect to right-to-left minima, right-to-left maxima, ascents, and 31-2 patterns, by refining a bijection of Françon and Viennot. Then we give a new formula for the partition function which generalizes the one of Blythe & al. It is proved in two combinatorial ways. The first proof is an enumeration of lattice paths which are known to be a solution of the Matrix Ansatz of Derrida & al. The second proof relies on a previous enumeration of rook placements, which appear in the combinatorial interpretation of a related normal ordering problem. We also obtain a closed formula for the moments of Al-Salam-Chihara polynomials.
Baron Münchhausen Redeems Himself: Bounds for a Coin-Weighing Puzzle
Authors: Khovanova Tanya , Lewis Joel Brewster
Published: January 2020

We investigate a coin-weighing puzzle that appeared in the 1991 Moscow Math Olympiad. We generalize the puzzle by varying the number of participating coins, and deduce an upper bound on the number of weighings needed to solve the puzzle that is noticeably better than the trivial upper bound. In particular, we show that logarithmically-many weighings on a balance suffice.