Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSeparation probabilities and analogues of a Zagier-Stanley formula
112
0
0.0
(
0
)
Authors
Ricky X. F. Chen
Ask ChatGPT about the research
No Arabic abstract
In this paper, we first obtain some analogues of a formula of Zagier (1995) and Stanley (2011). For instance, we prove that the number of pairs of $n$-cycles whose product has $k$ cycles and has $m$ given elements contained in distinct cycles (or separated) is given by $$ frac{2 (n-1)! C_m(n+1,k)}{(n+m)(n+1-m)} $$ when $n-k$ is even, where $C_m(n,k)$ is the number of permutations of $n$ elements having $k$ cycles and separating $m$ given elements. As consequences, we obtain the formulas for certain separation probabilities due to Du and Stanley, answering a call of Stanley for simple combinatorial proofs. Furthermore, we obtain the expectation and variance of the number of fixed points in the product of two random $n$-cycles.
rate research
Read More
In this paper, we enumerate the pairs of permutations that are long cycles and whose product has a given cycle-type. Our main result is a simple relation concerning the desired numbers for a few related cycle-types. The relation refines a formula of the number of pairs of long cycles whose product has $k$ cycles independently obtained by Zagier and Stanley relying on group characters, and was previously obtained by F{e}ray and Vassilieva by counting some colored permutations first and then relying on some algebraic computations in the ring of symmetric functions. Our approach here is simpler and combinatorial.
In this paper, we introduce plane permutations, i.e. pairs $mathfrak{p}=(s,pi)$ where $s$ is an $n$-cycle and $pi$ is an arbitrary permutation, represented as a two-row array. Accordingly a plane permutation gives rise to three distinct permutations: the permutation induced by the upper horizontal ($s$), the vertical $pi$) and the diagonal ($D_{mathfrak{p}}$) of the array. The latter can also be viewed as the three permutations of a hypermap. In particular, a map corresponds to a plane permutation, in which the diagonal is a fixed point-free involution. We study the transposition action on plane permutations obtained by permuting their diagonal-blocks. We establish basic properties of plane permutations and study transpositions and exceedances and derive various enumerative results. In particular, we prove a recurrence for the number of plane permutations having a fixed diagonal and $k$ cycles in the vertical, generalizing Chapuys recursion for maps filtered by the genus. As applications of this framework, we present a combinatorial proof of a result of Zagier and Stanley, on the number of $n$-cycles $omega$, for which the product $omega(1~2~cdots ~n)$ has exactly $k$ cycles. Furthermore, we integrate studies on the transposition and block-interchange distance of permutations as well as the reversal distance of signed permutations. Plane permutations allow us to generalize and recover various lower bounds for transposition and block-interchange distances and to connect reversals with block-interchanges.
Given a set of integers with no three in arithmetic progression, we construct a Stanley sequence by adding integers greedily so that no arithmetic progression is formed. This paper offers two main contributions to the theory of Stanley sequences. First, we characterize well-structured Stanley sequences as solutions to constraints in modular arithmetic, defining the modular Stanley sequences. Second, we introduce the basic Stanley sequences, where elements arise as the sums of subsets of a basis sequence, which in the simplest case is the powers of 3. Applications of our results include the construction of Stanley sequences with arbitrarily large gaps between terms, answering a weak version of a problem by ErdH{o}s et al. Finally, we generalize many results about Stanley sequences to $p$-free sequences, where $p$ is any odd prime.
Given a set of integers containing no 3-term arithmetic progressions, one constructs a Stanley sequence by choosing integers greedily without forming such a progression. Independent Stanley sequences are a well-structured class of Stanley sequences with two main parameters: the character $lambda(A)$ and the repeat factor $rho(A)$. Rolnick conjectured that for every $lambda in mathbb{N}_0backslash{1, 3, 5, 9, 11, 15}$, there exists an independent Stanley sequence $S(A)$ such that $lambda(A) =lambda$. This paper demonstrates that $lambda(A) otin {1, 3, 5, 9, 11, 15}$ for any independent Stanley sequence $S(A)$.
We define a subclass of Hessenberg varieties called abelian Hessenberg varieties, inspired by the theory of abelian ideals in a Lie algebra developed by Kostant and Peterson. We give an inductive formula for the $S_n$-representation on the cohomology of an abelian regular semisimple Hessenberg variety with respect to the action defined by Tymoczko. Our result implies that a graded version of the Stanley-Stembridge conjecture holds in the abelian case, and generalizes results obtained by Shareshian-Wachs and Teff. Our proof uses previous work of Stanley, Gasharov, Shareshian-Wachs, and Brosnan-Chow, as well as results of the second author on the geometry and combinatorics of Hessenberg varieties. As part of our arguments, we obtain inductive formulas for the Poincare polynomials of regular abelian Hessenberg varieties.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
