Bibliographic Details
| Title: |
Two Erd\H{o}s--Hajnal-type Theorems in Hypergraphs |
| Authors: |
Amir, Michal, Shapira, Asaf, Tyomkyn, Mykhaylo |
| Publication Year: |
2018 |
| Collection: |
Mathematics |
| Subject Terms: |
Mathematics - Combinatorics |
| More Details: |
The Erd\H{o}s--Hajnal Theorem asserts that non-universal graphs, that is, graphs that do not contain an induced copy of some fixed graph $H$, have homogeneous sets of size significantly larger than one can generally expect to find in a graph. We obtain two results of this flavor in the setting of $r$-uniform hypergraphs. A theorem of R\"odl asserts that if an $n$-vertex graph is non-universal then it contains an almost homogeneous set (i.e one with edge density either very close to $0$ or $1$) of size $\Omega(n)$. We prove that if a $3$-uniform hypergraph is non-universal then it contains an almost homogeneous set of size $\Omega(\log n)$. An example of R\"odl from 1986 shows that this bound is tight. Let $R_r(t)$ denote the size of the largest non-universal $r$-graph $G$ so that neither $G$ nor its complement contain a complete $r$-partite subgraph with parts of size $t$. We prove an Erd\H{o}s--Hajnal-type stepping-up lemma, showing how to transform a lower bound for $R_{r}(t)$ into a lower bound for $R_{r+1}(t)$. As an application of this lemma, we improve a bound of Conlon--Fox--Sudakov by showing that $R_3(t) \geq t^{\Omega(t)}$.
Comment: 19 pages |
| Document Type: |
Working Paper |
| Access URL: |
http://arxiv.org/abs/1805.07781 |
| Accession Number: |
edsarx.1805.07781 |
| Database: |
arXiv |
