Alon's universality conjecture for random permutations
Statement
Let be a positive integer and let be the set of permutations of . A permutation is -universal if it contains every pattern in . For fixed , consider a uniformly random permutation of length . Alon's universality conjecture. With high probability, it is -universal. Here, with high probability means with probability as . The conjecture predicts the asymptotically sharp threshold for a random permutation to contain all patterns of length ; the paper proves universality for substantially larger lengths but leaves this asymptotic threshold open.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.