Monotone subsequences in high-dimensional permutations

DOI10.1017/S0963548317000517MaRDI QIDQ4601054zbMATH OpenOpenAlexFDO

Authors 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)

Abstract: This paper is part of the ongoing effort to study high-dimensional permutations. We prove the analogue to the ErdH{o}s-Szekeres theorem: For every $kge1$, every order-$n$ $k$-dimensional permutation contains a monotone subsequence of length $Omeg{a}_{k}left(sqrtnight)$, and this is tight. On the other hand, and unlike the classical case, the longest monotone subsequence in a random $k$-dimensional permutation of order $n$ is asymptotically almost surely $Thet{a}_{k}left(n^{frackk+1}ight)$.

Recommendations

• Monotone subsequences in any dimension
• Monotonic subsequences in dimensions higher than one
• The minimum number of monotone subsequences
• Higher-order Erdős-Szekeres theorems
• An upper bound on the number of high-dimensional permutations

Cites work

• A decomposition theorem for partially ordered sets
• A Dual of Dilworth's Decomposition Theorem
• A multidimensional generalization of the Erdős-Szekeres lemma on monotone subsequences.
• A variational problem for random Young tableaux
• 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
• Generating uniformly distributed random latin squares
• scientific article; zbMATH DE number 3630761 (Why is no real title available?)
• scientific article; zbMATH DE number 795114 (Why is no real title available?)
• scientific article; zbMATH DE number 3373691 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Monotonic Subsequences
• On the distribution of the length of the longest increasing subsequence of random permutations
• On the vertices of the d-dimensional Birkhoff polytope
• The difference between consecutive primes. II
• The Longest Chain Among Random Points in Euclidean Space

Cited in

(18)

• Monotone subsequences in (0,1)-matrices
• Monotone subsequences in any dimension
• On Monge sequences in \(d\)-dimensional arrays
• Erdős-Szekeres theorem for cyclic permutations
• The minimum number of monotone subsequences
• Universal arrays
• A multidimensional generalization of the Erdős-Szekeres lemma on monotone subsequences.
• Heapability, interactive particle systems, partial orders: results and open problems
• An Erdős-Hajnal analogue for permutation classes
• An upper bound on the number of high-dimensional permutations
• Substructures in Latin squares
• Large deviations in random latin squares
• Erdős-Szekeres theorem for multidimensional arrays
• Discrete geometry. Abstracts from the workshop held January 21--26, 2024
• Exponential Erdős-Szekeres theorem for matrices
• Patterns in multi-dimensional permutations
• Extremal, enumerative and probabilistic results on ordered hypergraph matchings
• Partitioning permutations into monotone subsequences

This page was built for publication: Monotone subsequences in high-dimensional permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601054)