组合数学 — 待证明猜想列表

$R(5,5)$

$n$ 顶点完全图任意 2-染色含单色 $K_5$ 的最小 $n$。Erdős："找 $R(5,5)$ 比与外星人作战还难"。2024 Angeltveit/McKay 上界至 46。

$R(n,n)$ 上界

Erdős–Szekeres 给 $4^n$；70 年后 CGMS 2023 证 $R(n,n) \le (4 - \varepsilon)^n$；下界 $\sqrt{2}^n$ (Erdős 1947)。精确指数仍开放。

Hadwiger 猜想

无 $K_t$-minor 图 $(t-1)$-可染色。Robertson–Seymour–Thomas 证 $t = 6$；Norin–Postle–Song 2023 改进上界至 $\chi \le O(t \log \log t)$。

Total Coloring

同时染顶点 $+$ 边使相邻 / 关联元素不同色，至多需 $\Delta + 2$ 色。Behzad、Vizing 提出；$\Delta \le 5$ 等部分情形已证。

List Edge Coloring

$\chi'_\ell(G) = \chi'(G)$。Galvin 2 部图情形；一般情形多种弱化。Molloy 2017 证 $\chi_\ell \le (1 + o(1)) \Delta / \log \Delta$ for triangle-free。

Cycle Double Cover

每无桥图存在一族圈使每边恰被 2 圈覆盖。等价于多种"嵌入到曲面"命题。

Tutte 5-Flow

每无桥图有 nowhere-zero $\mathbb{Z}_5$-流。Tutte 4-flow（4 色定理强化）开放且更深。

Tutte 4-flow

不含 Petersen-minor 的无桥图有 nowhere-zero 4-flow。Robertson–Seymour–Thomas 项目部分证明（数百页未完整发表）。

Reconstruction 猜想

n ≥ 3 顶点图由其顶点删除 deck（n 个 G−v 同构类）确定。树（Kelly 1957）、disconnected、regular 等情形已证。

Edge Reconstruction

边数较多时由边删除 deck 重构图。已证许多稠密图情形；稀疏一般开放。

Caccetta–Häggkvist

n 顶点最小出度 r 的有向图，含长度 ≤ ⌈n/r⌉ 的有向圈。r = n/3 情形（最短圈 ≤ 3）是关键开放情形。

Hadamard 矩阵

每 n=4k 存在 ±1 行正交方阵。n < 668 全部构造成功。

Erdős–Faber–Lovász

$n$ 个两两至多共享一顶点的 $K_n$ 之并图色数 $\le n$。已对充分大 $n$ 证（仍 unpublished refereeing 中，多数视为已证）。

Polynomial Freiman–Ruzsa

$|A + A| \le K|A|$ 的集合可被 $\mathrm{poly}(K)$ 倍的"广义算术级数"覆盖。$\mathbb{F}_2^n$ 由 Gowers–Green–Manners–Tao 2023 用 entropy 证；$\mathbb{Z}$ 情形开放。

Union-Closed Sets

有限非空 union-closed 集合族存在元素 $\in$ 至少一半集合。Gilmer 2022 突破：证 $\ge 1\%$ 的元素属于 $\ge 0.382\ldots$ 比例集合；目标常数 $1/2$ 开放。

Sunflower Lemma

$k$-集族 $|F| > f(k, r)$ 含 $r$-sunflower。Erdős 猜想 $f(k, r) = O(C^k)$。Alweiss–Lovett–Wu–Zhang 2019 + Rao 改进证 $(\log k)^k$；指数 $1$ 开放。

📖 Our explore paper： 查看完整研究项目 — 16 节主笔记 + 5 命题深入研究（~120 agent，3 小时）+ 多 agent 模板套件应用。 关键发现：v2 流水线在 sentinel 阶段（第 7 agent）找到 Frankl shifting 保 sunflower-freeness 的显式反例（$k=2$ 即 24 反例），KILL 一个看似 lemma 级的 ambition；P3 数值半（Lasserre level-3 SDP for $f(k,3), k \le 6$）因 sunflower-SDP 文献为零反转为 split-PASS 立项命题；P5 修订为 encoding-specific SA-degree barrier 是 STOC/FOCS 量级 position paper。

EKR 推广

原始 EKR 经典；至 permutations、matroids、partition 等推广仍部分开放（如 Frankl–Deza 猜想）。

Singmaster

整数 a ≥ 2 在 Pascal 三角形出现次数 N(a) 是否一致有界？Singmaster 猜想 O(1) 或 O(log)。已知 N(3003) = 8 为最大。

Chvátal Toughness

充分大 toughness 蕴含 Hamilton 圈。Bauer–Broersma–Veldman 反例否决 t=2；t > 9/4 是否 ⇒ Hamilton 开放。

Bermond–Bollobás (n,Δ,D)

最大顶点数 n(Δ,D) 的精确公式或渐近。Moore 界 n ≤ 1+Δ+Δ(Δ-1)+… 一般不可达。

Distinct Distances

$n$ 点 $\mathbb{R}^d$ 最少 $\Omega(n^{2/d})$ 不同距离？$\mathbb{R}^2$ 由 Guth–Katz 证 $\Omega(n / \log n)$。高维仍间隔。

Manifold Khintchine

支持在子流形上的 Khintchine-type 0-1 律。Beresnevich–Velani 多次推进；部分仍开放。

Lovász 路径猜想

每连通顶点-传递图含 Hamilton 路。已对所有 ≤ 数百万顶点验证；理论证明开放。

Bollobás–Riordan

偏好附着模型的精细度数序列估计；高阶矩与极端值仍开放。

Erdős–Hajnal

每固定图 $H$ 存在 $c(H) > 0$：禁 $H$ 作 induced subgraph 的 $n$ 顶点图含 $n^{c(H)}$ 团或独立集。许多 $H$ 部分情形已证；2023 Bucić 等取得最大突破（$P_5$ 已证）。

Heesch 数有界

是否存在所有 k 的 Heesch 数 = k 的多边形？2020 Mann 等持续构造高 Heesch 实例。

Aharoni–Berger

Matroid 与图的横向 (rainbow) 相容性广义 Hall 定理。许多特殊 matroid 已证；一般开放。

Brualdi 矩阵猜想

关于 doubly stochastic 与 Latin square 的猜想；van der Waerden 猜想（Egorychev–Falikman 1981 已证）的精细化版本仍开放。

3-AP 极值 (Roth)

$\{1, \ldots, N\}$ 中无 3-AP 集合的最大密度。Kelley–Meka 2023 证 $\le 2^{-c (\log N)^{1/9}}$，几乎与 Behrend 下界匹配。4-AP、$k$-AP 仍存间隔。

Erdős–Turán $k$-AP

若 $\sum 1/a_i$ 发散则 $\{a_i\}$ 含任意长等差数列。Szemerédi 1975 证密度版本；Erdős 强版本对一般序列仍开放。素数情形 ($\sum 1/p$ 发散) 由 Green–Tao 解决。