bluuebunny/crossref_metadata_2025_split huggingface dataset:
On Cross-Intersecting Families of Set Partitions
Authors: Ku Cheng Yeaw , Wong Kok Bin 
Published: January 2020

Let $\mathcal{B}(n)$ denote the collection of all set partitions of $[n]$. Suppose $\mathcal A_1,\mathcal A_2\subseteq \mathcal{B}(n)$ are cross-intersecting i.e. for all $A_1\in \mathcal A_1$ and $A_2\in \mathcal A_2$, we have $A_1\cap A_2\neq\varnothing$. It is proved that for sufficiently large $n$,\[ \vert \mathcal A_1\vert\vert \mathcal A_2\vert\leq B_{n-1}^2\]where $B_{n}$ is the $n$-th Bell number. Moreover, equality holds if and only if $\mathcal{A}_1=\mathcal A_2$ and $\mathcal A_1$ consists of all set partitions with a fixed singleton.
Self-Dual Interval Orders and Row-Fishburn Matrices
Authors: Yan Sherry H. F. , Xu Yuexiao 
Published: January 2020

Recently, Jelínek derived that the number of self-dual interval orders of reduced size $n$ is twice the number of row-Fishburn matrices of size $n$ by using generating functions. In this paper, we present a bijective proof of this relation by establishing a bijection between two variations of upper-triangular matrices of nonnegative integers. Using the bijection, we provide a combinatorial proof of the refined relations between self-dual Fishburn matrices and row-Fishburn matrices in answer to a problem proposed by Jelínek.
Graph Labelings and Continuous Factors of Dynamical Systems
Authors: Shea Stephen M. 
Published: January 2020

A labeling of a graph is a function from the vertex set of the graph to some finite set. Certain dynamical systems (such as topological Markov shifts) can be defined by directed graphs. In these instances, a labeling of the graph defines a continuous, shift-commuting factor of the dynamical system. We find sufficient conditions on the labeling to imply classification results for the factor dynamical system. We define the topological entropy of a (directed or undirected) graph and its labelings in a way that is analogous to the definition of topological entropy for a shift space in symbolic dynamics. We show, for example, if $G$ is a perfect graph, all proper $\chi(G)$-colorings of $G$ have the same entropy, where $\chi(G)$ is the chromatic number of $G$.
Block Designs with SDP Parameters
Authors: Ward Harold 
Published: January 2020

It is traditional to call a quasi-symmetric design with certain parameters an SDP design if the symmetric difference of two different blocks is either a block or a block complement. In this note, we delete the requirements on the parameters and demand just that the symmetric difference of two blocks be a block, a block complement, or either the empty set or the whole point set. We obtain the parameters of such designs and use the result to prove Kantor's theorem on the parameters of a symmetric SDP design. A spin-off of an exponential Diophantine equation considered by Ramanujan is at the core.
A Short Proof of the Odd-Girth Theorem
Authors: Van Dam Edwin R. , Fiol Miquel Angel 
Published: January 2020

Recently, it has been shown that a connected graph $\Gamma$ with $d+1$ distinct eigenvalues and odd-girth $2d+1$ is distance-regular. The proof of this result was based on the spectral excess theorem. In this note we present an alternative and more direct proof which does not rely on the spectral excess theorem, but on a known characterization of distance regular graphs in terms of the predistance polynomial of degree $d$.
Structure of Colored Complete Graphs Free of Proper Cycles
Authors: Coll Vincent , Magnant Colton , Ryan Kathleen 
Published: January 2020

For a fixed integer $m$, we consider edge colorings of complete graphs which contain no properly edge colored cycle $C_{m}$ as a subgraph. Within colorings free of these subgraphs, we establish global structure by bounding the number of colors that can induce a spanning and connected subgraph. In the case of smaller cycles, namely $C_4,C_5$, and $C_6$, we show that our bounds are sharp.
Distance Powers and Distance Matrices of Integral Cayley Graphs over Abelian Groups
Authors: Klotz Walter , Sander Torsten 
Published: January 2020

It is shown that distance powers of an integral Cayley graph over an abelian group $\Gamma$ are again integral Cayley graphs over $\Gamma$. Moreover, it is proved that distance matrices of integral Cayley graphs over abelian groups have integral spectrum.
Sum and Shifted-Product Subsets of Product-Sets over Finite Rings
Authors: Le Anh Vinh 
Published: January 2020

For sufficiently large subsets $\mathcal{A}, \mathcal{B}, \mathcal{C}, \mathcal{D}$ of $\mathbb{F}_q$, Gyarmati and Sárközy (2008) showed the solvability of the equations $a + b= c d$ and $a b + 1 = c d$ with $a \in \mathcal{A}$, $b \in\mathcal{B}$, $c \in \mathcal{C}$, $d \in \mathcal{D}$. They asked whether one can extend these results to every $k \in \mathbb{N}$ in the following way: for large subsets $\mathcal{A}, \mathcal{B}, \mathcal{C}, \mathcal{D}$ of $\mathbb{F}_q$, there are $a_1, \ldots, a_k, a_1', \ldots, a_k' \in\mathcal{A}$, $b_1, \ldots, b_k, b_1', \ldots, b_k' \in \mathcal{B}$ with $a_i + b_j, a_i' b_j' + 1 \in \mathcal{C}\mathcal{D}$ (for $1 \leq i, j\leq k)$. The author (2010) gave an affirmative answer to this question using Fourier analytic methods. In this paper, we will extend this result to the setting of finite cyclic rings using tools from spectral graph theory.
Extremal Hypergraphs for the Biased Erdős-Selfridge Theorem
Authors: Sundberg Eric Lars 
Published: January 2020

A positional game is essentially a generalization of Tic-Tac-Toe played on a hypergraph $(V,{\cal F}).$ A pivotal result in the study of positional games is the Erdős–Selfridge theorem, which gives a simple criterion for the existence of a Breaker's winning strategy on a finite hypergraph ${\cal F}$. It has been shown that the bound in the Erdős–Selfridge theorem can be tight and that numerous extremal hypergraphs exist that demonstrate the tightness of the bound. We focus on a generalization of the Erdős–Selfridge theorem proven by Beck for biased $(p:q)$ games, which we call the $(p:q)$–Erdős–Selfridge theorem. We show that for $pn$-uniform hypergraphs there is a unique extremal hypergraph for the $(p:q)$–Erdős–Selfridge theorem when $q\geq 2$.
The Maximal Number of Runs in Standard Sturmian Words
Authors: Baturo Paweł , Piątkowski Marcin , Rytter Wojciech 
Published: January 2020

We investigate some repetition problems for a very special class $\mathcal{S}$ of strings called the standard Sturmian words, which have very compact representations in terms of sequences of integers. Usually the size of this word is exponential with respect to the size of its integer sequence, hence we are dealing with repetition problems in compressed strings. An explicit formula is given for the number $\rho(w)$ of runs in a standard word $w$. We show that $\rho(w)/|w|\le 4/5$ for each $w\in S$, and there is an infinite sequence of strictly growing words $w_k\in {\mathcal{S}}$ such that $\lim_{k\rightarrow \infty} \frac{\rho(w_k)}{|w_k|} = \frac{4}{5}$. Moreover, we show how to compute the number of runs in a standard Sturmian word in linear time with respect to the size of its compressed representation.
Expected Patterns in Permutation Classes
Authors: Homberger Cheyne 
Published: January 2020

Each length $k$ pattern occurs equally often in the set $S_n$ of all permutations of length $n$, but the same is not true in general for a proper subset of $S_n$. Miklós Bóna recently proved that if we consider the set of $n$-permutations avoiding the pattern 132, all other non-monotone patterns of length 3 are equally common. In this paper we focus on the set $\operatorname{Av}_n (123)$ of $n$-permutations avoiding $123$, and give exact formulae for the occurrences of each length 3 pattern. While this set does not have the same symmetries as $\operatorname{Av}_n (132)$, we find several similarities between the two and prove that the number of 231 patterns is the same in each.
Biregular Cages of Girth Five
Authors: Abreu Marién , Araujo-Pardo Gabriela , Balbuena Camino , Labbate Domenico , López-Chávez Gloria 
Published: January 2020

Let $2 \le r < m$ and $g$ be positive integers. An $(\{r,m\};g)$-graph (or biregular graph) is a graph with degree set $\{r,m\}$ and girth $g$, and an $(\{r,m\};g)$-cage (or biregular cage) is an $(\{r,m\};g)$-graph of minimum order $n(\{r,m\};g)$. If $m=r+1$, an $(\{r,m\};g)$-cage is said to be a semiregular cage.In this paper we generalize the reduction and graph amalgam operations from [M. Abreu, G. Araujo-Pardo, C. Balbuena, D. Labbate. Families of Small Regular Graphs of Girth $5$. Discrete Math. 312 (2012) 2832--2842] on the incidence graphs of an affine and a biaffine plane obtaining two new infinite families of biregular cages and two new semiregular cages. The constructed new families are $(\{r,2r-3\};5)$-cages for all $r=q+1$ with $q$ a prime power, and $(\{r,2r-5\};5)$-cages for all $r=q+1$ with $q$ a prime. The new semiregular cages are constructed for $r=5$ and $6$ with $31$ and $43$ vertices respectively.
Directed Animals, Quadratic Systems and Rewriting Systems
Authors: Marckert Jean-François 
Published: January 2020

A directed animal is a percolation cluster in the directed site percolation model. The aim of this paper is to exhibit a strong relation between the problem of computing the generating function G of directed animals on the square lattice, counted according to the area and the perimeter, and the problem of solving a system of quadratic equations involving unknown matrices. We present some solid evidence that some infinite explicit matrices, the fixed points of a rewriting like system are the natural solutions to this system of equations: some strong evidence is given that the problem of finding G reduces to the problem of finding an eigenvector to an explicit infinite matrix. Similar properties are shown for other combinatorial questions concerning directed animals, and for different lattices.
A Note on Automorphisms of the Infinite-Dimensional Hypercube Graph
Authors: Pankov Mark 
Published: January 2020

We define the infinite-dimensional hypercube graph $H_{{\aleph}_{0}}$ as a graph whose vertex set is formed by the so-called singular subsets of ${\mathbb Z}\setminus\{0\}$. This graph is not connected, but it has isomorphic connected components. We show that the restrictions of its automorphisms to the connected components are induced by permutations on ${\mathbb Z}\setminus\{0\}$ preserving the family of singular subsets. As an application, we describe the automorphism group of the connected components.
Enumeration of (16,4,16,4) Relative Difference Sets
Authors: Clark David , Tonchev Vladimir D. 
Published: January 2020

A complete enumeration of relative difference sets (RDS) with parameters $(16,4,16,4)$ in a group of order 64 with a normal subgroup $N$ of order 4 is given. If $N=Z_4$, three of the 11 abelian groups of order 64, and 23 of the 256 nonabelian groups of order 64 contain $(16,4,16,4)$ RDSs. If $N=Z_2 \times Z_2$, nine of the abelian groups and 194 of the non-abelian groups of order 64 contain $(16,4,16,4)$ RDSs.
Edge-Disjoint Induced Subgraphs with Given Minimum Degree
Authors: Yuster Raphael 
Published: January 2020

Let $h$ be a given positive integer. For a graph with $n$ vertices and $m$ edges, what is the maximum number of pairwise edge-disjoint {\em induced} subgraphs, each having minimum degree at least $h$? There are examples for which this number is $O(m^2/n^2)$. We prove that this bound is achievable for all graphs with polynomially many edges. For all $\epsilon > 0$, if $m \ge n^{1+\epsilon}$, then there are always $\Omega(m^2/n^2)$ pairwise edge-disjoint induced subgraphs, each having minimum degree at least $h$. Furthermore, any two subgraphs intersect in an independent set of size at most $1+ O(n^3/m^2)$, which is shown to be asymptotically optimal.
On the Relationship between Pipe Dreams and Permutation Words
Authors: Marcott Cameron 
Published: January 2020

Pipe dreams represent permutations pictorially as a series of crossing pipes. Recent applications of pipe dreams include the calculation of Schubert polynomials, fillings of moon polyominoes, and in the combinatorics of antidiagonal simplicial complexes. These applications associate pipe dreams to words of elementary symmetric transpositions via a canonical mapping. However, this canonical mapping is by no means the only way of mapping pipe dreams to permutation words. We define sensical mappings from pipe dreams to words and prove sensical mappings are in bijection with standard shifted tableaux of triangular shape. We characterize the set of pipe dreams associated to a given word (under any sensical map) using step ladder moves. These moves induce a partial order on the set of pipe dreams mapping to a given word, yielding a distributive lattice.
Extremal Values of Ratios: Distance Problems vs. Subtree Problems in Trees
Authors: Székely László , Wang Hua 
Published: January 2020

The authors discovered a dual behaviour of two tree indices, the Wiener index and the number of subtrees, for a number of extremal problems [Discrete Appl. Math. 155 (3) 2006, 374-385; Adv. Appl. Math. 34 (2005), 138-155]. Barefoot, Entringer and Székely [Discrete Appl. Math. 80 (1997), 37-56] determined extremal values of $\sigma_T(w)/\sigma_T(u)$, $\sigma_T(w)/\sigma_T(v)$, $\sigma(T)/\sigma_T(v)$, and $\sigma(T)/\sigma_T(w)$, where $T$ is a tree on $n$ vertices, $v$ is in the centroid of the tree $T$, and $u,w$ are leaves in $T$.In this paper we test how far the negative correlation between distances and subtrees go if we look for the extremal values of $F_T(w)/F_T(u)$, $F_T(w)/F_T(v)$, $F(T)/F_T(v)$, and $F(T)/F_T(w)$, where $T$ is a tree on $n$ vertices, $v$ is in the subtree core of the tree $T$, and $u,w$ are leaves in $T$-the complete analogue of [Discrete Appl. Math. 80 (1997), 37-56], changing distances to the number of subtrees. We include a number of open problems, shifting the interest towards the number of subtrees in graphs.
On the Number of Nonequivalent Propelinear Extended Perfect Codes
Authors: Borges Joaquim , Mogilnykh Ivan Yu. , Rifà Josep , Solov'eva Faina I. 
Published: January 2020

The paper proves that there exists an exponential number of nonequivalent propelinear extended perfect binary codes of length growing to infinity. Specifically, it is proved that all transitive extended perfect binary codes found by Potapov (2007) are propelinear. All such codes have small rank, which is one more than the rank of the extended Hamming code of the same length. We investigate the properties of these codes and show that any of them has a normalized propelinear representation.
Distance-Regular Graphs with an Eigenvalue $-k < \theta \leq 2-k$
Authors: Bang Sejeong 
Published: January 2020

It is known that bipartite distance-regular graphs with diameter $D\geq 3$, valency $k\geq 3$, intersection number $c_2\geq 2$ and eigenvalues $k = \theta_0 > \theta_1 > \cdots > \theta_D$ satisfy $\theta_1\leq k-2$ and thus $\theta_{D-1}\geq 2-k$. In this paper we classify non-complete distance-regular graphs with valency $k\geq 2$, intersection number $c_2\geq 2$ and an eigenvalue $\theta$ satisfying $-k< \theta \leq 2-k$. Moreover, we give a lower bound for valency $k$ which implies $\theta_D \geq 2-k$ for distance-regular graphs with girth $g\geq 5$ satisfying $g=5$ or $ g \equiv 3~(\operatorname{mod}~4)$.
Linked Partitions and Permutation Tableaux
Authors: Chen William Y.C. , Liu Lewis H. , Wang Carol J. 
Published: January 2020

Linked partitions were introduced by Dykema in the study of transforms in free probability theory, whereas permutation tableaux were introduced by Steingrímsson and Williams in the study of totally positive Grassmannian cells. Let $[n]=\{1,2,\ldots,n\}$. Let $L(n,k)$ denote the set of linked partitions of $[n]$ with $k$ blocks, let $P(n,k)$ denote the set of permutations of $[n]$ with $k$ descents, and let $T(n,k)$ denote the set of permutation tableaux of length $n$ with $k$ rows. Steingrímsson and Williams found a bijection between the set of permutation tableaux of length $n$ with $k$ rows and the set of permutations of $[n]$ with $k$ weak excedances. Corteel and Nadeau gave a bijection between the set of permutation tableaux of length $n$ with $k$ columns and the set of permutations of $[n]$ with $k$ descents. In this paper, we establish a bijection between $L(n,k)$ and $P(n,k-1)$ and a bijection between $L(n,k)$ and $T(n,k)$. Restricting the latter bijection to noncrossing linked partitions and nonnesting linked partitions, we find that the corresponding permutation tableaux can be characterized by pattern avoidance.
On the Number of Colored Birch and Tverberg Partitions
Authors: Hell Stephan 
Published: January 2020

In 2009, Blagojević, Matschke, and Ziegler established the first tight colored Tverberg theorem. We develop a colored version of our previous results (2008): Evenness and non-trivial lower bounds for the number of colored Tverberg partitions. Both properties follow from similar results on the number of colored Birch partitions.
The Ramsey Number $R(3,K_{10}-e)$ and Computational Bounds for $R(3,G)$
Authors: Goedgebeur Jan , Radziszowski Stanisław P. 
Published: January 2020

Using computer algorithms we establish that the Ramsey number $R(3,K_{10}-e)$ is equal to 37, which solves the smallest open case for Ramsey numbers of this type. We also obtain new upper bounds for the cases of $R(3,K_k-e)$ for $11 \le k \le 16$, and show by construction a new lower bound $55 \le R(3,K_{13}-e)$.The new upper bounds on $R(3,K_k-e)$ are obtained by using the values and lower bounds on $e(3,K_l-e,n)$ for $l \le k$, where $e(3,K_k-e,n)$ is the minimum number of edges in any triangle-free graph on $n$ vertices without $K_k-e$ in the complement. We complete the computation of the exact values of $e(3,K_k-e,n)$ for all $n$ with $k \leq 10$ and for $n \leq 34$ with $k = 11$, and establish many new lower bounds on $e(3,K_k-e,n)$ for higher values of $k$.Using the maximum triangle-free graph generation method, we determine two other previously unknown Ramsey numbers, namely $R(3,K_{10}-K_3-e)=31$ and $R(3,K_{10}-P_3-e)=31$. For graphs $G$ on 10 vertices, besides $G=K_{10}$, this leaves 6 open cases of the form $R(3,G)$. The hardest among them appears to be $G=K_{10}-2K_2$, for which we establish the bounds $31 \le R(3,K_{10}-2K_2) \le 33$.
The Expected Characteristic and Permanental Polynomials of the Random Gram Matrix
Authors: Martin Jacob G. , Canfield E. Rodney 
Published: January 2020

A $t \times n$ random matrix $A$ can be formed by sampling $n$ independent random column vectors, each containing $t$ components. The random Gram matrix of size $n$, $G_{n}=A^{T}A$, contains the dot products between all pairs of column vectors in the randomly generated matrix $A$, and has characteristic roots coinciding with the singular values of $A$. Furthermore, the sequences $\det{(G_{i})}$ and $\text{perm}(G_{i})$ (for $i = 0, 1, \dots, n$) are factors that comprise the expected coefficients of the characteristic and permanental polynomials of $G_{n}$. We prove theorems that relate the generating functions and recursions for the traces of matrix powers, expected characteristic coefficients, expected determinants $E(\det{(G_{n})})$, and expected permanents $E(\text{perm}(G_{n}))$ in terms of each other. Using the derived recursions, we exhibit the efficient computation of the expected determinant and expected permanent of a random Gram matrix $G_{n}$, formed according to any underlying distribution. These theoretical results may be used both to speed up numerical algorithms and to investigate the numerical properties of the expected characteristic and permanental coefficients of any matrix comprised of independently sampled columns.
On Counterexamples to a Conjecture of Wills and Ehrhart Polynomials whose Roots have Equal Real Parts
Authors: Henze Matthias 
Published: January 2020

As a discrete analog to Minkowski's theorem on convex bodies, Wills conjectured that the Ehrhart coefficients of a $0$-symmetric lattice polytope with exactly one interior lattice point are maximized by those of the cube of side length two. We discuss several counterexamples to this conjecture and, on the positive side, we identify a family of lattice polytopes that fulfill the claimed inequalities. This family is related to the recently introduced class of $l$-reflexive polytopes.
Genus Ranges of 4-Regular Rigid Vertex Graphs
Authors: Buck Dorothy , Dolzhenko Egor , Jonoska Natasa , Saito Masahico , Valencia Karin 
Published: January 2020

A rigid vertex of a graph is one that has a prescribed cyclic order of its incident edges. We study orientable genus ranges of 4-regular rigid vertex graphs. The (orientable) genus range is a set of genera values over all orientable surfaces into which a graph is embedded cellularly, and the embeddings of rigid vertex graphs are required to preserve the prescribed cyclic order of incident edges at every vertex. The genus ranges of 4-regular rigid vertex graphs are sets of consecutive integers, and we address two questions: which intervals of integers appear as genus ranges of such graphs, and what types of graphs realize a given genus range. For graphs with $2n$ vertices ($n>1$), we prove that all intervals $[a, b]$ for all $a<b \leq n$, and singletons $[h, h]$ for some $h\leq n$, are realized as genus ranges. For graphs with $2n-1$ vertices ($n\geq 1$), we prove that all intervals $[a, b]$ for all $a<b \leq n$ except $[0,n]$, and $[h,h]$ for some $h\leq n$, are realized as genus ranges. We also provide constructions of graphs that realize these ranges.
Conditions for the Parameters of the Block Graph of Quasi-Symmetric Designs
Authors: Pawale Rajendra M. , Shrikhande Mohan S. , Nyayate Shubhada M. 
Published: January 2020

A quasi-symmetric design (QSD) is a 2-$(v,k,\lambda)$ design with intersection numbers $x$ and $y$ with $x< y$. The block graph of such a design is formed on its blocks with two distinct blocks being adjacent if they intersect in $y$ points. It is well known that the block graph of a QSD is a strongly regular graph (SRG) with parameters $(b,a,c,d)$ with smallest eigenvalue $ -m =-\frac{k-x}{y-x}$.The classification result of SRGs with smallest eigenvalue $-m$, is used to prove that for a fixed pair $(\lambda\ge 2,m\ge 2)$, there are only finitely many QSDs. This gives partial support towards Marshall Hall Jr.'s conjecture, that for a fixed $\lambda\ge 2$, there exist finitely many symmetric $(v, k, \lambda)$-designs.We classify QSDs with $m=2$ and characterize QSDs whose block graph is the complete multipartite graph with $s$ classes of size $3$. We rule out the possibility of a QSD whose block graph is the Latin square graph $LS_m (n)$ or complement of $LS_m (n)$, for $m=3,4$.SRGs with no triangles have long been studied and are of current research interest. The characterization of QSDs with triangle-free block graph for $x=1$ and $y=x+1$ is obtained and the non-existence of such designs with $x=0$ or $\lambda > 2(x+2)$ or if it is a $3$-design is proven. The computer algebra system Mathematica is used to find parameters of QSDs with triangle-free block graph for $2\le m \le 100$. We also give the parameters of QSDs whose block graph parameters are $(b,a,c,d)$ listed in Brouwer's table of SRGs.
Fan-Extensions in Fragile Matroids
Authors: Chun Carolyn , Chun Deborah , Mayhew Dillon , Van Zwam Stefan H. M. 
Published: January 2020

If $\mathcal{S}$ is a set of matroids, then the matroid $M$ is $\mathcal{S}$-fragile if, for every element $e\in E(M)$, either $M\backslash e$ or $M/e$ has no minor isomorphic to a member of $\mathcal{S}$. Excluded-minor characterizations often depend, implicitly or explicitly, on understanding classes of fragile matroids. In certain cases, when $\mathcal{M}$ is a minor-closed class of $\mathcal{S}$-fragile matroids, and $N\in \mathcal{M}$, the only members of $\mathcal{M}$ that contain $N$ as a minor are obtained from $N$ by increasing the length of fans. We prove that if this is the case, then we can certify it with a finite case-analysis. The analysis involves examining matroids that are at most two elements larger than $N$.