bluuebunny/crossref_metadata_2025 huggingface dataset:
Trees and Meta-Fibonacci Sequences
Authors: Isgur Abraham , Reiss David , Tanny Stephen
Published: January 2020

For $k>1$ and nonnegative integer parameters $a_p, b_p$, $p = 1..k$, we analyze the solutions to the meta-Fibonacci recursion $C(n)=\sum_{p=1}^k C(n-a_p-C(n-b_p))$, where the parameters $a_p, b_p$, $p = 1..k$ satisfy a specific constraint. For $k=2$ we present compelling empirical evidence that solutions exist only for two particular families of parameters; special cases of the recursions so defined include the Conolly recursion and all of its generalizations that have been studied to date. We show that the solutions for all the recursions defined by the parameters in these families have a natural combinatorial interpretation: they count the number of labels on the leaves of certain infinite labeled trees, where the number of labels on each node in the tree is determined by the parameters. This combinatorial interpretation enables us to determine various new results concerning these sequences, including a closed form, and to derive asymptotic estimates. Our results broadly generalize and unify recent findings of this type relating to certain of these meta-Fibonacci sequences. At the same time they indicate the potential for developing an analogous counting interpretation for many other meta-Fibonacci recursions specified by the same recursion for $C(n)$ with other sets of parameters.
Monotone Paths in Random Hypergraphs
Authors: Novaga Matteo , Majer Pietro
Published: January 2020

We determine the probability thresholds for the existence of monotone paths, of finite and infinite length, in random oriented graphs with vertex set $\mathbb N^{[k]}$, the set of all increasing $k$-tuples in $\mathbb N$. These graphs appear as line graph of uniform hypergraphs with vertex set $\mathbb N$.
Strings of Length 3 in Grand-Dyck Paths and the Chung-Feller Property
Authors: Sapounakis Aristidis , Tsikouras Panagiotis , Tasoulas Ioannis , Manes Kostas
Published: January 2020

This paper deals with the enumeration of Grand-Dyck paths according to the statistic "number of occurrences of $\tau$" for every string $\tau$ of length $3$, taking into account the number of flaws of the path. Consequently, some new refinements of the Chung-Feller theorem are obtained.
Demazure Crystals, Kirillov-Reshetikhin Crystals, and the Energy Function
Authors: Schilling Anne , Tingley Peter
Published: January 2020

It has previously been shown that, at least for non-exceptional Kac-Moody Lie algebras, there is a close connection between Demazure crystals and tensor products of Kirillov-Reshetikhin crystals. In particular, certain Demazure crystals are isomorphic as classical crystals to tensor products of  Kirillov-Reshetikhin crystals via a canonically chosen isomorphism. Here we show that this isomorphism intertwines the natural affine grading on Demazure crystals with a combinatorially defined energy function. As a consequence, we obtain a formula of the Demazure character in terms of the energy function, which has applications to Macdonald polynomials and $q$-deformed Whittaker functions.
Some Relational Structures with Polynomial Growth and their Associated Algebras I: Quasi-Polynomiality of the Profile
Authors: Pouzet Maurice , Thiéry Nicolas Marc
Published: January 2020

The profile of a relational structure $R$ is the function $\phi_R$ which counts for every integer $n$ the number $\phi_R(n)$, possibly infinite, of substructures of $R$ induced on the $n$-element subsets, isomorphic substructures being identified.  If $\phi_R$ takes only finite values, this is the Hilbert function of a graded algebra associated with $R$, the age algebra $KA(R)$, introduced by P. J. Cameron. In this paper we give a closer look at this association, particularly when the relational structure $R$ admits a finite monomorphic decomposition. This setting still encompass well-studied graded commutative algebras like invariant rings of finite permutation groups, or the rings of quasi-symmetric polynomials. We prove that $\phi_R$ is eventually a quasi-polynomial, this supporting the conjecture that, under mild assumptions on $R$, $\phi_R$ is eventually a quasi-polynomial when it is bounded by some polynomial.
A New Determinant Expression of the Zeta Function for a Hypergraph
Authors: Sato Iwao
Published: January 2020

Recently, Storm defined the Ihara-Selberg zeta function of a hypergraph, and gave two determinant expressions of it by the Perron-Frobenius operator of a digraph and a deformation of the usual Laplacian of a graph. We present a new determinant expression for the Ihara-Selberg zeta function of a hypergraph, and give a linear algebraic proof of Storm's Theorem. Furthermore, we generalize these results to the Bartholdi zeta function of a hypergraph.
Non-Recursively Constructible Recursive Families of Graphs
Authors: Bouey Colleen , Graves Christina , Ostrander Aaron , Palma Gregory
Published: January 2020

In a publication by Noy and Ribó, it was shown that recursively constructible families of graphs are recursive.  The authors also conjecture that the converse holds; that is, recursive families are also recursively constructible.  In this paper, we provide two specific counterexamples to this conjecture, which we then extend to an infinite family of counterexamples.
Canonical Decompositions of Affine Permutations, Affine Codes, and Split $k$-Schur Functions
Authors: Denton Tom
Published: January 2020

We develop a new perspective on the unique maximal decomposition of an arbitrary affine permutation into a product of cyclically decreasing elements, implicit in work of Thomas Lam.  This decomposition is closely related to the affine code, which generalizes the $k$-bounded partition associated to Grassmannian elements.  We also prove that the affine code readily encodes a number of basic combinatorial properties of an affine permutation.  As an application, we prove a new special case of the Littlewood-Richardson Rule for $k$-Schur functions, using the canonical decomposition to control for which permutations appear in the expansion of the $k$-Schur function in noncommuting variables over the affine nil-Coxeter algebra.
Preserving Log-Convexity for Generalized Pascal Triangles
Authors: Ahmia Moussa , Belbachir Hacène
Published: January 2020

We establish the preserving log-convexity property for the generalized Pascal triangles. It is an extension of a result of H. Davenport and G. Pólya "On the product of two power series", who proved that the binomial convolution of two log-convex sequences is log-convex.
Alternating Permutations with Restrictions and Standard Young Tableaux
Authors: Xu Yuexiao , Yan Sherry H. F.
Published: January 2020

In this paper, we establish bijections between the set of 4123-avoiding down-up alternating permutations of length $2n$ and the set of standard Young tableaux of shape $(n,n,n)$, and between the set of 4123-avoiding down-up alternating permutations of length $2n-1$ and the set of shifted  standard Young tableaux of shape $(n+1, n, n-1)$ via an intermediate structure of Yamanouchi words. Moreover, we show that 4123-avoiding up-down alternating permutations of length $2n+1$  are in one-to-one correspondence with  standard Young tableaux of shape $(n+1,n,n-1)$, and 4123-avoiding up-down alternating permutations of length $2n$ are in bijection with shifted standard Young tableaux of shape $(n+2,n,n-2)$.
Can Colour-Blind Distinguish Colour Palettes?
Authors: Kalinowski Rafał , Pilśniak Monika , Przybyło Jakub , Woźniak Mariusz
Published: January 2020

Let $c:E(G)\rightarrow [k]$ be  a colouring, not necessarily proper, of edges of a graph $G$. For a vertex $v\in V$, let $\overline{c}(v)=(a_1,\ldots,a_k)$, where $ a_i =|\{u:uv\in E(G),\;c(uv)=i\}|$, for $i\in [k].$ If we re-order the sequence $\overline{c}(v)$ non-decreasingly, we obtain a sequence $c^*(v)=(d_1,\ldots,d_k)$, called a palette of a vertex $v$. This can be viewed as the most comprehensive information about colours incident with $v$ which can be delivered by a person who is unable to name colours but distinguishes one from another. The smallest $k$ such that $c^*$ is a proper colouring of vertices of $G$ is called the colour-blind index of a graph $G$, and is denoted by dal$(G)$. We conjecture that there is a constant $K$ such that dal$(G)\leq K$ for every graph $G$ for which the parameter is well defined. As our main result we prove that $K\leq 6$ for regular graphs of sufficiently large degree, and for irregular graphs with $\delta (G)$ and $\Delta(G)$ satisfying certain conditions. The proofs are based on the Lopsided Lovász Local Lemma. We also show that $K=3$ for all regular bipartite graphs, and for complete graphs of order $n\geq 8$.
Geodetic Topological Cycles in Locally Finite Graphs
Authors: Georgakopoulos Agelos , Sprüssel Philipp
Published: January 2020

We prove that the topological cycle space ${\cal C}(G)$ of a locally finite graph $G$ is generated by its geodetic topological circles. We further show that, although the finite cycles of $G$ generate ${\cal C}(G)$, its finite geodetic cycles need not generate ${\cal C}(G)$.
The 1/3-2/3 Conjecture for $N$-Free Ordered Sets
Authors: Zaguia Imed
Published: January 2020

A balanced pair in an ordered set $P=(V,\leq)$ is a pair $(x,y)$ of elements of $V$ such that the proportion of linear extensions of $P$ that put $x$ before $y$ is in the real interval $[1/3, 2/3]$. We prove that every finite $N$-free ordered set which is not totally ordered has a balanced pair.
The Ramsey Number of Loose Triangles and Quadrangles in Hypergraphs
Authors: Gyarfas Andras , Raeisi Ghaffar
Published: January 2020

Asymptotic values of hypergraph Ramsey numbers for loose cycles (and paths) were determined recently. Here we determine some of them exactly, for example the 2-color hypergraph Ramsey number of a $k$-uniform loose 3-cycle or 4-cycle: $R(\mathcal{C}^k_3,\mathcal{C}^k_3)=3k-2$ and $R(\mathcal{C}_4^k,\mathcal{C}_4^k)=4k-3$ (for $k\geq 3$). For more than 3-colors we could prove only that $R(\mathcal{C}^3_3,\mathcal{C}^3_3,\mathcal{C}^3_3)=8$. Nevertheless, the $r$-color Ramsey number of triangles for hypergraphs are much smaller than for graphs: for $r\geq 3$, $$r+5\le R(\mathcal{C}_3^3,\mathcal{C}_3^3,\dots,\mathcal{C}_3^3)\le 3r$$
Binomial Edge Ideals of Graphs
Authors: Kiani Dariush , Saeedi Sara
Published: January 2020

We characterize all graphs whose binomial edge ideals have a linear resolution. Indeed, we show that complete graphs are the only graphs with this property. We also compute some graded components of the first Betti number of the binomial edge ideal of a graph with respect to the graphical terms. Finally, we give an upper bound for the Castelnuovo-Mumford regularity of the binomial edge ideal of a closed graph.
Drawing Hamiltonian Cycles with no Large Angles
Authors: Dumitrescu Adrian , Pach János , Tóth Géza
Published: January 2020

Let $n \geq 4$ be even. It is shown that every set $S$ of $n$ points in the plane can be connected by a (possibly self-intersecting) spanning tour (Hamiltonian cycle) consisting of $n$ straight-line edges such that the angle between any two consecutive edges is at most $2\pi/3$. For $n=4$ and $6$, this statement is tight. It is also shown that every even-element point set $S$ can be partitioned  into at most two subsets, $S_1$ and $S_2$, each admitting a spanning tour with no angle larger than $\pi/2$. Fekete and Woeginger conjectured that for sufficiently large even $n$, every $n$-element set admits such a spanning tour. We confirm this conjecture for point sets in convex position. A much stronger result holds for large point sets randomly and uniformly selected from an open region bounded by finitely many rectifiable curves: for any $\epsilon>0$, these sets almost surely admit a spanning tour with no angle larger than $\epsilon$.
Lower Bounds on the Obstacle Number of Graphs
Authors: Mukkamala Padmini , Pach János , Pálvölgyi Dömötör
Published: January 2020

Given a graph $G$, an obstacle representation of $G$ is a set of points in the plane representing the vertices of $G$, together with a set of connected obstacles such that two vertices of $G$ are joined by an edge if and only if the corresponding points can be connected by a segment which avoids all obstacles. The obstacle number of $G$ is the minimum number of obstacles in an obstacle representation of $G$. It is shown that there are graphs on $n$ vertices with obstacle number at least $\Omega({n}/{\log n})$.
Cospectral Graphs and Regular Orthogonal Matrices of Level 2
Authors: Abiad Aida , Haemers Willem H
Published: January 2020

For a graph $\Gamma$ with adjacency matrix $A$, we consider a switching operation that takes $\Gamma$ into a graph $\Gamma'$ with adjacency matrix $A'$, defined by $A'=Q^\top A Q$, where $Q$ is a regular orthogonal matrix of level $2$ (that is, $Q^\top Q=I$, $Q$1 $=$ 1, $2Q$ is integral, and $Q$ is not a permutation matrix). If such an operation exists, and $\Gamma$ is nonisomorphic with $\Gamma'$, then we say that $\Gamma'$ is semi-isomorphic with $\Gamma$. Semi-isomorphic graphs are $\mathbb {R}$-cospectral, which means that they are cospectral and so are their complements. Wang and Xu [On the asymptotic behavior of graphs determined by their generalized spectra, Discrete Math. 310 (2010)] expect that almost all pairs of nonisomorphic $\mathbb {R}$-cospectral graphs are semi-isomorphic.Regular orthogonal matrices of level $2$ have been classified. By use of this classification we work out the requirements for this switching operation to work in case $Q$ has one nontrivial indecomposable block of size $4$, $6$, $7$ or $8$. Size $4$ corresponds to Godsil-McKay switching. The other cases provide new methods for constructions of $\mathbb {R}$-cospectral graphs. For graphs with eight vertices all these constructions are carried out. As a result we find that, out of the 1166 graphs on eight vertices which are $\mathbb {R}$-cospectral to another graph, only 44 are not semi-isomorphic to another graph.
Vertex-Decomposable Graphs, Codismantlability, Cohen-Macaulayness, and Castelnuovo-Mumford Regularity
Authors: Bıyıkoğlu Türker , Civan Yusuf
Published: January 2020

We call a vertex $x$ of a graph $G=(V,E)$ a codominated vertex if $N_G[y]\subseteq N_G[x]$ for some vertex $y\in V\backslash \{x\}$, and a graph $G$ is called codismantlable if either it is an edgeless graph or it contains a codominated vertex $x$ such that $G-x$ is codismantlable. We show that $(C_4,C_5)$-free vertex-decomposable graphs are codismantlable, and prove that if $G$ is a $(C_4,C_5,C_7)$-free well-covered graph, then vertex-decomposability, codismantlability and Cohen-Macaulayness for $G$ are all equivalent. These results complement and unify many of the earlier results on bipartite, chordal and very well-covered graphs. We also study the Castelnuovo-Mumford regularity $reg(G)$ of such graphs, and show that $reg(G)=im(G)$ whenever $G$ is a $(C_4,C_5)$-free vertex-decomposable graph, where $im(G)$ is the induced matching number of $G$. Furthermore, we prove that $H$ must be a codismantlable graph if $im(H)=reg(H)=m(H)$, where $m(H)$ is the matching number of $H$. We further describe an operation on digraphs that creates a vertex-decomposable and codismantlable graph from any acyclic digraph. By way of application, we provide an infinite family $H_n$ ($n\geq 4$) of sequentially Cohen-Macaulay graphs whose vertex cover numbers are half of their orders, while containing no vertex of degree-one such that they are vertex-decomposable, and $reg(H_n)=im(H_n)$ if $n\geq 6$. This answers a recent question of Mahmoudi et al.
Asymptotic Lower Bounds on Circular Chromatic Index of Snarks
Authors: Mačaj Martin , Mazák Ján
Published: January 2020

We prove that the circular chromatic index of a cubic graph $G$ with $2k$ vertices and chromatic index $4$ is at least $3+2/k$. This bound is (asymptotically) optimal for an infinite class of cubic graphs containing bridges. We also show that the constant $2$ in the above bound can be increased for graphs with larger girth or higher connectivity. In particular, if $G$ has girth at least $5$, its circular chromatic index is at least $3+2.5/k$. Our method gives an alternative proof that the circular chromatic index of the generalised type 1 Blanuša snark $B_m^1$ is $3+2/3m$.
On Drawings and Decompositions of 1-Planar Graphs
Authors: Czap Július , Hudák Dávid
Published: January 2020

A graph is called 1-planar if it can be drawn in the plane so that each of its edges is crossed by at most one other edge. We show that every 1-planar drawing of any 1-planar graph on $n$ vertices has at most $n-2$ crossings; moreover, this bound is tight. By this novel necessary condition for 1-planarity, we characterize the 1-planarity of Cartesian product $K_m\times P_n$. Based on this condition, we also derive an upper bound on the number of edges of bipartite 1-planar graphs, and we show that each subgraph of an optimal 1-planar graph (i.e., a 1-planar graph with $n$ vertices and $4n-8$ edges) can be decomposed into a planar graph and a forest.
Counting Bases of Representable Matroids
Authors: Snook Michael
Published: January 2020

We show that it is #P-complete to count the number of bases of matroids representable over a fixed infinite field or fields of fixed characteristic.
Probabilities of Boolean Functions given by Random Implicational Formulas
Authors: Genitrini Antoine , Gittenberger Bernhard , Kraus Veronika , Mailler Cécile
Published: January 2020

We study the asymptotic relation between the probability and the complexity of Boolean functions in the implicational fragment which are generated by large random Boolean expressions involving variables and implication, as the number of variables tends to infinity. In contrast to models studied in the literature so far, we consider two expressions to be equal if they differ only in the order of the premises. A precise asymptotic formula is derived for functions of low complexity. Furthermore, we show that this model does not exhibit the Shannon effect.An erratum was added to this paper on Feb 20, 2014.
Injective Envelopes and Projective Covers of Quivers
Authors: Grilliette Will
Published: January 2020

This paper characterizes the injective and projective objects in the category of directed multigraphs, or quivers.  Further, the injective envelope and projective cover of any quiver in this category is constructed.
Optimal Lower Bound for 2-Identifying Codes in the Hexagonal Grid
Authors: Junnila Ville , Laihonen Tero
Published: January 2020

An $r$-identifying code in a graph $G = (V,E)$ is a subset $C \subseteq V$ such that for each $u \in V$ the intersection of $C$ and the ball of radius $r$ centered at $u$ is non-empty and unique. Previously, $r$-identifying codes have been studied in various grids. In particular, it has been shown that there exists a $2$-identifying code in the hexagonal grid with density $4/19$ and that there are no $2$-identifying codes with density smaller than $2/11$. Recently, the lower bound has been improved to $1/5$ by Martin and Stanton (2010). In this paper, we prove that the $2$-identifying code with density $4/19$ is optimal, i.e. that there does not exist a $2$-identifying code in the hexagonal grid with smaller density.
Locally Identifying Coloring of Graphs
Authors: Esperet Louis , Gravier Sylvain , Montassier Mickaël , Ochem Pascal , Parreau Aline
Published: January 2020

We introduce the notion of locally identifying coloring of a graph. A proper vertex-coloring $c$ of a graph $G$ is said to be locally identifying, if for any adjacent vertices $u$ and $v$ with distinct closed neighborhoods, the sets of colors that appear in the closed neighborhood of $u$ and $v$, respectively, are distinct. Let $\chi_{\rm{lid}}(G)$ be the minimum number of colors used in a locally identifying vertex-coloring of $G$. In this paper, we give several bounds on $\chi_{\rm{lid}}$ for different families of graphs (planar graphs, some subclasses of perfect graphs, graphs with bounded maximum degree) and prove that deciding whether $\chi_{\rm{lid}}(G)=3$ for a subcubic bipartite graph $G$ with large girth is an NP-complete problem.
Some Quotients of Chain Products are Symmetric Chain Orders
Authors: Duffus Dwight , McKibben-Sanders Jeremy , Thayer Kyle
Published: January 2020

Canfield and Mason have conjectured that for all subgroups $G$ of the automorphism group of the Boolean lattice $B_n$ (which can be regarded as the symmetric group $S_n$), the quotient order $B_n/G$ is a symmetric chain order.  We provide a straightforward proof of a generalization of a result of K. K. Jordan: namely, $B_n/G$ is an SCO whenever $G$ is generated by powers of disjoint cycles. In addition, the Boolean lattice $B_n$ can be replaced by any product of finite chains. The symmetric chain decompositions of Greene and Kleitman provide the basis for partitions of these quotients.
The Number of Nilpotent Semigroups of Degree 3
Authors: Distler Andreas , Mitchell J. D.
Published: January 2020

A semigroup is nilpotent of degree $3$ if it has a zero, every product of $3$ elements equals the zero, and some product of $2$ elements is non-zero. It is part of the folklore of semigroup theory that almost all finite semigroups are nilpotent of degree $3$. We give formulae for the number of nilpotent semigroups of degree $3$ on a set with $n\in\mathbb{N}$ elements up to equality, isomorphism, and isomorphism or anti-isomorphism. Likewise, we give formulae for the number of nilpotent commutative semigroups on a set with $n$ elements up to equality and up to isomorphism.
The $n$-Card Problem, Stochastic Matrices, and the Extreme Principle
Authors: Chan Justin H.C. , Jedwab Jonathan
Published: January 2020

The $n$-card problem is to determine the minimal intervals $[u,v]$ such that for every $n \times n$ stochastic matrix $A$ there is an $n \times n$ permutation matrix $P$ (depending on $A$) such that tr$(PA) \in [u,v]$. This problem is closely related to classical mathematical problems from industry and management, including the linear assignment problem and the travelling salesman problem. The minimal intervals for the $n$-card problem are known only for $n \le 4$.We introduce a new method of analysis for the $n$-card problem that makes repeated use of the Extreme Principle. We use this method to answer a question posed by Sands (2011), by showing that $[1,2]$ is a solution to the $n$-card problem for all $n \ge 2$. We also show that each closed interval of length $\frac{n}{n-1}$ contained in $[0,2)$ is a solution to the $n$-card problem for all $n \ge 2$.
List-Coloring Graphs on Surfaces with Varying List-Sizes
Authors: Dean Alice M. , Hutchinson Joan P.
Published: January 2020

Let $G$ be a graph embedded on a surface $S_\varepsilon$ with Euler genus $\varepsilon > 0$, and let $P\subset V(G)$ be a set of vertices mutually at distance at least 4 apart. Suppose all vertices of $G$ have $H(\varepsilon)$-lists and the vertices of $P$ are precolored, where $H(\varepsilon)=\Big\lfloor\frac{7 + \sqrt{24\varepsilon + 1}}{2}\Big\rfloor$ is the Heawood number. We show that the coloring of $P$ extends to a list-coloring of $G$ and that the distance bound of 4 is best possible. Our result provides an answer to an analogous question of Albertson about extending a precoloring of a set of mutually distant vertices in a planar graph to a 5-list-coloring of the graph and generalizes a result of Albertson and Hutchinson to list-coloring extensions on surfaces.
An Iterative Approach to the Traceability Conjecture for Oriented Graphs
Authors: Van Aardt Susan , Burger Alewyn , Dunbar Jean , Frick Marietjie , Harris John , Singleton Joy
Published: January 2020

A digraph is $k$-traceable if its order is at least $k$ and each of its subdigraphs of order $k$ is traceable.  The Traceability Conjecture (TC) states that for $k\geq 2$ every $k$-traceable oriented graph of order at least $2k-1$ is traceable. It has been shown that for $2\leq k\leq 6$, every $k$-traceable oriented graph is traceable. We develop an iterative procedure to extend previous results regarding the TC. In particular, we prove that every $7$-traceable oriented graph of order at least 9 is traceable and every 8-traceable graph of order at least 14 is traceable.
The Maximum Size of a Partial Spread in $H(4 n +1, q^2)$ is $q^{2 n +1}+1$
Authors: Vanhove Frédéric
Published: January 2020

We prove that in every finite Hermitian polar space of odd dimension and even maximal dimension $\rho$ of the totally isotropic subspaces, a partial spread has size at most $q^{\rho+1}+1$, where $GF(q^2)$ is the defining field. This bound is tight and is a generalisation of the result of De Beule and Metsch for the case $\rho=2$.
A Set and Collection Lemma
Authors: Levit Vadim E. , Mandrescu Eugen
Published: January 2020

A set $S\subseteq V(G)$ is independent if no two vertices from $S$ are adjacent. Let $\alpha\left( G\right) $ stand for the cardinality of a largest independent set.In this paper we prove that if $\Lambda$ is a nonempty collection of maximum independent sets of a graph $G$, and $S$ is an independent set, thenthere is a matching from $S-\bigcap\Lambda$ into $\bigcup\Lambda-S$, and$\left\vert S\right\vert +\alpha(G)\leq\left\vert \bigcap\Lambda\cap S\right\vert +\left\vert \bigcup\Lambda\cup S\right\vert $.Based on these findings we provide alternative proofs for a number of well-known lemmata, such as the "Maximum Stable Set Lemma" due to Claude Berge and the "Clique Collection Lemma" due to András Hajnal.
Optimal Divisibility Conditions for Loose Hamilton Cycles in Random Hypergraphs
Authors: Dudek Andrzej , Frieze Alan , Loh Po-Shen , Speiss Shelley
Published: January 2020

In the random $k$-uniform hypergraph $H^{(k)}_{n,p}$ of order $n$, each possible $k$-tuple appears independently with probability $p$. A loose Hamilton cycle is a cycle of order $n$ in which every pair of consecutive edges intersects in a single vertex. It was shown by Frieze that if $p\geq c(\log n)/n^2$ for some absolute constant $c>0$, then a.a.s. $H^{(3)}_{n,p}$ contains a loose Hamilton cycle, provided that $n$ is divisible by $4$. Subsequently,  Dudek and Frieze extended this result for any uniformity $k\ge 4$, proving that if $p\gg (\log n)/n^{k-1}$, then $H^{(k)}_{n,p}$ contains a loose Hamilton cycle, provided that $n$ is divisible by $2(k-1)$. In this paper, we improve the divisibility requirement and show that in the above results it is enough to assume that $n$ is a multiple of $k-1$, which is best possible.
Parity Types, Cycle Structures and Autotopisms of Latin Squares
Authors: Kotlar Daniel
Published: January 2020

The parity type of a Latin square is defined in terms of the numbers of even and odd rows and columns. It is related to an Alon-Tarsi-like conjecture that applies to Latin squares of odd order. Parity types are used to derive upper bounds for the size of autotopy groups. A new algorithm for finding the autotopy group of a Latin square, based on the cycle decomposition of its rows, is presented, and upper bounds for the size of autotopy groups are derived from it.
On a Recurrence Arising in Graph Compression
Authors: Choi Yongwook , Knessl Charles , Szpankowski Wojciech
Published: January 2020

In a recently proposed graphical compression algorithm by Choi and Szpankowski (2012), the following tree arose in the course of the analysis. The root contains $n$ balls that are consequently distributed between two subtrees according to a simple rule: In each step, all balls independently move down to the left subtree (say with probability $p$) or the right subtree (with probability $1-p$). A new node is created as long as there is at least one ball in that node. Furthermore, a nonnegative integer $d$ is given, and at level $d$ or greater one ball is removed from the leftmost node before the balls move down to the next level. These steps are repeated until all balls are removed (i.e., after $n+d$ steps). Observe that when $d=\infty$ the above tree can be modeled as a trie that stores $n$ independent sequences generated by a binary memoryless source with parameter $p$. Therefore, we coin the name $(n,d)$-tries for the tree just described, and to which we often refer simply as $d$-tries. We study here in detail the path length, and show how much the path length of such a $d$-trie differs from that of regular tries. We use methods of analytic algorithmics, from Mellin transforms to analytic poissonization.
Set Systems with Restricted $t$-wise Intersections Modulo Prime Powers
Authors: Liu Rudy X. J.
Published: January 2020

We give a polynomial upper bound on the size of set systems with restricted $t$-wise intersections modulo prime powers. Let $t\geq 2$. Let $p$ be a prime and $q=p^{\alpha}$ be a prime power. Let ${\cal L}=\{l_1,l_2,\ldots,l_s\}$ be a subset of $\{0, 1, 2, \ldots, q-1\}$. If ${\cal F}$ is a family of subsets of an $n$ element set $X$ such that $|F_{1}\cap \cdots \cap F_{t}| \pmod{q} \in {\cal L}$ for any collection of $t$ distinct sets from ${\cal F}$ and $|F| \pmod{q} \notin {\cal L}$ for every $F\in {\cal F}$, then $$ |{\cal F}|\leq {t(t-1)\over2}\sum_{i=0}^{2^{s-1}}{n\choose i}. $$ Our result extends a theorem of Babai, Frankl, Kutin, and Štefankovič, who studied the $2$-wise case for prime power moduli, and also complements a result of Grolmusz that no polynomial upper bound holds for non-prime-power composite moduli.
Balanced Vertex Decomposable Simplicial Complexes and their h-vectors
Authors: Biermann Jennifer , Van Tuyl Adam
Published: January 2020

Given any finite simplicial complex $\Delta$, we show how to construct from a colouring $\chi$ of $\Delta$ a new simplicial complex $\Delta_{\chi}$ that is balanced and vertex decomposable. In addition, the $h$-vector of $\Delta_{\chi}$ is precisely the $f$-vector of $\Delta$.  Our construction generalizes the "whiskering'' construction of Villarreal, and Cook and Nagel. We also reverse this construction to prove a special case of a conjecture of Cook and Nagel, and Constantinescu and Varbaro on the $h$-vectors of flag complexes.
A Simple Branching Process Approach to the Phase Transition in $G_{n,p}$
Authors: Bollobás Béla , Riordan Oliver
Published: January 2020

It is well known that the branching process approach to the study of the random graph $G_{n,p}$ gives a very simple way of understanding the size of the giant component when it is fairly large (of order $\Theta(n)$). Here we show that a variant of this approach works all the way down to the phase transition: we use branching process arguments to give a simple new derivation of the asymptotic size of the largest component whenever $(np-1)^3n\to\infty$.
On the Independence Numbers of the Cubes of Odd Cycles
Authors: Bohman Tom , Holzman Ron , Natarajan Venkatesh
Published: January 2020

We give an upper bound on the independence number of the cube of the odd cycle $C_{8n+5}$. The best known lower bound is conjectured to be the truth; we prove the conjecture in the case $8n+5$ prime and, within $2$, for general $n$.
Some Constructions of General Covering Designs
Authors: Montecalvo Federico
Published: January 2020

Given five positive integers $v, m,k,\lambda$ and $t$ where $v\geq k \geq t$ and $v \geq m \geq t,$ a $t$-$(v,k,m,\lambda)$ general covering design is a pair $(X,\mathcal{B})$ where $X$ is a set of $v$ elements (called points) and $\mathcal{B}$ a multiset of $k$-subsets of $X$ (called blocks) such that every $m$-subset of $X$ intersects (is covered by) at least $\lambda$ members of $\mathcal{B}$ in at least $t$ points. In this article we present new constructions for general covering designs and we generalize some others. By means of these constructions we will be able to obtain some new upper bounds on the minimum size of such designs.
General Lower Bounds on Maximal Determinants of Binary Matrices
Authors: Brent Richard P. , Osborn Judy-anne H.
Published: January 2020

We give general lower bounds on the maximal determinant of $n \times n$ $\{+1,-1\}$-matrices, both with and without the assumption of the Hadamard conjecture. Our bounds improve on earlier results of de Launey and Levin (2010) and, for certain congruence classes of $n \bmod 4$, the results of Koukouvinos, Mitrouli and Seberry (2000). In an Appendix we give a new proof, using Jacobi's determinant identity, of a result of Szöllősi (2010) on minors of Hadamard matrices.
On the Energy of Unitary Cayley Graphs
Authors: Ramaswamy H. N. , Veena C. R.
Published: January 2020

In this note we obtain the energy of unitary Cayley graph $X_{n}$ which extends a result of R. Balakrishnan for power of a prime and also determine when they are hyperenergetic. We also prove that ${E(X_{n})\over 2(n-1)}\geq{2^{k}\over 4k}$, where $k$ is the number of distinct prime divisors of $n$. Thus the ratio ${E(X_{n})\over 2(n-1)}$, measuring the degree of hyperenergeticity of $X_{n}$, grows exponentially with $k$.
Metric Dimension for Random Graphs
Authors: Bollobás Béla , Mitsche Dieter , Prałat Paweł
Published: January 2020

The metric dimension of a graph $G$ is the minimum number of vertices in a subset $S$ of the vertex set of $G$ such that all other vertices are uniquely determined by their distances to the vertices in $S$. In this paper we investigate the metric dimension of the random graph $G(n,p)$ for a wide range of probabilities $p=p(n)$.
Invariant Principal Order Ideals under Foata’s Transformation
Authors: Li Teresa X.S. , Miao Melissa Y.F.
Published: January 2020

Let $\Phi$ denote  Foata's second fundamental transformation on permutations. For a permutation $\sigma$ in the symmetric group $S_n$, let $\widetilde{\Lambda}_{\sigma}=\{\pi\in S_n\colon\pi\leq_{w} \sigma\}$ be the principal order ideal generated by $\sigma$  in the weak order $\leq_{w}$. Björner and Wachs have shown that $\widetilde{\Lambda}_{\sigma}$ is invariant under $\Phi$ if and only if $\sigma$ is a 132-avoiding permutation. In this paper, we consider the invariance property of  $\Phi$ on the principal order ideals ${\Lambda}_{\sigma}=\{\pi\in S_n\colon \pi\leq \sigma\}$ with respect to the Bruhat order $\leq$.  We obtain a characterization  of permutations $\sigma$ such that ${\Lambda}_{\sigma}$ are invariant under $\Phi$. We also consider the invariant principal order  ideals with respect to the Bruhat order  under Han's bijection $H$. We find  that ${\Lambda}_{\sigma}$ is invariant under the bijection $H$ if and only if it is invariant under the transformation $\Phi$.
Orientations, Semiorders, Arrangements, and Parking Functions
Authors: Hopkins Sam , Perkinson David
Published: January 2020

It is known that the Pak-Stanley labeling of the Shi hyperplane arrangement provides a bijection between the regions of the arrangement and parking functions. For any graph $G$, we define the $G$-semiorder arrangement and show that the Pak-Stanley labeling of its regions produces all $G$-parking functions.
Maximal Antichains of Minimum Size
Authors: Kalinowski Thomas , Leck Uwe , Roberts Ian T.
Published: January 2020

Let $n\geqslant 4$ be a natural number, and let $K$ be a set $K\subseteq [n]:=\{1,2,\dots,n\}$. We study the problem of finding the smallest possible size of a maximal family $\mathcal{A}$ of subsets of $[n]$ such that $\mathcal{A}$ contains only sets whose size is in $K$, and $A\not\subseteq B$ for all $\{A,B\}\subseteq\mathcal{A}$, i.e. $\mathcal{A}$ is an antichain. We present a general construction of such antichains for sets $K$ containing 2, but not 1. If $3\in K$ our construction asymptotically yields the smallest possible size of such a family, up to an $o(n^2)$ error. We conjecture our construction to be asymptotically optimal also for $3\not\in K$, and we prove a weaker bound for the case $K=\{2,4\}$. Our asymptotic results are straightforward applications of the graph removal lemma to an equivalent reformulation of the problem in extremal graph theory, which is interesting in its own right.
Potential-Based Strategies for Tic-Tac-Toe on the Integer Lattice with Numerous Directions
Authors: Kruczek Klay , Sundberg Eric
Published: January 2020

We consider a tic-tac-toe game played on the $d$-dimensional integer lattice. The game that we investigate is a Maker–Breaker version of tic-tac-toe. In a Maker–Breaker game, the first player, Maker, only tries to occupy a winning line and the second player, Breaker, only tries to stop Maker from occupying a winning line. We consider the bounded number of directions game, in which we designate a finite set of direction-vectors ${\cal S} \subset {\Bbb Z}^d$ which determines the set of winning lines. We show, by using the Erdős–Selfridge theorem and a modification of a theorem by Beck about games played on almost-disjoint hypergraphs, that for the special case when the coordinates of each direction-vector are bounded, i.e., when ${\cal S} \subset \{ \vec{v} : \|\vec{v}\|_\infty \leq k \}$, Breaker can win this game if the length of each winning line is on the order of $d^2\lg(dk)$ and $d^2\lg(k)$, respectively. In addition, we show that Maker can build winning lines of length up to $(1+o(1))d\lg k $ if ${\cal S}$ is the set of all direction-vectors with coordinates bounded by $k$. We also apply these methods to the $n$-consecutive lattice points game on the $N^d$ board with (essentially) ${\cal S} = {\Bbb Z}^d$, and we show that the phase transition from a win for Maker to a win for Breaker occurs at $n= (d+o(1))\lg N$.
A Characterization of Graphs by Codes from their Incidence Matrices
Authors: Dankelmann Peter , Key Jennifer D. , Rodrigues Bernardo G.
Published: January 2020

We continue our earlier investigation of properties of linear codes generated by the rows of incidence matrices of $k$-regular connected graphs on $n$ vertices. The notion of edge connectivity is used to show that, for a wide range of such graphs, the $p$-ary code, for all primes $p$, from an $n \times \frac{1}{2}nk$ incidence matrix has dimension $n$ or $n-1$, minimum weight $k$, the minimum words are the scalar multiples of the rows, there is a gap in the weight enumerator between $k$ and $2k-2$, and the words of weight $2k-2$ are the scalar multiples of the differences of intersecting rows of the matrix. For such graphs, the graph can thus be retrieved from the code.
On Blow-Ups and Injectivity of Quivers
Authors: Grilliette Will , Seacrest Deborah E. , Seacrest Tyler
Published: January 2020

This work connects the idea of a "blow-up" of a quiver with that of injectivity, showing that for a class of monic maps $\Phi$, a quiver is $\Phi$-injective if and only if all blow-ups of it are as well.  This relationship is then used to characterize all quivers that are injective with respect to the natural embedding of $P_{n}$ into $C_{n}$.
Random Graphs from a Weighted Minor-Closed Class
Authors: McDiarmid Colin
Published: January 2020

There has been much recent interest in random graphs sampled uniformly from the n-vertex graphs in a suitable minor-closed class, such as the class of all planar graphs. Here we use combinatorial and probabilistic methods to investigate a more general model. We consider random graphs from a 'well-behaved' class of graphs: examples of such classes include all minor-closed classes of graphs with 2-connected excluded minors (such as forests, series-parallel graphs and planar graphs), the class of graphs embeddable on any given surface, and the class of graphs with at most $k$ vertex-disjoint cycles.  Also, we give weights to edges and components to specify probabilities, so that our random graphs correspond to the random cluster model, appropriately conditioned.We find that earlier results extend naturally in both directions, to general well-behaved classes of graphs, and to the weighted framework, for example results concerning the probability of a random graph being connected; and we also give results on the 2-core which are new even for the uniform (unweighted) case.
On a Sumset Problem for Integers
Authors: Du Shan-Shan , Cao Hui-Qin , Sun Zhi-Wei
Published: January 2020

Let $A$ be a finite set of integers. We show that if $k$ is a prime power or a product of two distinct primes then \[ |A+k\cdot A|\geq(k+1)|A|-\lceil k(k+2)/4\rceil \] provided $|A|\geq (k-1)^{2}k!$, where $A+k\cdot A=\{a+kb:\ a,b\in A\}$. We also establish the inequality $|A+4\cdot A|\geq5|A|-6 $ for $|A|\geq5$.
The Abel-Type Polynomial Identities
Authors: Huang Fengying , Liu Bolian
Published: January 2020

The Abel identity is $(x+y)^{n}=\sum\limits_{i=0}^{n}{n\choose i}x (x-iz)^{i-1}(y+iz)^{n-i}$, where $x,y$ and $z$ are real numbers. In this paper we deduce several polynomials expansions, referred to as Abel-type identities, by using Foata's method, and also show some of their applications.
An Involution Proof of the Alladi-Gordon Key Identity for Schur's Partition Theorem
Authors: Zhao James J.Y.
Published: January 2020

The Alladi-Gordon identity $\sum_{k=0}^{j}(q^{i-k+1};q)_k\, {j \brack k} q^{(i-k)(j-k)}=1$ plays an important role for the Alladi-Gordon generalization of Schur's partition theorem. By using Joichi-Stanton's insertion algorithm, we present an overpartition interpretation for the Alladi-Gordon key identity. Based on this interpretation, we further obtain a combinatorial proof of the Alladi-Gordon key identity by establishing an involution on the underlying set of overpartitions.
Lehmer's Conjecture for Hermitian Matrices over the Eisenstein and Gaussian Integers
Authors: Taylor Graeme , Greaves Gary
Published: January 2020

We solve Lehmer's problem for a class of polynomials arising from Hermitian matrices over the Eisenstein and Gaussian integers, that is, we show that all such polynomials have Mahler measure at least Lehmer's number $\tau_0 = 1.17628\dots$.
Flexible Color Lists in Alon and Tarsi's Theorem, and Time Scheduling with Unreliable Participants
Authors: Schauz Uwe
Published: January 2020

We present a purely combinatorial proof of Alon and Tarsi's Theorem about list colorings and orientations of graphs. More precisely, we describe a winning strategy for Mrs. Correct in the corresponding coloring game of Mr. Paint and Mrs. Correct. This strategy produces correct vertex colorings, even if the colors are taken from lists that are not completely fixed before the coloration process starts. The resulting strengthening of Alon and Tarsi's Theorem leads also to strengthening of its numerous repercussions. For example we study upper bounds for list chromatic numbers of bipartite graphs and list chromatic indices of complete graphs. As real life application, we examine a chess tournament time scheduling problem with unreliable participants.
Congruences Involving Alternating Multiple Harmonic Sums
Authors: Tauraso Roberto
Published: January 2020

We show that for any prime $p\neq 2$, $$\sum_{k=1}^{p-1}{(-1)^k\over k}{-{1\over 2} \choose k} \equiv -\sum_{k=1}^{(p-1)/2}{1\over k} \pmod{p^3}$$ by expressing the left-hand side as a combination of alternating multiple harmonic sums.
Combinatorial Tilings of the Sphere by Pentagons
Authors: Yan Min
Published: January 2020

A combinatorial tiling of the sphere is naturally given by an embedded graph. We study the case that each tile has exactly five edges, with the ultimate goal of classifying combinatorial tilings of the sphere by geometrically congruent pentagons. We show that the tiling cannot have only one vertex of degree $>3$. Moreover, we construct earth map tilings, which give classifications under the condition that vertices of degree $>3$ are at least of distance $4$ apart, or under the condition that there are exactly two vertices of degree $>3$.A corrigendum was added to this paper on 16th April 2014.
Arcs with Large Conical Subsets in Desarguesian Planes of Even Order
Authors: Coolsaet Kris , Sticker Heide
Published: January 2020

We give an explicit classification of the arcs in PG$(2,q)$ ($q$ even) with a large conical subset and excess 2, i.e., that consist of $q/2+1$ points of a conic and two points not on that conic. Apart from the initial setup, the methods used are similar to those for the case of odd $q$, published earlier (Electronic Journal of Combinatorics, 17, #R112).
Delay Colourings of Cubic Graphs
Authors: Georgakopoulos Agelos
Published: January 2020

In this note we prove the conjecture of  Wilfong, Haxell and Winkler (2001) that every bipartite multi-graph with integer edge delays admits an edge colouring with $d+1$ colours in the special case when $d = 3$.
On some Generalized $q$-Eulerian Polynomials
Authors: Lin Zhicong
Published: January 2020

The $(q,r)$-Eulerian polynomials are the (maj-exc,fix,exc) enumerative polynomials of permutations. Using Shareshian and Wachs' exponential generating function of these Eulerian polynomials, Chung and Graham proved two symmetrical $q$-Eulerian identities and asked for bijective proofs. We provide such proofs using Foata and Han's three-variable statistic (inv-lec,pix,lec). We also prove a new recurrence formula for the $(q,r)$-Eulerian polynomials and study a $q$-analogue of Chung and Graham's restricted descent polynomials. In particular, we obtain a generalized symmetrical identity for these restricted $q$-Eulerian polynomials with a combinatorial proof.
Minimally Intersecting Set Partitions of Type $B$
Authors: Chen William Y.C. , Wang David G.L.
Published: January 2020

Motivated by Pittel's study of minimally intersecting set partitions, we investigate minimally intersecting set partitions of type $B$. Our main result is a formula for the number of minimally intersecting $r$-tuples of $B_n$-partitions. As a consequence, it implies the formula of Benoumhani for the Dowling number in analogy to Dobiński's formula.
Fixed Point Polynomials of Permutation Groups
Authors: Harden C. M. , Penman D. B.
Published: January 2020

In this paper we study, given a group $G$ of permutations of a finite set, the so-called fixed point polynomial $\sum_{i=0}^{n}f_{i}x^{i}$, where $f_{i}$ is the number of permutations in $G$ which have exactly $i$ fixed points. In particular, we investigate how root location relates to properties of the permutation group. We show that for a large family of such groups most roots are close to the unit circle and roughly uniformly distributed round it. We prove that many families of such polynomials have few real roots. We show that many of these polynomials are irreducible when the group acts transitively. We close by indicating some future directions of this research. A corrigendum was appended to this paper on 10th October 2014.
Pattern Avoidance in Matchings and Partitions
Authors: Bloom Jonathan , Elizalde Sergi
Published: January 2020

Extending the notion of pattern avoidance in permutations, we study matchings and set partitions whose arc diagram representation avoids a given configuration of three arcs. These configurations, which generalize $3$-crossings and $3$-nestings, have an interpretation, in the case of matchings, in terms of patterns in full rook placements on Ferrers boards.We enumerate $312$-avoiding matchings and partitions, obtaining algebraic generating functions, in contrast with the known D-finite generating functions for the $321$-avoiding (i.e., $3$-noncrossing) case. Our approach provides a more direct proof of a formula of Bóna for the number of $1342$-avoiding permutations. We also give a bijective proof of the shape-Wilf-equivalence of the patterns $321$ and $213$ which greatly simplifies existing proofs by Backelin-West-Xin and Jelínek, and provides an extension of work of Gouyou-Beauchamps for matchings with fixed points. Finally, we classify pairs of patterns of length 3 according to shape-Wilf-equivalence, and enumerate matchings and partitions avoiding a pair in most of the resulting equivalence classes.
Multiplicative Partitions
Authors: Chamberland Marc , Johnson Colin , Nadeau Alice , Wu Bingxi
Published: January 2020

New formulas for the multiplicative partition function are developed. Besides giving a fast algorithm for generating these partitions, new identities for additive partitions and the Riemann zeta function are also produced.