Monotone Subsequences in High-Dimensional Permutations

DOI10.1017/S0963548317000517zbMath1378.05003arXiv1602.02719OpenAlexW2263741084MaRDI QIDQ4601054

Nathan Linial, Michael Simkin

Publication date: 19 January 2018

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.02719

zbMATH Keywords

\(k\)-dimensional permutation of order \(n\)

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Related Items

Substructures in Latin squares, Large deviations in random latin squares, Erdős-Szekeres theorem for multidimensional arrays, Universal arrays, Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An upper bound on the number of high-dimensional permutations
• Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 13th international workshop, APPROX 2010, and 14th international workshop, RANDOM 2010, Barcelona, Spain, September 1--3, 2010. Proceedings
• A variational problem for random Young tableaux
• On the vertices of the \(d\)-dimensional Birkhoff polytope
• A decomposition theorem for partially ordered sets
• The Difference Between Consecutive Primes, II
• A Multidimensional Generalization of the Erdős–Szekeres Lemma on Monotone Subsequences
• The Longest Chain Among Random Points in Euclidean Space
• Generating uniformly distributed random latin squares
• On the distribution of the length of the longest increasing subsequence of random permutations
• A Dual of Dilworth's Decomposition Theorem
• Monotonic Subsequences