bluuebunny/crossref_metadata_2025 huggingface dataset:
Efficient Counting and Asymptotics of $k$-Noncrossing Tangled Diagrams
Authors: Chen William Y. C. , Qin Jing , Reidys Christian M. , Zeilberger Doron
Published: January 2020

In this paper, we enumerate $k$-noncrossing tangled diagrams. A tangled diagram is a labeled graph with vertices $1,\dots,n$, having degree at most two, which are arranged in increasing order in a horizontal line. The arcs are drawn in the upper halfplane with a particular notion of crossings and nestings. Our main result is the asymptotic formula for the number of $k$-noncrossing tangled diagrams $T_{k}(n) \, \sim \,c_k \, n^{-((k-1)^2+(k-1)/2)}\, (4(k-1)^2+2(k-1)+1)^n$ for some $c_k>0$.
A Matrix Dynamics Approach to Golomb's Recursion
Authors: Barbeau Edward J. , Chew John , Tanny Stephen
Published: January 2020

In an unpublished note Golomb proposed a family of "strange" recursions of metafibonacci type, parametrized by $k$. Previously we showed that contrary to Golomb's conjecture, for each $k$ there are many increasing solutions, and an explicit construction for multiple solutions was displayed. By reformulating our solution approach using matrix dynamics, we extend these results to a characterization of the asymptotic behaviour of all solutions of the Golomb recursion. This matrix dynamics perspective is also used to construct what we believe is the first example of a "nontrivial" nonincreasing solution, that is, one that is not eventually increasing.
An Exploration of the Permanent-Determinant Method
Authors: Kuperberg Greg
Published: January 2020

The permanent-determinant method and its generalization, the Hafnian-Pfaffian method, are methods to enumerate perfect matchings of plane graphs that were discovered by P. W. Kasteleyn. We present several new techniques and arguments related to the permanent-determinant with consequences in enumerative combinatorics. Here are some of the results that follow from these techniques: 1. If a bipartite graph on the sphere with $4n$ vertices is invariant under the antipodal map, the number of matchings is the square of the number of matchings of the quotient graph. 2. The number of matchings of the edge graph of a graph with vertices of degree at most 3 is a power of 2. 3. The three Carlitz matrices whose determinants count $a \times b \times c$ plane partitions all have the same cokernel. 4. Two symmetry classes of plane partitions can be enumerated with almost no calculation.
Multivariate Asymptotics for Products of Large Powers with Applications to Lagrange Inversion
Authors: Bender Edward A. , Richmond L. Bruce
Published: January 2020

An asymptotic estimate is given for the coefficients of products of large powers of generating functions. This theorem and another local limit theorem which is useful for conditioning are applied to various combinatorial enumeration problems that involve multivariate Lagrange inversion.
Tilings of Diamonds and Hexagons with Defects
Authors: Helfgott Harald A. , Gessel Ira M.
Published: January 2020

We show how to count tilings of Aztec diamonds and hexagons with defects using determinants. In several cases these determinants can be evaluated in closed form. In particular, we obtain solutions to open problems 1, 2, and 10 in James Propp's list of problems on enumeration of matchings.
Bicoloring Steiner Triple Systems
Authors: Colbourn Charles J. , Dinitz Jeffrey H. , Rosa Alexander
Published: January 2020

A Steiner triple system has a bicoloring with $m$ color classes if the points are partitioned into $m$ subsets and the three points in every block are contained in exactly two of the color classes. In this paper we give necessary conditions for the existence of a bicoloring with 3 color classes and give a multiplication theorem for Steiner triple systems with 3 color classes. We also examine bicolorings with more than 3 color classes.
The Strongly Regular $(40,12,2,4)$ Graphs
Authors: Spence E.
Published: January 2020

In a previous paper it was established that there are at least $27$ non-isomorphic strongly regular $(40,12,2,4)$ graphs. Using a different and more efficient method we have re-investigated these graphs and have now been able to determine them all, and so complete the classification. We have discovered that there are precisely $28$ non-isomorphic $(40,12,2,4)$ strongly regular graphs. The one that was not found in the previous investigation is characterised uniquely by the fact that every neighbour graph is triangle-free.
Large Dihedral Symmetry of the Set of Alternating Sign Matrices
Authors: Wieland Benjamin
Published: January 2020

We prove a conjecture of Cohn and Propp, which refines a conjecture of Bosley and Fidkowski about the symmetry of the set of alternating sign matrices (ASMs). We examine data arising from the representation of an ASM as a collection of paths connecting $2n$ vertices and show it to be invariant under the dihedral group $D_{2n}$ rearranging those vertices, which is much bigger than the group of symmetries of the square. We also generalize conjectures of Propp and Wilson relating some of this data for different values of $n$.
The Skeleton of a Reduced Word and a Correspondence of Edelman and Greene
Authors: Felsner Stefan
Published: January 2020

Stanley conjectured that the number of maximal chains in the weak Bruhat order of $S_n$, or equivalently the number of reduced decompositions of the reverse of the identity permutation $ w_0 = n,n-1,n-2,\ldots,2,1$, equals the number of standard Young tableaux of staircase shape $s=\{n-1,n-2,\ldots,1\}$. Originating from this conjecture remarkable connections between standard Young tableaux and reduced words have been discovered. Stanley proved his conjecture algebraically, later Edelman and Greene found a bijective proof. We provide an extension of the Edelman and Greene bijection to a larger class of words. This extension is similar to the extension of the Robinson-Schensted correspondence to two line arrays. Our proof is inspired by Viennot's planarized proof of the Robinson-Schensted correspondence. As it is the case with the classical correspondence the planarized proofs have their own beauty and simplicity.
Colouring $4$-cycle Systems with Specified Block Colour Patterns: the Case of Embedding $P_3$-designs
Authors: Quattrocchi Gaetano
Published: January 2020

A colouring of a $4$-cycle system $(V,{\cal B})$ is a surjective mapping $\phi : V \rightarrow \Gamma$. The elements of $\Gamma$ are colours. If $|\Gamma|=m$, we have an $m$-colouring of $(V,{\cal B})$. For every $B\in{\cal B}$, let $\phi(B)=\{\phi(x) | x\in B\}$. There are seven distinct colouring patterns in which a $4$-cycle can be coloured: type $a$ (${\times}{\times}{\times}{\times}$, monochromatic), type $b$ (${\times}{\times}{\times}{\square}$, two-coloured of pattern $3+1$), type $c$ (${\times}{\times}{\square}{\square}$, two-coloured of pattern $2+2$), type $d$ (${\times}{\square}{\times}{\square}$, mixed two-colored), type $e$ (${\times}{\times}{\square}{\triangle}$, three-coloured of pattern $2+1+1$), type $f$ (${\times}{\square}{\times}{\triangle}$, mixed three-coloured), type $g$ (${\times}{\square}{\triangle}{\diamondsuit}$, four-coloured or polychromatic).Let $S$ be a subset of $\{a,b,c,d,e,f,g\}$. An $m$-colouring $\phi$ of $(V,{\cal B})$ is said of type $S$ if the type of every $4$-cycle of $\cal B$ is in $S$. A type $S$ colouring is said to be proper if for every type $\alpha \in S$ there is at least one $4$-cycle of $\cal B$ having colour type $\alpha$.We say that a $P(v,3,1)$, $(W,{\cal P})$, is embedded in a $4$-cycle system of order $n$, $(V,{\cal B})$, if every path $p=[a_1,a_2,a_3] \in {\cal P}$ occurs in a $4$-cycle $(a_1,a_2,a_3,x) \in {\cal B}$ such that $x \notin W$.In this paper we consider the following spectrum problem: given an integer $m$ and a set $S \subseteq \{b,d,f\}$, determine the set of integers $n$ such that there exists a $4$-cycle system of order $n$ with a proper $m$-colouring of type $S$ (note that each colour class of a such coloration is the point set of a $P_3$-design embedded in the $4$-cycle system).We give a complete answer to the above problem except when $S=\{b\}$. In this case the problem is completely solved only for $m=2$.
Recognizing Circulant Graphs in Polynomial Time: An Application of Association Schemes
Authors: Muzychuk Mikhail E. , Tinhofer Gottfried
Published: January 2020

In this paper we present a time-polynomial recognition algorithm for certain classes of circulant graphs. Our approach uses coherent configurations and Schur rings generated by circulant graphs for elucidating their symmetry properties and eventually finding a cyclic automorphism.
Towards a Katona Type Proof for the 2-intersecting Erdős-Ko-Rado Theorem
Authors: Howard Ralph , Károlyi Gyula , Székely László A.
Published: January 2020

We study the possibility of the existence of a Katona type proof for the Erdős-Ko-Rado theorem for 2- and 3-intersecting families of sets. An Erdős-Ko-Rado type theorem for 2-intersecting integer arithmetic progressions and a model theoretic argument show that such an approach works in the 2-intersecting case, at least for some values of $n$ and $k$.
On the Domination Number of a Random Graph
Authors: Wieland Ben , Godbole Anant P.
Published: January 2020

In this paper, we show that the domination number $D$ of a random graph enjoys as sharp a concentration as does its chromatic number $\chi$. We first prove this fact for the sequence of graphs $\{G(n,p_n\},\; n\to\infty$, where a two point concentration is obtained with high probability for $p_n=p$ (fixed) or for a sequence $p_n$ that approaches zero sufficiently slowly. We then consider the infinite graph $G({\bf Z}^+, p)$, where $p$ is fixed, and prove a three point concentration for the domination number with probability one. The main results are proved using the second moment method together with the Borel Cantelli lemma.
Diagonal Sums of Boxed Plane Partitions
Authors: Wilson David B.
Published: January 2020

We give a simple proof of a nice formula for the means and covariances of the diagonal sums of a uniformly random boxed plane parition.
Aviezri Fraenkel's Work in Information Retrieval and Related Areas
Authors: Choueka Yaacov
Published: January 2020

Against all Odds: The Amazing but Most True Story of Aviezri Fraenkel and his Special Favorite: The Responsa Project or The Multi-Faceted Contributions of Aviezri Fraenkel to Information Retrieval and the Related Areas
The Subword Complexity of a Two-Parameter Family of Sequences
Authors: Fraenkel Aviezri S. , Seeman Tamar , Simpson Jamie
Published: January 2020

We determine the subword complexity of the characteristic functions of a two-parameter family $\{A_n\}_{n=1}^\infty$ of infinite sequences which are associated with the winning strategies for a family of 2-player games. A special case of the family has the form $A_n=\lfloor n\alpha\rfloor$ for all $n\in {\bf Z}_{>0}$, where $\alpha$ is a fixed positive irrational number. The characteristic functions of such sequences have been shown to have subword complexity $n+1$. We show that every sequence in the extended family has subword complexity $O(n)$.
On Counting Permutations by Pairs of Congruence Classes of Major Index
Authors: Barcelo Hélène , Maule Robert , Sundaram Sheila
Published: January 2020

For a fixed positive integer $n,$ let $S_n$ denote the symmetric group of $n!$ permutations on $n$ symbols, and let maj${(\sigma)}$ denote the major index of a permutation $\sigma.$ Fix positive integers $k < \ell\leq n,$ and nonnegative integers $i,j.$ Let $m_n(i\backslash k; j\backslash \ell)$ denote the cardinality of the set $\{\sigma\in S_n:$ maj$(\sigma)\equiv i \pmod k,$ maj$ (\sigma^{-1})\equiv j \pmod \ell\}.$ In this paper we use combinatorial methods to investigate these numbers. Results of Gordon and Roselle imply that when $k,$ $\ell$ are relatively prime, $$ m_n(i\backslash k; j\backslash \ell)= { {n!}\over{k\cdot\ell}} .$$ We give a combinatorial proof of this in the case when $\ell$ divides $n-1$ and $k$ divides $n.$
Graph Color Extensions: When Hadwiger's Conjecture and Embeddings Help
Authors: Albertson Michael O. , Hutchinson Joan P.
Published: January 2020

Suppose $G$ is $r$-colorable and $P \subseteq V(G)$ is such that the components of $G[P]$ are far apart. We show that any $(r+s)$-coloring of $G[P]$ in which each component is $s$-colored extends to an $(r+s)$-coloring of $G$. If $G$ does not contract to $K_5$ or is planar and $s \geq 2$, then any $(r+s-1)$-coloring of $P$ in which each component is $s$-colored extends to an $(r+s-1)$-coloring of $G$. This result uses the Four Color Theorem and its equivalence to Hadwiger's Conjecture for $k = 5$. For $s=2$ this provides an affirmative answer to a question of Thomassen. Similar results hold for coloring arbitrary graphs embedded in both orientable and non-orientable surfaces.
Cycle Index, Weight Enumerator, and Tutte Polynomial
Authors: Cameron Peter J.
Published: January 2020

With every linear code is associated a permutation group whose cycle index is the weight enumerator of the code (up to a trivial normalisation). There is a class of permutation groups (the IBIS groups) which includes the groups obtained from codes as above. With every IBIS group is associated a matroid; in the case of a group from a code, the matroid differs only trivially from that which arises directly from the code. In this case, the Tutte polynomial of the code specialises to the weight enumerator (by Greene's Theorem), and hence also to the cycle index. However, in another subclass of IBIS groups, the base-transitive groups, the Tutte polynomial can be derived from the cycle index but not vice versa. I propose a polynomial for IBIS groups which generalises both Tutte polynomial and cycle index.
A Proof of the Two-path Conjecture
Authors: Fleischner Herbert , Molina Robert R. , Smith Ken W. , West Douglas B.
Published: January 2020

Let $G$ be a connected graph that is the edge-disjoint union of two paths of length $n$, where $n\ge2$. Using a result of Thomason on decompositions of 4-regular graphs into pairs of Hamiltonian cycles, we prove that $G$ has a third path of length $n$.
On the Identification of Vertices Using Cycles
Authors: Rosendahl Petri
Published: January 2020

A set of cycles $C_1,\ldots ,C_k$ in a graph $G$ is said to identify the vertices $v$ if the sets $\{j:v\in C_j\}$ are all nonempty and different. In this paper, bounds for the minimum possible $k$ are given when $G$ is the graph ${\bf Z}_p^n$ endowed with the Lee or Hamming metric or $G$ is a complete bipartite graph.
The Turán Density of the Hypergraph $\{abc,ade,bde,cde\}$
Authors: Füredi Zoltán , Pikhurko Oleg , Simonovits Miklós
Published: January 2020

Let ${\bf F}_{3,2}$ denote the $3$-graph $\{abc,ade,bde,cde\}$. We show that the maximum size of an ${\bf F}_{3,2}$-free $3$-graph on $n$ vertices is $({4\over9}+o(1)) {n\choose3}$, proving a conjecture of Mubayi and Rödl [J. Comb. Th. A, 100 (2002), 135–152].
Homotopy and Homology of Finite Lattices
Authors: Blass Andreas
Published: January 2020

We exhibit an explicit homotopy equivalence between the geometric realizations of the order complex of a finite lattice and the simplicial complex of coreless sets of atoms whose join is not ${}\hat 1{}$. This result, which extends a theorem of Segev, leads to a description of the homology of a finite lattice, extending a result of Björner for geometric lattices.
The Order of Monochromatic Subgraphs with a Given Minimum Degree
Authors: Caro Yair , Yuster Raphael
Published: January 2020

Let $G$ be a graph. For a given positive integer $d$, let $f_G(d)$ denote the largest integer $t$ such that in every coloring of the edges of $G$ with two colors there is a monochromatic subgraph with minimum degree at least $d$ and order at least $t$. Let $f_G(d)=0$ in case there is a $2$-coloring of the edges of $G$ with no such monochromatic subgraph. Let $f(n,k,d)$ denote the minimum of $f_G(d)$ where $G$ ranges over all graphs with $n$ vertices and minimum degree at least $k$. In this paper we establish $f(n,k,d)$ whenever $k$ or $n-k$ are fixed, and $n$ is sufficiently large. We also consider the case where more than two colors are allowed.
Permutation Separations and Complete Bipartite Factorisations of $K_{n,n}$
Authors: Martin Nigel , Stong Richard
Published: January 2020

Suppose $p < q$ are odd and relatively prime. In this paper we complete the proof that $K_{n,n}$ has a factorisation into factors $F$ whose components are copies of $K_{p,q}$ if and only if $n$ is a multiple of $pq(p+q)$. The final step is to solve the "c-value problem" of Martin. This is accomplished by proving the following fact and some variants: For any $0\le k\le n$, there exists a sequence $(\pi_1,\pi_2, \dots,\pi_{2k+1})$ of (not necessarily distinct) permutations of $\{1,2,\dots,n\}$ such that each value in $\{-k,1-k,\dots,k\}$ occurs exactly $n$ times as $\pi_j(i)-i$ for $1\le j\le 2k-1$ and $1\le i\le n$.
Asymptotics of Permutations with Nearly Periodic Patterns of Rises and Falls
Authors: Bender Edward A. , Helton William J. , Richmond L. Bruce
Published: January 2020

Ehrenborg obtained asymptotic results for nearly alternating permutations and conjectured an asymptotic formula for the number of permutations that have a nearly periodic run pattern. We prove a generalization of this conjecture, rederive the fact that the asymptotic number of permutations with a periodic run pattern has the form $Cr^{-n}\,n!$, and show how to compute the various constants. A reformulation in terms of iid random variables leads to an eigenvalue problem for a Fredholm integral equation. Tools from functional analysis establish the necessary properties.
Path Counting and Random Matrix Theory
Authors: Dumitriu Ioana , Rassart Etienne
Published: January 2020

We establish three identities involving Dyck paths and alternating Motzkin paths, whose proofs are based on variants of the same bijection. We interpret these identities in terms of closed random walks on the halfline. We explain how these identities arise from combinatorial interpretations of certain properties of the $\beta$-Hermite and $\beta$-Laguerre ensembles of random matrix theory. We conclude by presenting two other identities obtained in the same way, for which finding combinatorial proofs is an open problem.
One Pile Nim with Arbitrary Move Function
Authors: Holshouser Arthur , Reiter Harold
Published: January 2020

This paper solves a class of combinatorial games consisting of one-pile counter pickup games for which the maximum number of counters that can be removed on each successive move equals $f(t)$, where $t$ is the previous move size and $f$ is an arbitrary function.
On the Crossing Number of $K_{m,n}$
Authors: Nahas Nagi H.
Published: January 2020

The best lower bound known on the crossing number of the complete bipartite graph is : $$cr(K_{m,n}) \geq (1/5)(m)(m-1)\lfloor n/2 \rfloor \lfloor(n-1)/2\rfloor$$ In this paper we prove that: $$cr(K_{m,n}) \geq (1/5)m(m-1)\lfloor n/2 \rfloor \lfloor (n-1)/2 \rfloor + 9.9 \times 10^{-6} m^2n^2$$ for sufficiently large $m$ and $n$.
Subsequence Sums of Zero-sum-free Sequences
Authors: Yuan Pingzhi
Published: January 2020

Let $G$ be a finite abelian group, and let $S$ be a sequence of elements in $G$. Let $f(S)$ denote the number of elements in $G$ which can be expressed as the sum over a nonempty subsequence of $S$. In this paper, we slightly improve some results of Pixton on $f(S)$ and we show that for every zero-sum-free sequences $S$ over $G$ of length $|S|=\exp(G)+2$ satisfying $f(S)\geq 4\exp(G)-1$.
The Combinatorialization of Linear Recurrences
Authors: Benjamin Arthur T. , Derks Halcyon , Quinn Jennifer J.
Published: January 2020

We provide two combinatorial proofs that linear recurrences with constant coefficients have a closed form based on the roots of its characteristic equation. The proofs employ sign-reversing involutions on weighted tilings.
Christoffel Words and the Calkin-Wilf Tree
Authors: De Luca Alessandro , Reutenauer Christophe
Published: January 2020

In this note we present some results on the Calkin-Wilf tree of irreducible fractions, giving an insight on the duality relating it to the Stern-Brocot tree, and proving noncommutative versions of known results relating labels of the Calkin-Wilf trees to hyperbinary expansions of positive integers. The main tool is the Christoffel tree introduced in a paper by Berstel and de Luca.
Balanced Line for a 3-Colored Point Set in the Plane
Authors: Bereg Sergey , Kano Mikio
Published: January 2020

In this note we prove the following theorem. For any three sets of points in the plane, each of $n\ge 2$ points such that any three points (from the union of three sets) are not collinear and the convex hull of $3n$ points is monochromatic, there exists an integer $k\in\{1,2,\dots,n-1\}$ and an open half-plane containing exactly $k$ points from each set.
On the Unitary Cayley Graph of a Finite Ring
Authors: Akhtar Reza , Boggess Megan , Jackson-Henderson Tiffany , Jiménez Isidora , Karpman Rachel , Kinzel Amanda , Pritikin Dan
Published: January 2020

We study the unitary Cayley graph associated to an arbitrary finite ring, determining precisely its diameter, girth, eigenvalues, vertex and edge connectivity, and vertex and edge chromatic number. We also compute its automorphism group, settling a question of Klotz and Sander. In addition, we classify all planar graphs and perfect graphs within this class.
Marcel-Paul Schützenberger (1920-1996)
Authors: Wilf Herbert S
Published: January 2020

A memorial page for Marcel-Paul Schützenberger, with contributions from Herbert Wilf, Dominique Foata, David Berlinski, Dominique Perrin, Richard Askey and Moshé Flato.
An Elementary Chromatic Reduction for Gain Graphs and Special Hyperplane Arrangements
Authors: Berthomé Pascal , Cordovil Raul , Forge David , Ventos Véronique , Zaslavsky Thomas
Published: January 2020

A gain graph is a graph whose edges are labelled invertibly by gains from a group. Switching is a transformation of gain graphs that generalizes conjugation in a group. A weak chromatic function of gain graphs with gains in a fixed group satisfies three laws: deletion-contraction for links with neutral gain, invariance under switching, and nullity on graphs with a neutral loop. The laws are analogous to those of the chromatic polynomial of an ordinary graph, though they are different from those usually assumed of gain graphs or matroids. The three laws lead to the weak chromatic group of gain graphs, which is the universal domain for weak chromatic functions. We find expressions, valid in that group, for a gain graph in terms of minors without neutral-gain edges, or with added complete neutral-gain subgraphs, that generalize the expression of an ordinary chromatic polynomial in terms of monomials or falling factorials. These expressions imply relations for all switching-invariant functions of gain graphs, such as chromatic polynomials, that satisfy the deletion-contraction identity for neutral links and are zero on graphs with neutral loops. Examples are the total chromatic polynomial of any gain graph, including its specialization the zero-free chromatic polynomial, and the integral and modular chromatic functions of an integral gain graph. We apply our relations to some special integral gain graphs including those that correspond to the Shi, Linial, and Catalan arrangements, thereby obtaining new evaluations of and new ways to calculate the zero-free chromatic polynomial and the integral and modular chromatic functions of these gain graphs, hence the characteristic polynomials and hypercubical lattice-point counting functions of the arrangements. The proof involves gain graphs between the Catalan and Shi graphs whose polynomials are expressed in terms of descending-path vertex partitions of the graph of $(-1)$-gain edges. We also calculate the total chromatic polynomial of any gain graph and especially of the Catalan, Shi, and Linial gain graphs.
Minimum Clique Number, Chromatic Number, and Ramsey Numbers
Authors: Liu Gaku
Published: January 2020

Let $Q(n,c)$ denote the minimum clique number over graphs with $n$ vertices and chromatic number $c$. We investigate the asymptotics of $Q(n,c)$ when $n/c$ is held constant. We show that when $n/c$ is an integer $\alpha$, $Q(n,c)$ has the same growth order as the inverse function of the Ramsey number $R(\alpha+1,t)$ (as a function of $t$). Furthermore, we show that if certain asymptotic properties of the Ramsey numbers hold, then $Q(n,c)$ is in fact asymptotically equivalent to the aforementioned inverse function. We use this fact to deduce that $Q(n,\lceil n/3 \rceil)$ is asymptotically equivalent to the inverse function of $R(4,t)$.
A Family of Two-Variable Derivative Polynomials for Tangent and Secant
Authors: Ma Shi-Mei
Published: January 2020

In this paper we introduce a family of two-variable derivative polynomials for tangent and secant. Generating functions for the coefficients of this family of polynomials are studied. In particular, we establish a connection between these generating functions and Eulerian polynomials.
Expansions of k-Schur Functions in the Affine nilCoxeter Algebra
Authors: Berg Chris , Bergeron Nantel , Pon Steven , Zabrocki Mike
Published: January 2020

We give a type free formula for the expansion of $k$-Schur functions indexed by fundamental coweights within the affine nilCoxeter algebra. Explicit combinatorics are developed in affine type $C$.
Computational Results on the Traceability of Oriented Graphs of Small Order
Authors: Burger Alewyn
Published: January 2020

A digraph $D$ is traceable if it contains a path visiting every vertex, and hypotraceable if $D$ is not traceable, but $D-v$ is traceable for every vertex $v\in V(D)$. Van Aardt, Frick, Katrenič and Nielsen [Discrete Math. 11(2011), 1273-1280] showed that there exists a hypotraceable oriented graph of order $n$ for every $n\geq 8$, except possibly for $n=9$ or $11$. These two outstanding existence questions for hypotraceable oriented graphs are settled in this paper --- the first in the negative and the second in the affirmative.  Furthermore, $D$ is $k$-traceable if $D$ has at least $k$ vertices and each of its induced subdigraphs of order $k$ is traceable.  It is known that for $k\leq 6$ every k-traceable oriented graph is traceable and that for $k=7$ and each $k\geq 9$ there exist nontraceable $k$-traceable oriented graphs of order $k+1$. The Traceability Conjecture states that for $k\geq 2$ every $k$-traceable oriented graph of order $n\geq 2k-1$ is traceable. In this paper it is shown via computer searches that all $7$-traceable and $8$-traceable oriented graphs of orders $9$, $10$ and $11$ are traceable, and that all $9$-traceable oriented graphs of order $11$ are traceable. All hypotraceable graphs of order $10$ are also found. Recently, these results are used to prove that the Traceability Conjecture also holds for $k =7, 8$ and 9, except possibly when $k=9$ and $22\leq n\leq 32$.
Minimal Covers of the Archimedean Tilings, Part 1
Authors: Pellicer Daniel , Williams Gordon
Published: January 2020

We discuss representations of non-finite polyhedra as quotients of regular polytopes. We provide some structural results about the minimal regular covers of non-finite polyhedra and about the stabilizer subgroups of their flags under the flag action of the automorphism group of the covering polytope. As motivating examples we discuss the minimal regular covers of the Archimedean tilings, and we construct explicit minimal regular covers for three of them.
New Ramsey Classes from Old
Authors: Bodirsky Manuel
Published: January 2020

Let $\mathcal{C}_1$ and $\mathcal{C}_2$ be strong amalgamation classes of finite structures, with disjoint finite signatures $\sigma$ and $\tau$. Then $\mathcal{C}_1 \wedge \mathcal{C}_2$ denotes the class of all finite ($\sigma\cup\tau$)-structures whose $\sigma$-reduct is from $\mathcal{C}_1$ and whose $\tau$-reduct is from $\mathcal{C}_2$. We prove that when $\mathcal{C}_1$ and $\mathcal{C}_2$ are Ramsey, then $\mathcal{C}_1 \wedge \mathcal{C}_2$ is also Ramsey. We also discuss variations of this statement, and give several examples of new Ramsey classes derived from those general results.
Venn Diagrams
Authors: Ruskey Frank , Weston Mark
Published: January 2020

The purpose of these pages is to collect together various facts and figures about Venn diagrams, particularly as they relate to combinatorial and geometric properties of the diagrams. Aperiodic updates are planned and comments and suggestions are most welcome.
Triangle-Free Triangulations, Hyperplane Arrangements and Shifted Tableaux
Authors: Adin Ron , Roichman Yuval
Published: January 2020

Flips of diagonals in colored triangle-free triangulations of a convex polygon are interpreted as moves between two adjacent chambers in a certain graphic hyperplane arrangement. Properties of geodesics in the associated flip graph are deduced. In particular, it is shown that: (1) every diagonal is flipped exactly once in a geodesic between a pair of distinguished antipodes; (2) the number of geodesics between these antipodes is equal to twice the number of standard Young tableaux of a truncated shifted staircase shape.
Polynomials with Real Zeros and Compatible Sequences
Authors: Liu Li
Published: January 2020

In this paper, we study polynomials with only real zeros based on the method of compatible zeros. We obtain a necessary and sufficient condition for the compatible property of two polynomials whose leading coefficients have opposite sign. As applications, we partially answer a question proposed by M. Chudnovsky and P. Seymour in the recent publication [M. Chudnovsky, P. Seymour, The roots of the independence polynomial of a clawfree graph, J. Combin. Theory Ser. B 97 (2007) 350--357]. We also establish the connection between the interlacing property and the compatible property of two polynomials and give a simple proof of some known results.
Gorenstein Polytopes Obtained from Bipartite Graphs
Authors: Tagami Makoto
Published: January 2020

Beck et al. characterized the grid graphs whose perfect matching polytopes are Gorenstein and they also showed that for some parameters, perfect matching polytopes of torus graphs are Gorenstein. In this paper, we complement their result, that is, we characterize the torus graphs whose perfect matching polytopes are Gorenstein. Beck et al. also gave a method to construct an infinite family of Gorenstein polytopes. In this paper, we introduce a new class of polytopes obtained from graphs and we extend their method to construct many more Gorenstein polytopes.
Large Incidence-free Sets in Geometries
Authors: De Winter Stefaan , Schillewaert Jeroen , Verstraete Jacques
Published: January 2020

Let $\Pi = (P,L,I)$ denote a rank two geometry. In this paper, we are interested in the largest value of $|X||Y|$ where $X \subset P$ and $Y \subset L$ are sets such that $(X \times Y) \cap I = \emptyset$. Let $\alpha(\Pi)$ denote this value. We concentrate on the case where $P$ is the point set of $\mathsf{PG}(n,q)$ and $L$ is the set of $k$-spaces in $\mathsf{PG}(n,q)$. In the case that $\Pi$ is the projective plane $\mathsf{PG}(2,q)$, where $P$ is the set of points and $L$ is the set of lines of the projective plane, Haemers proved that maximal arcs in projective planes together with the set of lines not intersecting the maximal arc determine $\alpha(\mathsf{PG}(2,q))$ when $q$ is an even power of $2$. Therefore, in those cases,\[ \alpha(\Pi) = q(q - \sqrt{q} + 1)^2.\] We give both a short combinatorial proof and a linear algebraic proof of this result, and consider the analogous problem in generalized polygons. More generally, if $P$ is the point set of $\mathsf{PG}(n,q)$ and $L$ is the set of $k$-spaces in $\mathsf{PG}(n,q)$, where $1 \leq k \leq n - 1$, and $\Pi_q = (P,L,I)$, then we show as $q \rightarrow \infty$ that \[ \frac{1}{4}q^{(k + 2)(n - k)} \lesssim \alpha(\Pi) \lesssim q^{(k + 2)(n - k)}.\] The upper bounds are proved by combinatorial and spectral techniques. This leaves the open question as to the smallest possible value of $\alpha(\Pi)$ for each value of $k$. We prove that if for each $N \in \mathbb N$, $\Pi_N$ is a partial linear space with $N$ points and $N$ lines, then $\alpha(\Pi_N) \gtrsim \frac{1}{e}N^{3/2}$ as $N \rightarrow \infty$.
A Construction of Short Sequences Containing All Permutations of a Set as Subsequences
Authors: Radomirovic Sasa
Published: January 2020

A sequence over a fixed finite set is said to be complete if it contains all permutations of the set as subsequences. Determining the length of shortest complete sequences is an open problem. We improve the existing upper bound and introduce tools to manually prove the completeness of sequences.
Extremal Graph Theory for Metric Dimension and Diameter
Authors: Hernando Carmen , Mora Mercè , Pelayo Ignacio M. , Seara Carlos , Wood David R.
Published: January 2020

A set of vertices $S$ resolves a connected graph $G$ if every vertex is uniquely determined by its vector of distances to the vertices in $S$. The metric dimension of $G$ is the minimum cardinality of a resolving set of $G$. Let ${\cal G}_{\beta,D}$ be the set of graphs with metric dimension $\beta$ and diameter $D$. It is well-known that the minimum order of a graph in ${\cal G}_{\beta,D}$ is exactly $\beta+D$. The first contribution of this paper is to characterise the graphs in ${\cal G}_{\beta,D}$ with order $\beta+D$ for all values of $\beta$ and $D$. Such a characterisation was previously only known for $D\leq2$ or $\beta\leq1$. The second contribution is to determine the maximum order of a graph in ${\cal G}_{\beta,D}$ for all values of $D$ and $\beta$. Only a weak upper bound was previously known.
Application of Entropy Compression in Pattern Avoidance
Authors: Ochem Pascal , Pinlou Alexandre
Published: January 2020

In combinatorics on words, a word $w$ over an alphabet $\Sigma$ is said to avoid a pattern $p$ over an alphabet $\Delta$ if there is no factor $f$ of $w$ such that $f= h(p)$ where $h: \Delta^*\to\Sigma^*$ is a non-erasing morphism. A pattern $p$ is said to be $k$-avoidable if there exists an infinite word over a $k$-letter alphabet that avoids $p$. We give a positive answer to Problem 3.3.2 in Lothaire's book "Algebraic combinatorics on words'", that is, every pattern with $k$ variables of length at least $2^k$ (resp. $3\times2^{k-1}$) is 3-avoidable (resp. 2-avoidable). This conjecture was first stated by Cassaigne in his thesis in 1994. This improves previous bounds due to Bell and Goh, and Rampersad.
The Prime Stems of Rooted Circuits of Closure Spaces and Minimum Implicational Bases
Authors: Nakamura Masataka , Kashiwabara Kenji
Published: January 2020

A rooted circuit is firstly introduced for convex geometries (antimatroids). We generalize it for closure systems or equivalently for closure operators. A rooted circuit is a specific type of a pair $(X,e)$ of a subset $X$, called a stem, and an element $e\not\in X$, called a root. We introduce a notion called a 'prime stem', which plays the key role in this article. Every prime stem is shown to be a pseudo-closed set of an implicational system. If the sizes of stems are all the same, the stems are all pseudo-closed sets, and they give rise to a canonical minimum implicational basis. For an affine convex geometry, the prime stems determine a canonical minimum basis, and furthermore  gives rise to an optimal basis. A 'critical rooted circuit' is a special case of a rooted circuit defined for an antimatroid. As a precedence structure, 'critical rooted circuits' are necessary and sufficient to fix an antimatroid whereas critical rooted circuits are not necessarily sufficient to restore the original antimatroid as an implicational system. It is shown through an example.
Proof of Sun's Conjecture on the Divisibility of Certain Binomial Sums
Authors: Guo Victor J. W.
Published: January 2020

In this paper, we prove the following result conjectured by Z.-W. Sun:$$(2n-1){3n\choose n}|\sum_{k=0}^{n}{6k\choose 3k}{3k\choose k}{6(n-k)\choose 3(n-k)}{3(n-k)\choose n-k}$$by showing that the left-hand side divides each summand on the right-hand side.
Plancherel Averages: Remarks on a Paper by Stanley
Authors: Olshanski Grigori
Published: January 2020

Let $M_n$ stand for the Plancherel measure on ${\Bbb Y}_n$, the set of Young diagrams with $n$ boxes. A recent result of R. P. Stanley (arXiv: 0807.0383) says that for certain functions $G$ defined on the set ${\Bbb Y}$ of all Young diagrams, the average of $G$ with respect to $M_n$ depends on $n$ polynomially. We propose two other proofs of this result together with a generalization to the Jack deformation of the Plancherel measure.
Hamiltonian Paths in the Complete Graph with Edge-Lengths 1, 2, 3
Authors: Capparelli Stefano , Fra Alberto Del
Published: January 2020

Marco Buratti has conjectured that, given an odd prime $p$ and a multiset $L$ containing $p-1$ integers taken from $\{1,\ldots,(p-1)/2\}$, there exists a Hamiltonian path in the complete graph with $p$ vertices whose multiset of edge-lengths is equal to $L$ modulo $p$. We give a positive answer to this conjecture in the case of multisets of the type $\{1^a,2^b,3^c\}$ by completely classifying such multisets that are linearly or cyclically realizable.
Logarithmic Tree-Numbers for Acyclic Complexes
Authors: Kim Hyuk , Kook Woong
Published: January 2020

For a $d$-dimensional cell complex $\Gamma$ with $\tilde{H}_{i}(\Gamma)=0$ for $-1\leq i < d$, an $i$-dimensional tree is a non-empty collection $B$ of $i$-dimensional cells in $\Gamma$ such that $\tilde{H}_{i}(B\cup \Gamma^{(i-1)})=0$ and $w(B):= |\tilde{H}_{i-1}(B\cup \Gamma^{(i-1)})|$ is finite, where $\Gamma^{(i)}$ is the $i$-skeleton of $\Gamma$. The $i$-th tree-number is defined $k_{i}:=\sum_{B}w(B)^{2}$, where the sum is over all $i$-dimensional trees. In this paper, we will show that if $\Gamma$ is acyclic and $k_{i}>0$ for $-1\leq i \leq d$, then $k_{i}$ and the combinatorial Laplace operators $\Delta_{i}$  are related by  $\sum_{i=-1}^{d}\omega_{i}\,x^{i+1}=(1+x)^{2}\sum_{i=0}^{d-1}\kappa_{i} x^{i}$, where $\omega_{i}=\log \det \Delta_{i}$ and $\kappa_{i}=\log k_{i}$.  We will discuss various consequences and applications of this equation.
On Snarks that are far from being 3-Edge Colorable
Authors: Hägglund Jonas
Published: January 2020

In this note we construct two infinite snark families which have high oddness and low circumference compared to the number of vertices. Using this construction, we also give a counterexample to a suggested strengthening of Fulkerson's conjecture by showing that the Petersen graph is not the only cyclically 4-edge connected cubic graph which require at least five perfect matchings to cover its edges. Furthermore the counterexample presented has the interesting property that no 2-factor can be part of a cycle double cover.
Towards the Albertson Conjecture
Authors: Barát János , Tóth Géza
Published: January 2020

Albertson conjectured that if a graph $G$ has chromatic number $r$, then the crossing number of $G$ is at least as large as the crossing number of $K_r$, the complete graph on $r$ vertices. Albertson, Cranston, and Fox verified the conjecture for $r\le 12$. In this paper we prove it for $r\le 16$.
An Infinite Family of Graphs with the Same Ihara Zeta Function
Authors: Storm Christopher
Published: January 2020

In 2009, Cooper presented an infinite family of pairs of graphs which were conjectured to have the same Ihara zeta function. We give a proof of this result by using generating functions to establish a one-to-one correspondence between cycles of the same length without backtracking or tails in the graphs Cooper proposed. Our method is flexible enough that we are able to generalize Cooper's graphs, and we demonstrate additional families of pairs of graphs which share the same zeta function.
On the Number of Orientations of Random Graphs with No Directed Cycles of a Given Length
Authors: Allen P. , Kohayakawa Y. , Mota G. O. , Parente R. F.
Published: January 2020

Let $\vec H$ be an orientation of a graph $H$. Alon and Yuster proposed the problem of determining or estimating $D(n,m,\vec H)$, the maximum number of $\vec H$-free orientations a graph with $n$ vertices and $m$ edges may have. We consider the maximum number of $\vec H$-free orientations of typical graphs $G(n,m)$ with $n$ vertices and $m$ edges. Suppose $\vec H =C^\circlearrowright_\ell $ is the directed cycle of length $\ell\geq 3$. We show that if ${m\gg n^{1+1/(\ell-1)}}$, then this maximum is $2^{o(m)}$, while if ${m\ll n^{1+1/(\ell-1)}}$, then it is $2^{(1-o(1))m}$.
Some New Binomial Sums Related to the Catalan Triangle
Authors: Sun Yidong , Ma Fei
Published: January 2020

In this paper, we derive many new identities on the classical Catalan triangle $\mathcal{C}=(C_{n,k})_{n\geq k\geq 0}$, where $C_{n,k}=\frac{k+1}{n+1}\binom{2n-k}{n}$ are the well-known ballot numbers. The first three types are based on the determinant and the fourth is relied on the permanent of a square matrix. It not only produces many known and new identities involving Catalan numbers, but also provides a new viewpoint on combinatorial triangles.
Symmetric Bowtie Decompositions of the Complete Graph
Authors: Bonvicini Simona , Ruini Beatrice
Published: January 2020

Given a bowtie decomposition of the complete graph $K_v$ admitting an automorphism group $G$ acting transitively on the vertices of the graph, we give necessary conditions involving the rank of the group and the cycle types of the permutations in $G$. These conditions yield non–existence results for instance when $G$ is the dihedral group of order $2v$, with $v\equiv 1, 9\pmod{12}$, or a group acting transitively on the vertices of $K_9$ and $K_{21}$. Furthermore, we have non–existence for $K_{13}$ when the group $G$ is different from the cyclic group of order $13$ or for $K_{25}$ when the group $G$ is not an abelian group of order $25$. Bowtie decompositions admitting an automorphism group whose action on vertices is sharply transitive, primitive or $1$–rotational, respectively, are also studied. It is shown that if the action of $G$ on the vertices of $K_v$ is sharply transitive, then the existence of a $G$–invariant bowtie decomposition is excluded when $v\equiv 9\pmod{12}$ and is equivalent to the existence of a $G$–invariant Steiner triple system of order $v$. We are always able to exclude existence if the action of $G$ on the vertices of $K_v$ is assumed to be $1$–rotational. If, instead, $G$ is assumed to act primitively then existence can be excluded when $v$ is a prime power satisfying some additional arithmetic constraint.
Complexity Aspects of the Helly Property: Graphs and Hypergraphs
Authors: Dourado Mitre C. , Protti Fábio , Szwarcfiter Jayme L.
Published: January 2020

In 1923, Eduard Helly published his celebrated theorem, which originated the well known Helly property. A family of subsets has the Helly property when every sub-family thereof, formed by pairwise intersecting subsets, contains a common element. Many generalizations of this property exist which are relevant to some fields of mathematics, and have several applications in computer science. In this work, we survey complexity aspects of the Helly property. The main focus is on characterizations of several classes of graphs and hypergraphs related to the Helly property. We describe algorithms for solving different problems arising from the basic Helly property. We also discuss the complexity of these problems, some of them leading to NP-hardness results.
Crossings and Nestings in Set Partitions of Classical Types
Authors: Rubey Martin , Stump Christian
Published: January 2020

In this article, we investigate bijections on various classes of set partitions of classical types that preserve openers and closers. On the one hand we present bijections for types $B$ and $C$ that interchange crossings and nestings, which generalize a construction by Kasraoui and Zeng for type $A$. On the other hand we generalize a bijection to type $B$ and $C$ that interchanges the cardinality of a maximal crossing with the cardinality of a maximal nesting, as given by Chen, Deng, Du, Stanley and Yan for type $A$. For type $D$, we were only able to construct a bijection between non-crossing and non-nesting set partitions. For all classical types we show that the set of openers and the set of closers determine a non-crossing or non-nesting set partition essentially uniquely.
Combinatorial Study of Dellac Configurations and $q$-Extended Normalized Median Genocchi Numbers
Authors: Bigeni Ange
Published: January 2020

In two recent papers, Feigin proved that the Poincaré polynomials of the degenerate flag varieties have a combinatorial interpretation through Dellac configurations, and related them to the $q$-extended normalized median Genocchi numbers $\bar{c}_n(q)$ introduced by Han and Zeng, mainly by geometric considerations. In this paper, we give combinatorial proofs of these results by constructing statistic-preserving bijections between Dellac configurations and two other combinatorial models of $\bar{c}_n(q)$.
Some Identities involving the Partial Sum of $q$-Binomial Coefficients
Authors: He Bing
Published: January 2020

We give some identities involving sums of powers of the partial sum of $q$-binomial coefficients, which are $q$-analogues of Hirschhorn's identities [Discrete Math. 159 (1996), 273-278] and Zhang's identity [Discrete Math. 196 (1999), 291-298].
Fractional Coloring of Triangle-Free Planar Graphs
Authors: Dvořák Zdeněk , Sereni Jean-Sébastien , Volec Jan
Published: January 2020

We prove that every planar triangle-free graph on $n$ vertices has fractional chromatic number at most $3-3/(3n+1)$.
Graph Minors and Minimum Degree
Authors: Fijavž Gašper , Wood David R.
Published: January 2020

Let $\mathcal{D}_k$ be the class of graphs for which every minor has minimum degree at most $k$. Then $\mathcal{D}_k$ is closed under taking minors. By the Robertson-Seymour graph minor theorem, $\mathcal{D}_k$ is characterised by a finite family of minor-minimal forbidden graphs, which we denote by $\widehat{\mathcal{D}}_k$. This paper discusses $\widehat{\mathcal{D}}_k$ and related topics. We obtain four main results: We prove that every $(k+1)$-regular graph with less than $\frac{4}{3}(k+2)$ vertices is in $\widehat{\mathcal{D}}_k$, and this bound is best possible. We characterise the graphs in $\widehat{\mathcal{D}}_{k+1}$ that can be obtained from a graph in $\widehat{\mathcal{D}}_k$ by adding one new vertex. For $k\leq 3$ every graph in $\widehat{\mathcal{D}}_k$ is $(k+1)$-connected, but for large $k$, we exhibit graphs in $\widehat{\mathcal{D}}_k$ with connectivity $1$. In fact, we construct graphs in $\mathcal{D}_k$ with arbitrary block structure. We characterise the complete multipartite graphs in $\widehat{\mathcal{D}}_k$, and prove analogous characterisations with minimum degree replaced by connectivity, treewidth, or pathwidth.
The Number of Moves of the Largest Disc in Shortest Paths on Hanoi Graphs
Authors: Aumann Simon , Götz Katharina A.M. , Hinz Andreas M. , Petr Ciril
Published: January 2020

In contrast to the widespread interest in the Frame-Stewart conjecture (FSC) about the optimal number of moves in the classical Tower of Hanoi task with more than three pegs, this is the first study of the question of investigating shortest paths in Hanoi graphs $H_p^n$ in a more general setting. Here $p$ stands for the number of pegs and $n$ for the number of discs in the Tower of Hanoi interpretation of these graphs. The analysis depends crucially on the number of largest disc moves (LDMs). The patterns of these LDMs will be coded as binary strings of length $p-1$ assigned to each pair of starting and goal states individually. This will be approached both analytically and numerically. The main theoretical achievement is the existence, at least for all $n\geqslant p(p-2)$, of optimal paths where $p-1$ LDMs are necessary. Numerical results, obtained by an algorithm based on a modified breadth-first search making use of symmetries of the graphs, lead to a couple of conjectures about some cases not covered by our ascertained results. These, in turn, may shed some light on the notoriously open FSC.
A Formula for the Bivariate Map Asymptotics Constants in terms of the Univariate Map Asymptotics Constants
Authors: Gao Zhicheng
Published: January 2020

The parameters $t_g$, $p_g$, $t_g(r)$ and $p_g(r)$ appear in the asymptotics for a variety of maps on surfaces and embeddable graphs. In this paper we express $t_g(r)$ in terms of $t_g$ and $p_g(r)$ in terms of $p_g$.