Erdos–Hajnal-type theorems in hypergraphs
The Erdos–Hajnal conjecture states that if a graph on n vertices is H-free, that is, it does not contain an induced copy of a given graph H, then it must contain either a clique or an independent set of size n[superscript δ(H)], where δ(H) > 0 depends only on the graph H. Except for a few special...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier
2015
|
| Online Access: | http://hdl.handle.net/1721.1/99445 |
| _version_ | 1826196161161068544 |
|---|---|
| author | Conlon, David Fox, Jacob Sudakov, Benny |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Conlon, David Fox, Jacob Sudakov, Benny |
| author_sort | Conlon, David |
| collection | MIT |
| description | The Erdos–Hajnal conjecture states that if a graph on n vertices is H-free, that is, it does not contain an induced copy of a given graph H, then it must contain either a clique or an independent set of size n[superscript δ(H)], where δ(H) > 0 depends only on the graph H. Except for a few special cases, this conjecture remains wide open. However, it is known that an H-free graph must contain a complete or empty bipartite graph with parts of polynomial size.
We prove an analogue of this result for 3-uniform hypergraphs, showing that if a 3-uniform hypergraph on n vertices is H-free, for any given H, then it must contain a complete or empty tripartite subgraph with parts of order c(logn)[superscript 1/2 + δ(H)], where δ(H) > 0 depends only on H. This improves on the bound of c(logn)[superscript 1/]2, which holds in all 3-uniform hypergraphs, and, up to the value of the constant δ(H), is best possible.
We also prove that, for k ⩾ 4, no analogue of the standard Erdos–Hajnal conjecture can hold in k-uniform hypergraphs. That is, there are k -uniform hypergraphs H and sequences of H-free hypergraphs which do not contain cliques or independent sets of size appreciably larger than one would normally expect. |
| first_indexed | 2024-09-23T10:22:09Z |
| format | Article |
| id | mit-1721.1/99445 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:22:09Z |
| publishDate | 2015 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | mit-1721.1/994452022-09-30T20:38:41Z Erdos–Hajnal-type theorems in hypergraphs Conlon, David Fox, Jacob Sudakov, Benny Massachusetts Institute of Technology. Department of Mathematics Fox, Jacob The Erdos–Hajnal conjecture states that if a graph on n vertices is H-free, that is, it does not contain an induced copy of a given graph H, then it must contain either a clique or an independent set of size n[superscript δ(H)], where δ(H) > 0 depends only on the graph H. Except for a few special cases, this conjecture remains wide open. However, it is known that an H-free graph must contain a complete or empty bipartite graph with parts of polynomial size. We prove an analogue of this result for 3-uniform hypergraphs, showing that if a 3-uniform hypergraph on n vertices is H-free, for any given H, then it must contain a complete or empty tripartite subgraph with parts of order c(logn)[superscript 1/2 + δ(H)], where δ(H) > 0 depends only on H. This improves on the bound of c(logn)[superscript 1/]2, which holds in all 3-uniform hypergraphs, and, up to the value of the constant δ(H), is best possible. We also prove that, for k ⩾ 4, no analogue of the standard Erdos–Hajnal conjecture can hold in k-uniform hypergraphs. That is, there are k -uniform hypergraphs H and sequences of H-free hypergraphs which do not contain cliques or independent sets of size appreciably larger than one would normally expect. 2015-10-26T11:59:40Z 2015-10-26T11:59:40Z 2012-06 2011-04 Article http://purl.org/eprint/type/JournalArticle 00958956 1096-0902 http://hdl.handle.net/1721.1/99445 Conlon, David, Jacob Fox, and Benny Sudakov. “Erdos–Hajnal-Type Theorems in Hypergraphs.” Journal of Combinatorial Theory, Series B 102, no. 5 (September 2012): 1142–1154. en_US http://dx.doi.org/10.1016/j.jctb.2012.05.005 Journal of Combinatorial Theory, Series B Creative Commons Attribution-Noncommercial-NoDerivatives http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier MIT Web Domain |
| spellingShingle | Conlon, David Fox, Jacob Sudakov, Benny Erdos–Hajnal-type theorems in hypergraphs |
| title | Erdos–Hajnal-type theorems in hypergraphs |
| title_full | Erdos–Hajnal-type theorems in hypergraphs |
| title_fullStr | Erdos–Hajnal-type theorems in hypergraphs |
| title_full_unstemmed | Erdos–Hajnal-type theorems in hypergraphs |
| title_short | Erdos–Hajnal-type theorems in hypergraphs |
| title_sort | erdos hajnal type theorems in hypergraphs |
| url | http://hdl.handle.net/1721.1/99445 |
| work_keys_str_mv | AT conlondavid erdoshajnaltypetheoremsinhypergraphs AT foxjacob erdoshajnaltypetheoremsinhypergraphs AT sudakovbenny erdoshajnaltypetheoremsinhypergraphs |