bluuebunny/crossref_metadata_2025_split huggingface dataset:
Extensions of Infinite Partition Regular Systems
Authors: Hindman Neil , Leader Imre , Strauss Dona 
Published: January 2020

A finite or infinite matrix $A$ with rational entries (and only finitely many non-zero entries in each row) is called image partition regular if, whenever the natural numbers are finitely coloured, there is a vector $x$, with entries in the natural numbers, such that $Ax$ is monochromatic. Many of the classicial results of Ramsey theory are naturally stated in terms of image partition regularity.Our aim in this paper is to investigate maximality questions for image partition regular matrices. When is it possible to add rows on to $A$ and remain image partition regular? When can one add rows but `nothing new is produced'? What about adding rows and also new variables? We prove some results about extensions of the most interesting infinite systems, and make several conjectures.Our most surprising positive result is a compatibility result for Milliken-Taylor systems, stating that (in many cases) one may adjoin one Milliken-Taylor system to a translate of another and remain image partition regular. This is in contrast to earlier results, which had suggested a strong inconsistency between different Milliken-Taylor systems. Our main tools for this are some algebraic properties of $\beta {\mathbb N}$, the Stone-Čech compactification of the natural numbers.
Invariant Tensors and the Cyclic Sieving Phenomenon
Authors: Westbury Bruce W. 
Published: January 2020

We construct a large class of examples of the cyclic sieving phenomenon by exploiting the representation theory of semi-simple Lie algebras. Let $M$ be a finite dimensional representation of a semi-simple Lie algebra and let $B$ be the associated Kashiwara crystal. For $r\ge 0$, the triple $(X,c,P)$ which exhibits the cyclic sieving phenomenon is constructed as follows: the set $X$ is the set of isolated vertices in the crystal $\otimes^rB$; the map $c\colon X\rightarrow X$ is a generalisation of promotion acting on standard tableaux of rectangular shape and the polynomial $P$ is the fake degree of the Frobenius character of a representation of $\mathfrak{S}_r$ related to the natural action of $\mathfrak{S}_r$ on the subspace of invariant tensors in $\otimes^rM$. Taking $M$ to be the defining representation of $\mathrm{SL}(n)$ gives the cyclic sieving phenomenon for rectangular tableaux.
Zeros of Jones Polynomials of Graphs
Authors: Dong Fengming , Jin Xian'an 
Published: January 2020

In this paper, we introduce the Jones polynomial of a graph $G=(V,E)$ with $k$ components as the following specialization of the Tutte polynomial:$$J_G(t)=(-1)^{|V|-k}t^{|E|-|V|+k}T_G(-t,-t^{-1}).$$We first study its basic properties and determine certain extreme coefficients. Then we prove that $(-\infty, 0]$ is a zero-free interval of Jones polynomials of connected bridgeless graphs while for any small $\epsilon>0$ or large $M>0$, there is a zero of the Jones polynomial of a plane graph in $(0,\epsilon)$, $(1-\epsilon,1)$, $(1,1+\epsilon)$ or $(M,+\infty)$. Let $r(G)$ be the maximum moduli of zeros of $J_G(t)$. By applying Sokal's result on zeros of Potts model partition functions and Lucas's theorem, we prove that\begin{eqnarray*}{q_s-|V|+1\over |E|}\leq r(G)<1+6.907652\Delta_G\end{eqnarray*}for any connected bridgeless and loopless graph $G=(V,E)$ of maximum degree $\Delta_G$ with $q_s$ parallel classes. As a consequence of the upper bound, X.-S. Lin's conjecture holds if the positive checkerboard graph of a connected alternating link has a fixed maximum degree and a sufficiently large number of edges.
Subspaces Intersecting Each Element of a Regulus in One Point, André-Bruck-Bose Representation and Clubs
Authors: Lavrauw Michel , Zanella Corrado 
Published: January 2020

In this paper results are proved with applications to the orbits of $(n-1)$-dimensional subspaces disjoint from a regulus $\mathcal{R}$ of $(n-1)$-subspaces in $\mathrm{PG}(2n-1,q)$, with respect to the subgroup of $\mathrm{PGL}(2n,q)$ fixing $\mathcal{R}$. Such results have consequences on several aspects of finite geometry. First of all, a necessary condition for an $(n-1)$-subspace $U$ and a regulus $\mathcal{R}$ of $(n-1)$-subspaces to be extendable to a Desarguesian spread is given. The description also allows to improve results of Barwick and Jackson on the André -Bruck-Bose representation of a $q$-subline in $\mathrm{PG}(2,q^n)$. Furthermore, the results in this paper are applied to the classification of linear sets, in particular clubs.
On the Density of Certain Languages with $p^2$ Letters
Authors: Segovia Carlos , Winklmeier Monika 
Published: January 2020

The sequence $(x_n)_{n\in\mathbb N} = (2,5,15,51,187,\ldots)$ given by the rule $x_n=(2^n+1)(2^{n-1}+1)/3$ appears in several seemingly unrelated areas of mathematics. For example, $x_n$ is the density of a language of words of length $n$ with four different letters. It is also the cardinality of the quotient of $(\mathbb Z_2\times \mathbb Z_2)^n$ under the left action of the special linear group $\mathrm{SL}(2,\mathbb Z)$. In this paper we show how these two interpretations of $x_n$ are related to each other. More generally, for prime numbers $p$ we show a correspondence between a quotient of $(\mathbb Z_p\times\mathbb Z_p)^n$ and a language with $p^2$ letters and words of length $n$.
Enumeration of Hybrid Domino-Lozenge Tilings II: Quasi-Octagonal Regions
Authors: Lai Tri 
Published: January 2020

We use the subgraph replacement method to prove a simple product formula for the tilings of an 8-vertex counterpart of Propp's quasi-hexagons (Problem 16 in New Perspectives in Geometric Combinatorics, Cambridge University Press, 1999), called quasi-octagon.
A Relationship Between Generalized Davenport-Schinzel Sequences and Interval Chains
Authors: Geneson Jesse 
Published: January 2020

Let an $(r, s)$-formation be a concatenation of $s$ permutations of $r$ distinct letters, and let a block of a sequence be a subsequence of consecutive distinct letters. A $k$-chain on $[1, m]$ is a sequence of $k$ consecutive, disjoint, nonempty intervals of the form $[a_{0}, a_{1}] [a_{1}+1, a_{2}] \ldots [a_{k-1}+1, a_{k}]$ for integers $1 \leq a_{0} \leq a_{1} < \ldots < a_{k} \leq m$, and an $s$-tuple is a set of $s$ distinct integers. An $s$-tuple stabs an interval chain if each element of the $s$-tuple is in a different interval of the chain. Alon et al. (2008) observed similarities between bounds for interval chains and Davenport-Schinzel sequences, but did not identify the cause.We show for all $r \geq 1$ and $1 \leq s \leq k \leq m$ that the maximum number of distinct letters in any sequence $S$ on $m+1$ blocks avoiding every $(r, s+1)$-formation such that every letter in $S$ occurs at least $k+1$ times is the same as the maximum size of a collection $X$ of (not necessarily distinct) $k$-chains on $[1, m]$ so that there do not exist $r$ elements of $X$ all stabbed by the same $s$-tuple.Let $D_{s,k}(m)$ be the maximum number of distinct letters in any sequence which can be partitioned into $m$ blocks, has at least $k$ occurrences of every letter, and has no subsequence forming an alternation of length $s$. Nivasch (2010) proved that $D_{5, 2d+1}(m) = \Theta( m \alpha_{d}(m))$ for all fixed $d \geq 2$. We show that $D_{s+1, s}(m) = \binom{m- \lceil \frac{s}{2} \rceil}{\lfloor \frac{s}{2} \rfloor}$ for all $s \geq 2$. We also prove new lower bounds which imply that $D_{5, 6}(m) = \Theta(m \log \log m)$ and $D_{5, 2d+2}(m) = \Theta(m \alpha_{d}(m))$ for all fixed $d \geq 3$.
Equipopularity Classes in the Separable Permutations
Authors: Albert Michael , Homberger Cheyne , Pantone Jay 
Published: January 2020

When two patterns occur equally often in a set of permutations, we say that these patterns are equipopular. Using both structural and analytic tools, we classify the equipopular patterns in the set of separable permutations. In particular, we show that the number of equipopularity classes for length $n$ patterns in the separable permutations is equal to the number of partitions of $n-1$.
Hyperbinary Expansions and Stern Polynomials
Authors: Dilcher Karl , Ericksen Larry 
Published: January 2020

We introduce an infinite class of polynomial sequences $a_t(n;z)$ with integer parameter $t\geq 1$, which reduce to the well-known Stern (diatomic) sequence when $z=1$ and are $(0,1)$-polynomials when $t\geq 2$. Using these polynomial sequences, we derive two different characterizations of all hyperbinary expansions of an integer $n\geq 1$. Furthermore, we study the polynomials $a_t(n;z)$ as objects in their own right, obtaining a generating function and some consequences. We also prove results on the structure of these sequences, and determine expressions for the degrees of the polynomials.
A Construction of Uniquely $n$-Colorable Digraphs with Arbitrarily Large Digirth
Authors: Severino Michael 
Published: January 2020

A natural digraph analogue of the graph-theoretic concept of an `independent set' is that of an `acyclic set', namely a set of vertices not spanning a directed cycle. Hence a digraph analogue of a graph coloring is a decomposition of the vertex set into acyclic sets and we say a digraph is uniquely $n$-colorable when this decomposition is unique up to relabeling. It was shown probabilistically in [A. Harutyunyan et al., Uniquely $D$-colorable digraphs with large girth, Canad. J. Math., 64(6): 1310-1328, 2012] that there exist uniquely $n$-colorable digraphs with arbitrarily large girth. Here we give a construction of such digraphs and prove that they have circular chromatic number $n$. The graph-theoretic notion of `homomorphism' also gives rise to a digraph analogue. An acyclic homomorphism from a digraph $D$ to a digraph $H$ is a mapping $\varphi: V(D) \rightarrow V(H)$ such that $uv \in A(D)$ implies that either $\varphi(u)\varphi(v) \in A(H)$ or $\varphi(u)=\varphi(v)$, and all the `fibers' $\varphi^{-1}(v)$, for $v \in V(H)$, of $\varphi$ are acyclic. In this language, a core is a digraph $D$ for which there does not exist an acyclic homomorphism from $D$ to a proper subdigraph of itself. Here we prove some basic results about digraph cores and construct highly chromatic cores without short cycles.
Mutually Unbiased Bush-type Hadamard Matrices and Association Schemes
Authors: Kharaghani Hadi , Sasani Sara , Suda Sho 
Published: January 2020

It was shown by LeCompte, Martin, and Owens in 2010 that the existence of mutually unbiased Hadamard matrices and the identity matrix, which coincide with mutually unbiased bases, is equivalent to that of a $Q$-polynomial association scheme of class four which is both $Q$-antipodal and $Q$-bipartite. We prove that the existence of a set of mutually unbiased Bush-type Hadamard matrices is equivalent to that of an association scheme of class five. As an application of this equivalence, we obtain an upper bound of the number of mutually unbiased Bush-type Hadamard matrices of order $4n^2$ to be $2n-1$. This is in contrast to the fact that the best general upper bound for the mutually unbiased Hadamard matrices of order $4n^2$ is $2n^2$. We also discuss a relation of our scheme to some fusion schemes which are $Q$-antipodal and $Q$-bipartite $Q$-polynomial of class $4$.
Distance-Regular Graphs
Authors: Van Dam Edwin R. , Koolen Jack H. , Tanaka Hajime 
Published: January 2020

This is a survey of distance-regular graphs. We present an introduction to distance-regular graphs for the reader who is unfamiliar with the subject, and then give an overview of some developments in the area of distance-regular graphs since the monograph 'BCN' [Brouwer, A.E., Cohen, A.M., Neumaier, A., Distance-Regular Graphs, Springer-Verlag, Berlin, 1989] was written.
Tokuyama's Identity for Factorial Schur $P$ and $Q$ Functions
Authors: Hamel Angèle M. , King Ronald C. 
Published: January 2020

A recent paper of Bump, McNamara and Nakasuji introduced a factorial version of Tokuyama's identity, expressing the partition function of six vertex model as the product of a $t$-deformed Vandermonde and a Schur function. Here we provide an extension of their result by exploiting the language of primed shifted tableaux, with its proof based on the use of non-interesecting lattice paths.
Symmetric Chain Decompositions of Quotients by Wreath Products
Authors: Duffus Dwight , Thayer Kyle 
Published: January 2020

Subgroups of the symmetric group $S_n$ act on $C^n$ (the $n$-fold product $C \times \cdots \times C$ of a chain $C$) by permuting coordinates, and induce automorphisms of the power $C^n$. For certain families of subgroups of $S_n$, the quotients defined by these groups can be shown to have symmetric chain decompositions (SCDs). These SCDs allow us to enlarge the collection of subgroups $G$ of $S_n$ for which the quotient $\mathbf{2}^n/G$ on the Boolean lattice $\mathbf{2}^n$ is a symmetric chain order (SCO). The methods are also used to provide an elementary proof that quotients of powers of SCOs by cyclic groups are SCOs.
The Page-Rényi Parking Process
Authors: Gerin Lucas 
Published: January 2020

In the Page parking (or packing) model on a discrete interval (also known as the discrete Rényi packing problem or the unfriendly seating problem), cars of length two successively park uniformly at random on pairs of adjacent places, until only isolated places remain.We use a probabilistic construction of the Page parking to give a short proof of the (known) fact that the proportion of the interval occupied by cars goes to $1-e^{-2}$, when the length of the interval goes to infinity. We also obtain some new consequences on both finite and infinite parkings.
Linear Transformations Preserving the Strong $q$-log-convexity of Polynomials
Authors: Zhu Bao-Xuan , Sun Hua 
Published: January 2020

In this paper, we give a sufficient condition for the linear transformation preserving the strong $q$-log-convexity. As applications, we get some linear transformations (for instance, Morgan-Voyce transformation, binomial transformation, Narayana transformations of two kinds) preserving the strong $q$-log-convexity. In addition, our results not only extend some known results, but also imply the strong $q$-log-convexities of some sequences of polynomials.
Vizing's Conjecture for Graphs with Domination Number 3 - a New Proof
Authors: Brešar Boštjan 
Published: January 2020

Vizing's conjecture from 1968 asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In this note we use a new, transparent approach to prove Vizing's conjecture for graphs with domination number 3; that is, we prove that for any graph $G$ with $\gamma(G)=3$ and an arbitrary graph $H$, $\gamma(G\Box H) \ge 3\gamma(H)$.
Lifespan in a Primitive Boolean Linear Dynamical System
Authors: Wu Yaokun , Zhu Yinfeng 
Published: January 2020

Let $\mathcal F$ be a set of $k$ by $k$ nonnegative matrices such that every "long" product of elements of $\mathcal F$ is positive. Cohen and Sellers (1982) proved that, then, every such product of length $2^k-2$ over $\mathcal F$ must be positive. They suggested to investigate the minimum size of such $\mathcal F$ for which there exists a non-positive product of length $2^k-3$ over $\mathcal F$ and they constructed one example of size $2^k-2$. We construct one of size $k$ and further discuss relevant basic problems in the framework of Boolean linear dynamical systems. We also formulate several primitivity properties for general discrete dynamical systems.
Packing Polynomials on Multidimensional Integer Sectors
Authors: Morales Luis B. 
Published: January 2020

Denoting the real numbers and the nonnegative integers, respectively, by ${\bf R}$ and ${\bf N}$, let $S$ be a subset of ${\bf N}^n$ for $n = 1, 2,\ldots$, and $f$ be a mapping from ${\bf R}^n$ into ${\bf R}$. We call $f$ a packing function on $S$ if the restriction $f|_{S}$ is a bijection onto ${\bf N}$. For all positive integers $r_1,\ldots,r_{n-1}$, we consider the integer sector \[I(r_1, \ldots, r_{n-1}) =\{(x_1,\ldots,x_n) \in N^n \; | \; x_{i+1} \leq r_ix_i \mbox{ for } i = 1,\ldots,n-1 \}.\] Recently, Melvyn B. Nathanson (2014) proved that for $n=2$ there exist two quadratic packing polynomials on the sector $I(r)$. Here, for $n>2$ we construct $2^{n-1}$ packing polynomials on multidimensional integer sectors. In particular, for each packing polynomial on ${\bf N}^n$ we construct a packing polynomial on the sector $I(1, \ldots, 1)$.
Planar Graphs have Independence Ratio at least 3/13
Authors: Cranston Daniel W. , Rabern Landon 
Published: January 2020

The 4 Color Theorem (4CT) implies that every $n$-vertex planar graph has an independent set of size at least $\frac{n}4$; this is best possible, as shown by the disjoint union of many copies of $K_4$. In 1968, Erdős asked whether this bound on independence number could be proved more easily than the full 4CT. In 1976 Albertson showed (independently of the 4CT) that every $n$-vertex planar graph has an independent set of size at least $\frac{2n}9$. Until now, this remained the best bound independent of the 4CT. Our main result improves this bound to $\frac{3n}{13}$.
Decompositions of the Boolean Lattice into Rank-symmetric Chains
Authors: Tomon István 
Published: January 2020

The Boolean lattice $2^{[n]}$ is the power set of $[n]$ ordered by inclusion. A chain $c_{0}\subset\cdots\subset c_{k}$ in $2^{[n]}$ is rank-symmetric, if $|c_{i}|+|c_{k-i}|=n$ for $i=0,\ldots,k$; and it is symmetric, if $|c_{i}|=(n-k)/2+i$. We show that there exist a bijection $$p: [n]^{(\geq n/2)}\rightarrow [n]^{(\leq n/2)}$$ and a partial ordering $<$ on $[n]^{(\geq n/2)}$ satisfying the following properties:$\subset$ is an extension of $<$ on $[n]^{(\geq n/2)}$;if $C\subset [n]^{(\geq n/2)}$ is a chain with respect to $<$, then $p(C)\cup C$ is a rank-symmetric chain in $2^{[n]}$, where $p(C)=\{p(x): x\in C\}$;the poset $([n]^{(\geq n/2)},<)$ has the so called normalized matching property.We show two applications of this result.A conjecture of Füredi asks if $2^{[n]}$ can be partitioned into $\binom{n}{\lfloor n/2\rfloor}$ chains such that the size of any two chains differ by at most 1. We prove an asymptotic version of this conjecture with the additional condition that every chain in the partition is rank-symmetric: $2^{[n]}$ can be partitioned into $\binom{n}{\lfloor n/2\rfloor}$ rank-symmetric chains, each of size $\Theta(\sqrt{n})$.Our second application gives a lower bound for the number of symmetric chain partitions of $2^{[n]}$. We show that $2^{[n]}$ has at least $2^{\Omega(2^{n}\log n/\sqrt{n})}$ symmetric chain partitions.
Nice Reflection Arrangements
Authors: Hoge Torsten , Röhrle Gerhard 
Published: January 2020

The aim of this note is a classification of all nice and all inductively factored reflection arrangements. It turns out that apart from the supersolvable instances only the monomial groups $G(r,r,3)$ for $r \ge 3$ give rise to nice reflection arrangements. As a consequence of this and of the classification of all inductively free reflection arrangements from Hoge and Röhrle (2015) we deduce that the class of all inductively factored reflection arrangements coincides with the class of all supersolvable reflection arrangements. Moreover, we extend these classifications to hereditarily factored and hereditarily inductively factored reflection arrangements.
A Note on the $\gamma$-Coefficients of the Tree Eulerian Polynomial
Authors: González D'León Rafael S. 
Published: January 2020

We consider the generating polynomial of the number of rooted trees on the set $\{1,2,\dots,n\}$ counted by the number of descending edges (a parent with a greater label than a child). This polynomial is an extension of the descent generating polynomial of the set of permutations of a totally ordered $n$-set, known as the Eulerian polynomial. We show how this extension shares some of the properties of the classical one. A classical product formula shows that this polynomial factors completely over the integers. From this product formula it can be concluded that this polynomial has positive coefficients in the $\gamma$-basis and we show that a formula for these coefficients can also be derived. We discuss various combinatorial interpretations of these coefficients in terms of leaf-labeled binary trees and in terms of the Stirling permutations introduced by Gessel and Stanley. These interpretations are derived from previous results of Liu, Dotsenko-Khoroshkin, Bershtein-Dotsenko-Khoroshkin, González D'León-Wachs and Gonzláez D'León related to the free multibracketed Lie algebra and the poset of weighted partitions.
Chromatic Symmetric Functions of Hypertrees
Authors: Taylor Jair 
Published: January 2020

The chromatic symmetric function $X_H$ of a hypergraph $H$ is the sum of all monomials corresponding to proper colorings of $H$. When $H$ is an ordinary graph, it is known that $X_H$ is positive in the fundamental quasisymmetric functions $F_S$, but this is not the case for general hypergraphs. We exhibit a class of hypergraphs $H$ — hypertrees with prime-sized edges — for which $X_H$ is $F$-positive, and give an explicit combinatorial interpretation for the $F$-coefficients of $X_H$.
Guaranteed Scoring Games
Authors: Larsson Urban , Nowakowski Richard J. , Neto João P. , Santos Carlos P. 
Published: January 2020

The class of Guaranteed Scoring Games (GS) are two-player combinatorial games with the property that Normal-play games (Conway et. al.) are ordered embedded into GS. They include, as subclasses, the scoring games considered by Milnor (1953), Ettinger (1996) and Johnson (2014). We present the structure of GS and the techniques needed to analyze a sum of guaranteed games. Firstly, GS form a partially ordered monoid, via defined Right- and Left-stops over the reals, and with disjunctive sum as the operation. In fact, the structure is a quotient monoid with partially ordered congruence classes. We show that there are four reductions that when applied, in any order, give a unique representative for each congruence class. The monoid is not a group, but in this paper we prove that if a game has an inverse it is obtained by 'switching the players'. The order relation between two games is defined by comparing their stops in any disjunctive sum. Here, we demonstrate how to compare the games via a finite algorithm instead, extending ideas of Ettinger, and also Siegel (2013).
Graph Realizations Constrained by Skeleton Graphs
Authors: Erdős Péter L. , Hartke Stephen G. , Van Iersel Leo , Miklós István 
Published: January 2020

In 2008 Amanatidis, Green and Mihail introduced the Joint Degree Matrix (JDM) model to capture the fundamental difference in assortativity of networks in nature studied by the physical and life sciences and social networks studied in the social sciences. In 2014 Czabarka proposed a direct generalization of the JDM model, the Partition Adjacency Matrix (PAM) model. In the PAM model the vertices have specified degrees, and the vertex set itself is partitioned into classes. For each pair of vertex classes the number of edges between the classes in a graph realization is prescribed. In this paper we apply the new skeleton graph model to describe the same information as the PAM model. Our model is more convenient for handling problems with low number of partition classes or with special topological restrictions among the classes. We investigate two particular cases in detail: (i) when there are only two vertex classes and (ii) when the skeleton graph contains at most one cycle.