On increasing sequences formed by points from a random finite subset of a hypercube
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911053467615232 |
|---|---|
| author | Pittel, Boris |
| author_facet | Pittel, Boris |
| contents | Consider $S$, a set of $n$ points chosen uniformly at random and independently from the unit hypercube of dimension $t>2$. Order $S$ by using the Cartesian product of the $t$ standard orders of $[0,1]$. We determine a constant $\bar x(t)<e$ such that, with probability $\ge 1-\exp(-Θ(\eps)n^{1/t})$, cardinality of a largest subset of comparable points is at most $(\bar x(t)+\eps)n^{1/t}$. The bound $\bar x(t)$ complements an explicit lower bound obtained by Bollobás and Winkler in 1982. Furthermore, we use Dilworth's theorem on partitions of a set into chains to prove that the cardinality of a largest antichain, i. e. a largest subset of incomparable points, is at least $(1-\eps) (n/e)^{1-1/t}$ with probability exponentially close to $1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_05365 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On increasing sequences formed by points from a random finite subset of a hypercube Pittel, Boris Combinatorics 60C05, 05C05, 92B10 Consider $S$, a set of $n$ points chosen uniformly at random and independently from the unit hypercube of dimension $t>2$. Order $S$ by using the Cartesian product of the $t$ standard orders of $[0,1]$. We determine a constant $\bar x(t)<e$ such that, with probability $\ge 1-\exp(-Θ(\eps)n^{1/t})$, cardinality of a largest subset of comparable points is at most $(\bar x(t)+\eps)n^{1/t}$. The bound $\bar x(t)$ complements an explicit lower bound obtained by Bollobás and Winkler in 1982. Furthermore, we use Dilworth's theorem on partitions of a set into chains to prove that the cardinality of a largest antichain, i. e. a largest subset of incomparable points, is at least $(1-\eps) (n/e)^{1-1/t}$ with probability exponentially close to $1$. |
| title | On increasing sequences formed by points from a random finite subset of a hypercube |
| topic | Combinatorics 60C05, 05C05, 92B10 |
| url | https://arxiv.org/abs/2505.05365 |