Two Erdős-Hajnal-type theorems in hypergraphs

DOI10.1016/J.JCTB.2020.03.001MaRDI QIDQ2221933zbMATH OpenOpenAlexFDO

Authors Michal Amir, Asaf Shapira, Mykhaylo Tyomkyn

Publication date 3 February 2021

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.07781

zbMATH Keywords

Erdős-Hajnal theoremhypergraphsRamsey theory

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Hypergraphs (05C65) Ramsey theory (05D10)

Abstract: The ErdH{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(logn)$. 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 ErdH{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)}$.

Recommendations

• Erdős-Hajnal-type theorems in hypergraphs
• A note on the Erdős-Hajnal hypergraph Ramsey problem
• On the Erdős-Hajnal problem for 3-graphs
• The Erdős-Hajnal hypergraph Ramsey problem
• On Ramsey - Turan type theorems for hypergraphs

Cites work

• A Ramsey-Type Theorem for Orderings of a Graph
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• Complete partite subgraphs in dense hypergraphs
• Erdős-Hajnal-type theorems in hypergraphs
• Graphs with many r -cliques have large complete r -partite subgraphs
• scientific article; zbMATH DE number 3711961 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• Hypergraph Ramsey numbers
• Hypergraph regularity and quasi-randomness
• Induced Ramsey-type theorems
• Large almost monochromatic subsets in hypergraphs
• On a problem of K. Zarankiewicz
• On a Turán problem in weakly quasirandom 3-uniform hypergraphs
• On extremal problems of graphs and generalized graphs
• On universality of graphs with uniformly distributed edges
• Quasi-random hypergraphs
• Ramsey-type theorems
• Ramsey-type theorems with forbidden subgraphs
• The Erdős-Hajnal conjecture. A survey

Cited in

(6)

• A 2-isomorphism theorem for hypergraphs
• An Erdős-Gallai type theorem for uniform hypergraphs
• On 3‐graphs with no four vertices spanning exactly two edges
• Large cliques or cocliques in hypergraphs with forbidden order-size pairs
• Erdős-Hajnal-type theorems in hypergraphs
• Ramsey-type theorems

This page was built for publication: Two Erdős-Hajnal-type theorems in hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2221933)