bluuebunny/crossref_metadata_2025 huggingface dataset:
A Short Proof for the Number of Permutations Containing Pattern 321 Exactly Once
Authors: Burstein Alexander
Published: January 2020

We give a short proof for J. Noonan's result on the number of permutations containing pattern 321 exactly once.
The Distribution of Run Lengths in Integer Compositions
Authors: Wilf Herbert S.
Published: January 2020

We find explicitly the generating function for the number of compositions of $n$ that avoid all words on a given list of forbidden subwords, in the case where the forbidden words are pairwise letter-disjoint. From this we get the gf for compositions of $n$ with no $k$ consecutive parts equal, as well as the number with $m$ parts and no consecutive $k$ parts being equal, which generalizes corresponding results for Carlitz compositions.
Minimal Overlapping Patterns in Colored Permutations
Authors: Duane Adrian , Remmel Jeffrey
Published: January 2020

A pattern $P$ of length $j$ has the minimal overlapping property if two consecutive occurrences of the pattern can overlap in at most one place, namely, at the end of the first consecutive occurrence of the pattern and at the start of the second consecutive occurrence of the pattern. For patterns $P$ which have the minimal overlapping property, we derive a general formula for the generating function for the number of consecutive occurrences of $P$ in words, permutations and $k$-colored permutations in terms of the number of maximum packings of $P$ which are patterns of minimal length which has $n$ consecutive occurrences of the pattern $P$. Our results have as special cases several results which have appeared in the literature. Another consequence of our results is to prove a conjecture of Elizalde that two permutations $\alpha$ and $\beta$ of size $j$ which have the minimal overlapping property are strongly $c$-Wilf equivalent if $\alpha$ and $\beta$ have the same first and last elements.
Toward a Combinatorial Proof of the Jacobian Conjecture!
Authors: Singer Dan
Published: January 2020

The Jacobian conjecture [Keller, Monatsh. Math. Phys., 1939] gives rise to a problem in combinatorial linear algebra: Is the vector space generated by rooted trees spanned by forest shuffle vectors? In order to make headway on this problem we must study the algebraic and combinatorial properties of rooted trees. We prove three theorems about the vector space generated by binary rooted trees: Shuffle vectors of fixed length forests are linearly independent, shuffle vectors of nondegenerate forests relative to a fixed tree are linearly independent, and shuffle vectors of sufficient length forests are linearly independent. These results are proved using the acyclic digraph method for establishing that a coefficient matrix has full rank [Singer, The Electronic Journal of Combinatorics, 2009]. We also provide an infinite class of counterexamples to demonstrate the need for sufficient length in the third theorem.
Vertex-Oriented Hamilton Cycles in Directed Graphs
Authors: Plantholt Michael J. , Tipnis Shailesh K.
Published: January 2020

Let $D$ be a directed graph of order $n$. An anti-directed Hamilton cycle $H$ in $D$ is a Hamilton cycle in the graph underlying $D$ such that no pair of consecutive arcs in $H$ form a directed path in $D$. We prove that if $D$ is a directed graph with even order $n$ and if the indegree and the outdegree of each vertex of $D$ is at least ${2\over 3}n$ then $D$ contains an anti-directed Hamilton cycle. This improves a bound of Grant. Let $V(D) = P \cup Q$ be a partition of $V(D)$. A $(P,Q)$ vertex-oriented Hamilton cycle in $D$ is a Hamilton cycle $H$ in the graph underlying $D$ such that for each $v \in P$, consecutive arcs of $H$ incident on $v$ do not form a directed path in $D$, and, for each $v \in Q$, consecutive arcs of $H$ incident on $v$ form a directed path in $D$. We give sufficient conditions for the existence of a $(P,Q)$ vertex-oriented Hamilton cycle in $D$ for the cases when $|P| \geq {2\over 3}n$ and when ${1\over 3}n \leq |P| \leq {2\over 3}n$. This sharpens a bound given by Badheka et al.
Properties of $\theta$-super positive graphs
Authors: Ku Cheng Yeaw , Wong Kok Bin
Published: January 2020

Let the matching polynomial of a graph $G$ be denoted by $\mu (G,x)$. A graph $G$ is said to be $\theta$-super positive if  $\mu(G,\theta)\neq 0$ and $\mu(G\setminus v,\theta)=0$ for all $v\in V(G)$. In particular, $G$ is $0$-super positive if and only if $G$ has a perfect matching. While much is known about $0$-super positive graphs, almost nothing is known about $\theta$-super positive graphs for $\theta \neq 0$. This motivates us to investigate the structure of $\theta$-super positive graphs in this paper. Though a $0$-super positive graph need not contain any cycle, we show that a $\theta$-super positive graph with $\theta \neq 0$ must contain a cycle. We introduce two important types of $\theta$-super positive graphs, namely $\theta$-elementary and $\theta$-base graphs. One of our main results is that any $\theta$-super positive graph $G$ can be constructed by adding certain type of edges to a disjoint union of $\theta$-base graphs; moreover, these $\theta$-base graphs are uniquely determined by $G$. We also give a characterization of $\theta$-elementary graphs: a graph $G$ is $\theta$-elementary if and only if the set of all its $\theta$-barrier sets form a partition of $V(G)$. Here, $\theta$-elementary graphs and $\theta$-barrier sets can be regarded as $\theta$-analogue of elementary graphs and Tutte sets in classical matching theory.
On Suborbital Graphs for the Normalizer of $\Gamma_{0}(N)$
Authors: Keskin Refik , Demirtürk Bahar
Published: January 2020

In this study, we deal with the conjecture given in [R. Keskin, Suborbital graph for the normalizer of $\Gamma _{0}(m)$, European Journal of Combinatorics 27 (2006) 193-206.], that when the normalizer of $\Gamma _{0}(N)$ acts transitively on ${\Bbb Q\cup\{\infty \}}$, any circuit in the suborbital graph $G(\infty,u/n)$ for the normalizer of $\Gamma _{0}(N),$ is of the form $$ v\rightarrow T(v)\rightarrow T^{2}(v)\rightarrow {\ \cdot \cdot \cdot } \rightarrow T^{k-1}(v)\rightarrow v, $$ where $n>1$, $v\in {\Bbb Q\cup \{\infty \}}$ and $T$ is an elliptic mapping of order $k$ in the normalizer of $\Gamma_{0}(N)$.
Two-Part Set Systems
Authors: Erdős Péter L. , Gerbner Dániel , Lemons Nathan , Mubayi Dhruv , Palmer Cory , Patkós Balázs
Published: January 2020

The two part Sperner theorem of Katona and Kleitman states that if $X$ is an $n$-element set with partition $X_1 \cup X_2$, and $\mathcal{F}$ is a family of subsets of $X$ such that  no two sets $A, B \in \mathcal{F}$  satisfy $A \subset B$ (or $B \subset A$) and $A \cap X_i=B\cap X_i$ for some $i$, then $|\mathcal{F}| \le {n \choose \lfloor n/2\rfloor}$. We consider variations of this problem by replacing the Sperner property with the intersection property and considering families that satisfy various combinations of these properties on one or both parts $X_1$, $X_2$. Along the way, we prove the following  new result which may be of independent interest: let $\mathcal{F},\mathcal{G}$ be intersecting families of subsets of an $n$-element set that are additionally cross-Sperner, meaning that if $A \in\mathcal{F}$ and $B \in \mathcal{G}$, then $A \not\subset B$ and $B \not\subset A$. Then  $|\mathcal{F}| +|\mathcal{G}| \le 2^{n-1}$ and there are exponentially many examples showing that this bound is tight.
On the Number of Indecomposable Permutations with a Given Number of Cycles
Authors: Cori Robert , Mathieu Claire , Robson John Michael
Published: January 2020

A permutation $a_1a_2\ldots a_n$ is indecomposable if there does not exist $p<n$ such that $a_1a_2\ldots a_p$ is a permutation of $\{ 1,2,\ldots,p\}$. We consider the  probability that a permutation of ${\mathbb S}_n$  with $m$ cycles is indecomposable and prove that  this probability is monotone non-increasing in $n$.We compute  also the asymptotic probability when  $n$ goes to infinity with $m/n$ tending to a fixed ratio.  The asymptotic probability is monotone in $m/n$, and there is no threshold phenomenon: it degrades gracefully from 1 to 0. When $n=2m$, a slight majority ($51.117\ldots$ percent) of the permutations are indecomposable.
The Covered Components Polynomial: A New Representation of the Edge Elimination Polynomial
Authors: Trinks Martin
Published: January 2020

Motivated by the definition of the edge elimination polynomial of a graph we define the covered components polynomial counting spanning subgraphs with respect to their number of components, edges and covered components. We prove a recurrence relation, which shows that both graph polynomials are substitution instances of each other. We give some properties of the covered components polynomial and some results concerning relations to other graph polynomials.
Non-Isomorphic Graphs with Cospectral Symmetric Powers
Authors: Barghi Amir Rahnamai , Ponomarenko Ilya
Published: January 2020

The symmetric $m$-th power of a graph is the graph whose vertices are $m$-subsets of vertices and in which two $m$-subsets are adjacent if and only if their symmetric difference is an edge of the original graph. It was conjectured that there exists a fixed $m$ such that any two graphs are isomorphic if and only if their $m$-th symmetric powers are cospectral. In this paper we show that given a positive integer $m$ there exist infinitely many pairs of non-isomorphic graphs with cospectral $m$-th symmetric powers. Our construction is based on theory of multidimensional extensions of coherent configurations.
Partitions with Distinct Multiplicities of Parts: On An "Unsolved Problem" Posed By Herbert Wilf
Authors: Fill James Allen , Janson Svante , Ward Mark Daniel
Published: January 2020

Wilf's Sixth Unsolved Problem asks for any interesting properties of the set of partitions of integers for which the (nonzero) multiplicities of the parts are all different.  We refer to these as Wilf partitions.  Using $f(n)$ to denote the number of Wilf partitions, we establish lead-order asymptotics for $\ln{f(n)}$.
The Excessive [3]-Index of All Graphs
Authors: Cariolaro David , Fu Hung-Lin
Published: January 2020

Let $m$ be a positive integer and let $G$ be a graph. A set ${\cal M}$ of matchings of $G$, all of which of size $m$, is called an $[m]$-covering of $G$ if $\bigcup_{M\in {{\cal M}}}M=E(G)$. $G$ is called $[m]$-coverable if it has an $[m]$-covering. An $[m]$-covering ${\cal M}$ such that $|{{\cal M}}|$ is minimum is called an excessive $[m]$-factorization of $G$ and the number of matchings it contains is a graph parameter called excessive $[m]$-index and denoted by $\chi'_{[m]}(G)$ (the value of $\chi'_{[m]}(G)$ is conventionally set to $\infty$ if $G$ is not $[m]$-coverable). It is obvious that $\chi'_{[1]}(G)=|E(G)|$ for every graph $G$, and it is not difficult to see that $\chi'_{[2]}(G)=\max\{\chi'(G),\lceil |E(G)|/2 \rceil\}$ for every $[2]$-coverable graph $G$. However the task of determining $\chi'_{[m]}(G)$ for arbitrary $m$ and $G$ seems to increase very rapidly in difficulty as $m$ increases, and a general formula for $m\geq 3$ is unknown. In this paper we determine such a formula for $m=3,$ thereby determining the excessive $[3]$-index for all graphs.
Combinatorial Interpretations of Particular Evaluations of Complete and Elementary Symmetric Functions
Authors: Mongelli Pietro
Published: January 2020

The Jacobi-Stirling numbers and the Legendre-Stirling numbers of the first and second kind were first introduced by Everitt et al. (2002) and (2007) in the spectral theory. In this paper we note that Jacobi-Stirling numbers and Legendre-Stirling numbers are specializations of elementary and complete symmetric functions. We then study combinatorial interpretations of this specialization and obtain new combinatorial  interpretations of the Jacobi-Stirling and Legendre-Stirling numbers.
On a Class of Highly Symmetric k-Factorizations
Authors: Traetta Tommaso
Published: January 2020

A $k$-factorization of $K_v$ of type $(r, s)$ consists of $k$-factors each of which is the disjoint union of $r$ copies of $K_{k+1}$ and $s$ copies of $K_{k,k}$. By means of what we call the patterned $k$-factorization $F_k(D)$ over an arbitrary group $D$ of order $2s + 1$, it is shown that a $k$-factorization of type $(1, s)$ exists for any $k\ge2$ and for any $s\ge1$ with $D$ being an automorphism group acting sharply transitively on the factor-set. The general method to construct a $k$-factorization $F$ of type $(1, s)$ over an arbitrary 1-factorization $S$ of $K_{2s+2}$ ($F$ is said to be based on $S$) is used to prove that the number of pairwise non-isomorphic $k$-factorizations of this type goes to infinity with $s$. In this paper, we show that the full automorphism group of $F$ is known as soon as we know the one of $S$. In particular, the full automorphism group of $F_k(D)$ is determined for any $k\ge2$, generalizing a result given by P. J. Cameron for patterned 1-factorizations [J London Math Soc 11 (1975), 189-201]. Finally, it is shown that $F_k(D)$ has exactly $(k!)2s+1(2s+1)|Aut(D)|$ automorphisms whenever $D$ is abelian.
Maximum Frustration in Bipartite Signed Graphs
Authors: Bowlin Garry S
Published: January 2020

A signed graph is a graph where each edge is labeled as either positive or negative. A circle is positive if the product of edge labels is positive. The frustration index is the least number of edges that need to be removed so that every remaining circle is positive. The maximum frustration of a graph is the maximum frustration index over all possible sign labellings. We prove two results about the maximum frustration of a complete bipartite graph $K_{l,r}$, with $l$ left vertices and $r$ right vertices. First, it is bounded above by\[ \frac{lr}{2}\left(1-\frac{1}{2^{l-1}}\binom{l-1}{\lfloor \frac{l-1}{2}\rfloor}\right).\] Second, there is a unique family of signed $K_{l,r}$ that reach this bound. Using this fact, exact formulas for the maximum frustration of $K_{l,r}$ are found for $l \leq 7$.
Finite Homomorphism-Homogeneous Permutations via Edge Colourings of Chains
Authors: Dolinka Igor , Jungábel Éva
Published: January 2020

A relational structure is homomorphism-homogeneous if any homomorphism between its finite substructures extends to an endomorphism of the structure in question. In this note, we characterise all permutations on a finite set enjoying this property. To accomplish this, we switch from the more traditional view of a permutation as a set endowed with two linear orders to a different representation by a single linear order (considered as a directed graph with loops) whose non-loop edges are coloured in two colours, thereby `splitting' the linear order into two posets.
Inequivalence of Difference Sets: On a Remark of Baumert
Authors: Ó Catháin Padraig
Published: January 2020

An often cited statement of Baumert in his book Cyclic difference sets asserts that four well known families of cyclic $(4t-1,2t-1,t-1)$ difference sets are inequivalent, apart from a small number of exceptions with $t< 8$. We are not aware of a proof of this statement in the literature.Three of the families discussed by Baumert have analogous constructions in non-cyclic groups. We extend his inequivalence statement to a general inequivalence result, for which we provide a complete and self-contained proof. We preface our proof with a survey of the four families of difference sets, since there seems to be some confusion in the literature between the cyclic and non-cyclic cases.
An Undecidability Result on Limits of Sparse Graphs
Authors: Csóka Endre
Published: January 2020

Given a set $\mathcal{B}$ of finite rooted graphs and a radius $r$ as an input, we prove that it is undecidable to determine whether there exists a sequence $(G_i)$ of finite bounded degree graphs such that the rooted $r$-radius neighbourhood of a random node of $G_i$ is isomorphic to a rooted graph in $\mathcal{B}$ with probability tending to 1. Our proof implies a similar result for the case where the sequence $(G_i)$ is replaced by a unimodular random graph.
Excedance Numbers for the Permutations of Type B
Authors: Zhao Alina F.Y.
Published: January 2020

This work provides a study on the multidistribution of type $B$ excedances, fixed points and cycles on the permutations of type $B$. We derive the recurrences and closed formulas for the distribution of signed excedances on type $B$ permutations as well as derangements via combinatorial construction. Based on this result, we obtain the recurrence and generating function for the signed excedance polynomial and disclose some relationships with Euler numbers and Springer numbers, respectively.
Inequalities between Gamma-Polynomials of Graph-Associahedra
Authors: Aisbett Natalie
Published: January 2020

We prove a conjecture of Postnikov, Reiner and Williams by defining a partial order on the set of tree graphs with $n$ vertices that induces inequalities between the $\gamma$-polynomials of their associated graph-associahedra. The partial order is given by relating trees that can be obtained from one another by operations called tree shifts. We also show that tree shifts lower the $\gamma$-polynomials of graphs that are not trees, as do the flossing moves of Babson and Reiner.
Existence of 2-$(v,k,1)$ Designs Admitting a Block-Transitive Group of Affine Type
Authors: Shifeng Ding , Weijun Liu
Published: January 2020

In this paper we use Weil's estimate on character sums to prove that large admissible prime powers $q$ admit 2-$(q,k,1)$ designs having block-transitive automorphism groups in AGL$(1, q)$.
On $(K_{q},k)$ Stable Graphs with Small $k$
Authors: Fouquet Jean-Luc , Thuillier Henri , Vanherpe Jean-Marie , Wojda Adam Paweł
Published: January 2020

A graph $G$ is $(K_{q},k)$ stable if it contains a copy of $K_{q}$ after deleting any subset of $k$ vertices. In a previous paper we have characterized the $(K_q,k)$ stable graphs with minimum size for $3 \le q \le 5$ and we have proved that the only $(K_q,k)$ stable graph with minimum size is $K_{q+k}$ for $q \ge 5$ and $k \le 3$. We show that for $q \ge 6$ and $k \le \frac{q}{2}+1$ the only $(K_q,k)$ stable graph with minimum size is isomorphic to $K_{q+k}$.
Ramsey Properties of Random Subgraphs of Pseudo-Random Graphs
Authors: Shen Jia
Published: January 2020

Let $G=(V,E)$ be a $d$-regular graph of order $n$. Let $G_p$ be the random subgraph of $G$ for which each edge is selected from $E(G)$ independently at random with probability $p$. For a fixed graph $H$, define $m(H):=$max$\{e(H')/(v(H')-1):H' \subseteq H\}$. We prove that $n^{(m(H)-1)/m(H)}/d$ is a threshold function for $G_p$ to satisfy Ramsey, induced Ramsey, and canonical Ramsey properties with respect to vertex coloring, respectively, provided the eigenvalue $\lambda$ of $G$ that is second largest in absolute value is significantly smaller than $d$.As a consequence, it is also shown that $\displaystyle n^{(m(H)-1)/m(H)}/d$ is a threshold function for $G_p$ to contain a family of vertex disjoint copies of $H$ (an $H$ packing) that covers $(1-o(1))n$ vertices of $G$. Using a similar argument, the sharp threshold function for $G_p$ to contain $H$ as a subgraph is obtained as well.
An Ordered Turán Problem for Bipartite Graphs
Authors: Timmons Craig
Published: January 2020

Let $F$ be a graph.  A graph $G$ is $F$-free if it does not contain $F$ as a subgraph.  The Turán number of $F$, written $\textrm{ex}(n,F)$, is the maximum number of edges in an $F$-free graph with $n$ vertices.  The determination of Turán numbers of bipartite graphs is a challenging and widely investigated problem.  In this paper we introduce an ordered version of the Turán problem for bipartite graphs.  Let $G$ be a graph with $V(G) = \{1, 2, \dots , n \}$ and view the vertices of $G$ as being ordered in the natural way.  A zig-zag $K_{s,t}$, denoted $Z_{s,t}$, is a complete bipartite graph $K_{s,t}$ whose parts $A = \{n_1 < n_2 < \dots < n_s \}$ and $B = \{m_1 < m_2 < \dots < m_t \}$ satisfy the condition $n_s < m_1$.  A zig-zag $C_{2k}$ is an even cycle $C_{2k}$ whose vertices in one part precede all of those in the other part.  Write $\mathcal{Z}_{2k}$ for the family of zig-zag $2k$-cycles.  We investigate the Turán numbers $\textrm{ex}(n,Z_{s,t})$ and $\textrm{ex}(n,\mathcal{Z}_{2k})$.  In particular we show $\textrm{ex}(n, Z_{2,2}) \leq \frac{2}{3}n^{3/2} + O(n^{5/4})$.  For infinitely many $n$ we construct a $Z_{2,2}$-free $n$-vertex graph with more than $(n - \sqrt{n} - 1) + \textrm{ex} (n,K_{2,2})$ edges.
Note on Generating All Subsets of a Finite Set with Disjoint Unions
Authors: Ellis David
Published: January 2020

We call a family ${\cal G} \subset {\Bbb P}[n]$ a $k$-generator of ${\Bbb P}[n]$ if every $x \subset [n]$ can be expressed as a union of at most $k$ disjoint sets in ${\cal G}$. Frein, Lévêque and Sebő conjectured that for any $n \geq k$, such a family must be at least as large as the $k$-generator obtained by taking a partition of $[n]$ into classes of sizes as equal as possible, and taking the union of the power-sets of the classes. We generalize a theorem of Alon and Frankl in order to show that for fixed $k$, any $k$-generator of ${\Bbb P}[n]$ must have size at least $k2^{n/k}(1-o(1))$, thereby verifying the conjecture asymptotically for multiples of $k$.
Families that Remain $k$-Sperner Even After Omitting an Element of their Ground Set
Authors: Patkós Balázs
Published: January 2020

A family $\mathcal{F}\subseteq 2^{[n]}$ of sets is said to be $l$-trace $k$-Sperner if for any $l$-subset $L \subset [n]$ the family $\mathcal{F}|_L=\{F|_L:F \in \mathcal{F}\}=\{F \cap L: F \in \mathcal{F}\}$ is $k$-Sperner, i.e. does not contain any chain of length $k+1$. The maximum size that an $l$-trace $k$-Sperner family $\mathcal{F} \subseteq 2^{[n]}$ can have is denoted by $f(n,k,l)$.For pairs of integers $l<k$, if in a family $\mathcal{G}$ every pair of sets satisfies $||G_1|-|G_2||<k-l$, then $\mathcal{G}$ possesses the $(n-l)$-trace $k$-Sperner property. Among such families, the largest one is $\mathcal{F}_0=\{F\in 2^{[n]}: \lfloor \frac{n-(k-l)}{2}\rfloor+1 \le |F| \le \lfloor \frac{n-(k-l)}{2}\rfloor +k-l\}$ and also $\mathcal{F}'_0=\{F\in 2^{[n]}: \lfloor \frac{n-(k-l)}{2}\rfloor \le |F| \le \lfloor \frac{n-(k-l)}{2}\rfloor +k-l-1\}$ if $n-(k-l)$ is even.In an earlier paper, we proved that this is asymptotically optimal for all pair of integers $l<k$, i.e. $f(n,k,n-l)=(1+o(1))|\mathcal{F}_0|$. In this paper we consider the case when $l=1$, $k\ge 2$, and prove that $f(n,k,n-1)=|\mathcal{F}_0|$ provided $n$ is large enough. We also prove that the unique $(n-1)$-trace $k$-Sperner family with size $f(n,k,n-1)$ is $\mathcal{F}_0$ and also $\mathcal{F}'_0$ when $n+k$ is odd.
A Stability Property for Coefficients in Kronecker Products of Complex $S_n$ Characters
Authors: Vallejo Ernesto
Published: January 2020

In this note we make explicit a stability property for Kronecker coefficients that is implicit in a theorem of Y. Dvir. Even in the simplest nontrivial case this property was overlooked despite of the work of several authors. As applications we give a new vanishing result and a new formula for some Kronecker coefficients.
Graph Cospectrality using Neighborhood Matrices
Authors: Bessa Aline Duarte , Rocha-Neto Ivan Carmo , Pinho Suani Tavares Rubim de , Andrade Roberto Fernandes Silva , Petit Lobao Thierry Correa
Published: January 2020

In this note we address the problem of graph isomorphism by means of eigenvalue spectra of different matrix representations:  the neighborhood matrix $\hat{M}$, its corresponding signless Laplacian $Q_{\hat{M}}$, and the set of higher order adjacency matrices $M_{\ell}$s. We find that, in relation to graphs with at most 10 vertices, $Q_{\hat{M}}$ leads to better results than the signless Laplacian $Q$; besides, when combined with $\hat{M}$, it even surpasses the Godsil and McKay switching method.
On the Union Complexity of Diametral Disks
Authors: Aronov Boris , Dulieu Muriel , Pinchasi Rom , Sharir Micha
Published: January 2020

Let $S$ be a set of $n$ points in the plane, and let $\mathcal{D}$ be an arbitrary set of disks, each having a pair of points of $S$ as a diameter. We show that the combinatorial complexity of the union of $\mathcal{D}$ is $O(n^{3/2})$, and provide a lower bound construction with $\Omega(n^{4/3})$ complexity. If the points of $S$ are in convex position, the upper bound drops to $O(n\log n)$.
The Optimal Drawings of $K_{5,n}$
Authors: Hernández-Vélez César , Medina Carolina , Salazar Gelasio
Published: January 2020

Zarankiewicz's Conjecture (ZC) states that the crossing number cr$(K_{m,n})$ equals $Z(m,n):=\lfloor{\frac{m}{2}}\rfloor \lfloor{\frac{m-1}{2}}\rfloor  \lfloor{\frac{n}{2}}\rfloor \lfloor{\frac{n-1}{2}}\rfloor$. Since Kleitman's verification of ZC for $K_{5,n}$ (from which ZC for $K_{6,n}$ easily follows), very little progress has been made around ZC; the most notable exceptions involve computer-aided results. With the aim of gaining a more profound understanding of this notoriously difficult conjecture, we investigate the optimal (that is, crossing-minimal) drawings of $K_{5,n}$. The widely known natural drawings of $K_{m,n}$ (the so-called Zarankiewicz drawings) with $Z(m,n)$ crossings contain antipodal vertices, that is, pairs of degree-$m$ vertices such that their induced drawing of $K_{m,2}$ has no crossings. Antipodal vertices also play a major role in Kleitman's inductive proof that cr$(K_{5,n}) = Z(5,n)$. We explore in depth the role of antipodal vertices in optimal drawings of $K_{5,n}$, for $n$ even. We prove that if {$n \equiv 2$ (mod $4$)}, then every optimal drawing of $K_{5,n}$ has antipodal vertices. We also exhibit a two-parameter family of optimal drawings $D_{r,s}$ of $K_{5,4(r+s)}$ (for $r,s\ge 0$), with no antipodal vertices, and show that if $n\equiv 0$ (mod $4$), then every optimal drawing of $K_{5,n}$ without antipodal vertices is (vertex rotation) isomorphic to $D_{r,s}$ for some integers $r,s$. As a corollary, we show that if $n$ is even, then every optimal drawing of $K_{5,n}$ is the superimposition of Zarankiewicz drawings with a drawing isomorphic to $D_{r,s}$ for some nonnegative integers $r,s$.
Rainbow Connection of Sparse Random Graphs
Authors: Frieze Alan , Tsourakakis Charalampos E.
Published: January 2020

An edge colored graph $G$ is rainbow edge connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this work we study the rainbow connectivity of binomial random graphs at the connectivity threshold $p=\frac{\log n+\omega}{n}$ where $\omega=\omega(n)\to\infty$ and ${\omega}=o(\log{n})$ and of random $r$-regular graphs where $r \geq 3$ is a fixed integer. Specifically, we prove that the rainbow connectivity $rc(G)$ of $G=G(n,p)$ satisfies $rc(G) \sim \max\{Z_1,\text{diam}(G)\}$ with high probability (whp). Here $Z_1$ is the number of vertices in $G$ whose degree equals 1 and the diameter of $G$ is asymptotically equal to $\frac{\log n}{\log\log n}$ whp. Finally, we prove that the rainbow connectivity $rc(G)$ of the random $r$-regular graph $G=G(n,r)$ whp satisfies $rc(G) =O(\log^{2\theta_r}{n})$ where $\theta_r=\frac{\log (r-1)}{\log (r-2)}$ when $r\geq 4$ and $rc(G) =O(\log^4n)$ whp when $r=3$.
New Computational Upper Bounds for Ramsey Numbers $R(3,k)$
Authors: Goedgebeur Jan , Radziszowski Stanisław P.
Published: January 2020

Using computational techniques we derive six new upper bounds on the classical two-color Ramsey numbers: $R(3,10) \le 42$, $R(3,11) \le 50$, $R(3,13) \le 68$, $R(3,14) \le 77$, $R(3,15) \le 87$, and $R(3,16) \le 98$. All of them are improvements by one over the previously best known bounds. Let $e(3,k,n)$ denote the minimum number of edges in any triangle-free graph on $n$ vertices without independent sets of order $k$. The new upper bounds on $R(3,k)$ are obtained by completing the computation of the exact values of $e(3,k,n)$ for all $n$ with $k \leq 9$ and for all $n \leq 33$ for $k = 10$, and by establishing new lower bounds on $e(3,k,n)$ for most of the open cases for $10 \le k \le 15$. The enumeration of all graphs witnessing the values of $e(3,k,n)$ is completed for all cases with $k \le 9$. We prove that the known critical graph for $R(3,9)$ on 35 vertices is unique up to isomorphism. For the case of $R(3,10)$, first we establish that $R(3,10)=43$ if and only if $e(3,10,42)=189$, or equivalently, that if $R(3,10)=43$ then every critical graph is regular of degree 9. Then, using computations, we disprove the existence of the latter, and thus show that $R(3,10) \le 42$.
Integer Points in Knapsack Polytopes and $s$-Covering Radius
Authors: Aliev Iskander , Henk Martin , Linke Eva
Published: January 2020

Given a matrix $A\in \mathbb{Z}^{m\times n}$ satisfying certain regularity assumptions, we consider for a positive integer $s$ the set ${\mathcal F}_s(A)\subset \mathbb{Z}^m$ of all vectors $b\in \mathbb{Z}^m$ such that the associated knapsack polytope\begin{equation*}P(A, b)=\{ x \in \mathbb{R}^n_{\ge 0}: A x= b\}\end{equation*}contains at least $s$ integer points. We present lower and upper bounds on the so called diagonal $s$-Frobenius number associated to the set ${\mathcal F}_s(A)$. In the case $m=1$ we prove an optimal lower bound for the $s$-Frobenius number, which is the largest integer $b$ such that $P(A,b)$ contains less than $s$ integer points.
On the Topology of the Cambrian Semilattices
Authors: Kallipoliti Myrto , Mühle Henri
Published: January 2020

For an arbitrary Coxeter group $W$, Reading and Speyer defined Cambrian semilattices $\mathcal{C}_{\gamma}$ as sub-semilattices of the weak order on $W$ induced by so-called $\gamma$-sortable elements. In this article, we define an edge-labeling of $\mathcal{C}_{\gamma}$, and show that this is an EL-labeling for every closed interval of $\mathcal{C}_{\gamma}$. In addition, we use our labeling to show that every finite open interval in a Cambrian semilattice is either contractible or spherical, and we characterize the spherical intervals, generalizing a result by Reading.
The Capture Time of the Hypercube
Authors: Bonato Anthony , Gordinowicz Przemysław , Kinnersley Bill , Prałat Paweł
Published: January 2020

In the game of Cops and Robbers, the capture time of a graph is the minimum number of moves needed by the cops to capture the robber, assuming optimal play. We prove that the capture time of the $n$-dimensional hypercube is $\Theta (n\ln n)$. Our methods include a novel randomized strategy for the players, which involves the analysis of the coupon-collector problem.
Dense $H$-Free Graphs are Almost $(\chi(H)-1)$-Partite
Authors: Allen Peter
Published: January 2020

By using the Szemerédi Regularity Lemma, Alon and Sudakov recently extended the classical Andrásfai-Erdős-Sós theorem to cover general graphs. We prove, without using the Regularity Lemma, that the following stronger statement is true. Given any $(r+1)$-partite graph $H$ whose smallest part has $t$ vertices, there exists a constant $C$ such that for any given $\varepsilon>0$ and sufficiently large $n$ the following is true. Whenever $G$ is an $n$-vertex graph with minimum degree $$\delta(G)\geq\left(1-{3\over 3r-1}+\varepsilon\right)n,$$ either $G$ contains $H$, or we can delete $f(n,H)\leq Cn^{2-{1\over t}}$ edges from $G$ to obtain an $r$-partite graph. Further, we are able to determine the correct order of magnitude of $f(n,H)$ in terms of the Zarankiewicz extremal function.
Online Ramsey Theory for Planar Graphs
Authors: Petříčková Šárka
Published: January 2020

An online Ramsey game $(G,\mathcal{H})$ is a game between Builder and Painter, alternating in turns. During each turn, Builder draws an edge, and Painter colors it blue or red. Builder's goal is to force Painter to create a monochromatic copy of $G$, while Painter's goal is to prevent this. The only limitation for Builder is that after each of his moves, the resulting graph has to belong to the class of graphs $\mathcal{H}$. It was conjectured by Grytczuk, Hałuszczak, and Kierstead (2004) that if $\mathcal{H}$ is the class of planar graphs, then Builder can force a monochromatic copy of a planar graph $G$ if and only if $G$ is outerplanar. Here we show that the "only if" part does not hold while the "if" part does.
Decomposition of Triply Rooted Trees
Authors: Chen William Y.C. , Peng Janet F.F. , Yang Harold R.L.
Published: January 2020

In this paper, we give a decomposition of triply rooted trees into three doubly rooted trees. This leads to a combinatorial interpretation of an identity conjectured by Lacasse in the study of the PAC-Bayesian machine learning theory, and proved by Younsi by using the Hurwitz identity on multivariate Abel polynomials. We also give a bijection between the set of functions from [n+1] to [n] and the set of triply rooted trees on [n], which leads to the refined enumeration of functions from [n+1] to [n] with respect to the number of elements in the orbit of n+1 and the number of periodic points.
Products and Sums Divisible by Central Binomial Coefficients
Authors: Sun Zhi-Wei
Published: January 2020

In this paper we study products and sums divisible by central binomial coefficients. We show that $$2(2n+1)\binom{2n}n\ \bigg|\ \binom{6n}{3n}\binom{3n}n\ \ \mbox{for all}\ n=1,2,3,\ldots.$$ Also, for any nonnegative integers $k$ and $n$ we have $$\binom {2k}k\ \bigg|\ \binom{4n+2k+2}{2n+k+1}\binom{2n+k+1}{2k}\binom{2n-k+1}n$$ and $$\binom{2k}k\ \bigg|\ (2n+1)\binom{2n}nC_{n+k}\binom{n+k+1}{2k},$$ where $C_m$ denotes the Catalan number $\frac1{m+1}\binom{2m}m=\binom{2m}m-\binom{2m}{m+1}$. On the basis of these results, we obtain certain sums divisible by central binomial coefficients.
MacMahon's Theorem for a Set of Permutations with Given Descent Indices and Right-Maximal Records
Authors: Dzhumadil'daev A.
Published: January 2020

We show that the major codes and inversion codes are equidistributed over a set of permutations with prescribed descent indices and right-maximal records.
Satisfying States of Triangulations of a Convex $n$-gon
Authors: Jiménez A. , Kiwi M. , Loebl M.
Published: January 2020

In this work we count the number of satisfying states of triangulations of a convex $n$-gon using the transfer matrix method. We show an exponential (in $n$) lower bound. We also give the exact formula for the number of satisfying states of a strip of triangles.
A Basis for the Diagonally Signed-Symmetric Polynomials
Authors: Gómez José Manuel
Published: January 2020

Let $n\ge 1$ be an integer and let $B_{n}$ denote the hyperoctahedral group of rank $n$. The group $B_{n}$ acts on the polynomial ring $Q[x_{1},\dots,x_{n},y_{1},\dots,y_{n}]$ by signed permutations simultaneously on both of the sets of variables $x_{1},\dots,x_{n}$ and $y_{1},\dots,y_{n}.$ The invariant ring $M^{B_{n}}:=Q[x_{1},\dots,x_{n},y_{1},\dots,y_{n}]^{B_{n}}$  is the ring of diagonally signed-symmetric polynomials. In this article, we provide an explicit free basis of $M^{B_{n}}$ as a module over the ring of symmetric polynomials on both of the sets of variables $x_{1}^{2},\dots, x^{2}_{n}$ and  $y_{1}^{2},\dots, y^{2}_{n}$ using signed descent monomials.
Labeling the Regions of the Type $C_n$ Shi Arrangement
Authors: Mészáros Karola
Published: January 2020

The number of regions of the type $C_n$ Shi arrangement in $\mathbb{R}^n$ is $(2n+1)^n$. Strikingly, no bijective proof of this fact has been given thus far. The aim of this paper is to provide such a bijection and use it to prove more refined results. We construct a bijection between the regions of the type $C_n$ Shi arrangement in $\mathbb{R}^n$ and sequences $a_1a_2 \ldots a_n$, where $a_i \in \{-n, -n+1, \ldots, -1, 0, 1, \ldots, n-1, n\}$, $ i \in [n]$. Our bijection naturally restrict to bijections between special regions of the arrangement and sequences with a given number of distinct elements.
Positivity of Three-Term Recurrence Sequences
Authors: Liu Lily L.
Published: January 2020

In this paper, we give the sufficient conditions for the positivity of recurrence sequences defined by $$a_nu_{n}=b_nu_{n-1}-c_nu_{n-2}$$ for $n\geqslant 2$, where $a_n,b_n,c_n$ are all nonnegative and linear in $n$. As applications, we show the positivity of many famous combinatorial sequences.
Rooted $K_4$-Minors
Authors: Fabila-Monroy Ruy , Wood David R.
Published: January 2020

Let $a,b,c,d$ be four vertices in a graph $G$. A $K_4$ minor rooted at $a,b,c,d$ consists of four pairwise-disjoint pairwise-adjacent connected subgraphs of $G$, respectively containing $a,b,c,d$. We characterise precisely when $G$ contains a $K_4$-minor rooted at $a,b,c,d$ by describing six classes of obstructions, which are the edge-maximal graphs containing no $K_4$-minor rooted at $a,b,c,d$. The following two special cases illustrate the full characterisation: (1) A 4-connected non-planar graph contains a $K_4$-minor rooted at $a,b,c,d$ for every choice of $a,b,c,d$. (2) A 3-connected planar graph contains a $K_4$-minor rooted at $a,b,c,d$ if and only if $a,b,c,d$ are not on a single face.
A Conjecture of Biggs Concerning the Resistance of a Distance-Regular Graph
Authors: Markowsky Greg , Koolen Jacobus
Published: January 2020

Biggs conjectured that the resistance between any two points on a distance-regular graph of valency greater than 2 is bounded by twice the resistance between adjacent points. We prove this conjecture, give the sharp constant for the inequality, and display the graphs for which the conjecture most nearly fails. Some necessary background material is included, as well as some consequences.
Winning Positions in Simplicial Nim
Authors: Horrocks David
Published: January 2020

Simplicial Nim, introduced by Ehrenborg and Steingrímsson, is a generalization of the classical two-player game of Nim. The heaps are placed on the vertices of a simplicial complex and a player's move may affect any number of piles provided that the corresponding vertices form a face of the complex. In this paper, we present properties of a complex that are equivalent to the $\cal P$-positions (winning positions for the second player) being closed under addition. We provide examples of such complexes and answer a number of open questions posed by Ehrenborg and Steingrímsson.
Zeros of the Jones Polynomial are Dense in the Complex Plane
Authors: Jin Xian'an , Zhang Fuji , Dong Fengming , Tay Eng Guan
Published: January 2020

In this paper, we present a formula for computing the Tutte polynomial of the signed graph formed from a labeled graph by edge replacements in terms of the chain polynomial of the labeled graph. Then we define a family of 'ring of tangles' links and consider zeros of their Jones polynomials. By applying the formula obtained, Beraha-Kahane-Weiss's theorem and Sokal's lemma, we prove that zeros of Jones polynomials of (pretzel) links are dense in the whole complex plane.
Cyclic Decomposition of $k$-Permutations and Eigenvalues of the Arrangement Graphs
Authors: Chen Bai Fan , Ghorbani Ebrahim , Wong Kok Bin
Published: January 2020

The $(n,k)$-arrangement graph $A(n,k)$ is a graph with all the $k$-permutations of an $n$-element set as vertices where two $k$-permutations are adjacent if they agree in exactly $k-1$ positions. We introduce a cyclic decomposition for $k$-permutations and show that this gives rise to a very fine equitable partition of $A(n,k)$. This equitable partition can be employed to compute the complete set of eigenvalues (of the adjacency matrix) of $A(n,k)$. Consequently, we determine the eigenvalues of $A(n,k)$ for small values of $k$. Finally, we show that any eigenvalue of the Johnson graph $J(n,k)$ is an eigenvalue of $A(n,k)$ and that $-k$ is the smallest eigenvalue of $A(n,k)$ with multiplicity ${\cal O}(n^k)$ for fixed $k$.
The Unreasonable Ubiquitousness of Quasi-Polynomials
Authors: Woods Kevin
Published: January 2020

A function $g$, with domain the natural numbers, is a quasi-polynomial if there exists a period $m$ and polynomials $p_0,p_1,\ldots,p_{m-1}$ such that $g(t)=p_i(t)$ for $t\equiv i\bmod m$. Quasi-polynomials classically - and "reasonably'' - appear in Ehrhart theory and in other contexts where one examines a family of polyhedra, parametrized by a variable $t$, and defined by linear inequalities of the form $a_1x_1+\cdots+a_dx_d\le b(t)$. Recent results of Chen, Li, Sam; Calegari, Walker; and Roune, Woods show a quasi-polynomial structure in several problems where the $a_i$ are also allowed to vary with $t$. We discuss these "unreasonable'' results and conjecture a general class of sets that exhibit various (eventual) quasi-polynomial behaviors: sets $S_t\subseteq\mathbb{N}^d$ that are defined with quantifiers ($\forall$, $\exists$), boolean operations (and, or, not), and statements of the form $a_1(t)x_1+\cdots+a_d(t)x_d \le b(t)$, where $a_i(t)$ and $b(t)$ are polynomials in $t$. These sets are a generalization of sets defined in the Presburger arithmetic. We prove several relationships between our conjectures, and we prove several special cases of the conjectures. The title is a play on Eugene Wigner's "The unreasonable effectiveness of mathematics in the natural sciences''.
A Combinatorial Proof for Cayley's Identity
Authors: Fulmek Markus
Published: January 2020

In a recent paper, Caracciolo, Sokal and Sportiello presented, inter alia, an algebraic/combinatorial proof for Cayley's identity. The purpose of the present paper is to give a "purely combinatorial" proof for this identity; i.e., a proof involving only combinatorial arguments. Since these arguments eventually employ a generalization of Laplace’s Theorem, we present a "purely combinatorial" proof for this theorem, too.
On the Buratti-Horak-Rosa Conjecture about Hamiltonian Paths in Complete Graphs
Authors: Pasotti Anita , Pellegrini Marco Antonio
Published: January 2020

In this paper we investigate a problem proposed by Marco Buratti, Peter Horak and Alex Rosa (denoted by BHR-problem) concerning Hamiltonian paths in the complete graph with prescribed edge-lengths. In particular we solve BHR$(\{1^a, 2^b, t^c\})$ for any even integer $t \geq 4$,  provided that $a+b \geq t-1$. Furthermore, for $t=4, 6, 8$ we present a complete solution of BHR$(\{ 1^a,2^b,t^c \})$ for any positive integer $a,b,c$.
Counting Results for Thin Butson Matrices
Authors: Banica Teo
Published: January 2020

A partial Butson matrix is a matrix $H\in M_{M\times N}(\mathbb Z_q)$ having its rows pairwise orthogonal, where $\mathbb Z_q\subset\mathbb C^\times$ is the group of $q$-th roots of unity. We investigate here the counting problem for these matrices in the "thin" regime, where $M=2,3,\ldots$ is small, and where $N\to\infty$ (subject to the condition $N\in p\mathbb N$ when $q=p^k>2$). The proofs are inspired from the de Launey-Levin and Richmond-Shallit counting results.
Turán Problems on Non-Uniform Hypergraphs
Authors: Johnston J. Travis , Lu Linyuan
Published: January 2020

A non-uniform hypergraph $H=(V,E)$ consists of a vertex set $V$ and an edge set $E\subseteq 2^V$; the edges in $E$ are not required to all have the same cardinality. The set of all cardinalities of edges in $H$ is denoted by $R(H)$, the set of edge types. For a fixed hypergraph $H$, the Turán density $\pi(H)$ is defined to be $\lim_{n\to\infty}\max_{G_n}h_n(G_n)$, where the maximum is taken over all $H$-free hypergraphs $G_n$ on $n$ vertices satisfying $R(G_n)\subseteq R(H)$, and $h_n(G_n)$, the so called Lubell function, is the expected number of edges in $G_n$ hit by a random full chain. This concept, which generalizes  the Turán density of $k$-uniform hypergraphs, is motivated by recent work on extremal poset problems.  The details connecting these two areas will be revealed in the end of this paper.Several properties of Turán density, such as supersaturation, blow-up, and suspension, are generalized from uniform hypergraphs to non-uniform hypergraphs. Other questions such as "Which hypergraphs are degenerate?" are more complicated and don't appear to generalize well. In addition, we completely determine the Turán densities of $\{1,2\}$-hypergraphs.
A Bijective Proof of Shapiro's Catalan Convolution
Authors: Hajnal Péter , Nagy Gábor V.
Published: January 2020

We present a bijective proof of Shapiro's convolution formula involving Catalan numbers of even index. As a corollary, we give a new interpretation of the Catalan numbers.
Intersections of Nonclassical Unitals and Conics in $\mathrm{PG}(2,q^2)$
Authors: Aguglia Angela , Giordano Vincenzo
Published: January 2020

In $\mathrm{PG}(2,q^2)$ with $q>2$, we determine the possible intersections of a nonclassical Buekenhout–Metz unital $\mathcal U$ and a conic passing through the point at infinity of $\mathcal U$.
Riemann-Roch for Sub-Lattices of the Root Lattice $A_n$
Authors: Amini Omid , Manjunath Madhusudan
Published: January 2020

Recently, Baker and Norine (Advances in Mathematics, 215(2): 766-788, 2007) found new analogies between graphs and Riemann surfaces by developing a Riemann-Roch machinery on a finite graph $G$. In this paper, we develop a general Riemann-Roch theory for sub-lattices of the root lattice $A_n$ analogue to the work of Baker and Norine, and establish connections between the Riemann-Roch theory and the Voronoi diagrams of lattices under certain simplicial distance functions. In this way, we obtain a geometric proof of the Riemann-Roch theorem for graphs and generalise the result to other sub-lattices of $A_n$. In particular, we provide a new geometric approach for the study of the Laplacian of graphs. We also discuss some problems on classification of lattices with a Riemann-Roch formula as well as some related algorithmic issues.
Equidistributed Statistics on Matchings and Permutations
Authors: Eriksen Niklas , Sjöstrand Jonas
Published: January 2020

We show that the bistatistic of right nestings and right crossings in matchings without left nestings is equidistributed with the number of occurrences of two certain patterns in permutations, and furthermore that this equidistribution holds when refined to positions of these statistics in matchings and permutations. For this distribution we obtain a non-commutative generating function which specializes to Zagier's generating function for the Fishburn numbers after abelianization.As a special case we obtain proofs of two conjectures of Claesson and Linusson.Finally, we conjecture that our results can be generalized to involving left crossings of matchings too.
Refining Enumeration Schemes to Count According to Permutation Statistics
Authors: Baxter Andrew M.
Published: January 2020

We develop algorithmic tools to compute quickly the distribution of permutation statistics over sets of pattern-avoiding permutations. More specfically, the algorithms are based on enumeration schemes, the permutation statistics are based on the number of occurrences of certain vincular patterns, and the permutations avoid sets of vincular patterns. We prove that whenever a finite enumeration scheme exists to count the number of pattern-avoiding permutations, then the distribution of statistics like the number of descents can also be computed based on the same scheme. Statistics such as the number of peaks, right-to-left maxima, and the major index are also investigated, as well as multi-statistics.
Monochromatic Loose-Cycle Partitions in Hypergraphs
Authors: Gyárfás András , Sárközy Gábor
Published: January 2020

In this paper we study the monochromatic loose-cycle partition problem for non-complete hypergraphs. Our main result is that in any $r$-coloring of a $k$-uniform hypergraph with independence number $\alpha$ there is a partition of the vertex set into monochromatic loose cycles such that their number depends only on $r$, $k$ and $\alpha$. We also give an extension of the following result of Pósa to hypergraphs: the vertex set of every graph $G$ can be partitioned into at most $\alpha(G)$ cycles, edges and vertices.