bluuebunny/crossref_metadata_2025 huggingface dataset:
Structural Transition in Random Mappings
Authors: Hansen Jennie C. , Jaworski Jerzy
Published: January 2020

In this paper we characterise the  structural transition in random mappings with in-degree restrictions. Specifically, for integers $0~\!\!\leq~\!\!r\leq~\!\!n$, we  consider a random mapping model $\hat{T}_n^r$ from $[n]=\{1,2, \ldots , n\}$ into $[n]$ such that $\hat{G}_n^r$, the directed graph on $n$ labelled vertices which represents the mapping $\hat{T}_n^r$, has $r$ vertices that are constrained to have in-degree at most $1$ and the remaining vertices have in-degree at most 2. When $r=n$, $\hat{T}_n^r$ is a uniform random permutation and when $r<n$, we can view $\hat{T}_n^r$ as a 'corrupted' permutation. We investigate structural transition in $\hat{G}_n^r$ as we vary the integer parameter $r$ relative to the total number of vertices $n$. We obtain  exact and asymptotic distributions for the number of cyclic vertices, the number of components,  and the size of the typical component in $\hat{G}_n^r$, and we characterise the dependence of the limiting distributions  of these variables on the relationship between the parameters $n$ and $r$ as $n\to\infty$. We show that the number of cyclic vertices in $\hat{G}_n^r$ is $\Theta({n\over\sqrt{a}})$ and the number of components is $\Theta(\log({n\over \sqrt{a}}))$ where $a=n-r$. In contrast, provided only that $a=n-r\to\infty$, we show that the asymptotic distribution of the order statistics of the normalised component sizes of $\hat{G}_n^r$ is always the  Poisson-Dirichlet(1/2) distribution as in the case of uniform random mappings with no in-degree restrictions.
Yet Another Hat Game
Authors: Paterson Maura B. , Stinson Douglas R.
Published: January 2020

Several different "hat games" have recently received a fair amount of attention. Typically, in a hat game, one or more players are required to correctly guess their hat colour when given some information about other players' hat colours. Some versions of these games have been motivated by research in complexity theory and have ties to well-known research problems in coding theory, and some variations have led to interesting new research. In this paper, we review Ebert's Hat Game, which garnered a considerable amount of publicity in the late 90's and early 00's, and the Hats-on-a-line Game. Then we introduce a new hat game which is a "hybrid" of these two games and provide an optimal strategy for playing the new game. The optimal strategy is quite simple, but the proof involves an interesting combinatorial argument.
Schreier Graphs of an Extended Version of the Binary Adding Machine
Authors: D'Angeli Daniele
Published: January 2020

In this paper we give a complete classification of the infinite Schreier graphs of an automaton group generated by an extended version of the binary adding machine.
A New Lower Bound on the Independence Number of a Graph and Applications
Authors: Henning Michael A. , Löwenstein Christian , Southey Justin , Yeo Anders
Published: January 2020

The independence number of a graph $G$, denoted $\alpha(G)$, is the maximum cardinality of an independent set of vertices in $G$. The independence number is one of the most fundamental and well-studied graph parameters. In this paper, we strengthen a result of Fajtlowicz [Combinatorica 4 (1984), 35-38] on the independence of a graph given its maximum degree and maximum clique size. As a consequence of our result we give bounds on the independence number and transversal number of $6$-uniform hypergraphs with maximum degree three. This gives support for a conjecture due to Tuza and Vestergaard [Discussiones Math. Graph Theory 22 (2002), 199-210] that if $H$ is a $3$-regular $6$-uniform hypergraph of order $n$, then $\tau(H) \le n/4$.
The Number of Fixed Points of Wilf's Partition Involution
Authors: Wagner Stephan
Published: January 2020

Wilf partitions are partitions of an integer $n$ in which all nonzero multiplicities are distinct. On his webpage, the late Herbert Wilf posed the problem to find "any interesting theorems" about the number $f(n)$ of those partitions. Recently, Fill, Janson and Ward (and independently Kane and Rhoades) determined an asymptotic formula for $\log f(n)$. Since the original motivation for studying Wilf partitions was the fact that the operation that interchanges part sizes and multiplicities is an involution on the set of Wilf partitions, they mentioned as an open problem to determine a similar asymptotic formula for the number of fixed points of this involution, which we denote by $F(n)$. In this short note, we show that the method of Fill, Janson and Ward also applies to $F(n)$. Specifically, we obtain the asymptotic formula $\log F(n) \sim \frac12 \log f(n)$.
Random Cyclations
Authors: Pippenger Nicholas
Published: January 2020

Consider $n$ unit intervals, say $[1,2], [3,4], \ldots, [2n-1,2n]$. Identify their endpoints in pairs at random, with all $(2n-1)!! = (2n-1)(2n-3)\cdots 3\cdot 1$ pairings being equally likely. The result is a collection of cycles of various lengths, and we investigate the distribution of these lengths. The distribution is similar to that of the distribution of the lengths of cycles in a random permutation, but it also exhibits some striking differences.
A Combinatorial Formula for the Hilbert Series of Bigraded $S_n$-Modules
Authors: Yoo Meesue
Published: January 2020

We prove a combinatorial formula for the Hilbert series of the Garsia-Haiman bigraded $S_n$-modules as weighted sums over standard Young tableaux in the hook shape case. This method is based on the combinatorial formula of Haglund, Haiman and Loehr for the Macdonald polynomials and extends the result of A. Garsia and C. Procesi for the Hilbert series when $q=0$. Moreover, we construct an association of the fillings giving the monomial terms of Macdonald polynomials with the standard Young tableaux.
Formal Calculus and Umbral Calculus
Authors: Robinson Thomas J.
Published: January 2020

We use the viewpoint of the formal calculus underlying vertex operator algebra theory to study certain aspects of the classical umbral calculus. We begin by calculating the exponential generating function of the higher derivatives of a composite function, following a very short proof which naturally arose as a motivating computation related to a certain crucial "associativity" property of an important class of vertex operator algebras. Very similar (somewhat forgotten) proofs had appeared by the 19-th century, of course without any motivation related to vertex operator algebras. Using this formula, we derive certain results, including especially the calculation of certain adjoint operators, of the classical umbral calculus. This is, roughly speaking, a reversal of the logical development of some standard treatments, which have obtained formulas for the higher derivatives of a composite function, most notably Faà di Bruno's formula, as a consequence of umbral calculus. We also show a connection between the Virasoro algebra and the classical umbral shifts. This leads naturally to a more general class of operators, which we introduce, and which include the classical umbral shifts as a special case. We prove a few basic facts about these operators.
On Computing the Degree of Convexity of Polyominoes
Authors: Brocchi Stefano , Castiglione Giuseppa , Massazza Paolo
Published: January 2020

In this paper we present an algorithm which has as input a convex polyomino $P$ and computes its degree of convexity, defined as the smallest integer $k$ such that any two cells of $P$ can be joined by a monotone path inside $P$ with at most $k$ changes of direction. The algorithm uses space $O(m + n)$ to represent a polyomino $P$ with $n$ rows and $m$ columns, and has a running time $O(min(m; r k))$, where $r$ is the number of corners of $P$. Moreover, the algorithm leads naturally to a decomposition of $P$ into simpler polyominoes.
Certificates for Properties of Stability Polynomials of Graphs
Authors: Mo Ranjie , Farr Graham , Morgan Kerri
Published: January 2020

A stable (or independent) set is a set of vertices where no two of the vertices in the set are adjacent. The stability polynomial $A(G; p)$ of a graph $G$ is the probability that a set of randomly chosen vertices is stable where the probability of each vertex being chosen is $p$, with choices independent. This polynomial is analogous to the chromatic polynomial in a precise sense. This paper considers factorisation of stability polynomials, following work by Morgan and Farr on factorisation of the chromatic polynomial. The stability polynomial $A(G;p)$ is said to have an s-factorisation with s-factors $H_{1}$ and $H_{2}$ if $A(G; p) = A(H_{1};p) A(H_{2};p)$. This clearly occurs when $G$ is a disjoint union of $H_{1}$ and $H_{2}$. We find many other cases where such factorisation occurs even when $G$ is connected. We find 152 different s-factorisations of connected graphs of order at most 9, and two infinite families. We introduce certificates of s-factorisation to explain s-factorisations in terms of the structure of $G$. Short certificates for s-factorisations of connected graphs of order at most 6 are found. Upper bounds for the lengths of the certificates of s-factorisations are given. We also use certificates to explain stability equivalence, when two graphs have the same stability polynomial. We give certifications of stability equivalence for two infinite families of graphs.
A Generalization of Aztec Diamond Theorem, Part I
Authors: Lai Tri
Published: January 2020

We consider a new family of 4-vertex regions with zigzag boundary on the square lattice with diagonals drawn in. By proving that the number of tilings of the new regions is given by a power 2, we generalize both Aztec diamond theorem and Douglas' theorem. The proof extends an idea of Eu and Fu for Aztec diamonds, by using a  bijection between domino tilings and non-intersecting Schröder paths, then applying Lindström-Gessel-Viennot methodology.
Properties of the Steiner Triple Systems of Order 19
Authors: Colbourn Charles J. , Forbes Anthony D. , Grannell Mike J. , Griggs Terry S. , Kaski Petteri , Östergård Patric R. J. , Pike David A. , Pottonen Olli
Published: January 2020

Properties of the 11$\,$084$\,$874$\,$829 Steiner triple systems of order 19 are examined. In particular, there is exactly one 5-sparse, but no 6-sparse, STS(19); there is exactly one uniform STS(19); there are exactly two STS(19) with no almost parallel classes; all STS(19) have chromatic number 3; all have chromatic index 10, except for 4$\,$075 designs with chromatic index 11 and two with chromatic index 12; all are 3-resolvable; and there are exactly two 3-existentially closed STS(19).
Split $(n+t)$-Color Partitions and Gordon-McIntosh Eight Order Mock Theta Functions
Authors: Agarwal A.K. , Sood G.
Published: January 2020

In 2004, the first author gave the combinatorial interpretations of four mock theta functions of Srinivasa Ramanujan using $n$-color partitions which were introduced by himself and G.E. Andrews in 1987. In this paper we introduce a new class of partitions and call them "split $(n+t)$-color partitions". These new partitions generalize Agarwal-Andrews $(n+t)$-color partitions. We use these new combinatorial objects and give combinatorial meaning to two basic functions of Gordon-McIntosh found in 2000. They used these functions to establish the modular transformation formulas for certain eight order mock theta functions. The work done here has a great potential for future research.
Discrete Dirac Operators, Critical Embeddings and Ihara-Selberg Functions
Authors: Loebl Martin , Somberg Petr
Published: January 2020

The aim of the paper is to formulate a discrete analogue of the claim made by Alvarez-Gaume et al., realizing the partition function of the free fermion on a closed Riemann surface of genus $g$ as a linear combination of $2^{2g}$ Pfaffians of Dirac operators. Let $G=(V,E)$ be a finite graph embedded in a closed Riemann surface $X$ of genus $g$, $x_e$ the collection of independent variables associated with each edge $e$ of $G$ (collected in one vector variable $x$) and $\S$ the set of all $2^{2g}$ spin-structures on $X$.  We introduce $2^{2g}$ rotations $rot_s$ and $(2|E|\times 2|E|)$ matrices $\Delta(s)(x)$, $s\in \Sigma$, of the transitions between the oriented edges of $G$ determined by rotations $rot_s$. We show that the generating function of the even sets of edges of $G$, i.e., the Ising partition function, is a linear combination of the square roots of $2^{2g}$ Ihara-Selberg functions $I(\Delta(s)(x))$ also called Feynman functions. By a result of Foata and Zeilberger $I(\Delta(s)(x))=\det(I-\Delta'(s)(x))$, where $\Delta'(s)(x)$ is obtained from $\Delta(s)(x)$ by replacing some entries by $0$. Thus each Feynman function is computable in a polynomial time. We suggest that in the case of critical embedding of a bipartite graph $G$, the Feynman functions provide suitable discrete analogues for the Pfaffians of Dirac operators.
Generalized Spectral Characterization of Graphs Revisited
Authors: Wang Wei
Published: January 2020

A graph $G$ is said to be determined by its generalized spectrum (DGS for short) if for any graph $H$, $H$ and $G$ are cospectral with cospectral complements implies that $H$ is isomorphic to $G$. Wang and Xu (2006) gave some methods for determining whether a family of graphs are DGS. In this paper, we shall review some of the old results and present some new ones along this line of research.More precisely, let $A$ be the adjacency matrix of a graph $G$, and let $W=[e,Ae,\cdots,A^{n-1}e]$ ($e$ is the all-one vector) be its walk-matrix. Denote by $\mathcal{G}_n$ the set of all graphs on $n$ vertices with $\det(W)\neq 0$. We define a large family of graphs $$\mathcal{F}_n=\{G\in{\mathcal{G}_n}|\frac{\det(W)}{2^{\lfloorn/2\rfloor}}\mbox{is square-free and }2^{\lfloorn/2\rfloor+1}\not|\det(W)\}$$ (which may have positive density among all graphs, as suggested by some numerical experiments). The main result of the paper shows that for any graph $G\in {\mathcal{F}_n}$, if there is a rational orthogonal matrix $Q$ with $Qe=e$ such that $Q^TAQ$ is a (0,1)-matrix, then $2Q$ must be an integral matrix (and hence, $Q$ has well-known structures). As a consequence, we get the conclusion that almost all graphs in $\mathcal{F}_n$ are DGS.
Aztec Diamonds and Baxter Permutations
Authors: Canary Hal
Published: January 2020

We present a proof of a conjecture about the relationship between Baxter permutations and pairs of alternating sign matrices that are produced from domino tilings of Aztec diamonds. It is shown that a tiling corresponds to a pair of ASMs that are both permutation matrices if and only if the larger permutation matrix corresponds to a Baxter permutation. There has been a thriving literature on both pattern-avoiding permutations of various kinds [Baxter 1964, Dulucq and Guibert 1988] and tilings of regions using dominos or rhombuses as tiles [Elkies et al. 1992, Kuo 2004]. However, there have not as of yet been many links between these two areas of enumerative combinatorics. This paper gives one such link.
Rainbow Path and Color Degree in Edge Colored Graphs
Authors: Das Anita , Subrahmanya S. V. , Suresh P.
Published: January 2020

Let $G$ be an edge colored graph. A rainbow pathin $G$ is a path in which all the edges are colored with distinct colors. Let $d^c(v)$ be the color degree of a vertex $v$ in $G$, i.e. the number of distinct colors present on the edges incident on the vertex $v$. Let $t$ be the maximum length of a rainbow path in $G$. Chen and Li (2005) showed that if $d^c \geq k \,\, (k\geq 8)$, for every vertex $v$ of $G$, then $t \geq \left \lceil \frac{3 k}{5}\right \rceil + 1$. Unfortunately, the proof by Chen and Li is very long and comes to about 23 pages in the journal version. Chen and Li states in their paper that it was conjectured by Akira Saito, that $t \ge \left \lceil \frac {2k} {3} \right \rceil$. They also state in their paper that they believe $t \ge k - c$ for some constant $c$. In this note, we give a short proof to show that $t \ge \left \lceil \frac{3 k}{5}\right \rceil$, using an entirely different method. Our proof is only about 2 pages long. The draw-back is that our bound is less by 1, than the bound given by Chen and Li. We hope that the new approach adopted in this paper would eventually lead to the settlement of the conjectures by Saito and/or Chen and Li.
Logconcave Random Graphs
Authors: Frieze Alan , Vempala Santosh , Vera Juan
Published: January 2020

We propose the following model of a random graph on $n$ vertices. Let $F$ be a distribution in $R_+^{n(n-1)/2}$ with a coordinate for every pair $ij$ with $1 \le i,j \le n$. Then $G_{F,p}$ is the distribution on graphs with $n$ vertices obtained by picking a random point $X$ from $F$ and defining a graph on $n$ vertices whose edges are pairs $ij$ for which $X_{ij} \le p$. The standard Erdős-Rényi model is the special case when $F$ is uniform on the $0$-$1$ unit cube. We examine basic properties such as the connectivity threshold for quite general distributions. We also consider cases where the $X_{ij}$ are the edge weights in some random instance of a combinatorial optimization problem. By choosing suitable distributions, we can capture random graphs with interesting properties such as triangle-free random graphs and weighted random graphs with bounded total weight.
Counting Symmetric Nilpotent Matrices
Authors: Brouwer Andries E. , Gow Rod , Sheekey John
Published: January 2020

We determine the number of nilpotent matrices of order $n$ over $\mathbb{F}_q$ that are self-adjoint for a given nondegenerate symmetric bilinear form, and in particular find the number of symmetric nilpotent matrices.
The Concavity and Convexity of the Boros-Moll Sequences
Authors: Xia Ernest X.W.
Published: January 2020

In their study of a quartic integral, Boros and Moll discovered a special class of sequences, which is called the Boros–Moll sequences. In this paper, we consider the concavity and convexity of the Boros–Moll sequences $\{d_i(m)\}_{i=0}^m$. We show that for any integer $m\geq 6$, there exist two positive  integers $t_0(m)$ and $t_1(m)$  such that $d_i(m)+d_{i+2}(m)>2d_{i+1}(m)$  for $i\in [0,t_0(m)]\bigcup[t_1(m),m-2]$  and $d_i(m)+d_{i+2}(m) < 2d_{i+1}(m)$   for $i\in [t_0(m)+1,t_1(m)-1]$. When $m$ is a square, we find  $t_0(m)=\frac{m-\sqrt{m}-4}{2}$ and $t_1(m)  =\frac{m+\sqrt{m}-2}{2}$. As a corollary of our results, we  show that \[\lim_{m\rightarrow +\infty }\frac{{\rm card}\{i|d_i(m)+d_{i+2}(m)< 2d_{i+1}(m), 0\leq i \leq m-2\}}{\sqrt{m}}=1. \]
An Extremal Theorem in the Hypercube
Authors: Conlon David
Published: January 2020

The hypercube $Q_n$ is the graph whose vertex set is $\{0,1\}^n$ and where two vertices are adjacent if they differ in exactly one coordinate. For any subgraph $H$ of the cube, let $\textrm{ex}(Q_n, H)$ be the maximum number of edges in a subgraph of $Q_n$ which does not contain a copy of $H$. We find a wide class of subgraphs $H$, including all previously known examples, for which $\textrm{ex}(Q_n, H) = o(e(Q_n))$. In particular, our method gives a unified approach to proving that $\textrm{ex}(Q_n, C_{2t}) = o(e(Q_n))$ for all $t \geq 4$ other than $5$.
Orthogonality and Minimality in the Homology of Locally Finite Graphs
Authors: Diestel Reinhard , Pott Julian
Published: January 2020

Given a finite set $E$, a subset $D\subseteq E$ (viewed as a function $E\to \mathbb F_2$) is orthogonal to a given subspace $\mathcal F$ of the $\mathbb F_2$-vector space of functions $E\to \mathbb F_2$ as soon as $D$ is orthogonal to every $\subseteq$-minimal element of $\mathcal F$. This fails in general when $E$ is infinite.However, we prove the above statement for the six subspaces $\mathcal F$ of the edge space of any $3$-connected locally finite graph that are relevant to its homology: the topological, algebraic, and finite cycle and cut spaces. This solves a problem of Diestel (2010, arXiv:0912.4213).
On the Positive Moments of Ranks of Partitions
Authors: Chen William Y. C. , Ji Kathy Q. , Shen Erin Y. Y.
Published: January 2020

By introducing $k$-marked Durfee symbols, Andrews found a combinatorial interpretation of the $2k$-th symmetrized moment $\eta_{2k}(n)$ of ranks of partitions of $n$ in terms of $(k+1)$-marked Durfee symbols of $n$. In this paper, we consider the $k$-th symmetrized positive moment $\bar{\eta}_k(n)$ of ranks of partitions of $n$ which is defined as the truncated sum over positive ranks of partitions of $n$. As combinatorial interpretations of $\bar{\eta}_{2k}(n)$ and $\bar{\eta}_{2k-1}(n)$, we show that for given $k$ and $i$ with $1\leq i\leq k+1$, $\bar{\eta}_{2k-1}(n)$ equals the number of $(k+1)$-marked Durfee symbols of $n$ with the $i$-th rank being zero and $\bar{\eta}_{2k}(n)$ equals the number of $(k+1)$-marked Durfee symbols of $n$ with the $i$-th rank being positive. The interpretations of $\bar{\eta}_{2k-1}(n)$ and $\bar{\eta}_{2k}(n)$ are independent of $i$, and they imply the interpretation of $\eta_{2k}(n)$ given by Andrews since $\eta_{2k}(n)$ equals $\bar{\eta}_{2k-1}(n)$ plus twice of $\bar{\eta}_{2k}(n)$. Moreover, we obtain the generating functions for $\bar{\eta}_{2k}(n)$ and $\bar{\eta}_{2k-1}(n)$.
Bruhat Order on Fixed-Point-Free Involutions in the Symmetric Group
Authors: Watson Matthew
Published: January 2020

We provide a structural description of Bruhat order on the set $F_{2n}$ of fixed-point-free involutions in the symetric group $S_{2n}$ which yields a combinatorial proof of a combinatorial identity that is an expansion of its rank-generating function. The decomposition is accomplished via a natural poset congruence, which yields a new interpretation and proof of a combinatorial identity that counts the number of rook placements on the Ferrers boards lying under all Dyck paths of a given length $2n$. Additionally, this result extends naturally to prove new combinatorial identities that sum over other Catalan objects: 312-avoiding permutations, plane forests, and binary trees.
Evaluating the Numbers of some Skew Standard Young Tableaux of Truncated Shapes
Authors: Sun Ping
Published: January 2020

In this paper the number of standard Young tableaux (SYT) is evaluated by the methods of multiple integrals and combinatorial summations. We obtain the product formulas of the numbers of skew SYT of certain truncated shapes, including the skew SYT $((n+k)^{r+1},n^{m-1}) / (n-1)^r $ truncated by a rectangle or nearly a rectangle, the skew SYT of truncated shape $((n+1)^3,n^{m-2}) / (n-2) \backslash \; (2^2)$, and the SYT of truncated shape $((n+1)^2,n^{m-2}) \backslash \; (2)$.
Crystal Rules for $(\ell,0)$-JM Partitions
Authors: Berg Chris
Published: January 2020

Vazirani and the author [Electron. J. Combin., 15 (1) (2008), R130] gave a new interpretation of what we called $\ell$-partitions, also known as $(\ell,0)$-Carter partitions. The primary interpretation of such a partition $\lambda$ is that it corresponds to a Specht module $S^{\lambda}$ which remains irreducible over the finite Hecke algebra $H_n(q)$ when $q$ is specialized to a primitive $\ell^{th}$ root of unity. To accomplish this we relied heavily on the description of such a partition in terms of its hook lengths, a condition provided by James and Mathas. In this paper, I use a new description of the crystal $reg_\ell$ which helps extend previous results to all $(\ell,0)$-JM partitions (similar to $(\ell,0)$-Carter partitions, but not necessarily $\ell$-regular), by using an analogous condition for hook lengths which was proven by work of Lyle and Fayers.
The Topology of Competitively Constructed Graphs
Authors: Frieze Alan , Pegden Wesley
Published: January 2020

We consider a simple game, the $k$-regular graph game, in which players take turns adding edges to an initially empty graph subject to the constraint that the degrees of vertices cannot exceed $k$. We show a sharp topological threshold for this game: for the case $k=3$ a player can ensure the resulting graph is planar, while for the case $k=4$, a player can force the appearance of arbitrarily large clique minors.
New Multiple Harmonic Sum Identities
Authors: Tauraso Roberto , Prodinger Helmut
Published: January 2020

We consider a special class of binomial sums involving harmonic numbers and we prove three identities by using the elementary method of the partial fraction decomposition. Some applications to infinite series  and congruences are given.
The Ramsey Numbers of Paths Versus Wheels: a Complete Solution
Authors: Li Binlong , Ning Bo
Published: January 2020

Let $G_1$ and $G_2$ be two given graphs. The Ramsey number $R(G_1,G_2)$ is the least integer $r$ such that for every graph $G$ on $r$ vertices, either $G$ contains a $G_1$ or $\overline{G}$ contains a $G_2$. We denote by $P_n$ the path on $n$ vertices and $W_m$ the wheel on $m+1$ vertices. Chen et al. and Zhang determined the values of $R(P_n,W_m)$ when $m\leq n+1$ and when $n+2\leq m\leq 2n$, respectively. In this paper we determine all the values of $R(P_n,W_m)$ for the left case $m\geq 2n+1$. Together with Chen et al.'s and Zhang's results, we give a complete solution to the problem of determining the Ramsey numbers of paths versus wheels.
The Proof of the Removable Pair Conjecture for Fractional Dimension
Authors: Biró Csaba , Hamburger Peter , Pór Attila
Published: January 2020

In 1971 Trotter (or Bogart and Trotter) conjectured that every finite poset on at least 3 points has a pair whose removal does not decrease the dimension by more than 1. In 1992 Brightwell and Scheinerman introduced fractional dimension of posets, and they made a similar conjecture for fractional dimension. This paper settles this latter conjecture.
List Coloring Hypergraphs
Authors: Haxell Penny , Verstraete Jacques
Published: January 2020

Let $H$ be a hypergraph and let $L_v : v \in V(H)$ be sets; we refer to these sets as lists and their elements as colors. A list coloring of $H$ is an assignment of a color from $L_v$ to each $v \in V(H)$ in such a way that every edge of $H$ contains a pair of vertices of different colors. The hypergraph $H$ is $k$-list-colorable if it has a list coloring from any collection of lists of size $k$. The list chromatic number of $H$ is the minimum $k$ such that $H$ is $k$-list-colorable. In this paper we prove that every $d$-regular three-uniform linear hypergraph has list chromatic number at least $(\frac{\log d}{5\log \log d})^{1/2}$ provided $d$ is large enough. On the other hand there exist $d$-regular three-uniform linear hypergraphs with list chromatic number at most $\log_3 d+3$. This leaves the question open as to the existence of such hypergraphs with list chromatic number $o(\log d)$ as $d \rightarrow \infty$.
Vertex-Transitive Digraphs of Order $p^5$ are Hamiltonian
Authors: Zhang Jun-Yang
Published: January 2020

We prove that connected vertex-transitive digraphs of order $p^{5}$ (where $p$ is a prime) are Hamiltonian, and a connected digraph whose automorphism group contains a finite vertex-transitive subgroup $G$ of prime power order such that $G'$ is generated by two elements or elementary abelian is Hamiltonian.
On the Hyperbolicity of Random Graphs
Authors: Mitsche Dieter , Prałat Paweł
Published: January 2020

Let $G=(V,E)$ be a connected graph with the usual (graph) distance metric $d:V \times V \to \mathbb{N} \cup \{0 \}$. Introduced by Gromov, $G$ is $\delta$-hyperbolic if for every four vertices $u,v,x,y \in V$, the two largest values of the three sums $d(u,v)+d(x,y)$, $d(u,x)+d(v,y)$, $d(u,y)+d(v,x)$ differ by at most $2\delta$. In this paper, we determine precisely the value of this hyperbolicity for most binomial random graphs.
Crossings and Nestings for Arc-Coloured Permutations and Automation
Authors: Yen Lily
Published: January 2020

Symmetric joint distribution between crossings and nestings was established in several combinatorial objects. Recently, Marberg extended Chen and Guo's result on coloured matchings to coloured set partitions following a multi-dimensional generalization of the bijection and enumerative methods from Chen, Deng, Du, Stanley, and Yan. We complete the study for arc-coloured permutations by establishing symmetric joint distribution for crossings and nestings and by showing that the ordinary generating functions for $j$-noncrossing, $k$-nonnesting, $r$-coloured permutations according to size $n$ are rational functions. Finally, we automate the generation of these rational functions and analyse the first $70$ series.
On the Distribution of Depths in Increasing Trees
Authors: Kuba Markus , Wagner Stephan
Published: January 2020

By a theorem of Dobrow and Smythe, the depth of the $k$th node in very simple families of increasing trees (which includes, among others, binary increasing trees, recursive trees and plane ordered recursive trees) follows the same distribution as the number of edges of the form $j-(j+1)$ with $j < k$. In this short note, we present a simple bijective proof of this fact, which also shows that the result actually holds within a wider class of increasing trees. We also discuss some related results that follow from the bijection as well as a possible generalization. Finally, we use another similar bijection to determine the distribution of the depth of the lowest common ancestor of two nodes.
From a 1-Rotational RBIBD to a Partitioned Difference Family
Authors: Buratti Marco , Yan Jie , Wang Chengmin
Published: January 2020

Generalizing the case of $\lambda=1$ given by Buratti and Zuanni [Bull Belg. Math. Soc. (1998)], we characterize the $1$-rotational difference families generating a 1-rotational $(v,k,\lambda)$-RBIBD, that is a $(v,k,\lambda)$ resolvable balanced incomplete block design admitting an automorphism group $G$ acting sharply transitively on all but one point $\infty$ and leaving invariant a resolution $\cal R$ of it. When $G$ is transitive on $\cal R$ we prove that removing $\infty$ from a parallel class of $\cal R$ one gets a partitioned difference family, a concept recently introduced by Ding and Yin [IEEE Trans. Inform. Theory, 2005] and used to construct optimal constant composition codes. In this way, by exploiting old and new results about the existence of 1-rotational RBIBDs we are able to derive a great bulk of previously unnoticed partitioned difference families. Among our RBIBDs we construct, in particular, a $(45,5,2)$-RBIBD whose existence was previously in doubt.
On Ternary Square-Free Circular Words
Authors: Shur Arseny M.
Published: January 2020

Circular words are cyclically ordered finite sequences of letters. We give a computer-free proof of the following result by Currie: square-free circular words over the ternary alphabet exist for all lengths $l$ except for 5, 7, 9, 10, 14, and 17. Our proof reveals an interesting connection between ternary square-free circular words and closed walks in the $K_{3{,}3}$ graph. In addition, our proof implies an exponential lower bound on the number of such circular words of length $l$ and allows one to list all lengths $l$ for which such a circular word is unique up to isomorphism.
A Quantitative Approach to Perfect One-Factorizations of Complete Bipartite Graphs
Authors: Astromujoff Natacha , Matamala Martin
Published: January 2020

Given a one-factorization $\mathcal{F}$ of the complete bipartite graph $K_{n,n}$, let ${\sf pf}(\mathcal{F})$ denote the number of Hamiltonian cycles obtained by taking pairwise unions of perfect matchings in $\mathcal{F}$. Let ${\sf pf}(n)$ be the maximum of ${\sf pf}(\mathcal{F})$ over all one-factorizations $\mathcal{F}$ of $K_{n,n}$. In this work we prove that ${\sf pf}(n)\geq n^2/4$, for all $n\geq 2$.
Brown's Theorem and its Application for Enumeration of Dissections and Planar Trees
Authors: Krasko Evgeniy , Omelchenko Alexander
Published: January 2020

We present new functional equations connecting the counting series of plane and planar (in the sense of Harary and Palmer) dissections. Simple rigorous expressions for counting symmetric $r$-dissections of polygons and planar $S$-dissections are obtained.
On Keller’s Conjecture in Dimension Seven
Authors: Kisielewicz Andrzej P. , Łysakowska Magdalena
Published: January 2020

A cube tiling of $\mathbb{R}^d$ is a family of pairwise disjoint cubes $[0,1)^d+T=\{[0,1)^d+t:t\in T\}$ such that $\bigcup_{t\in T}([0,1)^d+t=\mathbb{R}^d$. Two cubes $[0,1)^d+t$, $[0,1)^d+s$ are called a twin pair if $|t_j-s_j|=1$ for some $j\in [d]=\{1,\ldots, d\}$ and $t_i=s_i$ for every $i\in [d]\setminus \{j\}$. In $1930$, Keller conjectured that in every cube tiling of $\mathbb{R}^d$ there is a twin pair. Keller's conjecture is true for dimensions $d\leq 6$ and false for all dimensions $d\geq 8$. For $d=7$ the conjecture is still open. Let $x\in \mathbb{R}^d$, $i\in [d]$, and let $L(T,x,i)$ be the set of all $i$th coordinates $t_i$ of vectors $t\in T$ such that $([0,1)^d+t)\cap ([0,1]^d+x)\neq \emptyset$ and $t_i\leq x_i$. Let $r^-(T)=\min_{x\in \mathbb{R}^d}\; \max_{1\leq i\leq d}|L(T,x,i)|$ and $r^+(T)=\max_{x\in \mathbb{R}^d}\; \max_{1\leq i\leq d}|L(T,x,i)|$. It is known that if $r^-(T)\leq 2$ or $r^+(T)\geq 6$, then Keller's conjecture is true for $d=7$. In the present paper we show that it is also true for $d=7$ if $r^+(T)=5$. Thus, if $[0,1)^d+T$ is a counterexample to Keller's conjecture in dimension seven, then $r^-(T),r^+(T)\in \{3,4\}$.
A Polynomial Invariant and Duality for Triangulations
Authors: Krushkal Vyacheslav , Renardy David
Published: January 2020

The Tutte polynomial ${T}_G(X,Y)$ of a graph $G$ is a classical invariant, important in combinatorics and statistical mechanics. An essential feature of the Tutte polynomial is the duality for planar graphs $G$, $T_G(X,Y) = {T}_{G^*}(Y,X)$ where $G^*$ denotes the dual graph. We examine this property from the perspective of manifold topology, formulating polynomial invariants for higher-dimensional simplicial complexes. Polynomial duality for triangulations of a sphere follows as a consequence of Alexander duality. The main goal of this paper is to introduce and begin the study of a more general $4$-variable polynomial for triangulations and handle decompositions of orientable manifolds. Polynomial duality in this case is a consequence of Poincaré duality on manifolds. In dimension 2 these invariants specialize to the well-known polynomial invariants of ribbon graphs defined by B. Bollobás and O. Riordan. Examples and specific evaluations of the polynomials are discussed.
Infinite Gammoids
Authors: Afzali Borujeni Seyed Hadi , Law Hiu-Fai , Müller Malte
Published: January 2020

Finite strict gammoids, introduced in the early 1970's, are matroids defined via finite digraphs equipped with some set of sinks: a set of vertices is independent if it admits a linkage to these sinks. In particular, an independent set is maximal (i.e. a base) precisely if it is linkable onto the sinks.In the infinite setting, this characterization of the maximal independent sets need not hold. We identify a type of substructure as the unique obstruction. This allows us to prove that the sets linkable onto the sinks form the bases of a (possibly non-finitary) matroid if and only if this substructure does not occur.
An Interesting New Mahonian Permutation Statistic
Authors: Wilson Mark C.
Published: January 2020

The standard algorithm for generating a random permutation gives rise to an obvious permutation statistic DIS that is readily seen to be Mahonian. We give evidence showing that it is not equal to any previously published statistic. Nor does its joint distribution with the standard Eulerian statistics des and exc appear to coincide with any known Euler-Mahonian pair. A general construction of Skandera yields an Eulerian partner eul such that (eul, DIS) is equidistributed with (des, MAJ). However eul itself appears not to be a known Eulerian statistic. Several ideas for further research on this topic are listed.
The Nonexistence of Regular Near Octagons with Parameters $(s,t,t_2,t_3)=(2,24,0,8)$
Authors: De Bruyn Bart
Published: January 2020

Let $\mathcal{S}$ be a regular near octagon with $s+1=3$ points per line, let $t+1$ denote the constant number of lines through a given point of $\mathcal{S}$ and for every two points $x$ and $y$ at distance $i \in \{ 2,3 \}$ from each other, let $t_i+1$ denote the constant number of lines through $y$ containing a (necessarily unique) point at distance $i-1$ from $x$. It is known, using algebraic combinatorial techniques, that $(t_2,t_3,t)$ must be equal to either $(0,0,1)$, $(0,0,4)$, $(0,3,4)$, $(0,8,24)$, $(1,2,3)$, $(2,6,14)$ or $(4,20,84)$. For all but one of these cases, there is a unique example of a regular near octagon known. In this paper, we deal with the existence question for the remaining case. We prove that no regular near octagons with parameters $(s,t,t_2,t_3)=(2,24,0,8)$ can exist.
Rotor-Router Aggregation on the Layered Square Lattice
Authors: Kager Wouter , Levine Lionel
Published: January 2020

In rotor-router aggregation on the square lattice $\mathbb{Z}^2$, particles starting at the origin perform deterministic analogues of random walks until reaching an unoccupied site. The limiting shape of the cluster of occupied sites is a disk. We consider a small change to the routing mechanism for sites on the $x$- and $y$-axes, resulting in a limiting shape which is a diamond instead of a disk. We show that for a certain choice of initial rotors, the occupied cluster grows as a perfect diamond.
A Hessenberg Generalization of the Garsia-Procesi Basis for the Cohomology Ring of Springer Varieties
Authors: Mbirika Aba
Published: January 2020

The Springer variety is the set of flags stabilized by a nilpotent operator. In 1976, T.A. Springer observed that this variety's cohomology ring carries a symmetric group action, and he offered a deep geometric construction of this action. Sixteen years later, Garsia and Procesi made Springer's work more transparent and accessible by presenting the cohomology ring as a graded quotient of a polynomial ring. They combinatorially describe an explicit basis for this quotient. The goal of this paper is to generalize their work. Our main result deepens their analysis of Springer varieties and extends it to a family of varieties called Hessenberg varieties, a two-parameter generalization of Springer varieties. Little is known about their cohomology. For the class of regular nilpotent Hessenberg varieties, we conjecture a quotient presentation for the cohomology ring and exhibit an explicit basis. Tantalizing new evidence supports our conjecture for a subclass of regular nilpotent varieties called Peterson varieties.
Proof of two Divisibility Properties of Binomial Coefficients Conjectured by Z.-W. Sun
Authors: Guo Victor J. W.
Published: January 2020

For all positive integers $n$, we prove the following divisibility properties:\[ (2n+3){2n\choose n}  \left|3{6n\choose 3n}{3n\choose n},\right. \quad\text{and}\quad(10n+3){3n\choose n} \left|21{15n\choose 5n}{5n\choose n}.\right. \]This confirms two recent conjectures of Z.-W. Sun. Some similar divisibility properties are given. Moreover, we show that, for all positive integers $m$ and $n$, the product $am{am+bm-1\choose am}{an+bn\choose an}$ is divisible by $m+n$. In fact, the latter result can be further generalized to the $q$-binomial coefficients and $q$-integers case, which generalizes the positivity of $q$-Catalan numbers. We also propose several related conjectures.
Symmetric Laman Theorems for the Groups $\mathcal{C}_2$ and $\mathcal{C}_s$
Authors: Schulze Bernd
Published: January 2020

For a bar and joint framework $(G,p)$ with point group $\mathcal{C}_3$ which describes 3-fold rotational symmetry in the plane, it was recently shown in (Schulze, Discret. Comp. Geom. 44:946-972) that the standard Laman conditions, together with the condition derived in (Connelly et al., Int. J. Solids Struct. 46:762-773) that no vertices are fixed by the automorphism corresponding to the 3-fold rotation (geometrically, no vertices are placed on the center of rotation), are both necessary and sufficient for $(G,p)$ to be isostatic, provided that its joints are positioned as generically as possible subject to the given symmetry constraints. In this paper we prove the analogous Laman-type conjectures for the groups $\mathcal{C}_2$ and $\mathcal{C}_s$ which are generated by a half-turn and a reflection in the plane, respectively. In addition, analogously to the results in (Schulze, Discret. Comp. Geom. 44:946-972), we also characterize symmetry generic isostatic graphs for the groups $\mathcal{C}_2$ and $\mathcal{C}_s$ in terms of inductive Henneberg-type constructions, as well as Crapo-type 3Tree2 partitions - the full sweep of methods used for the simpler problem without symmetry.
Infinite Graphs with Finite 2-Distinguishing Cost
Authors: Boutin Debra , Imrich Wilfried
Published: January 2020

A graph $G$ is said to be 2-distinguishable if there is a labeling of the vertices with two labels such that only the trivial automorphism preserves the labels. Call the minimum size of a label class in such a labeling of $G$ the cost of 2-distinguishing $G$.We show that the connected, locally finite, infinite graphs with finite 2-distinguishing cost are exactly the graphs with countable automorphism group. Further we show that in such graphs the cost is less than three times the size of a smallest determining set. We also another, sharper bound on the 2-distinguishing cost, in particular for graphs of linear growth.
Climbing elements in finite Coxeter groups
Authors: Brady Thomas , Kenny Aisling , Watt Colum
Published: January 2020

We define the notion of a climbing element in a finite real reflection group relative to a total order on the reflection set and we characterise these elements in the case where the total order arises from a bipartite Coxeter element.
Regular Factors of Regular Graphs from Eigenvalues
Authors: Lu Hongliang
Published: January 2020

Let $r$ and $m$ be two integers such that $r\geq m$. Let $H$ be a graph with order $|H|$, size $e$ and maximum degree $r$ such that $2e\geq |H|r-m$. We find a best lower bound on spectral radius of graph $H$ in terms of $m$ and $r$. Let $G$ be a connected $r$-regular graph of order $|G|$ and $ k < r$ be an integer. Using the previous results, we find some best upper bounds (in terms of $r$ and $k$) on the third largest eigenvalue that is sufficient to guarantee that $G$ has a $k$-factor when $k|G|$ is even. Moreover, we find a best bound on the second largest eigenvalue that is sufficient to guarantee that $G$ is $k$-critical when $k|G|$ is odd. Our results extend the work of Cioabă, Gregory and Haemers [J. Combin. Theory Ser. B, 1999] who obtained such results for 1-factors.
Group Homomorphisms as Error Correcting Codes
Authors: Guo Alan
Published: January 2020

We investigate the minimum distance of the error correcting code formed by the homomorphisms between two finite groups $G$ and $H$. We prove some general structural results on how the distance behaves with respect to natural group operations, such as passing to subgroups and quotients, and taking products. Our main result is a general formula for the distance when $G$ is solvable or $H$ is nilpotent, in terms of the normal subgroup structure of $G$ as well as the prime divisors of $|G|$ and $|H|$. In particular, we show that in the above case, the distance is independent of the subgroup structure of $H$. We complement this by showing that, in general, the distance depends on the subgroup structure of $H$.
Cyclic Derangements
Authors: Assaf Sami H.
Published: January 2020

A classic problem in enumerative combinatorics is to count the number of derangements, that is, permutations with no fixed point. Inspired by a recent generalization to facet derangements of the hypercube by Gordon and McMahon, we generalize this problem to enumerating derangements in the wreath product of any finite cyclic group with the symmetric group. We also give $q$- and $(q,t)$-analogs for cyclic derangements, generalizing results of Gessel, Brenti and Chow.
Arithmetic Properties of Overcubic Partition Pairs
Authors: Lin Bernard L.S.
Published: January 2020

Let $\overline{b}(n)$ denote the number of overcubic partition pairs of $n$. In this paper, we establish two Ramanujan type congruences and several infinite families of congruences modulo $3$ satisfied by $\overline{b}(n)$ . For modulus $5$, we obtain one Ramanujan type congruence and two congruence relations for $\overline{b}(n)$, from which some strange congruences are derived.
The Minimum Number of Nonnegative Edges in Hypergraphs
Authors: Huang Hao , Sudakov Benny
Published: January 2020

An $r$-uniform $n$-vertex hypergraph $H$ is said to have the Manickam-Miklós-Singhi (MMS) property if for every assignment of weights to its vertices with nonnegative sum, the number of edges whose total weight is nonnegative is at least the minimum degree of $H$. In this paper we show that for $n>10r^3$, every $r$-uniform $n$-vertex hypergraph with equal codegrees has the MMS property, and the bound on $n$ is essentially tight up to a constant factor. This result has two immediate corollaries. First it shows that every set of $n>10k^3$ real numbers with nonnegative sum has at least $\binom{n-1}{k-1}$ nonnegative $k$-sums, verifying the Manickam-Miklós-Singhi conjecture for this range. More importantly, it implies the vector space Manickam-Miklós-Singhi conjecture which states that for $n \ge 4k$ and any weighting on the $1$-dimensional subspaces of $\mathbb{F}_{q}^n$ with nonnegative sum, the number of nonnegative $k$-dimensional subspaces is at least ${n-1 \brack k-1}_q$. We also discuss two additional generalizations, which can be regarded as analogues of the Erdős-Ko-Rado theorem on $k$-intersecting families.
A Spectral Equivalent Condition of the $P$-Polynomial Property for Association Schemes
Authors: Nozaki Hiroshi , Kurihara Hirotake
Published: January 2020

We give two equivalent conditions of the $P$-polynomial property of a symmetric association scheme. The first equivalent condition shows that the $P$-polynomial property is determined only by the first and second eigenmatrices of the symmetric association scheme. The second equivalent condition is another expression of the first using predistance polynomials.
Classification of Generalized Hadamard Matrices $H(6,3)$ and Quaternary Hermitian Self-Dual Codes of Length 18
Authors: Harada Masaaki , Lam Clement , Munemasa Akihiro , Tonchev Vladimir D.
Published: January 2020

All generalized Hadamard matrices of order 18 over a group of order 3, $H(6,3)$, are enumerated in two different ways: once, as class regular symmetric $(6,3)$-nets, or symmetric transversal designs on 54 points and 54 blocks with a group of order 3 acting semi-regularly on points and blocks, and secondly, as collections of full weight vectors in quaternary Hermitian self-dual codes of length 18. The second enumeration is based on the classification of Hermitian self-dual $[18,9]$ codes over $GF(4)$, completed in this paper. It is shown that up to monomial equivalence, there are 85 generalized Hadamard matrices $H(6,3)$, and 245 inequivalent Hermitian self-dual codes of length 18 over $GF(4)$.
On the Linearity of Higher-Dimensional Blocking Sets
Authors: De Voorde G. Van
Published: January 2020

A small minimal $k$-blocking set $B$ in $\mathrm{PG}(n,q)$, $q=p^t$, $p$ prime, is a set of less than $3(q^k+1)/2$ points in $\mathrm{PG}(n,q)$, such that every $(n-k)$-dimensional space contains at least one point of $B$ and such that no proper subset of $B$ satisfies this property. The linearity conjecture states that all small minimal $k$-blocking sets in $\mathrm{PG}(n,q)$ are linear over a subfield $\mathbb{F}_{p^e}$ of $\mathbb{F}_q$. Apart from a few cases, this conjecture is still open. In this paper, we show that to prove the linearity conjecture for $k$-blocking sets in $\mathrm{PG}(n,p^t)$, with exponent $e$ and $p^e\geq 7$, it is sufficient to prove it for one value of $n$ that is at least $2k$. Furthermore, we show that the linearity of small minimal blocking sets in $\mathrm{PG}(2,q)$ implies the linearity of small minimal $k$-blocking sets in $\mathrm{PG}(n,p^t)$, with exponent $e$, with $p^e\geq t/e+11$.