Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA product of invariant random permutations has the same small cycle structure as uniform
143
0
0.0
(
0
)
Authors
Mohamed Slim Kammoun
Ask ChatGPT about the research
No Arabic abstract
We use moment method to understand the cycle structure of the composition of independent invariant permutations. We prove that under a good control on fixed points and cycles of length 2, the limiting joint distribution of the number of small cycles is the same as in the uniform case i.e. for any positive integer k, the number of cycles of length k converges to the Poisson distribution with parameter 1/k and is asymptotically independent of the number of cycles of length k different from k.
rate research
Read More
In this article we consider the cycle structure of compositions of pairs of involutions in the symmetric group S_n chosen uniformly at random. These can be modeled as modified 2-regular graphs, giving rise to exponential generating functions. A composition of two random involutions in S_n typically has about n^(1/2) cycles, and the cycles are characteristically of length n^(1/2). Compositions of two random fixed-point-free involutions, on the other hand, typically have about log n cycles and are closely related to permutations with all cycle lengths even. The number of factorizations of a random permutation into two involutions appears to be asymptotically lognormally distributed, which we prove for a closely related probabilistic model. This study is motivated by the observation that the number of involutions in [n] is (n!)^(1/2) times a subexponential factor; more generally the number of permutations with all cycle lengths in a finite set S is n!^(1-1/m) times a subexponential factor, and the typical number of k-cycles is nearly n^(k/m)/k. Connections to pattern avoidance in involutions are also considered.
This paper develops an analogy between the cycle structure of, on the one hand, random permutations with cycle lengths restricted to lie in an infinite set $S$ with asymptotic density $sigma$ and, on the other hand, permutations selected according to the Ewens distribution with parameter $sigma$. In particular we show that the asymptotic expected number of cycles of random permutations of $[n]$ with all cycles even, with all cycles odd, and chosen from the Ewens distribution with parameter 1/2 are all ${1 over 2} log n + O(1)$, and the variance is of the same order. Furthermore, we show that in permutations of $[n]$ chosen from the Ewens distribution with parameter $sigma$, the probability of a random element being in a cycle longer than $gamma n$ approaches $(1-gamma)^sigma$ for large $n$. The same limit law holds for permutations with cycles carrying multiplicative weights with average $sigma$. We draw parallels between the Ewens distribution and the asymptotic-density case and explain why these parallels should exist using permutations drawn from weighted Boltzmann distributions.
We consider a generalised model of a random simplicial complex, which arises from a random hypergraph. Our model is generated by taking the downward-closure of a non-uniform binomial random hypergraph, in which for each $k$, each set of $k+1$ vertices forms an edge with some probability $p_k$ independently. As a special case, this contains an extensively studied model of a (uniform) random simplicial complex, introduced by Meshulam and Wallach [Random Structures & Algorithms 34 (2009), no. 3, pp. 408-417]. We consider a higher-dimensional notion of connectedness on this new model according to the vanishing of cohomology groups over an arbitrary abelian group $R$. We prove that this notion of connectedness displays a phase transition and determine the threshold. We also prove a hitting time result for a natural process interpretation, in which simplices and their downward-closure are added one by one. In addition, we determine the asymptotic behaviour of cohomology groups inside the critical window around the time of the phase transition.
In this note we investigate correlation inequalities for `up-sets of permutations, in the spirit of the Harris--Kleitman inequality. We focus on two well-studied partial orders on $S_n$, giving rise to differing notions of up-sets. Our first result shows that, under the strong Bruhat order on $S_n$, up-sets are positively correlated (in the Harris--Kleitman sense). Thus, for example, for a (uniformly) random permutation $pi$, the event that no point is displaced by more than a fixed distance $d$ and the event that $pi$ is the product of at most $k$ adjacent transpositions are positively correlated. In contrast, under the weak Bruhat order we show that this completely fails: surprisingly, there are two up-sets each of measure $1/2$ whose intersection has arbitrarily small measure. We also prove analogous correlation results for a class of non-uniform measures, which includes the Mallows measures. Some applications and open problems are discussed.
We compute the limiting distribution, as n approaches infinity, of the number of cycles of length between gamma n and delta n in a permutation of [n] chosen uniformly at random, for constants gamma, delta such that 1/(k+1) <= gamma < delta <= 1/k for some integer k. This distribution is supported on {0, 1, ... k} and has 0th, 1st, ..., kth moments equal to those of a Poisson distribution with parameter log (delta/gamma). For more general choices of gamma, delta we show that such a limiting distribution exists, which can be given explicitly in terms of certain integrals over intersections of hypercubes with half-spaces; these integrals are analytically intractable but a recurrence specifying them can be given. The results herein provide a basis of comparison for similar statistics on restricted classes of permutations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
