问题
Erdős–Hajnal 1977：对每个 ε > 0 存在 δ = δ(ε) > 0，使任何 n 顶点图若 ω(G), α(G) ≤ n1−ε，则 G 含一切 «至多 nδ 顶点» 图的诱导拷贝。等价形式（更常用）：固定禁止诱导图 H，则无诱导 H 的 n 顶点图有大 «同质集»（团或独立集）——大小 nδ(H)，δ > 0。这是 «随机图是最优的» 哲学在诱导世界的体现：随机图的 ω, α ~ 2 log n = no(1)，而一般图只保证 log n（拉姆齐），猜想断言 «禁止一个诱导模式就换取多项式增益»。
主要概念
χ-有界与诱导拉姆齐
猜想的两个 «近亲»：χ-有界（问题 12 的森林版）与 «诱导拉姆齐数»。EH 猜想蕴含 «无诱导 H ⟹ χ ≤ n/(nδ) = n1−δ»——即 EH 的 δ 与 «χ-有界的多项式指数» 直接换算。
ε-均匀性与嵌入引理
当代骨架的两件套：①均匀性——若图 «处处 ε-均匀»（每对大子集间的边密度偏离不超过 ε），则可嵌入任意固定 H 为诱导拷贝（Szlankó–Fox–Sudakov 型引理）；②«非均匀 ⟹ 大同质»——Szemerédi 正则性或其诱导版把 «非均匀» 转化为大团/大盘。EH 猜想 ⇔ «ε-均匀 ⟹ 嵌入一切 nδ 顶点图» 的统一刻画。
主要命题与证明
命题 1（嵌入引理，完整骨架） 若 G 是 «(1/2, ε)-均匀» 的（每对 ≥ n/2 的顶点子集间密度与全局 1/2 偏差 ≤ ε），则 G 含一切 k ≤ nδ 顶点图的诱导拷贝（δ 依赖 ε）。
骨架 贪婪嵌入：逐顶点安放 H。第 t 步时已安放 t 个 «锚»，剩余候选集需同时满足 «与各锚同邻/异邻» 的约束——候选集是 t 层 «布尔组合»（对每锚 «邻集∩补邻集»），每层损失因子 (1/2 ± ε)，t 层后候选集 ≥ n(1/2−ε)t ≥ 1 当 t ≤ log n/log 2 ——不够（需 nδ）。精化：把 «逐点贪婪» 换成 «分批嵌入»（Fox–Sudakov 的 «有序嵌入»），损失因子改进到 εt/…——ε-均匀的 «对称双密度» 结构使布尔树剪枝有效，最终容量 n1−c(ε)k… 型——骨架给出 δ = δ(ε) 的存在。□
命题 2（已证图类清单，完整陈述） ①无诱导 C₅（Bousquet–Lagoutte–Thomassé 2012）；②«半完美» 家族（无诱导洞的图——完美性定理）；③有序图的 «EH 带序版»（Fox–Pach 等）；④无诱导 P₅ 及小树族（Scott–Seymour–Spirkl 系列）；⑤«所有 H 的 EH 对 «无诱导 H 的图具有 nδ 同质»» 对 δ = c·log(|H|)/log(|H|+1) 型弱常数由 Erdős–Hajnal 原文给出（平凡版）。
展开（平凡版证明，完整） 递归：若 G 有顶点 v 使 N(v) 与 N̄(v) 均 ≥ |G|/2^{|H|}……标准 «分裂递归»:构造 «二叉决策树»，每层按 «某诱导 H 的一个前缀» 分裂，深度 ≤ |H| 的路径给出 «同质集 ≥ n1/|H|»——即 δ ≥ 1/|H| 的平凡 EH。猜想断言 δ 可 «只依赖 ε（= 团指数缺口）»——两版间差整个 «诱导结构»。□
进展与文献
Erdős–Hajnal 1977；Fox–Sudakov《Induced Ramsey-type theorems》；Bousquet–Lagoutte–Thomassé 的 C₅ 定理；Scott–Seymour–Spirkl 的 «无诱导森林 χ-有界» 系列（与问题 12 联动）。开放核心：一般 H 的 δ > 0（连 H = C₆ 都未知）；«对数型反例» 的构造障碍（Fox–Sudakov 的 «条件反例» 只在 «弱 EH» 下成立）；EH 猜想与 χ-有界猜想的 «多项式等价» 地图。