RECORD
A Sharp Ramsey Theorem for Ordered Hypergraph Matchings
Combinatorics · Submitted 9 Sep 2023
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We prove essentially sharp bounds for Ramsey numbers of ordered hypergraph matchings, inroduced recently by Dudek, Grytczuk, and Ruci\'{n}ski.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We prove essentially sharp bounds for Ramsey numbers of ordered hypergraph matchings, inroduced recently by Dudek, Grytczuk, and Ruci\'{n}ski. Namely, for any $r \ge 2$ and $n \ge 2$, we show that any collection $\mathcal H$ of $n$ pairwise disjoint subsets in $\mathbb Z$ of size $r$ contains a subcollection of size $\lfloor n^{1/(2^r-1)}/2\rfloor$ in which every pair of sets are in the same relative position with respect to the linear ordering on $\mathbb Z$. This improves previous bounds of Dudek-Grytczuk-Ruci\'nski and of Anastos-Jin-Kwan-Sudakov and is sharp up to a factor of $2$. For large $r$, we even obtain such a subcollection of size $\lfloor (1-o(1))\cdot n^{1/(2^r-1)}\rfloor$, which is asymptotically tight (here, the $o(1)$-term tends to zero as $r \to \infty$, regardless of the value of $n$). Furthermore, we prove a multiparameter extension of this result where one wants to find a clique of prescribed size $m_P$ for each relative position pattern $P$. Our bound is sharp for all choices of parameters $m_P$, up to a constant factor depending on $r$ only. This answers questions of Anastos-Jin-Kwan-Sudakov and of Dudek-Grytczuk-Ruci\'nski.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We prove essentially sharp bounds for Ramsey numbers of ordered hypergraph matchings, inroduced recently by Dudek, Grytczuk, and Ruci\'{n}ski. | contribution 0.94 | 0.95 | 0.48 | asserted 1.00 |
| s1 | Namely, for any $r \ge 2$ and $n \ge 2$, we show that any collection $\mathcal H$ of $n$ pairwise disjoint subsets in $\mathbb Z$ of size $r$ contains a subcollection of size $\lfloor n^{1/(2^r-1)}/2\rfloor$ in which every pair of sets are in the same relative position with respect to the linear ordering on $\mathbb Z$. | result 0.99 | 0.95 | 0.83 | asserted 1.00 |
| s2 | This improves previous bounds of Dudek-Grytczuk-Ruci\'nski and of Anastos-Jin-Kwan-Sudakov and is sharp up to a factor of $2$. | interpretation 0.54 | 0.73 | 0.20 | asserted 1.00 |
| s3 | For large $r$, we even obtain such a subcollection of size $\lfloor (1-o(1))\cdot n^{1/(2^r-1)}\rfloor$, which is asymptotically tight (here, the $o(1)$-term tends to zero as $r \to \infty$, regardless of the value of $n$). | result 0.98 | 0.95 | 0.17 | asserted 1.00 |
| s4 | Furthermore, we prove a multiparameter extension of this result where one wants to find a clique of prescribed size $m_P$ for each relative position pattern $P$. | contribution 0.76 | 0.95 | 0.09 | asserted 1.00 |
| s5 | Our bound is sharp for all choices of parameters $m_P$, up to a constant factor depending on $r$ only. | result 0.84 | 0.92 | 0.17 | asserted 1.00 |
| s6 | This answers questions of Anastos-Jin-Kwan-Sudakov and of Dudek-Grytczuk-Ruci\'nski. | interpretation 0.84 | 0.49 | 0.11 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v4
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We prove essentially sharp bounds for Ramsey numbers of ordered hypergraph matchings, inroduced recently by Dudek, Grytczuk, and Ruci\'{n}ski. Namely, for any $r \ge 2$ and $n \ge 2$, we show that any collection $\mathcal H$ of $n$ pairwise disjoint subsets in $\mathbb Z$ of size $r$ contains a subcollection of size $\lfloor n^{1/(2^r-1)}/2\rfloor$ in which every pair of sets are in the same relative position with respect to the linear ordering on $\mathbb Z$. This improves previous bounds of Dudek-Grytczuk-Ruci\'nski and of Anastos-Jin-Kwan-Sudakov and is sharp up to a factor of $2$. For large $r$, we even obtain such a subcollection of size $\lfloor (1-o(1))\cdot n^{1/(2^r-1)}\rfloor$, which is asymptotically tight (here, the $o(1)$-term tends to zero as $r \to \infty$, regardless of the value of $n$). Furthermore, we prove a multiparameter extension of this result where one wants to find a clique of prescribed size $m_P$ for each relative position pattern $P$. Our bound is sharp for all choices of parameters $m_P$, up to a constant factor depending on $r$ only. This answers questions of Anastos-Jin-Kwan-Sudakov and of Dudek-Grytczuk-Ruci\'nski.
Human review
How the literature uses it
1 arXiv paper cite this in 4 sentences
What it cites
Cites as background 2 papers
-
Ramsey Theory is one of the most active areas of combinatorics, with a rich history spanning an entire century and many exciting recent results (e.g. [ref] , to mention just a few).
An exponential improvement for diagonal Ramsey · Introduction · 1.00
-
Ramsey Theory is one of the most active areas of combinatorics, with a rich history spanning an entire century and many exciting recent results (e.g. [ref] , to mention just a few).
The girth Ramsey theorem · Introduction · 1.00
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.