اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLimit Densities of Patterns in Permutation Inflations
108
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Call a permutation $k$-inflatable if the sequence of its tensor products with uniform random permutations of increasing lengths has uniform $k$-point pattern densities. Previous work has shown that nontrivial $k$-inflatable permutations do not exist for $k geq 4$. In this paper, we derive a general formula for the limit densities of patterns in the sequence of tensor products of a fixed permutation with each permutation from a convergent sequence. By applying this result, we completely characterize $3$-inflatable permutations and find explicit examples of $3$-inflatable permutations with various lengths, including the shortest examples with length $17$.
قيم البحث
اقرأ أيضاً
Let $pi_n$ be a uniformly chosen random permutation on $[n]$. Using an analysis of the probability that two overlapping consecutive $k$-permutations are order isomorphic, we show that the expected number of distinct consecutive patterns in $pi_n$ is
$frac{n^2}{2}(1-o(1))$. This exhibits the fact that random permutations pack consecutive patterns near-perfectly.
This note gives a central limit theorem for the length of the longest subsequence of a random permutation which follows some repeating pattern. This includes the case of any fixed pattern of ups and downs which has at least one of each, such as the a
lternating case considered by Stanley in [2] and Widom in [3]. In every case considered the convergence in the limit of long permutations is to normal with mean and variance linear in the length of the permutations.
Let $mathcal{S}_n$ denote the set of permutations of ${1,2,dots,n}$. The function $f(n,s)$ is defined to be the minimum size of a subset $Ssubseteq mathcal{S}_n$ with the property that for any $rhoin mathcal{S}_n$ there exists some $sigmain S$ such t
hat the Hamming distance between $rho$ and $sigma$ is at most $n-s$. The value of $f(n,2)$ is the subject of a conjecture by Kezdy and Snevily, which implies several famous conjectures about latin squares. We prove that the odd $n$ case of the Kezdy-Snevily Conjecture implies the whole conjecture. We also show that $f(n,2)>3n/4$ for all $n$, that $s!< f(n,s)< 3s!(n-s)log n$ for $1leq sleq n-2$ and that [f(n,s)>leftlfloor frac{2+sqrt{2s-2}}{2}rightrfloor frac{n}{2}] if $sgeq 3$.
Permutation tableaux were introduced by Steingr{i}msson and Williams. Corteel and Kim defined the sign of a permutation tableau in terms of the number of unrestricted columns. The sign-imbalance of permutation tableaux of length $n$ is the sum of sig
ns over permutation tableaux of length $n$. They have btained a formula for the sign-imbalance of permutation tableaux of length $n$ by using generating functions and asked for a combinatorial proof. Moreover, they raised the question of finding a sign-imbalance formula for type $B$ permutation tableaux introduced by Lam and Williams. We define a statistic $ wnm$ over permutations and show that the number of unrestricted columns over permutation tableaux of length $n$ is equally distributed with $ wnm$ over permutations of length $n$. This leads to a combinatorial interpretation of the formula of Corteel and Kim. For type $B$ permutation tableaux, we define the sign of a type $B$ permutation tableau in term of the number of certain rows and columns. On the other hand, we construct a bijection between the type $B$ permutation tableaux of length $n$ and symmetric permutations of length $2n$ and we show that the statistic $ wnm$ over symmetric permutations of length $2n$ is equally distributed with the number of certain rows and columns over type $B$ permutation tableaux of length $n$. Based on this correspondence and an involution on symmetric permutation of length $2n$, we obtain a sign-imbalance formula for type $B$ permutation tableaux.
Let d_i(G) be the density of the 3-vertex i-edge graph in a graph G, i.e., the probability that three random vertices induce a subgraph with i edges. Let S be the set of all quadruples (d_0,d_1,d_2,d_3) that are arbitrary close to 3-vertex graph dens
ities in arbitrary large graphs. Huang, Linial, Naves, Peled and Sudakov have recently determined the projection of the set S to the (d_0,d_3) plane. We determine the projection of the set S to all the remaining planes.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
