bluuebunny/crossref_metadata_2025 huggingface dataset:
On the Codes Related to the Higman-Sims Graph
Authors: Knapp Wolfgang , Schaeffer Hans-Jörg
Published: January 2020

All linear codes of length $100$ over a field $F$ which admit the Higman-Sims simple group HS in its rank $3$ representation are determined. By group representation theory it is proved that they can all be understood as submodules of the permutation module $F\Omega$ where $\Omega$ denotes the vertex set of the Higman-Sims graph. This module is semisimple if $\mathrm{char} F\neq 2,5$ and absolutely indecomposable otherwise. Also if $\mathrm{char} F \in \{2, 5\}$ the submodule lattice is determined explicitly. The binary case $F = \mathbb{F}_2$ is studied in detail under coding theoretic aspects. The HS-orbits in the subcodes of dimension $\leq 23$ are computed explicitly and so also the weight enumerators are obtained. The weight enumerators of the dual codes are determined by MacWilliams transformation. Two fundamental methods are used: Let $v$ be the endomorphism determined by an adjacency matrix. Then in $H_{22} = \mathrm{Im} v $ the HS-orbits are determined as $v$-images of certain low weight vectors in $F\Omega$ which carry some special graph configurations. The second method consists in using the fact that $H_{23}/H_{21}$ is a Klein four group under addition, if $H_{23}$ denotes the code generated by $H_{22}$ and a "Higman vector" $x(m)$ of weight 50 associated to a heptad $m$ in the shortened Golay code $G_{22}$, and $H_{21}$ denotes the doubly even subcode of $H_{22}\leq H_{78} = {H_{22}}^\perp$. Using the mentioned observation about $H_{23}/H_{21}$ and the results on the HS-orbits in $H_{23}$ a model of G. Higman's geometry is constructed, which leads to a direct geometric proof that G. Higman's simple group is isomorphic to HS. Finally, it is shown that almost all maximal subgroups of the Higman-Sims group can be understood as stabilizers in HS of codewords in $H_{23}$.
The Degree-Diameter Problem for Circulant Graphs of Degree 8 and 9
Authors: Lewis Robert R.
Published: January 2020

This paper considers the degree-diameter problem for undirected circulant graphs. The focus is on extremal graphs of given (small) degree and arbitrary diameter. The published literature only covers graphs of up to degree 7. The approach used to establish the results for degree 6 and 7 has been extended successfully to degree 8 and 9. Candidate graphs are defined as functions of the diameter for both degree 8 and degree 9. They are proven to be extremal for small diameters. They establish new lower bounds for all greater diameters, and are conjectured to be extremal. The existence of the degree 8 solution is proved for all diameters. Finally some conjectures are made about solutions for circulant graphs of higher degree.
The Diameter of Almost Eulerian Digraphs
Authors: Dankelmann Peter , Volkmann L.
Published: January 2020

Soares [J. Graph Theory 1992] showed that the well known upper bound $\frac{3}{\delta+1}n+O(1)$ on the diameter of undirected graphs of order $n$ and minimum degree $\delta$ also holds for digraphs, provided they are eulerian. In this paper we investigate if similar bounds can be given for digraphs that are, in some sense, close to being eulerian. In particular we show that a directed graph of order $n$ and minimum degree $\delta$ whose arc set can be partitioned into $s$ trails, where $s\leq \delta-2$, has diameter at most $3 ( \delta+1 - \frac{s}{3})^{-1}n+O(1)$. If $s$ also divides $\delta-2$, then we show the diameter to be at most $3(\delta+1 - \frac{(\delta-2)s}{3(\delta-2)+s} )^{-1}n+O(1)$. The latter bound is sharp, apart from an additive constant. As a corollary we obtain the sharp upper bound $3( \delta+1 - \frac{\delta-2}{3\delta-5})^{-1} n + O(1)$ on the diameter of digraphs that have an eulerian trail.
Iterative Properties of Birational Rowmotion I: Generalities and Skeletal Posets
Authors: Grinberg Darij , Roby Tom
Published: January 2020

We study a birational map associated to any finite poset $P$. This map is a far-reaching generalization (found by Einstein and Propp) of classical rowmotion, which is a certain permutation of the set of order ideals of $P$. Classical rowmotion has been studied by various authors (Fon-der-Flaass, Cameron, Brouwer, Schrijver, Striker, Williams and many more) under different guises (Striker-Williams promotion and Panyushev complementation are two examples of maps equivalent to it). In contrast, birational rowmotion is new and has yet to reveal several of its mysteries. In this paper, we set up the tools for analyzing the properties of iterates of this map, and prove that it has finite order for a certain class of posets which we call "skeletal". Roughly speaking, these are graded posets constructed from one-element posets by repeated disjoint union and "grafting onto an antichain"; in particular, any forest having its leaves all on the same rank is such a poset. We also make a parallel analysis of classical rowmotion on this kind of posets, and prove that the order in this case equals the order of birational rowmotion.
An Abstraction of Whitney's Broken Circuit Theorem
Authors: Dohmen Klaus , Trinks Martin
Published: January 2020

We establish a broad generalization of Whitney's broken circuit theorem on the chromatic polynomial of a graph to sums of type $\sum_{A\subseteq S} f(A)$ where $S$ is a finite set and $f$ is a mapping from the power set of $S$ into an abelian group. We give applications to the domination polynomial and the subgraph component polynomial of a graph, the chromatic polynomial of a hypergraph, the characteristic polynomial and Crapo's beta invariant of a matroid, and the principle of inclusion-exclusion. Thus, we discover several known and new results in a concise and unified way. As further applications of our main result, we derive a new generalization of the maximums-minimums identity and of a theorem due to Blass and Sagan on the Möbius function of a finite lattice, which generalizes Rota's crosscut theorem. For the classical Möbius function, both Euler's totient function and its Dirichlet inverse, and the reciprocal of the Riemann zeta function we obtain new expansions involving the greatest common divisor resp. least common multiple. We finally establish an even broader generalization of Whitney's broken circuit theorem in the context of convex geometries (antimatroids).
The Cover Time of Deterministic Random Walks
Authors: Friedrich Tobias , Sauerwald Thomas
Published: January 2020

The rotor router model is a popular deterministic analogue of a random walk on a graph. Instead of moving to a random neighbor, the neighbors are served in a fixed order. We examine how quickly this "deterministic random walk" covers all vertices (or all edges). We present general techniques to derive upper bounds for the vertex and edge cover time and derive matching lower bounds for several important graph classes. Depending on the topology, the deterministic random walk can be asymptotically faster, slower or equally fast as the classic random walk. We also examine the short term behavior of deterministic random walks, that is, the time to visit a fixed small number of vertices or edges.
Some Combinatorial Arrays Related to the Lotka-Volterra System
Authors: Callan David , Ma Shi-Mei , Mansour Toufik
Published: January 2020

The purpose of this paper is to investigate several context-free grammars suggested by the Lotka-Volterra system. Some combinatorial arrays, involving the Stirling numbers of the second kind and Eulerian numbers, are generated by these context-free grammars. In particular, we present grammatical characterization of some statistics on cyclically ordered partitions.
On Symmetry of Uniform and Preferential Attachment Graphs
Authors: Magner Abram , Janson Svante , Kollias Giorgos , Szpankowski Wojciech
Published: January 2020

Motivated by the problem of graph structure compression under realistic source models, we study the symmetry behavior of preferential and uniform attachment graphs. These are two dynamic models of network growth in which new nodes attach to a constant number $m$ of existing ones according to some attachment scheme. We prove symmetry results for $m=1$ and $2$, and we conjecture that for $m\geq 3$, both models yield asymmetry with high probability. We provide new empirical evidence in terms of graph defect. We also prove that vertex defects in the uniform attachment model grow at most logarithmically with graph size, then use this to prove a weak asymmetry result for all values of $m$ in the uniform attachment model. Finally, we introduce a natural variation of the two models that incorporates preference of new nodes for nodes of a similar age, and we show that the change introduces symmetry for all values of $m$.
Bessenrodt-Stanley Polynomials and the Octahedron Recurrence
Authors: Di Francesco Philippe
Published: January 2020

We show that a family of multivariate polynomials recently introduced by Bessenrodt and Stanley can be expressed as solution of the octahedron recurrence with suitable initial data. This leads to generalizations and explicit expressions as path or dimer partition functions.
The Polytope of $k$-Star Densities
Authors: Rauh Johannes
Published: January 2020

This paper describes the polytope $\mathbf{P}_{k;N}$ of $i$-star counts, for all $i\le k$, for graphs on $N$ nodes.  The vertices correspond to graphs that are regular or as regular as possible.  For even $N$ the polytope is a cyclic polytope, and for odd $N$ the polytope is well-approximated by a cyclic polytope.  As $N$ goes to infinity, $\mathbf{P}_{k;N}$ approaches the convex hull of the moment curve. The affine symmetry group of $\mathbf{P}_{k;N}$ contains just a single non-trivial element, which corresponds to forming the complement of a graph.The results generalize to the polytope $\mathbf{P}_{I;N}$ of $i$-star counts, for $i$ in some set $I$ of non-consecutive integers.  In this case, $\mathbf{P}_{I;N}$ can still be approximated by a cyclic polytope, but it is usually not a cyclic polytope itself.Polytopes of subgraph statistics characterize corresponding exponential random graph models.  The elongated shape of the $k$-star polytope gives a qualitative explanation of some of the degeneracies found in such random graph models.
Rank Three Residually Connected Geometries for $M_{22}$, Revisited
Authors: Leemans Dimitri , Rowley Peter
Published: January 2020

The rank $3$ residually connected flag transitive geometries $\Gamma$ for $M_{22}$ for which the stabilizer of each object in $\Gamma$ is a maximal subgroup of $M_{22}$ are determined. As a result this deals with the infelicities in Theorem $3$ of Kilic and Rowley [On rank 2 and rank 3 residually connected geometries for $M_{22}$. Note di Matematica, 22(2003), 107–154].
An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube
Authors: Filmus Yuval
Published: January 2020

We present a simple, explicit orthogonal basis of eigenvectors for the Johnson and Kneser graphs, based on Young's orthogonal representation of the symmetric group. Our basis can also be viewed as an orthogonal basis for the vector space of all functions over a slice of the Boolean hypercube (a set of the form $\{(x_1,\ldots,x_n) \in \{0,1\}^n : \sum_i x_i = k\}$), which refines the eigenspaces of the Johnson association scheme; our basis is orthogonal with respect to any exchangeable measure. More concretely, our basis is an orthogonal basis for all multilinear polynomials $\mathbb{R}^n \to \mathbb{R}$ which are annihilated by the differential operator $\sum_i \partial/\partial x_i$. As an application of the last point of view, we show how to lift low-degree functions from a slice to the entire Boolean hypercube while maintaining properties such as expectation, variance and $L^2$-norm.As an application of our basis, we streamline Wimmer's proof of Friedgut's theorem for the slice. Friedgut's theorem, a fundamental result in the analysis of Boolean functions, states that a Boolean function on the Boolean hypercube with low total influence can be approximated by a Boolean junta (a function depending on a small number of coordinates). Wimmer generalized this result to slices of the Boolean hypercube, working mostly over the symmetric group, and utilizing properties of Young's orthogonal representation. Using our basis, we show how the entire argument can be carried out directly on the slice.
On the Real-Rootedness of the Descent Polynomials of $(n-2)$-Stack Sortable Permutations
Authors: Zhang Philip B.
Published: January 2020

Bóna conjectured that the descent polynomials on $(n-2)$-stack sortable permutations have only real zeros. Brändén proved this conjecture by establishing a more general result. In this paper, we give another proof of Brändén's result by using the theory of $s$-Eulerian polynomials recently developed by Savage and Visontai.
Strong Turán Stability
Authors: Tyomkyn Mykhaylo , Uzzell Andrew J.
Published: January 2020

We study maximal $K_{r+1}$-free graphs $G$ of almost extremal size—typically, $e(G)=\operatorname{ex}(n,K_{r+1})-O(n)$. We show that any such graph $G$ must have a large amount of `symmetry': in particular, all but very few vertices of $G$ must have twins. (Two vertices $u$ and $v$ are twins if they have the same neighbourhood.) As a corollary, we obtain a new, short proof of a theorem of Simonovits on the structure of extremal $K_{r+1}$-free graphs of chromatic number at least $k$ for all fixed $k \geq r \geq 2$.
Guessing Games on Triangle-Free Graphs
Authors: Cameron Peter J. , Dang Anh N. , Riis Søren
Published: January 2020

The guessing game introduced by Riis [Electron. J. Combin. 2007] is a variant of the "guessing your own hats" game and can be played on any simple directed graph $G$ on $n$ vertices. For each digraph $G$, it is proved that there exists a unique guessing number $\mathrm{gn}(G)$ associated to the guessing game played on $G$. When we consider the directed edge to be bidirected, in other words, the graph $G$ is undirected, Christofides and Markström [Electron. J. Combin. 2011] introduced a method to bound the value of the guessing number from below using the fractional clique cover number $\kappa_f(G)$. In particular they showed $\mathrm{gn}(G) \geq |V(G)| - \kappa_f(G)$. Moreover, it is pointed out that equality holds in this bound if the underlying undirected graph  $G$ falls into one of the following categories: perfect graphs, cycle graphs or their complement. In this paper, we show that there are triangle-free graphs that have guessing numbers which do not meet the fractional clique cover bound. In particular, the famous triangle-free Higman-Sims graph has guessing number at least $77$ and at most $78$, while the bound given by fractional clique cover is $50$.
Cataloguing PL 4-Manifolds by Gem-Complexity
Authors: Casali Maria Rita , Cristofori Paola
Published: January 2020

We describe an algorithm to subdivide automatically a given set of PL $n$-manifolds (via coloured triangulations or, equivalently, via crystallizations) into classes whose elements are PL-homeomorphic. The algorithm, implemented in the case n=4, succeeds to solve completely the PL-homeomorphism problem among the catalogue of all closed connected PL 4-manifolds up to gem-complexity 8 (i.e., which admit a coloured triangulation with at most 18 4-simplices).Possible interactions with the (not completely known) relationship among different classification in TOP and DIFF=PL categories are also investigated. As a first consequence of the above PL classification, the non-existence of exotic PL 4-manifolds up to gem-complexity 8 is proved. Further applications of the tool are described, related to possible PL-recognition of different triangulations of the K3-surface.
Thresholds and Expectation-Thresholds of Monotone Properties with Small Minterms
Authors: Friedgut Ehud , Kahn Jeff , Shikhelman Clara
Published: January 2020

Let $N$ be a finite set, let $p \in (0,1)$, and let $N_p$ denote a random binomial subset of $N$ where every element of $N$ is taken to belong to the subset independently with probability $p$ . This defines a product measure $\mu_p$ on the power set of $N$, where $\mu_p(\cal{A}) := Pr[N_p \in \cal{A}]$ for $\cal{A} \subseteq 2^N$.In this paper we study monotone (upward-closed) families $\cal{A}$ for which all minimal sets in $cal{A}$ have size at most $k$, for some positive integer $k$. We prove that for such a family $\mu_p(\cal{A}) / p^k $ is a decreasing function, which implies a uniform bound on the coarseness of the thresholds of such families. We also prove a structure theorem which enables one to identify in $\cal{A}$ either a substantial subfamily $\cal{A}_0$ for which the first moment method gives a good approximation of its measure, or a subfamily which can be well approximated by a family with all minimal sets of size strictly smaller than $k$.Finally, we relate the (fractional) expectation threshold and the probability threshold of such a family, using linear programming duality. This is related to the threshold conjecture of Kahn and Kalai.
Loose Hamilton Cycles in Random 3-Uniform Hypergraphs
Authors: Frieze Alan
Published: January 2020

In the random hypergraph $H=H_{n,p;3}$ each possible triple appears independently with probability $p$. A loose Hamilton cycle can be described as a sequence of edges $\{x_i,y_i,x_{i+1}\}$ for $i=1,2,\ldots,n/2$ where $x_1,x_2,\ldots,x_{n/2},y_1,y_2,\ldots,y_{n/2}$ are all distinct. We prove that there exists an absolute constant $K>0$ such that if $p\geq {K\log n\over n^2}$ then $$\lim_{\textstyle{n\to \infty\atop 4|n}}\Pr(H_{n,p;3}\ contains\ a\ loose\ Hamilton\ cycle)=1.$$
When Does the Set of $(a, b, c)$-Core Partitions Have a Unique Maximal Element?
Authors: Aggarwal Amol
Published: January 2020

In 2007, Olsson and Stanton gave an explicit form for the largest $(a, b)$-core partition, for any relatively prime positive integers $a$ and $b$, and asked whether there exists an $(a, b)$-core that contains all other $(a, b)$-cores as subpartitions; this question was answered in the affirmative first by Vandehey and later by Fayers independently. In this paper we investigate a generalization of this question, which was originally posed by Fayers: for what triples of positive integers $(a, b, c)$ does there exist an $(a, b, c)$-core that contains all other $(a, b, c)$-cores as subpartitions? We completely answer this question when $a$, $b$, and $c$ are pairwise relatively prime; we then use this to generalize the result of Olsson and Stanton.
Finite Edge-Transitive Oriented Graphs of Valency Four: a Global Approach
Authors: Al-bar Jehan A. , Al-kenani Ahmad N. , Muthana Najat M. , Praeger Cheryl E. , Spiga Pablo
Published: January 2020

We develop a new framework for analysing finite connected, oriented graphs of valency four, which admit a vertex-transitive and edge-transitive group of automorphisms preserving the edge orientation. We identify a sub-family of `basic' graphs such that each graph of this type is a normal cover of at least one basic graph. The basic graphs either admit an edge-transitive group of automorphisms that is quasiprimitive or biquasiprimitive on vertices, or admit an (oriented or unoriented) cycle as a normal quotient. We anticipate that each of these additional properties will facilitate effective further analysis, and we demonstrate that this is so for the quasiprimitive basic graphs. Here we obtain strong restrictions on the group involved, and construct several infinite families of such graphs which, to our knowledge, are different from any recorded in the literature so far. Several open problems are posed in the paper.
Combinatorial Proofs of Addition Formulas
Authors: Chang Xiang-Ke , Hu Xing-Biao , Lei Hongchuan , Yeh Yeong-Nan
Published: January 2020

In this paper we give a combinatorial proof of an addition formula for weighted partial Motzkin paths. The addition formula allows us to determine the $LDU$ decomposition of a Hankel matrix of the polynomial sequence defined by weighted partial Motzkin paths. As a direct consequence, we get the determinant of the Hankel matrix of certain combinatorial sequences. In addition, we obtain an addition formula for weighted large Schröder paths.
The Number of Prefixes of Minimal Factorisations of a Cycle
Authors: Lévy Thierry
Published: January 2020

We prove in two different ways that the number of distinct prefixes of length $k$ of minimal factorisations of the $n$-cycle $(1\ldots n)$ as a product of $n-1$ transpositions is $\binom{n}{k+1}n^{k-1}$. Our first proof is not bijective but makes use of a correspondence between minimal factorisations and Cayley trees. The second proof consists of establishing a bijection between the set which we want to enumerate and the set of parking functions of a certain kind, which can be counted by a standard conjugation argument.
Generalized Stirling Permutations and Forests: Higher-Order Eulerian and Ward Numbers
Authors: Barbero G. J. Fernando , Salas Jesús , Villaseñor Eduardo J.S.
Published: January 2020

We define a new family of generalized Stirling permutations that can be interpreted in terms of ordered trees and forests. We prove that the number of generalized Stirling permutations with a fixed number of ascents is given by a natural three-parameter generalization of the well-known Eulerian numbers. We give the generating function for this new class of numbers and, in the simplest cases, we find closed formulas for them and the corresponding row polynomials. By using a non-trivial involution our generalized Eulerian numbers can be mapped onto a family of generalized Ward numbers, forming a Riordan inverse pair, for which we also provide a combinatorial interpretation.
Nondeterministic Automatic Complexity of Overlap-Free and Almost Square-Free Words
Authors: Hyde Kayleigh K. , Kjos-Hanssen Bjørn
Published: January 2020

Shallit and Wang studied deterministic automatic complexity of words.  They showed that the automatic Hausdorff dimension $I(\mathbf t)$ of the infinite Thue word satisfies $1/3\le I(\mathbf t)\le 1/2$.   We improve that result by showing that $I(\mathbf t)= 1/2$.  We prove that the nondeterministic automatic complexity $A_N(x)$ of a word $x$ of length $n$ is bounded by $b(n):=\lfloor n/2\rfloor + 1$.  This enables us to define the complexity deficiency $D(x)=b(n)-A_N(x)$.  If $x$ is square-free then $D(x)=0$. If $x$ is almost square-free in the sense of Fraenkel and Simpson, or if $x$ is a overlap-free binary word such as the infinite Thue--Morse word, then $D(x)\le 1$.  On the other hand, there is no constant upper bound on $D$ for overlap-free words over a ternary alphabet, nor for cube-free words over a binary alphabet.The decision problem whether $D(x)\ge d$ for given $x$, $d$ belongs to $\mathrm{NP}\cap \mathrm{E}$.
On Relative $t$-Designs in Polynomial Association Schemes
Authors: Bannai Eiichi , Bannai Etsuko , Suda Sho , Tanaka Hajime
Published: January 2020

Motivated by the similarities between the theory of spherical $t$-designs and that of $t$-designs in $Q$-polynomial association schemes, we study two versions of relative $t$-designs, the counterparts of Euclidean $t$-designs for $P$- and/or $Q$-polynomial association schemes. We develop the theory based on the Terwilliger algebra, which is a noncommutative associative semisimple $\mathbb{C}$-algebra associated with each vertex of an association scheme. We compute explicitly the Fisher type lower bounds on the sizes of relative $t$-designs, assuming that certain irreducible modules behave nicely. The two versions of relative $t$-designs turn out to be equivalent in the case of the Hamming schemes. From this point of view, we establish a new algebraic characterization of the Hamming schemes.
Generating the Cycle Space of Planar Graphs
Authors: Hamann Matthias
Published: January 2020

We prove that the cycle space of every planar finitely separable 3-connected graph $G$ is generated by some $\operatorname{Aut}(G)$-invariant nested set of cycles. We also discuss the situation in the case of smaller connectivity.
Representing Graphs via Pattern Avoiding Words
Authors: Jones Miles , Kitaev Sergey , Pyatkin Artem , Remmel Jeffrey
Published: January 2020

The notion of a word-representable graph has been studied in a series of papers in the literature. A graph $G=(V,E)$ is word-representable if there exists a word $w$ over the alphabet $V$ such that letters $x$ and $y$ alternate in $w$ if and only if $xy$ is an edge in $E$. If $V =\{1, \ldots, n\}$, this is equivalent to saying that $G$ is word-representable if for all $x,y \in \{1, \ldots, n\}$, $xy \in E$ if and only if the subword $w_{\{x,y\}}$ of $w$ consisting of all occurrences of $x$ or $y$ in $w$ has no consecutive occurrence of the pattern 11.In this paper, we introduce the study of $u$-representable graphs for any word $u \in \{1,2\}^*$. A graph $G$ is $u$-representable if and only if there is a vertex-labeled version of $G$, $G=(\{1, \ldots, n\}, E)$, and a word $w \in \{1, \ldots, n\}^*$ such that for all $x,y \in \{1, \ldots, n\}$, $xy \in E$ if and only if $w_{\{x,y\}}$ has no consecutive occurrence of the pattern $u$. Thus, word-representable graphs are just $11$-representable graphs. We show that for any $k \geq 3$, every finite graph $G$ is $1^k$-representable. This contrasts with the fact that not all graphs are 11-representable graphs.The main focus of the paper is the study of $12$-representable graphs. In particular, we classify the $12$-representable trees. We show that any $12$-representable graph is a comparability graph and the class of $12$-representable graphs include the classes of co-interval graphs and permutation graphs. We also state a number of facts on $12$-representation of induced subgraphs of a grid graph.
Some Probabilistic Trees with Algebraic Roots
Authors: Bernardi Olivier , Morales Alejandro H.
Published: January 2020

We consider several probabilistic processes defining a random graph. One of these processes appeared recently in connection with a factorization problem in the symmetric group. For each process, we prove that the probability for the random graph to be a tree has an unexpectedly simple expression, which is independent of most parameters of the problem. This raises many open questions.
Distinct Parts Partitions without Sequences
Authors: Bringmann Kathrin , Mahlburg Karl , Nataraj Karthik
Published: January 2020

Partitions without sequences of consecutive integers as parts have been studied recently by many authors, including Andrews, Holroyd, Liggett, and Romik, among others. Their results include a description of combinatorial properties, hypergeometric representations for the generating functions, and asymptotic formulas for the enumeration functions. We complete a similar investigation of partitions into distinct parts without sequences, which are of particular interest due to their relationship with the Rogers-Ramanujan identities. Our main results include a double series representation for the generating function, an asymptotic formula for the enumeration function, and several combinatorial inequalities.
The Covering Problem in Rosenbloom-Tsfasman Spaces
Authors: Castoldi André G. , Monte Carmelo Emerson L.
Published: January 2020

We investigate the covering problem in RT spaces induced by the Rosenbloom-Tsfasman metric, extending the classical covering problem in Hamming spaces. Some connections between coverings in RT spaces and coverings in Hamming spaces are derived. Several lower and upper bounds are established for the smallest cardinality of a covering code in an RT space, generalizing results by Carnielli, Chen and Honkala, Brualdi et al., Yildiz et al. A new construction of MDS codes in RT spaces is obtained. Upper bounds are given on the basis of MDS codes, generalizing well-known results due to Stanton et al., Blokhuis and Lam, and Carnielli. Tables of lower and upper bounds are presented too.
Painting Squares in $\Delta^2-1$ Shades
Authors: Cranston Daniel W. , Rabern Landon
Published: January 2020

Cranston and Kim conjectured that if $G$ is a connected graph with maximum degree $\Delta$ and $G$ is not a Moore Graph, then $\chi_{\ell}(G^2)\le \Delta^2-1$; here $\chi_{\ell}$ is the list chromatic number. We prove their conjecture; in fact, we show that this upper bound holds even for online list chromatic number.
0-Sum and 1-Sum Flows in Regular Graphs
Authors: Akbari S. , Kano M. , Zare S.
Published: January 2020

Let $G$ be a graph. Assume that $l$ and $k$ are two natural numbers. An $l$-sum flow on a graph $G$ is an assignment of non-zero real numbers to the edges of $G$ such that for every vertex $v$ of $G$ the sum of values of all edges incidence with $v$ equals $l$. An $l$-sum $k$-flow is an $l$-sum flow with values from the set $\{\pm 1,\ldots ,\pm(k-1)\}$. Recently, it was proved that for every $r, r\geq 3$, $r\neq 5$, every $r$-regular graph admits a $0$-sum $5$-flow. In this paper we settle a conjecture by showing that every $5$-regular graph admits a $0$-sum $5$-flow. Moreover, we prove that every $r$-regular graph of even order admits a $1$-sum $5$-flow.
Arithmetic Properties of a Restricted Bipartition Function
Authors: Liu Jian , Wang Andrew Y.Z.
Published: January 2020

A bipartition of $n$ is an ordered pair of partitions $(\lambda,\mu)$ such that the sum of all of the parts equals $n$. In this article, we concentrate on the function $c_5(n)$, which counts the number of bipartitions $(\lambda,\mu)$ of $n$ subject to the restriction that each part of $\mu$ is divisible by $5$. We explicitly establish four Ramanujan type congruences and several infinite families of congruences for $c_5(n)$ modulo $3$.
Threshold and Hitting Time for High-Order Connectedness in Random Hypergraphs
Authors: Cooley Oliver , Kang Mihyun , Koch Christoph
Published: January 2020

We consider the following definition of connectedness in $k$-uniform hypergraphs: two $j$-sets (sets of $j$ vertices) are $j$-connected if there is a walk of edges between them such that two consecutive edges intersect in at least $j$ vertices. The hypergraph is $j$-connected if all $j$-sets are pairwise $j$-connected. We determine the threshold at which the random $k$-uniform hypergraph with edge probability $p$ becomes $j$-connected with high probability. We also deduce a hitting time result for the random hypergraph process – the hypergraph becomes $j$-connected at exactly the moment when the last isolated $j$-set disappears. This generalises the classical hitting time result of Bollobás and Thomason for graphs.
Infinite Gammoids: Minors and Duality
Authors: Afzali Borujeni Seyed Hadi , Law Hiu-Fai , Müller Malte
Published: January 2020

This sequel to Afzali Borujeni et. al. (2015) considers minors and duals of infinite gammoids. We prove that the class of gammoids defined by digraphs not containing a certain type of substructure, called an outgoing comb, is minor-closed. Also, we prove that finite-rank minors of gammoids are gammoids. Furthermore, the topological gammoids of Carmesin (2014) are proved to coincide, as matroids, with the finitary gammoids. A corollary is that topological gammoids are minor-closed.It is a well-known fact that the dual of any finite strict gammoid is a transversal matroid. The class of strict gammoids defined by digraphs not containing alternating combs, introduced in Afzali Borujeni et. al. (2015), contains examples which are not dual to any transversal matroid. However, we describe the duals of matroids in this class as a natural extension of  transversal matroids. While finite gammoids are closed under duality, we construct a strict gammoid that is not dual to any gammoid.
Correlation Among Runners and Some Results on the Lonely Runner Conjecture
Authors: Perarnau Guillem , Serra Oriol
Published: January 2020

The Lonely Runner Conjecture, posed independently by Wills and by Cusick, states that for any set of runners running along the unit circle with constant different speeds and starting at the same point, there is a time where all of them are far enough from the origin. We study the correlation among the time that runners spend close to the origin. By means of these correlations, we improve a result of Chen on the gap of loneliness. In the last part, we introduce dynamic interval graphs to deal with a weak version of the conjecture thus providing a new result related to the invisible runner theorem of Czerwinski and Grytczuk.
Hadwiger's Conjecture for 3-Arc Graphs
Authors: Wood David R , Xu Guangjun , Zhou Sanming
Published: January 2020

The 3-arc graph of a digraph $D$ is defined to have vertices the arcs of $D$ such that two arcs $uv, xy$ are adjacent if and only if $uv$ and $xy$ are distinct arcs of $D$ with $v\ne x$, $y\ne u$ and $u,x$ adjacent. We prove Hadwiger's conjecture for 3-arc graphs.
Locating-Total Dominating Sets in Twin-Free Graphs: a Conjecture
Authors: Foucaud Florent , Henning Michael A.
Published: January 2020

A total dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every vertex of $G$ has a neighbor in $D$. A locating-total dominating set of $G$ is a total dominating set $D$ of $G$ with the additional property that every two distinct vertices outside $D$ have distinct neighbors in $D$; that is, for distinct vertices $u$ and $v$ outside $D$, $N(u) \cap D \ne N(v) \cap D$ where $N(u)$ denotes the open neighborhood of $u$. A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods.  The location-total domination number of $G$, denoted $\gamma_t^L(G)$, is the minimum cardinality of a locating-total dominating set in $G$. It is well-known that every connected graph of order $n \ge 3$ has a total dominating set of size at most $\frac{2}{3}n$. We conjecture that if $G$ is a twin-free graph of order $n$ with no isolated vertex, then $\gamma_t^L(G) \le \frac{2}{3}n$. We prove the conjecture for graphs without $4$-cycles as a subgraph. We also prove that if $G$ is a twin-free graph of order $n$, then $\gamma_t^L(G) \le \frac{3}{4}n$.
The Toggle Group, Homomesy, and the Razumov-Stroganov Correspondence
Authors: Striker Jessica
Published: January 2020

The Razumov-Stroganov correspondence, an important link between statistical physics and combinatorics proved in 2011 by L. Cantini and A. Sportiello, relates the ground state eigenvector of the $O(1)$ dense loop model on a semi-infinite cylinder to a refined enumeration of fully-packed loops, which are in bijection with alternating sign matrices. This paper reformulates a key component of this proof in terms of posets, the toggle group, and homomesy, and proves two new homomesy results on general posets which we hope will have broader implications.
The Maximal Length of a Gap between $r$-Graph Turán Densities
Authors: Pikhurko Oleg
Published: January 2020

The Turán density $\pi(\cal F)$ of a family $\cal F$ of $r$-graphs is the limit as $n\to\infty$ of the maximum edge density of an $\cal F$-free $r$-graph on $n$ vertices. Erdős [Israel J. Math, 2 (1964):183—190] proved that no Turán density can lie in the open interval $(0,r!/r^r)$. Here we show that any other open subinterval of $[0,1]$ avoiding Turán densities has strictly smaller length. In particular, this implies a conjecture of Grosu [arXiv:1403.4653, 2014].
Walks, Partitions, and Normal Ordering
Authors: Dzhumadil'daev Askar , Yeliussizov Damir
Published: January 2020

We describe the relation between graph decompositions into walks and the normal ordering of differential operators in the $n$-th Weyl algebra. Under several specifications, we study new types of restricted set partitions, and a generalization of Stirling numbers, which we call the $\lambda$-Stirling numbers.
Enumeration of Lozenge Tilings of Halved Hexagons with a Boundary Defect
Authors: Rohatgi Ranjan
Published: January 2020

We generalize a special case of a theorem of Proctor on the enumeration of lozenge tilings of a hexagon with a maximal staircase removed using Kuo’s graphical condensation method. Additionally, we prove a formula for a weighted version of the given region. The result also extends work of Ciucu and Fischer. By applying the factorization theorem of Ciucu, we are also able to generalize a special case of MacMahon’s boxed plane partition formula.
Lower Bounds for Cover-Free Families
Authors: Abdi Ali Z. , Bshouty Nader H.
Published: January 2020

Let ${\cal F}$ be a set of blocks of a $t$-set $X$. A pair $(X,{\cal F})$ is called an $(w,r)$-cover-free family ($(w,r)-$CFF) provided that, the intersection of any $w$ blocks in ${\cal F}$ is not contained in the union of any other $r$ blocks in ${\cal F}$.We give new asymptotic lower bounds for the number of minimum points $t$ in a $(w,r)$-CFF when $w\le r=|{\cal F}|^\epsilon$ for some constant $\epsilon\ge 1/2$.
Overpartitions with Restricted Odd Differences
Authors: Bringmann Kathrin , Dousse Jehanne , Lovejoy Jeremy , Mahlburg Karl
Published: January 2020

We use $q$-difference equations to compute a two-variable $q$-hypergeometric generating function for overpartitions where the difference between two successive parts may be odd only if the larger part is overlined. This generating function specializes in one case to a modular form, and in another to a mixed mock modular form. We also establish a two-variable generating function for the same overpartitions with odd smallest part, and again find modular and mixed mock modular specializations. Applications include linear congruences arising from eigenforms for $3$-adic Hecke operators, as well as asymptotic formulas for the enumeration functions. The latter are proven using Wright's variation of the circle method.
Overview on Heisenberg—Weyl Algebra and Subsets of Riordan Subgroups
Authors: Goodenough Silvia , Lavault Christian
Published: January 2020

In a first part, we are concerned with the relationships between polynomials in the two generators of the algebra of Heisenberg—Weyl, its Bargmann—Fock representation with differential operators and the associated one-parameter group.Upon this basis, the paper is then devoted to the groups of Riordan matrices associated to the related transformations of matrices (i.e., substitutions with prefunctions). Thereby, various properties are studied arising in Riordan arrays, in the Riordan group and, more specifically, in the "striped" Riordan subgroups; further, a striped quasigroup and a semigroup are also examined. A few  applications to combinatorial structures are also briefly addressed in the Appendix.
Hyperbolicity and Chordality of a Graph
Authors: Wu Yaokun , Zhang Chengpeng
Published: January 2020

Let $G$ be a connected graph with the usual shortest-path metric $d$. The graph $G$ is $\delta$-hyperbolic provided for any vertices $x,y,u,v$ in it, the two larger of the three sums $d(u,v)+d(x,y),d(u,x)+d(v,y)$ and $d(u,y)+d(v,x)$ differ by at most $2\delta.$ The graph $G$ is $k$-chordal provided it has no induced cycle of length greater than $k.$ Brinkmann, Koolen and Moulton find that every $3$-chordal graph is $1$-hyperbolic and that graph is not $\frac{1}{2}$-hyperbolic if and only if it contains one of two special graphs as an isometric subgraph. For every $k\geq 4,$ we show that a $k$-chordal graph must be $\frac{\lfloor\frac{k}{2}\rfloor}{2}$-hyperbolic and there does exist a $k$-chordal graph which is not $\frac{\lfloor \frac{k-2}{2}\rfloor}{2}$-hyperbolic. Moreover, we prove that a $5$-chordal graph is $\frac{1}{2}$-hyperbolic if and only if it does not contain any of a list of five special graphs as an isometric subgraph.
Neighborhood Complexes of Some Exponential Graphs
Authors: Nilakantan Nandini , Shukla Samir
Published: January 2020

In this article, we consider the bipartite graphs $K_2 \times K_n$. We first show that the connectedness of the neighborhood complex $\mathcal{N}(K_{n+1}^{K_n}) =0$. Further, we show that Hom$(K_2 \times K_{n}, K_{m})$ is homotopic to $S^{m-2}$, if $2\leq m <n$.
Stirling Permutations, Cycle Structure of Permutations and Perfect Matchings
Authors: Ma Shi-Mei , Yeh Yeong-Nan
Published: January 2020

In this paper we provide constructive proofs that the following three statistics are equidistributed: the number of ascent plateaus of Stirling permutations of order $n$, a weighted variant of the number of excedances in permutations of length $n$ and the number of blocks with even maximal elements in perfect matchings of the set $\{1,2,3,\ldots,2n\}$.
Hurwitz Equivalence in Dihedral Groups
Authors: Berger Emily
Published: January 2020

In this paper we determine the orbits of the braid group $B_n$ action on $G^n$ when $G$ is a dihedral group and for any $T \in G^n$. We prove that the following invariants serve as necessary and sufficient conditions for Hurwitz equivalence. They are: the product of its entries, the subgroup generated by its entries, and the number of times each conjugacy class (in the subgroup generated by its entries) is represented in $T$.
HOMFLY Polynomials of Torus Links as Generalized Fibonacci Polynomials
Authors: Taşköprü Kemal , Altıntaş İsmet
Published: January 2020

The focus of this paper is to study the HOMFLY polynomial of $(2,n)$-torus link as a generalized Fibonacci polynomial. For this purpose, we first introduce a form of generalized Fibonacci and Lucas polynomials and provide their some fundamental properties. We define the HOMFLY polynomial of $ (2,n) $-torus link with a way similar to our generalized Fibonacci polynomials and provide its fundamental properties. We also show that the HOMFLY polynomial of $ (2,n) $-torus link can be obtained from its Alexander-Conway polynomial or the classical Fibonacci polynomial. We finally give the matrix representations and prove important identities, which are similar to the Fibonacci identities, for the our generalized Fibonacci polynomial and the HOMFLY polynomial of $ (2,n) $-torus link.
Coloring Graphs with no Even Hole of Length at Least 6: the Triangle-Free Case
Authors: Lagoutte Aurélie
Published: January 2020

In this paper, we prove that the class of graphs with no triangle and no induced cycle of even length at least 6 has bounded chromatic number. It is well-known that even-hole-free graphs are $\chi$-bounded but we allow here the existence of $C_4$. The proof relies on the concept of Parity Changing Path, an adaptation of Trinity Changing Path which was recently introduced by Bonamy, Charbit and Thomassé to prove that graphs with no induced cycle of length divisible by three have bounded chromatic number.
Stability for Intersecting Families in PGL(2,q)
Authors: Plaza Rafael
Published: January 2020

We consider the action of the $2$-dimensional projective general linear group $PGL(2,q)$ on the projective line $PG(1,q)$. A subset $S$ of $PGL(2,q)$ is said to be an intersecting family if for every $g_1,g_2 \in S$, there exists $\alpha \in PG(1,q)$ such that $\alpha^{g_1}= \alpha^{g_2}$. It was proved by Meagher and Spiga that the intersecting families of maximum size in $PGL(2,q)$ are precisely the cosets of point stabilizers. We prove that if an intersecting family $S \subset PGL(2,q)$ has size close to the maximum then it must be "close" in structure to a coset of a point stabilizer. This phenomenon is known as stability. We use this stability result proved here to show that if the size of $S$ is close enough to the maximum then $S$ must be contained in a coset of a point stabilizer.
A Note on Perfect Matchings in Uniform Hypergraphs
Authors: Treglown Andrew , Zhao Yi
Published: January 2020

We determine the exact minimum $\ell$-degree threshold for perfect matchings in $k$-uniform hypergraphs when the corresponding threshold for perfect fractional matchings is significantly less than $\frac{1}{2}\left( \begin{array}{c} n \\ k- \ell\end{array}\right)$. This extends our previous results that determine the minimum $\ell$-degree thresholds for perfect matchings in $k$-uniform hypergraphs for all $\ell\ge k/2$ and provides two new (exact) thresholds: $(k,\ell)=(5,2)$ and $(7,3)$.
Infinite Orders and Non-D-finite Property of 3-Dimensional Lattice Walks
Authors: Du Daniel K. , Hou Qing-Hu , Wang Rong-Hua
Published: January 2020

Recently, Bostan and his coauthors investigated lattice walks restricted to the non-negative octant $\mathbb{N}^3$. For the $35548$ non-trivial models with at most six steps, they found that many models associated to a group of order at least $200$ and conjectured these groups were in fact infinite groups. In this paper, we first confirm these conjectures and then consider the non-$D$-finite property of the generating function for some of these models.
The Maximal Order of Hyper-($b$-ary)-expansions
Authors: Coons Michael , Spiegelhofer Lukas
Published: January 2020

Using methods developed by Coons and Tyler, we give a new proof of a recent result of Defant, by determining the maximal order of the number of hyper-($b$-ary)-expansions of a nonnegative integer $n$ for general integral bases $b\geqslant 2$.
Permanent Index of Matrices Associated with Graphs
Authors: Wong Tsai-Lien , Zhu Xuding
Published: January 2020

A total weighting of a graph $G$ is a mapping $f$ which assigns to each element $z \in V(G) \cup E(G)$ a real number $f(z)$ as its weight. The vertex sum of $v$ with respect to $f$ is $\phi_f(v)=\sum_{e \in E(v)}f(e)+f(v)$. A total weighting is proper if $\phi_f(u) \ne \phi_f(v)$ for any edge $uv$ of $G$. A $(k,k')$-list assignment is a mapping $L$ which assigns to each vertex $v$ a set $L(v)$ of $k$ permissible weights, and assigns to each edge $e$ a set $L(e)$ of $k'$ permissible weights. We say $G$ is $(k,k')$-choosable if for any $(k,k')$-list assignment $L$, there is a proper total weighting $f$ of $G$ with $f(z) \in L(z)$ for each $z \in V(G) \cup E(G)$. It was conjectured in [T. Wong and X. Zhu, Total weight choosability of graphs, J. Graph Theory 66 (2011), 198-212] that every graph is $(2,2)$-choosable and every graph with no isolated edge is $(1,3)$-choosable. A promising tool in the study of these conjectures is Combinatorial Nullstellensatz.  This approach leads to conjectures on the permanent indices of matrices  $A_G$ and $B_G$ associated to a graph $G$. In this  paper, we establish a method that reduces the study of permanent of  matrices associated to a graph $G$ to the study of permanent of  matrices associated to induced subgraphs of $G$. Using this  reduction method, we show that if $G$ is a subcubic graph, or a $2$-tree, or a Halin graph, or a grid, then $A_G$ has permanent index $1$. As a consequence, these graphs are $(2,2)$-choosable.
Maximal Partial Spreads of Polar Spaces
Authors: Cossidente Antonio , Pavese Francesco
Published: January 2020

Some constructions of maximal partial spreads of finite classical polar spaces are provided. In particular we show that, for $n \ge 1$, $\mathcal{H}(4n-1,q^2)$ has a maximal partial spread of size $q^{2n}+1$, $\mathcal{H}(4n+1,q^2)$ has a maximal partial spread of size $q^{2n+1}+1$ and, for $n \ge 2$, $\mathcal{Q}^+(4n-1,q)$, $\mathcal{Q}(4n-2,q)$, $\mathcal{W}(4n-1,q)$, $q$ even, $\mathcal{W}(4n-3,q)$, $q$ even, have a maximal partial spread of size $q^n+1$.
Generalised Polygons Admitting a Point-Primitive Almost Simple Group of Suzuki or Ree Type
Authors: Morgan Luke , Popiel Tomasz
Published: January 2020

Let $G$ be a collineation group of a thick finite generalised hexagon or generalised octagon $\Gamma$. If $G$ acts primitively on the points of $\Gamma$, then a recent result of Bamberg et al. shows that $G$ must be an almost simple group of Lie type. We show that, furthermore, the minimal normal subgroup $S$ of $G$ cannot be a Suzuki group or a Ree group of type $^2\mathrm{G}_2$, and that if $S$ is a Ree group of type $^2\mathrm{F}_4$, then $\Gamma$ is (up to point-line duality) the classical Ree-Tits generalised octagon.