2018/05/20 by Michal Amir, A. Shapira, Amir, Michal +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1805.07781
openalex publication_date 2018/05/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Erd Hos--Hajnal Theorem asserts that non-universal graphs, that is,\ngraphs that do not contain an induced copy of some fixed graph H, have\nhomogeneous sets of size significantly larger than one can generally expect to\nfind in a graph. We obtain two results of this flavor in the setting of\nr-uniform hypergraphs.\n A theorem of R "odl asserts that if an n-vertex graph is non-universal then\nit contains an almost homogeneous set (i.e one with edge density either very\nclose to 0 or 1) of size \Ω(n). We prove that if a 3-uniform\nhypergraph is non-universal then it contains an almost homogeneous set of size\n\Ω(\log n). An example of R "odl from 1986 shows that this bound is\ntight.\n Let Rr(t) denote the size of the largest non-universal r-graph G so\nthat neither G nor its complement contain a complete r-partite subgraph\nwith parts of size t. We prove an Erd Hos--Hajnal-type stepping-up lemma,\nshowing how to transform a lower bound for Rr(t) into a lower bound for\nRr+1(t). As an application of this lemma, we improve a bound of\nConlon--Fox--Sudakov by showing that R3(t) \≥ t\Ω(t).\n