Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: We seek simple conditions on a pair of labeled posets that determine when the difference of their \((P,\omega )\) -partition enumerators is F-positive, i.e., positive in Gessel’s fundamental basis. This is a quasisymmetric analogue of the extensively studied problem of finding conditions on a pair of skew shapes that determine when the difference of their skew Schur functions is Schur-positive. We determine necessary conditions and separate sufficient conditions for F-positivity, and show that a broad operation for combining posets preserves positivity properties. We conclude with classes of posets for which we have conditions that are both necessary and sufficient. PubDate: 2022-01-16

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Consider equipping an alphabet \(\mathcal {A}\) with a group action which partitions the set of words into equivalence classes which we call patterns. We answer standard questions for Penney’s game on patterns and show non-transitivity for the game on patterns as the length of the pattern tends to infinity. We also analyze bounds on the pattern-based Conway leading number and expected wait time, and further explore the game under the cyclic and symmetric group actions. PubDate: 2022-01-15

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: A complete dessin of type \(\{2^e,2^f\}\) is an orientable map with underlying graph being a complete bipartite graph \(\mathbf{K}_{2^e,2^f}\) , which is said to be regular if all edges are equivalent under the group of color- and orientation-preserving automorphisms, and circular if the boundary cycle of each face is a circuit (a simple cycle). As one of a series papers towards a classification of complete circular regular dessins of type \(\{m,n\}\) , this paper presents such a classification for the case \(\{m,n\}=\{2^e,2^f\}\) , where e, f are positive integers and \(e\ge f\ge 2\) . We note that the group G of color- and orientation-preserving automorphisms is a bicyclic 2-group of type \(\{2^e,2^f\}\) , and our analysis splits naturally into two cases depending on whether the group G is metacyclic or not. In this paper, we deal with the case that G is metacyclic. PubDate: 2021-12-12

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: The number of peaks of a random permutation is known to be asymptotically normal. We give a new proof of this and prove a central limit theorem for the distribution of peaks in a fixed conjugacy class of the symmetric group. Our technique is to apply analytic combinatorics to study a complicated but exact generating function for peaks in a given conjugacy class. PubDate: 2021-12-07

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Recently, Mc Laughlin proved several new results on vanishing coefficients in certain q-product expansions by classifying the results into various families. Also, Mc Laughlin stated some families of results with negative signs for arithmetic progressions modulo 5, modulo 7 and modulo 11. We have already proved the families of results modulo 7. In this paper, we prove results for arithmetic progressions modulo 5 and 11. For instance, we prove that if \(t \in \{1,2,3,4\}\) and the sequence \(\{A(n)\}\) is defined by $$\begin{aligned} \sum _{n=-9}^{\infty }A(n)q^n := \left( -q^{2t},-q^{5-2t};q^5\right) _{\infty }^3\left( q^{5-t},q^{5+t};q^{10}\right) _{\infty }, \end{aligned}$$ then \(A(5n+3t^2+3t)=0\) for all n and if t is even, then \(A(5n+2t^2+3t)=0\) for all n. Also, if \(t \in \{1,2,3,4,5,6,7,8,9,10\}\) and the sequence \(\{F(n)\}\) is defined by $$\begin{aligned} \sum _{n=-81}^{\infty }F(n)q^n := \left( q^{3t},q^{11-3t};q^{11}\right) _{\infty }^3\left( -q^{11-t},-q^{11+t};q^{22}\right) _{\infty }, \end{aligned}$$ then \(F(11n+8t^2+10t)=0\) for all n. PubDate: 2021-12-02

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: We correct some lemmas in Section 3 and Section 4 in ’New non-existence proofs for ovoids of Hermitian polar spaces and hyperbolic quadrics’, Ann. Comb., 21(1):25–42, 2017. PubDate: 2021-12-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: We continue our study of a new boundedness condition for affine permutations, motivated by the fruitful concept of periodic boundary conditions in statistical physics. We focus on bounded affine permutations of size N that avoid the monotone decreasing pattern of fixed size m. We prove that the number of such permutations is asymptotically equal to \((m-1)^{2N} N^{(m-2)/2}\) times an explicit constant as \(N\rightarrow \infty \) . For instance, the number of bounded affine permutations of size N that avoid 321 is asymptotically equal to \(4^N (N/4\pi )^{1/2}\) . We also prove a permuton-like result for the scaling limit of random permutations from this class, showing that the plot of a typical bounded affine permutation avoiding \(m\cdots 1\) looks like \(m-1\) random lines of slope 1 whose y intercepts sum to 0. PubDate: 2021-12-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: We show that for any permutation w that avoids a certain set of 13 patterns of length 5 and 6, the Schubert polynomial \({\mathfrak {S}}_w\) can be expressed as the determinant of a matrix of elementary symmetric polynomials in a manner similar to the Jacobi–Trudi identity. For such w, this determinantal formula is equivalent to a (signed) subtraction-free expansion of \(\mathfrak S_w\) in the basis of standard elementary monomials. PubDate: 2021-12-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Two permutations are similar if they have the same length and the same relative order. A collection of \(r\geqslant 2\) disjoint, similar subsequences of a permutation \(\pi \) forms r-twins in \(\pi \) . We study the longest guaranteed length of r-twins which are tight in the sense that either each twin alone forms a block or their union does. We address the same question with respect to a random permutation. PubDate: 2021-12-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: A catalogue of simplicial hyperplane arrangements was first given by Grünbaum in 1971. These arrangements naturally generalize finite Coxeter arrangements and also the weak order through the poset of regions. The weak order is known to be a congruence normal lattice, and congruence normality of lattices of regions of simplicial arrangements can be determined using polyhedral cones called shards. In this article, we update Grünbaum’s catalogue by providing normals realizing all known simplicial arrangements with up to 37 lines and key invariants. Then we add structure to this catalogue by determining which arrangements always/sometimes/never lead to congruence normal lattices of regions. To this end, we use oriented matroids to recast shards as covectors to determine congruence normality of large hyperplane arrangements. We also show that lattices of regions coming from finite Weyl groupoids of any rank are always congruence normal. PubDate: 2021-11-08

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: For a finite set of S points in the plane and a graph with vertices on S, consider the disks with diameters induced by the edges. We show that for any odd set S, there exists a Hamiltonian cycle for which these disks share a point, and for an even set S, there exists a Hamiltonian path with the same property. We discuss high-dimensional versions of these theorems and their relation to other results in discrete geometry. PubDate: 2021-10-11 DOI: 10.1007/s00026-021-00557-0

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: We introduce a quasisymmetric class function associated with a group acting on a double poset or on a directed graph. The latter is a generalization of the chromatic quasisymmetric function of a digraph introduced by Ellzey, while the former is a generalization of a quasisymmetric function introduced by Grinberg. We prove representation-theoretic analogues of classical and recent results, including F-positivity, and combinatorial reciprocity theorems. We deduce results for orbital quasisymmetric functions, and study a generalization of the notion of strongly flawless sequences. PubDate: 2021-10-08 DOI: 10.1007/s00026-021-00556-1

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: For each integer partition \(\mathbf {q}\) with d parts, we denote by \(\Delta _{(1,\mathbf {q})}\) the lattice simplex obtained as the convex hull in \(\mathbb {R}^d\) of the standard basis vectors along with the vector \(-\mathbf {q}\) . For \(\mathbf {q}\) with two distinct parts such that \(\Delta _{(1,\mathbf {q})}\) is reflexive and has the integer decomposition property, we establish a characterization of the lattice points contained in \(\Delta _{(1,\mathbf {q})}\) . We then construct a Gröbner basis with a squarefree initial ideal of the toric ideal defined by these simplices. This establishes the existence of a regular unimodular triangulation for reflexive 2-supported \(\Delta _{(1,\mathbf {q})}\) having the integer decomposition property. As a corollary, we obtain a new proof that these simplices have unimodal Ehrhart \(h^*\) -vectors. PubDate: 2021-09-28 DOI: 10.1007/s00026-021-00554-3

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: If every perfect matching of a graph G extends to a Hamiltonian cycle, we shall say that G has the PMH-property—a concept first studied in the 1970s by Las Vergnas and Häggkvist. A pairing of a graph G is a perfect matching of the complete graph having the same vertex set as G. A somewhat stronger property than the PMH-property is the following. A graph G has the PH-property if every pairing of G can be extended to a Hamiltonian cycle of the underlying complete graph using only edges from G. The name for the latter property was coined in 2015 by Alahmadi et al.; however, this was not the first time this property was studied. In 2007, Fink proved that every n-dimensional hypercube, for \(n\ge 2\) , has the PH-property. After characterising all the cubic graphs having the PH-property, Alahmadi et al. attempt to characterise all 4-regular graphs having the same property by posing the following problem: for which values of p and q does the Cartesian product \(C_p\square C_q\) of two cycles on p and q vertices have the PH-property' We here show that this only happens when both p and q are equal to four, namely for \(C_{4}\square C_{4}\) , the 4-dimensional hypercube. For all other values, we show that \(C_{p}\square C_{q}\) does not even admit the PMH-property. PubDate: 2021-09-01 DOI: 10.1007/s00026-021-00548-1

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: In this paper, we study concave compositions, an extension of partitions that were considered by Andrews, Rhoades, and Zwegers. They presented several open problems regarding the statistical structure of concave compositions including the distribution of the perimeter and tilt, the number of summands, and the shape of the graph of a typical concave composition. We present solutions to these problems by applying Fristedt’s conditioning device on the uniform measure. PubDate: 2021-09-01 DOI: 10.1007/s00026-021-00543-6

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: We study f-vectors, which are the maximal degree vectors of F-polynomials in cluster algebra theory. For a cluster algebra of finite type, we find that positive f-vectors correspond with d-vectors, which are exponent vectors of denominators of cluster variables. Furthermore, using this correspondence and properties of d-vectors, we prove that cluster variables in a cluster are uniquely determined by their f-vectors when the cluster algebra is of finite type or rank 2. PubDate: 2021-09-01 DOI: 10.1007/s00026-021-00527-6

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Given a bipartite graph with parts A and B having maximum degrees at most \(\Delta _A\) and \(\Delta _B\) , respectively, consider a list assignment such that every vertex in A or B is given a list of colours of size \(k_A\) or \(k_B\) , respectively. We prove some general sufficient conditions in terms of \(\Delta _A\) , \(\Delta _B\) , \(k_A\) , \(k_B\) to be guaranteed a proper colouring such that each vertex is coloured using only a colour from its list. These are asymptotically nearly sharp in the very asymmetric cases. We establish one sufficient condition in particular, where \(\Delta _A=\Delta _B=\Delta \) , \(k_A=\log \Delta \) and \(k_B=(1+o(1))\Delta /\log \Delta \) as \(\Delta \rightarrow \infty \) . This amounts to partial progress towards a conjecture from 1998 of Krivelevich and the first author. We also derive some necessary conditions through an intriguing connection between the complete case and the extremal size of approximate Steiner systems. We show that for complete bipartite graphs these conditions are asymptotically nearly sharp in a large part of the parameter space. This has provoked the following. In the setup above, we conjecture that a proper list colouring is always guaranteed if \(k_A \ge \Delta _A^\varepsilon \) and \(k_B \ge \Delta _B^\varepsilon \) for any \(\varepsilon >0\) provided \(\Delta _A\) and \(\Delta _B\) are large enough; if \(k_A \ge C \log \Delta _B\) and \(k_B \ge C \log \Delta _A\) for some absolute constant \(C>1\) ; or if \(\Delta _A=\Delta _B = \Delta \) and \( k_B \ge C (\Delta /\log \Delta )^{1/k_A}\log \Delta \) for some absolute constant \(C>0\) . These are asymmetric generalisations of the above-mentioned conjecture of Krivelevich and the first author, and if true are close to best possible. Our general sufficient conditions provide partial progress towards these conjectures. PubDate: 2021-09-01 DOI: 10.1007/s00026-021-00552-5

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: The degree of symmetry of a combinatorial object, such as a lattice path, is a measure of how symmetric the object is. It typically ranges from zero, if the object is completely asymmetric, to its size, if it is completely symmetric. We study the behavior of this statistic on Dyck paths and grand Dyck paths, with symmetry described by reflection along a vertical line through their midpoint; partitions, with symmetry given by conjugation; and certain compositions interpreted as bargraphs. We find expressions for the generating functions for these objects with respect to their degree of symmetry, and their semilength or semiperimeter, deducing in most cases that, asymptotically, the degree of symmetry has a Rayleigh or half-normal limiting distribution. The resulting generating functions are often algebraic, with the notable exception of Dyck paths, for which we conjecture that it is D-finite (but not algebraic), based on a functional equation that we obtain using bijections to walks in the plane. PubDate: 2021-08-24 DOI: 10.1007/s00026-021-00551-6

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Recently, the study of patterns in inversion sequences was initiated by Corteel–Martinez–Savage–Weselcouch and Mansour–Shattuck independently. Motivated by their works and a double Eulerian equidistribution due to Foata (1977), we investigate several classical statistics on restricted inversion sequences that are either known or conjectured to be enumerated by Catalan, Large Schröder, Baxter and Euler numbers. One of the two highlights of our results is a fascinating bijection between 000-avoiding inversion sequences and Simsun permutations, which together with Foata’s V- and S-codes, provide a proof of a restricted double Eulerian equidistribution. The other one is a refinement of a conjecture due to Martinez and Savage that the cardinality of \({\mathbf{I}}_n(\ge ,\ge ,>)\) is the n-th Baxter number, which is proved via the so-called obstinate kernel method developed by Bousquet-Mélou. PubDate: 2021-08-23 DOI: 10.1007/s00026-021-00550-7

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: We study a number of combinatorial and algebraic structures arising from walks on the two-dimensional integer lattice. To a given step set \(X\subseteq \mathbb Z^2\) , there are two naturally associated monoids: \(\mathscr {F}_X\) , the monoid of all X-walks/paths; and \(\mathscr {A}_X\) , the monoid of all endpoints of X-walks starting from the origin O. For each \({A\in \mathscr {A}_X}\) , write \(\pi _X(A)\) for the number of X-walks from O to A. Calculating the numbers \(\pi _X(A)\) is a classical problem, leading to Fibonacci, Catalan, Motzkin, Delannoy and Schröder numbers, among many other well-studied sequences and arrays. Our main results give relationships between finiteness properties of the numbers \(\pi _X(A)\) , geometrical properties of the step set X, algebraic properties of the monoid \(\mathscr {A}_X\) , and combinatorial properties of a certain bi-labelled digraph naturally associated to X. There is an intriguing divergence between the cases of finite and infinite step sets, and some constructions rely on highly non-trivial properties of real numbers. We also consider the case of walks constrained to stay within a given region of the plane. Several examples are considered throughout to highlight the sometimes-subtle nature of the theoretical results. PubDate: 2021-08-18 DOI: 10.1007/s00026-021-00546-3