bluuebunny/crossref_metadata_2025 huggingface dataset:
Fixing Numbers of Graphs and Groups
Authors: Gibbons Courtney R. , Laison Joshua D.
Published: January 2020

The fixing number of a graph $G$ is the smallest cardinality of a set of vertices $S$ such that only the trivial automorphism of $G$ fixes every vertex in $S$. The fixing set of a group $\Gamma$ is the set of all fixing numbers of finite graphs with automorphism group $\Gamma$. Several authors have studied the distinguishing number of a graph, the smallest number of labels needed to label $G$ so that the automorphism group of the labeled graph is trivial. The fixing number can be thought of as a variation of the distinguishing number in which every label may be used only once, and not every vertex need be labeled. We characterize the fixing sets of finite abelian groups, and investigate the fixing sets of symmetric groups.
Real Time Asymptotic Packing
Authors: Spencer Joel
Published: January 2020

A random greedy algorithm, somewhat modified, is analyzed by using a real time context and showing that the variables remain close to the solution of a natural differential equation. Given a $(k+1)$-uniform simple hypergraph on $N$ vertices, regular of degree $D$, the algorithm gives a packing of disjoint hyperedges containing all but $O(ND^{-1/k}\ln^cD)$ of the vertices.
A Note on Constructing Large Cayley Graphs of Given Degree and Diameter by Voltage Assignments
Authors: Branković Ljiljana , Miller Mirka , Plesník Ján , Ryan Joe , Širáň Jozef
Published: January 2020

Voltage graphs are a powerful tool for constructing large graphs (called lifts) with prescribed properties as covering spaces of small base graphs. This makes them suitable for application to the degree/diameter problem, which is to determine the largest order of a graph with given degree and diameter. Many currently known largest graphs of degree $\le 15$ and diameter $\le 10$ have been found by computer search among Cayley graphs of semidirect products of cyclic groups. We show that all of them can in fact be described as lifts of smaller Cayley graphs of cyclic groups, with voltages in (other) cyclic groups. This opens up a new possible direction in the search for large vertex-transitive graphs of given degree and diameter.
Venn Diagrams with Few Vertices
Authors: Bultena Bette , Ruskey Frank
Published: January 2020

An $n$-Venn diagram is a collection of $n$ finitely-intersecting simple closed curves in the plane, such that each of the $2^n$ sets $X_1 \cap X_2 \cap \cdots \cap X_n$, where each $X_i$ is the open interior or exterior of the $i$-th curve, is a non-empty connected region. The weight of a region is the number of curves that contain it. A region of weight $k$ is a $k$-region. A monotone Venn diagram with $n$ curves has the property that every $k$-region, where $0 < k < n$, is adjacent to at least one $(k-1)$-region and at least one $(k+1)$-region. Monotone diagrams are precisely those that can be drawn with all curves convex. An $n$-Venn diagram can be interpreted as a planar graph in which the intersection points of the curves are the vertices. For general Venn diagrams, the number of vertices is at least $ \lceil {2^n-2 \over n-1} \rceil$. Examples are given that demonstrate that this bound can be attained for $1 < n \le 7$. We show that each monotone Venn diagram has at least ${n \choose {\lfloor n/2 \rfloor}}$ vertices, and that this lower bound can be attained for all $n > 1$.
Derivative Polynomials, Euler Polynomials, and Associated Integer Sequences
Authors: Hoffman Michael E.
Published: January 2020

Let $P_n$ and $Q_n$ be the polynomials obtained by repeated differentiation of the tangent and secant functions respectively. From the exponential generating functions of these polynomials we develop relations among their values, which are then applied to various numerical sequences which occur as values of the $P_n$ and $Q_n$. For example, $P_n(0)$ and $Q_n(0)$ are respectively the $n$th tangent and secant numbers, while $P_n(0)+Q_n(0)$ is the $n$th André number. The André numbers, along with the numbers $Q_n(1)$ and $P_n(1)-Q_n(1)$, are the Springer numbers of root systems of types $A_n$, $B_n$, and $D_n$ respectively, or alternatively (following V. I. Arnol'd) count the number of "snakes" of these types. We prove this for the latter two cases using combinatorial arguments. We relate the values of $P_n$ and $Q_n$ at $\sqrt3$ to certain "generalized Euler and class numbers" of D. Shanks, which have a combinatorial interpretation in terms of 3-signed permutations as defined by R. Ehrenborg and M. A. Readdy. Finally, we express the values of Euler polynomials at any rational argument in terms of $P_n$ and $Q_n$, and from this deduce formulas for Springer and Shanks numbers in terms of Euler polynomials.
Positivity for Special Cases of $(q,t)$-Kostka Coefficients and Standard Tableaux Statistics
Authors: Zabrocki Mike
Published: January 2020

We present two symmetric function operators $H_3^{qt}$ and $H_4^{qt}$ that have the property $H_{m}^{qt} H_{(2^a1^b)}(X;q,t) = H_{(m2^a1^b)}(X;q,t)$. These operators are generalizations of the analogous operator $H_2^{qt}$ and also have expressions in terms of Hall-Littlewood vertex operators. We also discuss statistics, $a_{\mu}(T)$ and $b_{\mu}(T)$, on standard tableaux such that the $q,t$ Kostka polynomials are given by the sum over standard tableaux of shape $\lambda$, $K_{\lambda\mu}(q,t) = \sum_T t^{a_{\mu}(T)} q^{b_{\mu}(T)}$ for the case when when $\mu$ is two columns or of the form $(32^a1^b)$ or $(42^a1^b)$. This provides proof of the positivity of the $(q,t)$-Kostka coefficients in the previously unknown cases of $K_{\lambda (32^a1^b)}(q,t)$ and $K_{\lambda (42^a1^b)}(q,t)$. The vertex operator formulas are used to give formulas for generating functions for classes of standard tableaux that generalize the case when $\mu$ is two columns.
A Fibonacci-like Sequence of Composite Numbers
Authors: Nicol John W.
Published: January 2020

In 1964, Ronald Graham proved that there exist relatively prime natural numbers $a$ and $b$ such that the sequence $\{A_n\}$ defined by $$ {A}_{n} =A_{n-1}+A_{n-2}\qquad (n\ge 2;A_0=a,A_1=b)$$ contains no prime numbers, and constructed a 34-digit pair satisfying this condition. In 1990, Donald Knuth found a 17-digit pair satisfying the same conditions. That same year, noting an improvement to Knuth's computation, Herbert Wilf found a yet smaller 17-digit pair. Here we improve Graham's construction and generalize Wilf's note, and show that the 12-digit pair $$(a,b)= (407389224418,76343678551)$$ also defines such a sequence.
Parity Systems and the Delta-Matroid Intersection Problem
Authors: Bouchet André , Jackson Bill
Published: January 2020

We consider the problem of determining when two delta-matroids on the same ground-set have a common base. Our approach is to adapt the theory of matchings in 2-polymatroids developed by Lovász $[13]$ to a new abstract system, which we call a parity system. Examples of parity systems may be obtained by combining either, two delta-matroids, or two orthogonal 2-polymatroids, on the same ground-sets. We show that many of the results of Lovász concerning 'double flowers' and 'projections' carry over to parity systems.
Constrained graph processes
Authors: Bollobás Béla , Riordan Oliver
Published: January 2020

Let $\mathcal{Q}$ be a monotone decreasing property of graphs $G$ on $n$ vertices. Erdős, Suen and Winkler [5] introduced the following natural way of choosing a random maximal graph in $\mathcal{Q}$: start with $G$ the empty graph on $n$ vertices. Add edges to $G$ one at a time, each time choosing uniformly from all $e\in G^c$ such that $G+e\in \mathcal{Q}$. Stop when there are no such edges, so the graph $G_\infty$ reached is maximal in $\mathcal{Q}$. Erdős, Suen and Winkler asked how many edges the resulting graph typically has, giving good bounds for $\mathcal{Q}=\{$bipartite graphs$\}$ and $\mathcal{Q}=\{$triangle free graphs$\}$. We answer this question for $C_4$-free graphs and for $K_4$-free graphs, by considering a related question about standard random graphs $G_p\in \mathcal{G}(n,p)$. The main technique we use is the 'step by step' approach of [3]. We wish to show that $G_p$ has a certain property with high probability. For example, for $K_4$ free graphs the property is that every 'large' set $V$ of vertices contains a triangle not sharing an edge with any $K_4$ in $G_p$. We would like to apply a standard Martingale inequality, but the complicated dependence involved is not of the right form. Instead we examine $G_p$ one step at a time in such a way that the dependence on what has gone before can be split into 'positive' and 'negative' parts, using the notions of up-sets and down-sets. The relatively simple positive part is then estimated directly. The much more complicated negative part can simply be ignored, as shown in [3].
Asymptotics for the Probability of Connectedness and the Distribution of Number of Components
Authors: Bell Jason P. , Bender Edward A. , Cameron Peter J. , Richmond L. Bruce
Published: January 2020

Let $\rho _n$ be the fraction of structures of "size" $n$ which are "connected"; e.g., (a) the fraction of labeled or unlabeled $n$-vertex graphs having one component, (b) the fraction of partitions of $n$ or of an $n$-set having a single part or block, or (c) the fraction of $n$-vertex forests that contain only one tree. Various authors have considered $\lim \rho _n$, provided it exists. It is convenient to distinguish three cases depending on the nature of the power series for the structures: purely formal, convergent on the circle of convergence, and other. We determine all possible values for the pair $(\liminf \rho _{n},\;\limsup \rho _{n})$ in these cases. Only in the convergent case can one have $0 < \lim \rho _{n} < 1$. We study the existence of $\lim \rho _{n}$ in this case.
A Note on Random Minimum Length Spanning Trees
Authors: Frieze Alan , Ruszinkó Miklós , Thoma Lubos
Published: January 2020

Consider a connected $r$-regular $n$-vertex graph $G$ with random independent edge lengths, each uniformly distributed on $[0,1]$. Let $mst(G)$ be the expected length of a minimum spanning tree. We show in this paper that if $G$ is sufficiently highly edge connected then the expected length of a minimum spanning tree is $\sim {n\over r}\zeta(3)$. If we omit the edge connectivity condition, then it is at most $\sim {n\over r}(\zeta(3)+1)$.
A Complete Categorization of When Generalized Tribonacci Sequences Can Be Avoided by Additive Partitions
Authors: Develin Mike
Published: January 2020

A set or sequence $U$ in the natural numbers is defined to be avoidable if ${\bf N}$ can be partitioned into two sets $A$ and $B$ such that no element of $U$ is the sum of two distinct elements of $A$ or of two distinct elements of $B$. In 1980, Hoggatt [5] studied the Tribonacci sequence $T=\{t_n\}$ where $t_1=1$, $t_2=1$, $t_3=2$, and $t_n=t_{n-1}+t_{n-2}+t_{n-3}$ for $n\ge 4$, and showed that it was avoidable. Dumitriu [3] continued this research, investigating Tribonacci sequences with arbitrary initial terms, and achieving partial results. In this paper we give a complete answer to the question of when a generalized Tribonacci sequence is avoidable.
From a Polynomial Riemann Hypothesis to Alternating Sign Matrices
Authors: Eğecioğlu Ömer , Redmond Timothy , Ryavec Charles
Published: January 2020

This paper begins with a brief discussion of a class of polynomial Riemann hypotheses, which leads to the consideration of sequences of orthogonal polynomials and 3-term recursions. The discussion further leads to higher order polynomial recursions, including 4-term recursions where orthogonality is lost. Nevertheless, we show that classical results on the nature of zeros of real orthogonal polynomials (i. e., that the zeros of $p_n$ are real and those of $p_{n+1}$ interleave those of $p_n$) may be extended to polynomial sequences satisfying certain 4-term recursions. We identify specific polynomial sequences satisfying higher order recursions that should also satisfy this classical result. As with the 3-term recursions, the 4-term recursions give rise naturally to a linear functional. In the case of 3-term recursions the zeros fall nicely into place when it is known that the functional is positive, but in the case of our 4-term recursions, we show that the functional can be positive even when there are non-real zeros among some of the polynomials. It is interesting, however, that for our 4-term recursions positivity is guaranteed when a certain real parameter $C$ satisfies $C\ge 3$, and this is exactly the condition of our result that guarantees the zeros have the aforementioned interleaving property. We conjecture the condition $C\ge 3$ is also necessary. Next we used a classical determinant criterion to find exactly when the associated linear functional is positive, and we found that the Hankel determinants $\Delta_n$ formed from the sequence of moments of the functional when $C = 3$ give rise to the initial values of the integer sequence $1, 3, 26, 646, 45885, \cdots,$ of Alternating Sign Matrices (ASMs) with vertical symmetry. This spurred an intense interest in these moments, and we give 9 diverse characterizations of this sequence of moments. We then specify these Hankel determinants as Macdonald-type integrals. We also provide an an infinite class of integer sequences, each sequence of which gives the Hankel determinants $\Delta_n$ of the moments. Finally we show that certain $n$-tuples of non-intersecting lattice paths are evaluated by a related class of special Hankel determinants. This class includes the $\Delta_n$. At the same time, ASMs with vertical symmetry can readily be identified with certain $n$-tuples of osculating paths. These two lattice path models appear as a natural bridge from the ASMs with vertical symmetry to Hankel determinants.
New Lower Bound Formulas for Multicolored Ramsey Numbers
Authors: Robertson Aaron
Published: January 2020

We give two lower bound formulas for multicolored Ramsey numbers. These formulas improve the bounds for several small multicolored Ramsey numbers.
Inversion of Bilateral Basic Hypergeometric Series
Authors: Schlosser Michael
Published: January 2020

We present a new matrix inverse with applications in the theory of bilateral basic hypergeometric series. Our matrix inversion result is directly extracted from an instance of Bailey's very-well-poised ${}_6\psi_6$ summation theorem, and involves two infinite matrices which are not lower-triangular. We combine our bilateral matrix inverse with known basic hypergeometric summation theorems to derive, via inverse relations, several new identities for bilateral basic hypergeometric series.
Moments of Characteristic Polynomials Enumerate Two-Rowed Lexicographic Arrays
Authors: Strahov E.
Published: January 2020

A combinatorial interpretation is provided for the moments of characteristic polynomials of random unitary matrices. This leads to a rather unexpected consequence of the Keating and Snaith conjecture: the moments of $|\zeta(1/2+it)|$ turn out to be connected with some increasing subsequence problems (such as the last passage percolation problem).
Some Non-Normal Cayley Digraphs of the Generalized Quaternion Group of Certain Orders
Authors: Dobson Edward
Published: January 2020

We show that an action of SL$(2,p)$, $p\ge 7$ an odd prime such that $4\mathrel{\not|}(p-1)$, has exactly two orbital digraphs $\Gamma_1$, $\Gamma_2$, such that Aut$(\Gamma_i)$ admits a complete block system ${\cal B}$ of $p+1$ blocks of size $2$, $i = 1,2$, with the following properties: the action of Aut$(\Gamma_i)$ on the blocks of ${\cal B}$ is nonsolvable, doubly-transitive, but not a symmetric group, and the subgroup of Aut$(\Gamma_i)$ that fixes each block of ${\cal B}$ set-wise is semiregular of order $2$. If $p = 2^k - 1 > 7$ is a Mersenne prime, these digraphs are also Cayley digraphs of the generalized quaternion group of order $2^{k+1}$. In this case, these digraphs are non-normal Cayley digraphs of the generalized quaternion group of order $2^{k+1}$.
Bicoloured Dyck Paths and the Contact Polynomial for $n$ Non-Intersecting Paths in a Half-Plane Lattice
Authors: Brak R. , Essam J. W.
Published: January 2020

In this paper configurations of $n$ non-intersecting lattice paths which begin and end on the line $y=0$ and are excluded from the region below this line are considered. Such configurations are called Hankel $n-$paths and their contact polynomial is defined by $\hat{Z}^{\cal{H}}_{2r}(n;\kappa)\equiv \sum_{c= 1}^{r+1} |{\cal H}_{2r}^{(n)}(c)|\kappa^c$ where ${\cal H}_{2r}^{(n)}(c)$ is the set of Hankel $n$-paths which make $c$ intersections with the line $y=0$ the lowest of which has length $2r$. These configurations may also be described as parallel Dyck paths. It is found that replacing $\kappa$ by the length generating function for Dyck paths, $\kappa(\omega) \equiv \sum_{r=0}^\infty C_r \omega^r$, where $C_r$ is the $r^{th}$ Catalan number, results in a remarkable simplification of the coefficients of the contact polynomial. In particular it is shown that the polynomial for configurations of a single Dyck path has the expansion $\hat{Z}^{\cal{H}}_{2r}(1;\kappa(\omega)) = \sum_{b=0}^\infty C_{r+b}\omega^b$. This result is derived using a bijection between bi-coloured Dyck paths and plain Dyck paths. A bi-coloured Dyck path is a Dyck path in which each edge is coloured either red or blue with the constraint that the colour can only change at a contact with the line $y=0$. For $n>1$, the coefficient of $\omega^b$ in $\hat{Z}^{\cal{W}}_{2r}(n;\kappa(\omega))$ is expressed as a determinant of Catalan numbers which has a combinatorial interpretation in terms of a modified class of $n$ non-intersecting Dyck paths. The determinant satisfies a recurrence relation which leads to the proof of a product form for the coefficients in the $\omega$ expansion of the contact polynomial.
Short Generating Functions for some Semigroup Algebras
Authors: Denham Graham
Published: January 2020

Let $a_1,\ldots,a_n$ be distinct, positive integers with $(a_1,\ldots,a_n)=1$, and let k be an arbitrary field. Let $H(a_1,\ldots,a_n;z)$ denote the Hilbert series of the graded algebra k$[t^{a_1},t^{a_2},\ldots,t^{a_n}]$. We show that, when $n=3$, this rational function has a simple expression in terms of $a_1,a_2,a_3$; in particular, the numerator has at most six terms. By way of contrast, it is known that no such expression exists for any $n\geq4$.
The Restricted Arc-Width of a Graph
Authors: Arthur David
Published: January 2020

An arc-representation of a graph is a function mapping each vertex in the graph to an arc on the unit circle in such a way that adjacent vertices are mapped to intersecting arcs. The width of such a representation is the maximum number of arcs passing through a single point. The arc-width of a graph is defined to be the minimum width over all of its arc-representations. We extend the work of Barát and Hajnal on this subject and develop a generalization we call restricted arc-width. Our main results revolve around using this to bound arc-width from below and to examine the effect of several graph operations on arc-width. In particular, we completely describe the effect of disjoint unions and wedge sums while providing tight bounds on the effect of cones.
Even Circuits of Prescribed Clockwise Parity
Authors: Fischer Ilse , Little C. H. C.
Published: January 2020

We show that a graph has an orientation under which every circuit of even length is clockwise odd if and only if the graph contains no subgraph which is, after the contraction of at most one circuit of odd length, an even subdivision of $K_{2,3}$. In fact we give a more general characterisation of graphs that have an orientation under which every even circuit has a prescribed clockwise parity. Moreover we show that this characterisation has an equivalent analogue for signed graphs. We were motivated to study the original problem by our work on Pfaffian graphs, which are the graphs that have an orientation under which every alternating circuit is clockwise odd. Their significance is that they are precisely the graphs to which Kasteleyn's powerful method for enumerating perfect matchings may be applied.
Global Defensive Alliances in Graphs
Authors: Haynes Teresa W. , Hedetniemi Stephen T. , Henning Michael A.
Published: January 2020

A defensive alliance in a graph $G = (V,E)$ is a set of vertices $S \subseteq V$ satisfying the condition that for every vertex $v \in S$, the number of neighbors $v$ has in $S$ plus one (counting $v$) is at least as large as the number of neighbors it has in $V-S$. Because of such an alliance, the vertices in $S$, agreeing to mutually support each other, have the strength of numbers to be able to defend themselves from the vertices in $V-S$. A defensive alliance $S$ is called global if it effects every vertex in $V-S$, that is, every vertex in $V-S$ is adjacent to at least one member of the alliance $S$. Note that a global defensive alliance is a dominating set. We study global defensive alliances in graphs.
Self-Describing Sequences and the Catalan Family Tree
Authors: Šuniƙ Zoran
Published: January 2020

We introduce a transformation of finite integer sequences, show that every sequence eventually stabilizes under this transformation and that the number of fixed points is counted by the Catalan numbers. The sequences that are fixed are precisely those that describe themselves — every term $t$ is equal to the number of previous terms that are smaller than $t$. In addition, we provide an easy way to enumerate all these self-describing sequences by organizing them in a Catalan tree with a specific labelling system.
An Edge-Minimization Problem for Regular Polygons
Authors: Buchholz Ralph H. , De Launey Warwick
Published: January 2020

In this paper we will examine the following problem: What is the minimum number of unit edges required to construct $k$ identical size regular polygons in the plane if sharing of edges is allowed?
Saturation Numbers for Trees
Authors: Faudree Jill , Faudree Ralph J. , Gould Ronald J. , Jacobson Michael S.
Published: January 2020

For a fixed graph $H$, a graph $G$ is $H$-saturated if there is no copy of $H$ in $G$, but for any edge $e \notin G$, there is a copy of $H$ in $G + e$. The collection of $H$-saturated graphs of order $n$ is denoted by ${\bf SAT}(n,H)$, and the saturation number, ${\bf sat}(n, H),$ is the minimum number of edges in a graph in ${\bf SAT}(n,H)$. Let $T_k$ be a tree on $k$ vertices. The saturation numbers ${\bf sat}(n,T_k)$ for some families of trees will be determined precisely. Some classes of trees for which ${\bf sat}(n, T_k) < n$ will be identified, and trees $T_k$ in which graphs in ${\bf SAT}(n,T_k)$ are forests will be presented. Also, families of trees for which ${\bf sat}(n,T_k) \geq n$ will be presented. The maximum and minimum values of ${\bf sat}(n,T_k)$ for the class of all trees will be given. Some properties of ${\bf sat}(n,T_k)$ and ${\bf SAT} (n,T_k)$ for trees will be discussed.
Conjectured Combinatorial Models for the Hilbert Series of Generalized Diagonal Harmonics Modules
Authors: Loehr Nicholas A. , Remmel Jeffrey B.
Published: January 2020

Haglund and Loehr previously conjectured two equivalent combinatorial formulas for the Hilbert series of the Garsia-Haiman diagonal harmonics modules. These formulas involve weighted sums of labelled Dyck paths (or parking functions) relative to suitable statistics. This article introduces a third combinatorial formula that is shown to be equivalent to the first two. We show that the four statistics on labelled Dyck paths appearing in these formulas all have the same univariate distribution, which settles an earlier question of Haglund and Loehr. We then introduce analogous statistics on other collections of labelled lattice paths contained in trapezoids. We obtain a fermionic formula for the generating function for these statistics. We give bijective proofs of the equivalence of several forms of this generating function. These bijections imply that all the new statistics have the same univariate distribution. Using these new statistics, we conjecture combinatorial formulas for the Hilbert series of certain generalizations of the diagonal harmonics modules.
The Degree of the Splitting Field of a Random Polynomial over a Finite Field
Authors: Dixon John D. , Panario Daniel
Published: January 2020

The asymptotics of the order of a random permutation have been widely studied. P. Erdös and P. Turán proved that asymptotically the distribution of the logarithm of the order of an element in the symmetric group $S_{n}$ is normal with mean ${1\over2}(\log n)^{2}$ and variance ${1\over3}(\log n)^{3}$. More recently R. Stong has shown that the mean of the order is asymptotically $\exp(C\sqrt{n/\log n}+O(\sqrt{n}\log\log n/\log n))$ where $C=2.99047\ldots$. We prove similar results for the asymptotics of the degree of the splitting field of a random polynomial of degree $n$ over a finite field.
Composition of Transpositions and Equality of Ribbon Schur $Q$-Functions
Authors: Barekat Farzin , Van Willigenburg Stephanie
Published: January 2020

We introduce a new operation on skew diagrams called composition of transpositions, and use it and a Jacobi-Trudi style formula to derive equalities on skew Schur $Q$-functions whose indexing shifted skew diagram is an ordinary skew diagram. When this skew diagram is a ribbon, we conjecture necessary and sufficient conditions for equality of ribbon Schur $Q$-functions. Moreover, we determine all relations between ribbon Schur $Q$-functions; show they supply a ${\Bbb Z}$-basis for skew Schur $Q$-functions; assert their irreducibility; and show that the non-commutative analogue of ribbon Schur $Q$-functions is the flag $h$-vector of Eulerian posets.
On Kadell's Two Conjectures for the $q$-Dyson Product
Authors: Zhou Yue
Published: January 2020

By extending Lv-Xin-Zhou's first layer formulas of the $q$-Dyson product, we prove Kadell's conjecture for the Dyson product and show the error of his $q$-analogous conjecture. With the extended formulas we establish a $q$-analog of Kadell's conjecture for the Dyson product.
The Degree of a $q$-Holonomic Sequence is a Quadratic Quasi-Polynomial
Authors: Garoufalidis Stavros
Published: January 2020

A sequence of rational functions in a variable $q$ is $q$-holonomic if it satisfies a linear recursion with coefficients polynomials in $q$ and $q^n$. We prove that the degree of a $q$-holonomic sequence is eventually a quadratic quasi-polynomial, and that the leading term satisfies a linear recursion relation with constant coefficients. Our proof uses differential Galois theory (adapting proofs regarding holonomic $D$-modules to the case of $q$-holonomic $D$-modules) combined with the Lech-Mahler-Skolem theorem from number theory. En route, we use the Newton polygon of a linear $q$-difference equation, and introduce the notion of regular-singular $q$-difference equation and a WKB basis of solutions of a linear $q$-difference equation at $q=0$. We then use the Skolem-Mahler-Lech theorem to study the vanishing of their leading term. Unlike the case of $q=1$, there are no analytic problems regarding convergence of the WKB solutions. Our proofs are constructive, and they are illustrated by an explicit example.
Pattern Avoidance by Even Permutations
Authors: Baxter Andrew , Jaggard Aaron D.
Published: January 2020

We study questions of even-Wilf-equivalence, the analogue of Wilf-equivalence when attention is restricted to pattern avoidance by permutations in the alternating group. Although some Wilf-equivalence results break when considering even-Wilf-equivalence analogues, we prove that other Wilf-equivalence results continue to hold in the even-Wilf-equivalence setting. In particular, we prove that $t(t-1)\cdots 321$ and $(t-1)(t-2)\cdots 21t$ are even-shape-Wilf-equivalent for odd $t$, paralleling a result (which held for all $t$) of Backelin, West, and Xin for shape-Wilf-equivalence. This allows us to classify the symmetric group $\mathcal{S}_{4}$, and to partially classify $\mathcal{S}_{5}$ and $\mathcal{S}_{6}$, according to even-Wilf-equivalence. As with transition to involution-Wilf-equivalence, some—but not all—of the classical Wilf-equivalence results are preserved when we make the transition to even-Wilf-equivalence.
The Effect of Random Edge Removal on Network Degree Sequence
Authors: DuBois Thomas , Eubank Stephen , Srinivasan Aravind
Published: January 2020

Many networks arise in a random and distributed fashion, and yet result in having a specific type of degree structure: e.g., the WWW, many social networks, biological networks, etc., exhibit power-law, stretched exponential, or similar degree structures. Much work has examined how a graph's degree-structure influences other graph properties such as connectivity, diameter, etc.  Probabilistic edge removal models link failures, information spreading, and processes that consider (random) subgraphs.  They also model spreading influence of information as in the independent cascade model. We examine what happens to a graph's degree structure under edge failures where the edges are removed independently with identical probabilities. We start by analyzing the effect of edge failure on the degree sequence for power-law and exponential networks, and improve upon results of Martin, Carr & Faulon and Cooper & Lu; then, using intuition from the power-law case, we derive asymptotic results for almost any degree sequence of interest.  Our major result shows a classification of degree sequences which leads to simple rules that give much of the new expected degree sequence after random edge-removal; we also provide associated concentration bounds.
On the Ramsey Number $R(4,6)$
Authors: Exoo Geoffrey
Published: January 2020

The lower bound for the classical Ramsey number $R(4,6)$ is improved from 35 to 36. The author has found 37 new edge colorings of $K_{35}$ that have no complete graphs of order 4 in the first color, and no complete graphs of order 6 in the second color. The most symmetric of the colorings has an automorphism group of order 4, with one fixed point, and is presented in detail. The colorings were found using a heuristic search procedure.
Perfect Matchings for the Three-Term Gale-Robinson Sequences
Authors: Bousquet-Mélou Mireille , Propp James , West Julian
Published: January 2020

In 1991, David Gale and Raphael Robinson, building on explorations carried out by Michael Somos in the 1980s, introduced a three-parameter family of rational recurrence relations, each of which (with suitable initial conditions) appeared to give rise to a sequence of integers, even though a priori the recurrence might produce non-integral rational numbers. Throughout the '90s, proofs of integrality were known only for individual special cases. In the early '00s, Sergey Fomin and Andrei Zelevinsky proved Gale and Robinson's integrality conjecture. They actually proved much more, and in particular, that certain bivariate rational functions that generalize Gale-Robinson numbers are actually polynomials with integer coefficients. However, their proof did not offer any enumerative interpretation of the Gale-Robinson numbers/polynomials. Here we provide such an interpretation in the setting of perfect matchings of graphs, which makes integrality/polynomiality obvious. Moreover, this interpretation implies that the coefficients of the Gale-Robinson polynomials are positive, as Fomin and Zelevinsky conjectured.
An Extension Theorem for Terraces
Authors: Ollis Matt , Willmott Devin
Published: January 2020

We generalise an extension theorem for terraces for abelian groups to apply to non-abelian groups with a central subgroup isomorphic to the Klein 4-group $V$.  We also give terraces for three of the non-abelian groups of order a multiple of 8 that have a cyclic subgroup of index 2 that may be used in the extension theorem.  These results imply the existence of terraces for many groups that were not previously known to be terraced, including 27 non-abelian groups of order 64 and all groups of the form $V^s \times D_{8k}$ for all $s$ and all $k > 1$ where $D_{8k}$ is the dihedral group of order $8k$.
On the Rank Function of a Differential Poset
Authors: Stanley Richard P. , Zanello Fabrizio
Published: January 2020

We study $r$-differential posets, a class of combinatorial objects introduced in 1988 by the first author, which gathers together a number of remarkable combinatorial and algebraic properties, and generalizes important examples of ranked posets, including the Young lattice. We first provide a simple bijection relating differential posets to a certain class of hypergraphs, including all finite projective planes, which are shown to be naturally embedded in the initial ranks of some differential poset. As a byproduct, we prove the existence, if and only if $r\geq 6$, of $r$-differential posets nonisomorphic in any two consecutive ranks but having the same rank function. We also show that the Interval Property, conjectured by the second author and collaborators for several sequences of interest in combinatorics and combinatorial algebra, in general fails for differential posets. In the second part, we prove that the rank function $p_n$ of any arbitrary $r$-differential poset has nonpolynomial growth; namely, $p_n\gg n^ae^{2\sqrt{rn}},$ a bound very close to the Hardy-Ramanujan asymptotic formula that holds in the special case of Young's lattice. We conclude by posing several open questions.
Multi-Covering Radius for Rank Metric Codes
Authors: Vasantha W. B. , Selvaraj R. S.
Published: January 2020

The results of this paper are concerned with the multi-covering radius, a generalization of covering radius, of Rank Distance (RD) codes. This leads to greater understanding of RD codes and their distance properties. Results on multi-covering radii of RD codes under various constructions are given by varying the parameters. Some bounds are established. A relationship between multi-covering radii of an RD code and that of its ambient space is also found. The classical sphere bound is generalized.
Umbral Calculus
Authors: Di Bucchianico A. , Loeb D.
Published: January 2020

We survey the mathematical literature on umbral calculus (otherwise known as the calculus of finite differences) from its roots in the 19th century (and earlier) as a set of “magic rules” for lowering and raising indices, through its rebirth in the 1970’s as Rota’s school set it on a firm logical foundation using operator methods, to the current state of the art with numerous generalizations and applications. The survey itself is complemented by a fairly complete bibliography (over 500 references) which we expect to update regularly.
Some Convolution Identities and an Inverse Relation Involving Partial Bell Polynomials
Authors: Birmajer Daniel , Gil Juan B. , Weiner Michael D.
Published: January 2020

We prove an inverse relation and a family of convolution formulas involving partial Bell polynomials. Known and some presumably new combinatorial identities of convolution type are discussed. Our approach relies on an interesting multinomial formula for the binomial coefficients. The inverse relation is deduced from a parametrization of suitable identities that facilitate dealing with nested compositions of partial Bell polynomials.
A Note on Embedding Hypertrees
Authors: Loh Po-Shen
Published: January 2020

A classical result from graph theory is that every graph with chromatic number $\chi > t$ contains a subgraph with all degrees at least $t$, and therefore contains a copy of every $t$-edge tree. Bohman, Frieze, and Mubayi recently posed this problem for $r$-uniform hypergraphs. An $r$-tree is a connected $r$-uniform hypergraph with no pair of edges intersecting in more than one vertex, and no sequence of distinct vertices and edges $(v_1, e_1, \ldots, v_k, e_k)$ with all $e_i \ni \{v_i, v_{i+1}\}$, where we take $v_{k+1}$ to be $v_1$. Bohman, Frieze, and Mubayi proved that $\chi > 2rt$ is sufficient to embed every $r$-tree with $t$ edges, and asked whether the dependence on $r$ was necessary. In this note, we completely solve their problem, proving the tight result that $\chi > t$ is sufficient to embed any $r$-tree with $t$ edges.
The Number of Ways to Assemble a Graph
Authors: Vince Andrew , Bóna Miklós
Published: January 2020

Motivated by the question of how macromolecules assemble,the notion of an assembly tree of a graph is introduced. Given a graph $G$, the paper is concerned with enumerating the number of assembly trees of $G$, a problem that applies to the macromolecular assembly problem. Explicit formulas or generating functions are provided for the number of assembly trees of several families of graphs, in particular for what we call $(H,\phi)$-graphs.  In some natural special cases, we use a powerful recent result of Zeilberger and Apagodu to provide recurrence relations for the diagonal of the relevant multivariate generating functions, and we use a result of Wimp and Zeilberger to find very precise asymptotic formulae for the coefficients of these diagonals.  Future directions for reseach, as well as open questions, are suggested.
Oriented Hypergraphs: Introduction and Balance
Authors: Rusnak Lucas J.
Published: January 2020

An oriented hypergraph is an oriented incidence structure that extends the concept of a signed graph. We introduce hypergraphic structures and techniques central to the extension of the circuit classication of signed graphs to oriented hypergraphs. Oriented hypergraphs are further decomposed into three families—balanced, balanceable, and unbalanceable—and we obtain a complete classification of the balanced circuits of oriented hypergraphs.
Generalized Permutohedra, h-Vectors of Cotransversal Matroids and Pure O-Sequences
Authors: Oh Suho
Published: January 2020

Stanley has conjectured that the h-vector of a matroid complex is a pure O-sequence. We will prove this for cotransversal matroids by using generalized permutohedra. We construct a bijection between lattice points inside an r-dimensional convex polytope and bases of a rank r transversal matroid.
Totally Symmetric Functions are Reconstructible from Identification Minors
Authors: Lehtonen Erkko
Published: January 2020

We formulate a reconstruction problem for functions of several arguments: Is a function of several arguments uniquely determined, up to equivalence, by its identification minors? We establish some positive and negative results on this reconstruction problem. In particular, we show that totally symmetric functions (of sufficiently large arity) are reconstructible.
Symmetric Polynomials and Symmetric Mean Inequalities
Authors: Mahlburg Karl , Smyth Clifford
Published: January 2020

We prove generalized arithmetic-geometric mean inequalities for quasi-means arising from symmetric polynomials. The inequalities are satisfied by all positive, homogeneous symmetric polynomials, as well as a certain family of non-homogeneous polynomials; this family allows us to prove the following combinatorial result for marked square grids.Suppose that the cells of a $n \times n$ checkerboard are each independently filled or empty, where the probability that a cell is filled depends only on its column. We prove that for any $0 \leq \ell \leq n$, the probability that each column has at most $\ell$ filled sites is less than or equal to the probability that each row has at most $\ell$ filled sites.
Degree Distributions in General Random Intersection Graphs
Authors: Shang Yilun
Published: January 2020

We study $G(n,m,F,H)$, a variant of the standard random intersection graph model in which random weights are assigned to both vertex types in the bipartite structure. Under certain assumptions on the distributions of these weights, the degree of a vertex is shown to depend on the weight of that particular vertex and on the distribution of the weights of the other vertex type.
Enumeration Schemes for Permutations Avoiding Barred Patterns
Authors: Pudwell Lara
Published: January 2020

We give the first comprehensive collection of enumeration results for permutations that avoid barred patterns of length $\leq 4$. We then use the method of prefix enumeration schemes to find recurrences counting permutations that avoid a barred pattern of length $>4$ or a set of barred patterns.
Enumeration of Bipartite Graphs and Bipartite Blocks
Authors: Gainer-Dewar Andrew , Gessel Ira M.
Published: January 2020

We use the theory of combinatorial species to count unlabelled bipartite graphs and bipartite blocks (nonseparable or 2-connected graphs). We start with bicolored graphs, which are bipartite graphs that are properly colored in two colors. The two-element group $\mathfrak{S}_2$ acts on these graphs by switching the colors, and connected bipartite graphs are orbits of connected bicolored graphs under this action. From first principles we compute the $\mathfrak{S}_2$-cycle index for bicolored graphs, an extension of the ordinary cycle index, introduced by Henderson, that incorporates the $\mathfrak{S}_2$-action. From this we can compute the $\mathfrak{S}_2$-cycle index for connected bicolored graphs, and then the ordinary cycle index for connected bipartite graphs. The cycle index for connected bipartite graphs allows us, by standard techniques, to count unlabeled bipartite graphs and bipartite blocks.
Some Inequalities in Functional Analysis, Combinatorics, and Probability Theory
Authors: Feng Chunrong , Li Liangpan , Shen Jian
Published: January 2020

The main purpose of this paper is to show that many inequalities in functional analysis, probability theory and combinatorics are immediate corollaries of the best approximation theorem in inner product spaces. Besides, as applications of the de Caen-Selberg inequality, the finite field Kakeya and Nikodym problems are also studied.
Consecutive Patterns: From Permutations to Column-Convex Polyominoes and Back
Authors: Rawlings Don , Tiefenbruck Mark
Published: January 2020

We expose the ties between the consecutive pattern enumeration problems associated with permutations, compositions, column-convex polyominoes, and words. Our perspective allows powerful methods from the contexts of compositions, column-convex polyominoes, and of words to be applied directly to the enumeration of permutations by consecutive patterns. We deduce a host of new consecutive pattern results, including a solution to the $(2m+1)$-alternating pattern problem on permutations posed by Kitaev.
Ramsey Theory Applications
Authors: Rosta Vera
Published: January 2020

There are many interesting applications of Ramsey theory, these include results in number theory, algebra, geometry, topology, set theory, logic, ergodic theory, information theory and theoretical computer science. Relations of Ramsey-type theorems to various fields in mathematics are well documented in published books and monographs. The main objective of this survey is to list applications mostly in theoretical computer science of the last two decades not contained in these.
Rational Associahedra and Noncrossing Partitions
Authors: Armstrong Drew , Rhoades Brendon , Williams Nathan
Published: January 2020

Each positive rational number $x>0$ can be written uniquely as $x=a/(b-a)$ for coprime positive integers $0<a0$ a simplicial complex $\mathsf{Ass}(x)=\mathsf{Ass}(a,b)$ called the rational associahedron.  It is a pure simplicial complex of dimension $a-2$, and its maximal faces are counted by the rational Catalan number $$\mathsf{Cat}(x)=\mathsf{Cat}(a,b):=\frac{(a+b-1)!}{a!\,b!}.$$The cases $(a,b)=(n,n+1)$ and $(a,b)=(n,kn+1)$ recover the classical associahedron and its "Fuss-Catalan" generalization studied by Athanasiadis-Tzanaki and Fomin-Reading.  We prove that $\mathsf{Ass}(a,b)$ is shellable and give nice product formulas for its $h$-vector (the rational Narayana numbers) and $f$-vector (the rational Kirkman numbers).  We define $\mathsf{Ass}(a,b)$ via rational Dyck paths: lattice paths from $(0,0)$ to $(b,a)$ staying above the line $y = \frac{a}{b}x$.  We also use rational Dyck paths to define a rational generalization of noncrossing perfect matchings of $[2n]$.  In the case $(a,b) = (n, mn+1)$, our construction produces the noncrossing partitions of $[(m+1)n]$ in which each block has size $m+1$.
Colorful Subhypergraphs in Kneser Hypergraphs
Authors: Meunier Frédéric
Published: January 2020

Using a $\mathbb{Z}_q$-generalization of a theorem of Ky Fan, we extend to Kneser hypergraphs a theorem of Simonyi and Tardos that ensures the existence of multicolored complete bipartite graphs in any proper coloring of a Kneser graph. It allows to derive a lower bound for the local chromatic number of Kneser hypergraphs (using a natural definition of what can be the local chromatic number of a uniform hypergraph).
Semi-Degree Threshold for Anti-Directed Hamiltonian Cycles
Authors: DeBiasio Louis , Molla Theodore
Published: January 2020

In 1960 Ghouila-Houri extended Dirac's theorem to directed graphs by proving that if $D$ is a directed graph on $n$ vertices with minimum out-degree and in-degree at least $n/2$, then $D$ contains a directed Hamiltonian cycle. For directed graphs one may ask for other orientations of a Hamiltonian cycle and in 1980 Grant initiated the problem of determining minimum degree conditions for a directed graph $D$ to contain an anti-directed Hamiltonian cycle (an orientation in which consecutive edges alternate direction). We prove that for sufficiently large even $n$, if $D$ is a directed graph on $n$ vertices with minimum out-degree and in-degree at least $\frac{n}{2}+1$, then $D$ contains an anti-directed Hamiltonian cycle. In fact, we prove the stronger result that $\frac{n}{2}$ is sufficient unless $D$ is one of two counterexamples. This result is sharp.
Bounding Sequence Extremal Functions with Formations
Authors: Geneson Jesse , Prasad Rohil , Tidor Jonathan
Published: January 2020

An $(r, s)$-formation is a concatenation of $s$ permutations of $r$ letters. If $u$ is a sequence with $r$ distinct letters, then let $\mathit{Ex}(u, n)$ be the maximum length of any $r$-sparse sequence with $n$ distinct letters which has no subsequence isomorphic to $u$. For every sequence $u$ define $\mathit{fw}(u)$, the formation width of $u$, to be the minimum $s$ for which there exists $r$ such that there is a subsequence isomorphic to $u$ in every $(r, s)$-formation. We use $\mathit{fw}(u)$ to prove upper bounds on $\mathit{Ex}(u, n)$ for sequences $u$ such that $u$ contains an alternation with the same formation width as $u$.We generalize Nivasch's bounds on $\mathit{Ex}((ab)^{t}, n)$ by showing that $\mathit{fw}((12 \ldots l)^{t})=2t-1$ and $\mathit{Ex}((12\ldots l)^{t}, n) =n2^{\frac{1}{(t-2)!}\alpha(n)^{t-2}\pm O(\alpha(n)^{t-3})}$ for every $l \geq 2$ and $t\geq 3$, such that $\alpha(n)$ denotes the inverse Ackermann function. Upper bounds on $\mathit{Ex}((12 \ldots l)^{t} , n)$ have been used in other papers to bound the maximum number of edges in $k$-quasiplanar graphs on $n$ vertices with no pair of edges intersecting in more than $O(1)$ points.If $u$ is any sequence of the form $a v a v' a$ such that $a$ is a letter, $v$ is a nonempty sequence excluding $a$ with no repeated letters and $v'$ is obtained from $v$ by only moving the first letter of $v$ to another place in $v$, then we show that $\mathit{fw}(u)=4$ and $\mathit{Ex}(u, n) =\Theta(n\alpha(n))$. Furthermore we prove that $\mathit{fw}(abc(acb)^{t})=2t+1$ and $\mathit{Ex}(abc(acb)^{t}, n) = n2^{\frac{1}{(t-1)!}\alpha(n)^{t-1}\pm O(\alpha(n)^{t-2})}$ for every $t\geq 2$.
A Group Action on Derangements
Authors: Sun Hua , Wang Yi
Published: January 2020

In this paper we define a cyclic analogue of the MFS-action on derangements, and give a combinatorial interpretation of the expansion of the $n$-th derangement polynomial on the basis $\{q^k(1 + q)^{n-1-2k}, k = 0, 1,... , \lfloor (n-1)/2\rfloor \}$.
On Generalizations of the Petersen Graph and the Coxeter Graph
Authors: Orel Marko
Published: January 2020

In this note we consider two related infinite families of graphs, which generalize the Petersen and the Coxeter graph. The main result proves that these graphs are cores. It is determined which of these graphs are vertex/edge/arc-transitive or distance-regular. Girths and odd girths are computed. A problem on hamiltonicity is posed.A Corrigendum for this paper was added on August 19, 2017.