bluuebunny/crossref_metadata_2025_split huggingface dataset:
A Generalization of the $k$-Bonacci Sequence from Riordan Arrays
Authors: Ramírez José L. , Sirvent Víctor F. 
Published: January 2020

In this article, we introduce a family of weighted lattice paths, whose step set is $\{H=(1,0), V=(0,1), D_1=(1,1), \dots, D_{m-1}=(1,m-1)\}$. Using these lattice paths, we define a family of Riordan arrays whose sum on the rising diagonal is the $k$-bonacci sequence. This construction generalizes the Pascal and Delannoy Riordan arrays, whose sum on the rising diagonal is the Fibonacci and tribonacci sequence, respectively. From this family of Riordan arrays we introduce a generalized $k$-bonacci polynomial sequence, and we give a lattice path combinatorial interpretation of these polynomials. In particular, we find a combinatorial interpretation of tribonacci and tribonacci-Lucas polynomials.
Local Probabilities for Random Permutations Without Long Cycles
Authors: Manstavičius Eugenijus , Petuchovas Robertas 
Published: January 2020

We explore the probability $\nu(n,r)$ that a permutation sampled from the symmetric group of order $n!$ uniformly at random has no cycles of length exceeding $r$, where $1\leq r\leq n$ and $n\to\infty$. Asymptotic formulas valid in specified regions for the ratio $n/r$ are obtained using the saddle-point method combined with ideas originated in analytic number theory.
On a Conjecture of Thomassen
Authors: Delcourt Michelle , Ferber Asaf 
Published: January 2020

In 1989, Thomassen asked whether there is an integer-valued function $f(k)$ such that every $f(k)$-connected graph admits a spanning, bipartite $k$-connected subgraph. In this paper we take a first, humble approach, showing the conjecture is true up to a $\log n$ factor.
Exact Forbidden Subposet Results using Chain Decompositions of the Cycle
Authors: Methuku Abhishek , Tompkins Casey 
Published: January 2020

We introduce a method of decomposing the family of intervals along a cyclic permutation into chains to determine the size of the largest family of subsets of $[n]$ not containing one or more given posets as a subposet. De Bonis, Katona and Swanepoel determined the size of the largest butterfly-free family. We strengthen this result by showing that, for certain posets containing the butterfly poset as a subposet, the same bound holds. We also obtain the corresponding LYM-type inequalities.
Generalized Small Schröder Numbers
Authors: Huh JiSun , Park SeungKyung 
Published: January 2020

We study generalized small Schröder paths in the sense of arbitrary sizes of steps. A generalized small Schröder path is a generalized lattice path from $(0,0)$ to $(2n,0)$ with the step set of $\{(k,k), (l,-l), (2r,0)\, |\, k,l,r \in {\bf P}\}$, where ${\bf P}$ is the set of positive integers, which never goes below the $x$-axis, and with no horizontal steps at level 0. We find a bijection between 5-colored Dyck paths and generalized small Schröder paths, proving that the number of generalized small Schröder paths is equal to $\sum_{k=1}^{n} N(n,k)5^{n-k}$ for $n\geq 1$.
Simplicial Complexes of Whisker Type
Authors: Bigdeli Mina , Herzog Jürgen , Hibi Takayuki , Macchia Antonio 
Published: January 2020

Let $I\subset K[x_1,\ldots,x_n]$ be a zero-dimensional monomial ideal, and $\Delta(I)$ be the simplicial complex whose Stanley--Reisner ideal is the polarization of $I$. It follows from a result of Soleyman Jahan that $\Delta(I)$ is shellable. We give a new short proof of this fact by providing an explicit shelling. Moreover, we show that $\Delta(I)$ is even vertex decomposable. The ideal $L(I)$, which is defined to be the Stanley--Reisner ideal of the Alexander dual of $\Delta(I)$, has a linear resolution which is cellular and supported on a regular CW-complex. All powers of $L(I)$ have a linear resolution. We compute $\mathrm{depth}\ L(I)^k$ and show that $\mathrm{depth}\ L(I)^k=n$ for all $k\geq n$.
Dimensions of the Irreducible Representations of the Symmetric and Alternating Group
Authors: Debaene Korneel 
Published: January 2020

We establish the existence of an irreducible representation of $A_n$ whose dimension does not occur as the dimension of an irreducible representation of $S_n$, and vice versa. This proves a conjecture by Tong-Viet. The main ingredient in the proof is a result on large prime factors in short intervals.
The Topology of the External Activity Complex of a Matroid
Authors: Ardila Federico , Castillo Federico , Samper José Alejandro 
Published: January 2020

We prove that the external activity complex $\textrm{Act}_<(M)$ of a matroid is shellable. In fact, we show that every linear extension of LasVergnas's external/internal order $<_{ext/int}$ on $M$ provides a shelling of $\textrm{Act}_<(M)$. We also show that every linear extension of LasVergnas's internal order $<_{int}$ on $M$ provides a shelling of the independence complex $IN(M)$. As a corollary, $\textrm{Act}_<(M)$ and $M$ have the same $h$-vector. We prove that, after removing its cone points, the external activity complex is contractible if $M$ contains $U_{1,3}$ as a minor, and a sphere otherwise.
Lattices Related to Extensions of Presentations of Transversal Matroids
Authors: Bonin Joseph E. 
Published: January 2020

For a presentation $\mathcal{A}$ of a transversal matroid $M$, we study the ordered set $T_{\mathcal{A}}$ of single-element transversal extensions of $M$ that have presentations that extend $\mathcal{A}$; extensions are ordered by the weak order. We show that $T_{\mathcal{A}}$ is a distributive lattice, and that each finite distributive lattice is isomorphic to $T_{\mathcal{A}}$ for some presentation $\mathcal{A}$ of some transversal matroid $M$. We show that $T_{\mathcal{A}}\cap T_{\mathcal{B}}$, for any two presentations $\mathcal{A}$ and $\mathcal{B}$ of $M$, is a sublattice of both $T_{\mathcal{A}}$ and $T_{\mathcal{B}}$. We prove sharp upper bounds on $|T_{\mathcal{A}}|$ for presentations $\mathcal{A}$ of rank less than $r(M)$ in the order on presentations; we also give a sharp upper bound on $|T_{\mathcal{A}}\cap T_{\mathcal{B}}|$. The main tool we introduce to study $T_{\mathcal{A}}$ is the lattice $L_{\mathcal{A}}$ of closed sets of a certain closure operator on the lattice of subsets of $\{1,2,\ldots,r(M)\}$.
Flag Statistics from the Ehrhart $h^∗$-Polynomial of Multi-Hypersimplices
Authors: Han Guo-Niu , Josuat-Vergès Matthieu 
Published: January 2020

It is known that the normalized volume of standard hypersimplices (defined as some slices of the unit hypercube) are the Eulerian numbers. More generally, a recent conjecture of Stanley relates the Ehrhart series of hypersimplices with descents and excedences in permutations. This conjecture was proved by Nan Li, who also gave a generalization to colored permutations. In this article, we give another generalization to colored permutations, using the flag statistics introduced by Foata and Han. We obtain in particular a new proof of Stanley’s conjecture, and some combinatorial identities relating pairs of Eulerian statistics on colored permutations.
On Mixed Almost Moore Graphs of Diameter Two
Authors: López Nacho , Miret Josep M. 
Published: January 2020

Mixed almost Moore graphs appear in the context of the Degree/Diameter problem as a class of extremal mixed graphs, in the sense that their order is one less than the Moore bound for mixed graphs. The problem of their existence has been considered before for directed graphs and undirected ones, but not for the mixed case, which is a kind of generalization. In this paper we give some necessary conditions for the existence of mixed almost Moore graphs of diameter two derived from the factorization in $\mathbb{Q}[x]$ of their characteristic polynomial. In this context, we deal with the irreducibility of $\Phi_i(x^2+x-(r-1))$, where $\Phi_i(x)$ denotes the i-th cyclotomic polynomial.
Cyclic Sieving and Rational Catalan Theory
Authors: Bodnar Michelle , Rhoades Brendon 
Published: January 2020

Let $a < b$ be coprime positive integers. Armstrong, Rhoades, and Williams (2013) defined a set NC(a,b) of `rational noncrossing partitions', which form a subset of the ordinary noncrossing partitions of $\{1, 2, \dots, b-1\}$. Confirming a conjecture of Armstrong et. al., we prove that NC(a,b) is closed under rotation and prove an instance of the cyclic sieving phenomenon for this rotational action. We also define a rational generalization of the $\mathfrak{S}_a$-noncrossing parking functions of Armstrong, Reiner, and Rhoades.
On Almost-Regular Edge Colourings of Hypergraphs
Authors: Bryant Darryn 
Published: January 2020

We prove that if ${\cal{H}}=(V({\cal{H}}),{\cal{E}}({\cal{H}}))$ is a hypergraph, $\gamma$ is an edge colouring of ${\cal{H}}$, and $S\subseteq V({\cal{H}})$ such that any permutation of $S$ is an automorphism of ${\cal{H}}$, then there exists a permutation $\pi$ of ${\cal{E}}({\cal{H}})$ such that $|\pi(E)|=|E|$ and $\pi(E)\setminus S=E\setminus S$ for each $E\in{\cal{H}}({\cal{H}})$, and such that the edge colouring $\gamma'$ of ${\cal{H}}$ given by $\gamma'(E)=\gamma(\pi^{-1}(E))$ for each $E\in{\cal{E}}({\cal{H}})$ is almost regular on $S$. The proof is short and elementary. We show that a number of known results, such as Baranyai's Theorem on almost-regular edge colourings of complete $k$-uniform hypergraphs, are easy corollaries of this theorem.
Incidences with Curves in $\mathbb{R}^d$
Authors: Sharir Micha , Sheffer Adam , Solomon Noam 
Published: January 2020

We prove that the number of incidences between $m$ points and $n$ bounded-degree curves with $k$ degrees of freedom in ${\mathbb R}^d$ is\[ O\left(m^{\frac{k}{dk-d+1}+\varepsilon}n^{\frac{dk-d}{dk-d+1}}+ \sum_{j=2}^{d-1} m^{\frac{k}{jk-j+1}+\varepsilon}n^{\frac{d(j-1)(k-1)}{(d-1)(jk-j+1)}} q_j^{\frac{(d-j)(k-1)}{(d-1)(jk-j+1)}}+m+n\right),\]for any $\varepsilon>0$, where the constant of proportionality depends on $k, \varepsilon$ and $d$, provided that no $j$-dimensional surface of degree $\le c_j(k,d,\varepsilon)$, a constant parameter depending on $k$, $d$, $j$, and $\varepsilon$, contains more than $q_j$ input curves, and that the $q_j$'s satisfy certain mild conditions. This bound generalizes the well-known planar incidence bound of Pach and Sharir to $\mathbb{R}^d$. It generalizes a recent result of Sharir and Solomon concerning point-line incidences in four dimensions (where d=4 and k=2), and partly generalizes a recent result of Guth (as well as the earlier bound of Guth and Katz) in three dimensions (Guth's three-dimensional bound has a better dependency on $q_2$). It also improves a recent d-dimensional general incidence bound by Fox, Pach, Sheffer, Suk, and Zahl, in the special case of incidences with algebraic curves. Our results are also related to recent works by Dvir and Gopi and by Hablicsek and Scherr concerning rich lines in high-dimensional spaces. Our bound is not known to be tight in most cases.
Minimal Obstructions for Partial Representations of Interval Graphs
Authors: Klavik Pavel , Saumell Maria 
Published: January 2020

Interval graphs are intersection graphs of closed intervals. A generalization of recognition called partial representation extension was introduced recently. The input gives an interval graph with a partial representation specifying some pre-drawn intervals. We ask whether the remaining intervals can be added to create an extending representation. Two linear-time algorithms are known for solving this problem. In this paper, we characterize the minimal obstructions which make partial representations non-extendible. This generalizes Lekkerkerker and Boland's characterization of the minimal forbidden induced subgraphs of interval graphs. Each minimal obstruction consists of a forbidden induced subgraph together with at most four pre-drawn intervals. A Helly-type result follows: A partial representation is extendible if and only if every quadruple of pre-drawn intervals is extendible by itself. Our characterization leads to a linear-time certifying algorithm for partial representation extension.
Recurrence Relations for the Linear Transformation Preserving the Strong $q$-Log-Convexity
Authors: Liu Lily Li , Li Ya-Nan 
Published: January 2020

Let $[T(n,k)]_{n,k\geqslant0}$ be a triangle of positive numbers satisfying the three-term recurrence relation\[T(n,k)=(a_1n+a_2k+a_3)T(n-1,k)+(b_1n+b_2k+b_3)T(n-1,k-1).\]In this paper, we give a new sufficient condition for linear transformations\[Z_n(q)=\sum_{k=0}^{n}T(n,k)X_k(q)\]that preserves the strong $q$-log-convexity of polynomials sequences. As applications, we show linear transformations, given by matrices of the binomial coefficients, the Stirling numbers of the first kind and second kind, the Whitney numbers of the first kind and second kind, preserving the strong $q$-log-convexity in a unified manner.
Treelike Snarks
Authors: Abreu Marién , Kaiser Tomáš , Labbate Domenico , Mazzuoccolo Giuseppe 
Published: January 2020

We study snarks whose edges cannot be covered by fewer than five perfect matchings. Esperet and Mazzuoccolo found an infinite family of such snarks, generalising an example provided by Hägglund. We construct another infinite family, arising from a generalisation in a different direction. The proof that this family has the requested property is computer-assisted. In addition, we prove that the snarks from this family (we call them treelike snarks) have circular flow number $\phi_C (G)\ge5$ and admit a 5-cycle double cover.
Domination of the Rectangular Queen's Graph
Authors: Bozóki Sándor , Gál Péter , Marosi István , Weakley William D. 
Published: January 2020

The queens graph $Q_{m \times n}$ has the squares of the $m \times n$ chessboard as its vertices; two squares are adjacent if they are in the same row, column, or diagonal of the board. A set $D$ of squares of $Q_{m \times n}$ is a dominating set for $Q_{m \times n}$ if every square of $Q_{m \times n}$ is either in $D$ or adjacent to a square in $D$. The minimum size of a dominating set of $Q_{m \times n}$ is the domination number, denoted by $\gamma(Q_{m \times n})$.
Values of $\gamma(Q_{m \times n}), \, 4 \leq m \leq n \leq 18,\,$ are given here, in each case with a file of minimum dominating sets (often all of them, up to symmetry) in an online appendix. In these ranges for $m$ and $n$, monotonicity fails once: $\gamma(Q_{8\times 11}) = 6 > 5 = \gamma(Q_{9 \times 11}) = \gamma(Q_{10 \times 11}) = \gamma(Q_{11 \times 11})$.
Let $g(m)$ [respectively $g^{*}(m)$] be the largest integer such that $m$ queens suffice to dominate the $(m+1) \times g(m)$ board [respectively, to dominate the $(m+1) \times g^{*}(m)$ board with no two queens in a row]. Starting from the elementary bound $g(m) \leq 3m$, domination when the board is far from square is investigated. It is shown (Theorem 2) that $g(m) = 3m$ can only occur when $m \equiv 0, 1, 2, 3, \mbox{or } 4 \mbox{ (mod 9)}$, with an online appendix showing that this does occur for $m \leq 40, m \neq 3$. Also (Theorem 4), if $m \equiv 5, 6, \mbox{or } 7 \mbox{ (mod 9)}$ then $g^{*}(m) \leq 3m-2$, and if $m \equiv 8 \mbox{ (mod 9)}$ then $g^{*}(m) \leq 3m-4$. It is shown that equality holds in these bounds for $m \leq 40 $.
Lower bounds on $\gamma(Q_{m \times n})$ are given. In particular, if $m \leq n$ then $\gamma(Q_{m \times n}) \geq \min \{ m,\lceil (m+n-2)/4 \rceil \}$.
Two types of dominating sets (orthodox covers and centrally strong sets) are developed; each type is shown to give good upper bounds of $\gamma(Q_{m \times n})$ in several cases.
Three questions are posed: whether monotonicity of $\gamma(Q_{m \times n})$ holds (other than from $(m, n) = (8, 11)$ to $(9, 11)$), whether $\gamma(Q_{m \times n}) = (m+n-2)/4$ occurs with $m \leq n < 3m+2$ (other than for $(m, n) = (3, 3)$ and $(11, 11)$), and whether the lower bound given above can be improved.
A set of squares is independent if no two of its squares are adjacent. The minimum size of an independent dominating set of $Q_{m \times n}$ is the independent domination number, denoted by $i(Q_{m \times n})$. Values of $i(Q_{m \times n}), \, 4 \leq m \leq n \leq 18, \,$ are given here, in each case with some minimum dominating sets. In these ranges for $m$ and $n$, monotonicity fails twice: $i(Q_{8\times 11}) = 6 > 5 = i(Q_{9 \times 11}) = i(Q_{10 \times 11}) = i(Q_{11 \times 11})$, and $i(Q_{11 \times 18}) = 9 > 8 = i(Q_{12\times 18})$.
Topological Infinite Gammoids, and a New Menger-Type Theorem for Infinite Graphs
Authors: Carmesin Johannes 
Published: January 2020

Answering a question of Diestel, we develop a topological notion of gammoids in infinite graphs which, unlike traditional infinite gammoids, always define a matroid.As our main tool, we prove for any infinite graph $G$ with vertex-sets $A$ and $B$, if every finite subset of $A$ is linked to $B$ by disjoint paths, then the whole of $A$ can be linked to the closure of $B$ by disjoint paths or rays in a natural topology on $G$ and its ends.This latter theorem implies the topological Menger theorem of Diestel for locally finite graphs. It also implies a special case of the infinite Menger theorem of Aharoni and Berger.
Colorful Subhypergraphs in Uniform Hypergraphs
Authors: Alishahi Meysam 
Published: January 2020

There are several topological results ensuring in any properly colored graph the existence of a colorful complete bipartite subgraph, whose order is bounded from below by some topological invariants of some topological spaces associated to the graph. Meunier [Colorful subhypergraphs in Kneser hypergraphs, The Electronic Journal of Combinatorics, 2014] presented the first colorful type result for uniform hypergraphs. In this paper, we give some new generalizations of the $\mathbb{Z}_p$-Tucker lemma and by use of them, we improve Meunier's result and some other colorful results by Simonyi, Tardif, and Zsbán [Colourful theorems and indices of homomorphism complexes, The Electronic Journal of Combinatorics, 2014] and by Simonyi and Tardos [Colorful subgraphs in Kneser-like graphs, European Journal of Combinatorics, 2007] to uniform hypergraphs. Also, we introduce some new lower bounds for the chromatic number and local chromatic number of uniform hypergraphs. A hierarchy between these lower bounds is presented as well.
Matching Polytons
Authors: Doležal Martin , Hladký Jan 
Published: January 2020

Hladký, Hu, and Piguet [Tilings in graphons, preprint] introduced the notions of matching and fractional vertex covers in graphons. These are counterparts to the corresponding notions in finite graphs.
Combinatorial optimization studies the structure of the matching polytope and the fractional vertex cover polytope of a graph. Here, in analogy, we initiate the study of the structure of the set of all matchings and of all fractional vertex covers in a graphon. We call these sets the matching polyton and the fractional vertex cover polyton.
We also study properties of matching polytons and fractional vertex cover polytons along convergent sequences of graphons.
As an auxiliary tool of independent interest, we prove that a graphon is $r$-partite if and only if it contains no graph of chromatic number $r+1$. This in turn gives a characterization of bipartite graphons as those having a symmetric spectrum.
All or Nothing at All
Authors: D'Arco Paolo , Esfahani Navid Nasr , Stinson Douglas R. 
Published: January 2020

We continue a study of unconditionally secure all-or-nothing transforms (AONT) begun by Stinson (2001). An AONT is a bijective mapping that constructs $s$ outputs from $s$ inputs. We consider the security of $t$ inputs, when $s-t$ outputs are known. Previous work concerned the case $t=1$; here we consider the problem for general $t$, focussing on the case $t=2$. We investigate constructions of binary matrices for which the desired properties hold with the maximum probability. Upper bounds on these probabilities are obtained via a quadratic programming approach, while lower bounds can be obtained from combinatorial constructions based on symmetric BIBDs and cyclotomy. We also report some results on exhaustive searches and random constructions for small values of $s$.
Longest Monotone Subsequences and Rare Regions of Pattern-Avoiding Permutations
Authors: Madras Neal , Yıldırım Gökhan 
Published: January 2020

We consider the distributions of the lengths of the longest monotone and alternating subsequences in classes of permutations of size $n$ that avoid a specific pattern or set of patterns, with respect to the uniform distribution on each such class. We obtain exact results for any class that avoids two patterns of length 3, as well as results for some classes that avoid one pattern of length 4 or more. In our results, the longest monotone subsequences have expected length proportional to $n$ for pattern-avoiding classes, in contrast with the $\sqrt n$ behaviour that holds for unrestricted permutations. In addition, for a pattern $\tau$ of length $k$, we scale the plot of a random $\tau$-avoiding permutation down to the unit square and study the "rare region", which is the part of the square that is exponentially unlikely to contain any points. We prove that when $\tau_1>\tau_k$, the complement of the rare region is a closed set that contains the main diagonal of the unit square. For the case $\tau_1=k,$ we also show that the lower boundary of the part of the rare region above the main diagonal is a curve that is Lipschitz continuous and strictly increasing on $[0,1]$.
On Spherical Designs of Some Harmonic Indices
Authors: Zhu Yan , Bannai Eiichi , Bannai Etsuko , Kim Kyoung-Tark , Yu Wei-Hsuan 
Published: January 2020

A finite subset $Y$ on the unit sphere $S^{n-1} \subseteq \mathbb{R}^n$ is called a spherical design of harmonic index $t$, if the following condition is satisfied: $\sum_{\mathbf{x}\in Y}f(\mathbf{x})=0$ for all real homogeneous harmonic polynomials $f(x_1,\ldots,x_n)$ of degree $t$. Also, for a subset $T$ of $\mathbb{N} = \{1,2,\cdots \}$, a finite subset $Y \subseteq S^{n-1}$ is called a spherical design of harmonic index $T,$ if $\sum_{\mathbf{x}\in Y}f(\mathbf{x})=0$ is satisfied for all real homogeneous harmonic polynomials $f(x_1,\ldots,x_n)$ of degree $k$ with $k\in T$.In the present paper we first study Fisher type lower bounds for the sizes of spherical designs of harmonic index $t$ (or for harmonic index $T$). We also study `tight' spherical designs of harmonic index $t$ or index $T$. Here `tight' means that the size of $Y$ attains the lower bound for this Fisher type inequality. The classification problem of tight spherical designs of harmonic index $t$ was started by Bannai-Okuda-Tagami (2015), and the case $t = 4$ was completed by Okuda-Yu (2016). In this paper we show the classification (non-existence) of tight spherical designs of harmonic index 6 and 8, as well as the asymptotic non-existence of tight spherical designs of harmonic index $2e$ for general $e\geq 3$. We also study the existence problem for tight spherical designs of harmonic index $T$ for some $T$, in particular, including index $T = \{8,4\}$.
Forbidden Berge Hypergraphs
Authors: Anstee R. P. , Salazar Santiago 
Published: January 2020

A simple matrix is a (0,1)-matrix with no repeated columns. For a (0,1)-matrix $F$, we say that a (0,1)-matrix $A$ has $F$ as a Berge hypergraph if there is a submatrix $B$ of $A$ and some row and column permutation of $F$, say $G$, with $G\le B$. Letting $\|A\|$ denote the number of columns in $A$, we define the extremal function $\mathrm{Bh}(m,{ F})=\max\{\|A\|\,:\, A \hbox{ }m\hbox{-rowed simple matrix and no Berge hypergraph }F\}$. We determine the asymptotics of $\mathrm{Bh}(m,F)$ for all $3$- and $4$-rowed $F$ and most $5$-rowed $F$. For certain $F$, this becomes the problem of determining the maximum number of copies of $K_r$ in a $m$-vertex graph that has no $K_{s,t}$ subgraph, a problem studied by Alon and Shikhelman.