Property O and Erdős--Szekeres properties in linear hypergraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909781716893696 |
|---|---|
| author | Jiang, Suyun Lamaison, Ander Ouyang, Minghui |
| author_facet | Jiang, Suyun Lamaison, Ander Ouyang, Minghui |
| contents | An oriented $k$-uniform hypergraph, or oriented $k$-graph, is said to satisfy Property O if, for every linear ordering of its vertex set, there is some edge oriented consistently with this order. The minimum number $f(k)$ of edges in a $k$-graph with Property O was first studied by Duffus, Kay, and Rödl, and later improved by Kronenberg, Kusch, Lamaison, Micek, and Tran. In particular, they established the bounds $k! + 1 \le f(k) \le \left(\lfloor\tfrac{k}{2}\rfloor+1 \right) k! - \lfloor\tfrac{k}{2}\rfloor(k-1)!$ for every $k \ge 2$.
In this note, we extend the study of Property O to the linear setting. We determine the minimum number $f'(k)$ of edges in a linear $k$-graph up to a $\operatorname{poly}(k)$ multiplicative factor, showing that $\frac{(k!)^2}{2e^2k^4} \le f'(k) \le (1+o(1)) \cdot 4 k^6 \ln^2 k \cdot (k!)^2$. Our approach also yields bounds on the minimum number $n'(k)$ of vertices in an oriented linear $k$-graph with Property O. Additionally, we explore the minimum number of edges and vertices required in a linear $k$-graph satisfying the newly introduced Erdős--Szekeres properties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_08692 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Property O and Erdős--Szekeres properties in linear hypergraphs Jiang, Suyun Lamaison, Ander Ouyang, Minghui Combinatorics 05C65 (Primary), 05C35, 05D40 (Secondary) An oriented $k$-uniform hypergraph, or oriented $k$-graph, is said to satisfy Property O if, for every linear ordering of its vertex set, there is some edge oriented consistently with this order. The minimum number $f(k)$ of edges in a $k$-graph with Property O was first studied by Duffus, Kay, and Rödl, and later improved by Kronenberg, Kusch, Lamaison, Micek, and Tran. In particular, they established the bounds $k! + 1 \le f(k) \le \left(\lfloor\tfrac{k}{2}\rfloor+1 \right) k! - \lfloor\tfrac{k}{2}\rfloor(k-1)!$ for every $k \ge 2$. In this note, we extend the study of Property O to the linear setting. We determine the minimum number $f'(k)$ of edges in a linear $k$-graph up to a $\operatorname{poly}(k)$ multiplicative factor, showing that $\frac{(k!)^2}{2e^2k^4} \le f'(k) \le (1+o(1)) \cdot 4 k^6 \ln^2 k \cdot (k!)^2$. Our approach also yields bounds on the minimum number $n'(k)$ of vertices in an oriented linear $k$-graph with Property O. Additionally, we explore the minimum number of edges and vertices required in a linear $k$-graph satisfying the newly introduced Erdős--Szekeres properties. |
| title | Property O and Erdős--Szekeres properties in linear hypergraphs |
| topic | Combinatorics 05C65 (Primary), 05C35, 05D40 (Secondary) |
| url | https://arxiv.org/abs/2509.08692 |