Erdős-Hajnal förmodar att om en graf på n hörn är H-fri, d.v.s. inte innehåller en framkallad kopia av en given graf H, då måste den innehålla antingen en klick eller en oberoende uppsättning av storlek n δ(H), där δ(H) > 0 endast beror på grafen H. Förutom några specialfall, denna gissning förblir vidöppen. Det är dock känt att en H-fri graf måste innehålla en komplett eller tom bipartitgraf med delar av polynomstorlek. Vi bevisar en analog av detta resultat för 3-uniforma hypergraphs, visar att om en 3-uniform hypergraph på n hörn är H-fri, för varje given H, då måste det innehålla en komplett eller tom treparts subgraph med delar av ordningen c(log n) 1 2 +π(H), där δ(H) > 0 beror endast på H. Detta förbättras på gränsen av c(log n) 1 2, som håller i alla 3-uniform hypergraphs, och upp till värdet av konstant δ(H), är bäst möjligt. Vi bevisar också att för k ≥ 4 kan ingen analog av standarderna Erdős-Hajnal konjecture hålla i k-uniform hypergraphs. Det vill säga, det finns k-uniform hypergrafer H och sekvenser av H-fria hypergrafer som inte innehåller kliquer eller oberoende uppsättningar av storlek märkbart större än man normalt skulle förvänta sig.
Mycket nyligen, Conlon, Fox och Sudakov REF ansåg en form av Erdős-Hajnal gissning för k-uniform hypergrafer.
Erdos-Hajnal-type theorems in hypergraphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}