| | |
| | |
Stat |
Members: 3645 Articles: 2'501'711 Articles rated: 2609
20 April 2024 |
|
| | | |
|
Article overview
| |
|
Monotone Subsequences in High-Dimensional Permutations | Nathan Linial
; Michael Simkin
; | Date: |
8 Feb 2016 | 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 $Omega_{k}left(sqrt{n}
ight)$, 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 $Theta_{k}left(n^{frac{k}{k+1}}
ight)$. | Source: | arXiv, 1602.2719 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |