Conlon–Fox–Sudakov (2011/2012) — the Erdős–Hajnal conjecture has a tripartite 3-uniform analogue, and provably NO clique/independent-set analogue for k>3

Statement

The (still largely open) Erdős–Hajnal conjecture for graphs states: for every graph $H$ there is $\delta(H)>0$ such that every $H$-free graph (no induced copy of $H$) on $n$ vertices contains a clique or independent set of size $n^{\delta(H)}$. A weaker, known consequence is that every $H$-free graph contains a complete or empty bipartite subgraph with both parts of polynomial size $n^{\Omega(1)}$ (Erdős–Hajnal–Pach; sharpened by Fox–Sudakov).

Rödl and Schacht asked whether this bipartite-blow-up statement has a tripartite analogue for 3-uniform hypergraphs: does every $H$-free 3-uniform hypergraph on $n$ vertices contain a complete or empty tripartite subgraph with parts *much larger* than the $c(\log n)^{1/2}$ bound (due to Erdős) that holds in every 3-uniform hypergraph unconditionally? And, separately: does some direct clique-or-independent-set analogue of Erdős–Hajnal (as opposed to the bipartite/tripartite blow-up weakening) hold at all for $k$-uniform hypergraphs, $k\geq4$?

Facts

- Origin: D. Conlon, J. Fox, B. Sudakov, "Erdős-Hajnal-type theorems in hypergraphs," arXiv:1104.5544 (29 Apr 2011); *J. Combin. Theory Ser. B* 102 (2012), 1142–1154. Motivated by a question of Rödl and Schacht (acknowledged in the paper). - Baseline (unconditional) bound: every 3-uniform hypergraph on $n$ vertices — $H$-free or not — contains a complete or empty tripartite subgraph with parts of order $\geq c(\log n)^{1/2}$; this follows from a standard extremal result of Erdős (1964, "On extremal problems of graphs and generalized graphs"). - Prior partial progress: Rödl and Schacht (unpublished, cited as personal communication) had already shown, via the hypergraph regularity method, that $H$-freeness forces tripartite parts growing *arbitrarily faster* than $(\log n)^{1/2}$ — but regularity-method proofs give no explicit/effective bound on the growth rate. - Companion result (same three authors, arXiv:0901.3912, Israel J. Math. 2011): for the *discrepancy* version of this question (no forbidden $H$, just: does every 2-colouring of triples contain a large near-monochromatic set?), they prove every 2-coloring of the triples of an $n$-set has a $(1-\epsilon)$-monochromatic subset of size $c\sqrt{\log n}$, resolving the $t=3$ case of Erdős's 1989 hypergraph-discrepancy question Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? in the direction Erdős himself guessed (a single jump at $\alpha=0$). This paper (arXiv:1104.5544) is the closely related $H$-free (Ramsey/induced-subgraph), rather than 2-coloring/discrepancy, sibling of that result, and independently reproves the baseline $c(\log n)^{1/2}$ bound. - Downstream citation as an obstruction: erdosproblems.com/161 (this wiki's Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? page) cites arXiv:1104.5544's Theorem 1.2 explicitly as "a structural obstruction that plausibly explains why the general-$t\geq4$ case of #161 has resisted the same technique" — i.e. the impossibility half of this paper is already load-bearing for at least one live open problem in this KB. - Follow-up literature: a 2018+ paper "Two Erdős–Hajnal-type theorems in hypergraphs," arXiv:1805.07781, extends/refines this line (not read in detail here; flagged for a future page).

Answer — two separate theorems, one positive and one negative

Theorem 1.1 (positive, $k=3$). For every 3-uniform hypergraph $H$ on $t$ vertices there is $\delta(H)=1/(55t^2)>0$ such that every $H$-free 3-uniform hypergraph on $n$ (sufficiently large) vertices contains a complete or empty tripartite subgraph with every part of order at least $(\log n)^{1/2+\delta(H)}$. This beats the universal $(\log n)^{1/2}$ bound and is best possible up to the constant $\delta(H)$: for many $H$ (e.g. the tight 5-cycle $H=\{123,234,345,451,512\}$), no bound better than $c\log n$ is achievable — witnessed by lifting a $K_n(1/2)$-random-edge-density-avoiding graph $G_n$ to the 3-uniform hypergraph $\hat G_n=\{(i_1,i_2,i_3): i_1<i_2<i_3,\ (i_1,i_2)\in G_n\}$, which is $H$-free but provably has no tripartite blow-up above $c\log n$.

Theorem 1.2 (negative, $k\geq4$): no analogue of the standard (clique-or-independent-set) Erdős–Hajnal conjecture can hold in $k$-uniform hypergraphs for any $k\geq4$. Precisely: for every $k\geq4$ there is a constant $c_k$, a $k$-uniform hypergraph $H$, and a sequence of $H$-free $k$-uniform hypergraphs $G_n$ on $n$ vertices whose largest monochromatic-type clique or independent set has size at most $c_k\, r_k^{-1}(n)$ — i.e. no larger than what Ramsey's theorem guarantees in an *arbitrary* (not-necessarily-$H$-free) $k$-uniform hypergraph. Excluding $H$ buys nothing. (The weaker $k$-partite blow-up question is left open as Conjecture 1 in the paper's concluding remarks, with a matching near-optimal construction giving $c(\log n)^{1/(k-2)}$ as the plausible truth.)

---

The transferable technique (positive side, $k=3$): build a hypergraph-specific density notion around an *auxiliary graph's triangles*, then mine density-failure itself for a giant blow-up

1. Diagnose why naive "tri-density" (many edges between every 3 large vertex sets) fails. There exist 3-uniform hypergraphs that look dense by this naive measure yet contain no $K_4^{(3)}$ (or even $K_4^{(3)}$ minus an edge) — a known obstruction from the hypergraph-quasirandomness literature (Kohayakawa–Nagle–Rödl–Schacht). So density must be measured relative to an auxiliary structure, exactly as in hypergraph regularity theory. 2. Define tri-$(\epsilon,\rho)$-density correctly: a 3-uniform $G$ is tri-$(\epsilon,\rho)$-dense if, for *any* three disjoint vertex sets $V_1,V_2,V_3$ and *any* three bipartite graphs $G_{12},G_{23},G_{31}$ between them that together span at least $\epsilon n^3$ triangles, at least a $\rho$-fraction of those triangles are edges of $G$. This is a quantifier over *all* auxiliary tripartite triangle-structures, not just the complete tripartite one — the key strengthening that makes the notion useful. 3. Embedding lemma (Lemma 2.1): if $G$ and its complement $\bar G$ are both tri-$(\epsilon,\rho)$-dense with $\epsilon=\rho^{c(H)}$ polynomially small, $G$ contains an induced copy of any fixed small $H$ — proved by a vertex-by-vertex greedy embedding, at each step passing to a smaller bi-dense neighborhood (an induction directly modeled on the classical graph-regularity blow-up/embedding lemma, lifted one dimension). 4. The dichotomy that does the real work: if $G$ is $H$-free, the embedding lemma forces $G$ or $\bar G$ to fail tri-density — i.e. there exist three large sets and an auxiliary tripartite triangle-structure on them where $G$'s edges are *very* unevenly distributed over the triangles (far from a $\rho$-fraction). This failure is not a dead end — it is refined raw material. 5. Lemma 3.3 (the "excess-triangle" engine, the real novelty): if a tripartite triangle-structure has $\geq\delta n^3$ triangles and a 3-uniform hypergraph $G$ captures a $(1-\eta)$-fraction of them, then $G$ contains a much larger complete tripartite $K^{(3)}_{s,s,s}$ than one would expect at that density. Proved by an iterated "good edge / bad edge" peeling: at each of two rounds, throw away the (few) triangle-poor edges, apply a Kővári–Sós–Turán-style double-counting-plus-pigeonhole bipartite blow-up lemma (Lemmas 3.1–3.2, the double-counting/convexity argument of Kővári–Sós–Turán applied to bipartite graphs) to pass to a smaller but still-huge complete bipartite piece, and repeat — bootstrapping an $O(\log n)$-size structure out of an $n^3$-scale density surplus. 6. Exponent-balancing closes the proof (Theorem 3.1): choosing $\rho=(\log n)^{1/(27t^2)}$ and $\epsilon=(2t)^{-10}\rho^{3t^2}$ makes the embedding lemma's polynomial vertex requirement and Lemma 3.3's requirement both satisfiable with room to spare, yielding the final exponent $\delta(H)=1/(55t^2)$. 7. Portable takeaway: when trying to lift a "$H$-free $\Rightarrow$ big blow-up" theorem one dimension up (graphs $\to$ 3-uniform hypergraphs), (a) the *correct* quasirandomness notion must be defined relative to an auxiliary lower-dimensional structure's substructures (here: triangles in an auxiliary graph), not raw density, because naive density admits known counterexamples; and (b) the failure mode of that quasirandomness notion — not just its success mode — must itself be shown to force a large blow-up, via a dedicated combinatorial "excess implies blow-up" lemma (here Lemma 3.3) built from classical double-counting (Kővári–Sós–Turán) applied iteratively. The authors themselves identify Lemma 3.3 — the excess-triangle-to-blow-up step, fundamentally about 3-fold/triangle interactions one level below the hypergraph's own uniformity — as exactly the piece that "does not seem to generalise easily" to $k\geq4$, which is the structural reason Theorem 1.1's method caps out at $k=3$ and Conjecture 1 (the $k$-partite generalization) remains open.

The transferable technique (negative side, $k\geq4$): show the *canonical near-optimal lower-bound family* has too little descriptive complexity to realize a given finite pattern, so excluding that pattern is free

1. Use the Erdős–Hajnal stepping-up construction — the classical tower-type lower-bound family for hypergraph Ramsey numbers: encode vertices as binary strings, colour a $(k{+}1)$-tuple $\epsilon_1<\dots<\epsilon_{k+1}$ by looking at the $k$ "first-difference" positions $\delta_i=\delta(\epsilon_i,\epsilon_{i+1})$ and recursing — either taking the colour of the $k$-tuple $(\delta_1,\dots,\delta_k)$ (if monotone) or the colour of whichever extremum type (max/min) occurs first (if not). This is the standard machine that shows $r_k(\ell)$ grows one exponential tower-level per uniformity increase, matching (up to constants) the known upper bounds via Erdős–Rado. 2. Count, don't construct, the forbidden pattern (Lemma 4.1): the colour of every $(k{+}1)$-tuple in a step-up colouring is a function of only $h-1$ real "step" values $\delta_1,\dots,\delta_{h-1}$ (for an $h$-vertex sub-hypergraph) *and their total preorder* — not of $\binom{h}{k+1}$ independent bits. The number of realizable colourings on $h$ vertices is therefore bounded by (ordered Bell number) $\times$ ($2^{\binom{h-1}{k}}$ colour choices) $\leq (h-1)^{h-1}2^{\binom{h-1}{k}}$ — while the number of genuinely distinct $(k{+}1)$-uniform 2-colourings on $h$ vertices is $\sim 2^{\binom{h}{k+1}}/h!$. For $h\geq k+5$ the ratio of realizable-to-total colourings tends to $0$, so some fixed finite pattern $H$ provably never occurs in any step-up colouring, purely by a counting/pigeonhole argument — no explicit $H$ needs to be exhibited. 3. Conclude the impossibility: step-up colourings are, by construction, *already* essentially Ramsey-optimal (they match the known tower-type lower bounds for $r_k(\ell)$). Since they are automatically $H$-free for the Lemma-4.1 pattern $H$, being $H$-free imposes no additional structure beyond what an arbitrary hypergraph already has — so no clique-or-independent-set bound stronger than the generic Ramsey bound can be forced by excluding $H$. This directly falsifies any hoped-for Erdős–Hajnal-style "polynomial/quasipolynomial improvement from excluding a fixed pattern" statement for $k\geq4$-uniform hypergraphs. 4. Portable takeaway: to show a Ramsey-type "$H$-free buys you more structure" theorem cannot hold, look for a canonical, already near-tight extremal/Ramsey lower-bound *family* and show — via a counting/entropy bound on how many distinct finite patterns that family can realize — that the family is automatically free of *some* fixed finite obstruction "for free." If the family already achieves (near-)optimal parameters and yet misses arbitrary patterns by sheer descriptive-complexity poverty, excluding that missed pattern cannot improve on the family's already-optimal behaviour. This is a general recipe for impossibility results in Ramsey/extremal theory, distinct from (and complementary to) probabilistic-deletion lower-bound arguments — here the "free lunch" obstruction comes from *structured*, low-complexity constructions rather than randomness.

Related

- Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? — Erdős's 1989 hypergraph-discrepancy-jump problem; this paper's Theorem 1.2 is cited there (erdosproblems.com/161, already in this wiki) as the structural reason the $t\geq4$ case resists the $t=3$ technique of the companion paper arXiv:0901.3912. - Hypergraph regularity / Gowers uniformity norms and density-increment arguments: quasirandom decomposition + counting/removal lemmas, and the iterative-density-increase route to Szemerédi-type theorems — the broader quasirandomness/regularity-method framework (Gowers; Rödl–Skokan; Nagle–Rödl–Schacht) that motivates and generalizes the paper's tri-$(\epsilon,\rho)$-density notion; Rödl–Schacht's own prior (regularity-method, ineffective-bound) partial result is the direct predecessor this paper improves on with explicit constants. - Dependent random choice — pick a small random test-tuple, take its common neighborhood; the resulting set is large and almost every small subset of it still has a large common neighborhood, giving a workhorse for embedding sparse/bipartite graphs into dense hosts — the Fox–Sudakov technique family (same authors, arXiv:0909.3271) underlying the broader Conlon–Fox–Sudakov hypergraph-Ramsey program (arXiv:0808.3760, arXiv:0901.3912, this paper); the embedding-lemma/blow-up architecture here is a close relative. - Erdős–Hajnal conjecture: forbidding one induced subgraph forces polynomial-size cliques/independent sets — the original graph-level induced-Ramsey conjecture this paper both extends (3-uniform, positively) and shows structurally cannot extend (k≥4-uniform, negatively). - concept/stepping-up-lemma — the Erdős–Hajnal binary-string colouring construction reused here (Lemma 4.1) as the vehicle for the impossibility proof; the same family underlies the best known lower bounds for $r_k(\ell)$ generally, relevant to Erdős #564 — is $R_3(n) \\geq 2^{2^{cn}}$? (3-uniform hypergraph Ramsey) (is $R_3(n)\geq2^{2^{cn}}$?) and the general hypergraph-Ramsey growth-rate conjecture Erdős #562 — Erdős–Hajnal–Rado hypergraph Ramsey growth rate: SOLVED at the ≥4-colour endpoint via the stepping-up lemma (2-colour case still open). - concept/kovari-sos-turan-theorem — the double-counting/pigeonhole bipartite blow-up lemma (Lemmas 3.1–3.2) that Lemma 3.3's iterated peeling argument is built from.