Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEquidistributions of mesh patterns of length two and Kitaev and Zhangs conjectures
73
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A systematic study of avoidance of mesh patterns of length 2 was conducted by Hilmarsson et al. in 2015. In a recent paper Kitaev and Zhang examined the distribution of the aforementioned patterns. The aim of this paper is to prove more equidistributions of mesh pattern and confirm Kitaev and Zhangs four conjectures by constructing two involutions on permutations.
rate research
Read More
A systematic study of avoidance of mesh patterns of length 2 was conducted by Hilmarsson et al., where 25 out of 65 non-equivalent cases were solved. In this paper, we give 27 distribution results for these patterns including 14 distributions for which avoidance was not known. Moreover, for the unsolved cases, we prove an equidistribution result (out of 6 equidistribution results we prove in total), and conjecture 6 more equidistributions. Finally, we find seemingly unknown distribution of the well known permutation statistic ``strict fixed point, which plays a key role in many of our enumerative results. This paper is the first systematic study of distributions of mesh patterns. Our techniques to obtain the results include, but are not limited to, obtaining functional relations for generating functions, and finding recurrence relations and bijections.
Branden and Claesson introduced mesh patterns to provide explicit expansions for certain permutation statistics as linear combinations of (classical) permutation patterns. The first systematic study of avoidance of mesh patterns was conducted by Hilmarsson et al., while the first systematic study of the distribution of mesh patterns was conducted by the first two authors. In this paper, we provide far-reaching generalizations for 8 known distribution results and 5 known avoidance results related to mesh patterns by giving distribution or avoidance formulas for certain infinite families of mesh patterns in terms of distribution or avoidance formulas for smaller patterns. Moreover, as a corollary to a general result, we find the distribution of one more mesh pattern of length 2.
We consider a sequence of four variable polynomials by refining Stieltjes continued fraction for Eulerian polynomials. Using combinatorial theory of Jacobi-type continued fractions and bijections we derive various combinatorial interpretations in terms of permutation statistics for these polynomials, which include special kinds of descents and excedances in a recent paper of Baril and Kirgizov. As a by-product, we derive several equidistribution results for permutation statistics, which enables us to confirm and strengthen a recent conjecture of Vajnovszki and also to obtain several compagnion permutation statistics for two bistatistics in a conjecture of Baril and Kirgizov.
Babson and Steingr{i}msson introduced generalized permutation patterns and showed that most of the Mahonian statistics in the literature can be expressed by the combination of generalized pattern functions. Particularly, they defined a new Mahonian statistic in terms of generalized pattern functions, which is denoted $stat$. Recently, Amini investigated the equidistributions of these Mahonian statistics over sets of pattern avoiding permutations. Moreover, he posed several conjectures. In this paper, we construct a bijection from $S_n(213)$ to $S_n(231)$, which maps the statistic $(maj,stat)$ to the statistic $(stat,maj)$. This allows us to give solutions to some of Aminis conjectures.
For a graph $G$, let $cp(G)$ denote the minimum number of cliques of $G$ needed to cover the edges of $G$ exactly once. Similarly, let $bp_k(G)$ denote the minimum number of bicliques (i.e. complete bipartite subgraphs of $G$) needed to cover each edge of $G$ exactly $k$ times. We consider two conjectures -- one regarding the maximum possible value of $cp(G) + cp(overline{G})$ (due to de Caen, ErdH{o}s, Pullman and Wormald) and the other regarding $bp_k(K_n)$ (due to de Caen, Gregory and Pritikin). We disprove the first, obtaining improved lower and upper bounds on $max_G cp(G) + cp(overline{G})$, and we prove an asymptotic version of the second, showing that $bp_k(K_n) = (1+o(1))n$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
