Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2406.04154 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910719375572992 |
|---|---|
| author | Arnold, Fabian Gishboliner, Lior Sudakov, Benny |
| author_facet | Arnold, Fabian Gishboliner, Lior Sudakov, Benny |
| contents | The celebrated Erdős-Hajnal conjecture says that any graph without a fixed induced subgraph $H$ contains a very large homogeneous set. A direct analog of this conjecture is not true for hypergraphs. In this paper we present two natural variants of this problem which do hold for hypergraphs. We show that for every $r \geq 3$, $m \geq m_0(r)$ and $0 \leq f \leq \binom{m}{r}$, if an $r$-graph $G$ does not contain $m$ vertices spanning exactly $f$ edges, then $G$ contains much bigger homogeneous sets than what is guaranteed to exist in general $r$-graphs. We also prove that if a $3$-graph $G$ does not contain homogeneous sets of polynomial size, then for every $m \geq 3$ there are $Ω(m^3)$ values of $f$ such that $G$ contains $m$ vertices spanning exactly $f$ edges. This makes progress on a problem of Axenovich, Bradač, Gishboliner, Mubayi and Weber. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_04154 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Two Erdos-Hajnal-type theorems for forbidden order-size pairs Arnold, Fabian Gishboliner, Lior Sudakov, Benny Combinatorics The celebrated Erdős-Hajnal conjecture says that any graph without a fixed induced subgraph $H$ contains a very large homogeneous set. A direct analog of this conjecture is not true for hypergraphs. In this paper we present two natural variants of this problem which do hold for hypergraphs. We show that for every $r \geq 3$, $m \geq m_0(r)$ and $0 \leq f \leq \binom{m}{r}$, if an $r$-graph $G$ does not contain $m$ vertices spanning exactly $f$ edges, then $G$ contains much bigger homogeneous sets than what is guaranteed to exist in general $r$-graphs. We also prove that if a $3$-graph $G$ does not contain homogeneous sets of polynomial size, then for every $m \geq 3$ there are $Ω(m^3)$ values of $f$ such that $G$ contains $m$ vertices spanning exactly $f$ edges. This makes progress on a problem of Axenovich, Bradač, Gishboliner, Mubayi and Weber. |
| title | Two Erdos-Hajnal-type theorems for forbidden order-size pairs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2406.04154 |