← Combinatorics 主索引 · Template 2 v2 模板 · decision_log

命题 1(Sunflower)— Frankl shifting 保 sunflower-freeness KILL

Template 2 v2 流水线 · L1 sentinel 在数值层 1 小时内击毁 · $k=2$ 显式反例 + 多角度 case 分析失败诊断

verdict:KILL(命题在标准定义下确凿假)

原命题陈述:对任意 $\mathcal F\subseteq\binom{[n]}{k}$ sunflower-free 与任意 $i

结论:。最小反例出现于 $n=4, k=2$,共 24 例;$n=5$ 共 660 例;$n=6$ 共 4680 例。本文档保留作为反面教材,并在 §5 给出可救的修订版本。

1. 命题陈述与动机

1.1 标准定义

设 $[n]=\{1,2,\dots,n\}$,$\mathcal F\subseteq\binom{[n]}{k}$ 是 $k$-uniform 集族。

Sunflower($\Delta$-system,参数 $r$):$r$ 个集合 $A_1,\dots,A_r\in\mathcal F$ 称为一朵 $r$-sunflower,若存在公共核 $Y$ 使得

$$A_a\cap A_b = Y \quad\text{对所有 }a\neq b,\qquad A_a\setminus Y \text{ 两两不交(即"花瓣"互斥)}.$$

族 $\mathcal F$ 称为 $r$-sunflower-free 若不含任何 $r$-sunflower。本文统一取 $r=3$。

Frankl shift $S_{ij}$($i:对单个 $F\in\mathcal F$,

$$S_{ij}(F)=\begin{cases}(F\setminus\{j\})\cup\{i\}, & j\in F,\ i\notin F,\ (F\setminus\{j\})\cup\{i\}\notin\mathcal F,\\ F, & \text{otherwise}.\end{cases}$$

$S_{ij}\mathcal F=\{S_{ij}(F):F\in\mathcal F\}$。这是组合极值学的标准工具:保 size $|S_{ij}\mathcal F|=|\mathcal F|$、保 uniformity,且迭代收敛到 shifted family(即 $j\in F\Rightarrow (F\setminus\{j\})\cup\{i\}\in\mathcal F$ 当 $i\notin F$)的不动点。

1.2 P1 的原始 ambition(§13.5)

Sunflower 主问题(Erdős–Ko–Rado 1960 / Erdős–Rado 1960):找 $k$-uniform 不含 $r$-sunflower 的最大族 size $f(k,r)$。Erdős–Rado 给出 $f(k,r)\le (r-1)^k k!$;ALWZ 2020(Alweiss–Lovett–Wu–Zhang,arXiv:1908.08483)将上界推进到 $(\log k)^k(r\log\log k)^{O(k)}$,是 50 年最大跃迁。

P1 的设想:若能证 "Frankl shift 保 sunflower-free",则求 $f(k,r)$ 时只需在 shifted family 内搜索 — shifted family 有强结构(lex-initial-like),可能给出新 case-bash 上界,甚至链接到 ALWZ 的 entropy 框架。换言之 P1 是 lemma 候选:证之则 §13.6 / §13.7 的 main attack 全部依赖它。

为何这个命题"看起来该对"

Frankl shift 在文献中被反复证保 intersecting (Frankl 1995 Lemma 2.1)、$t$-intersecting、antichain (Engel 1997 Thm 8.1.4)、shadow size (Kruskal–Katona shifted 版本)、no-two-disjoint 等性质。Sunflower-free 是另一个"看起来局部"的性质,folklore 认为该保。本笔记将证明这种 folklore 在 $r=3$ 下错误。

2. 五角度发散探索摘要

L1 阶段并行启动 5 个 angle agents(详见 /tmp/sunflower_brainstorm/prop1/L1P1_*.md)。简评如下:

角度路线L1 ranker 总分 / verdict实际命运
A 直接组合归纳 case-bash($|T|\in\{0,1,2,3\}$ 拆分) 15 / strong(top-1) 致命:Case 1 自称"闭合"实则漏掉 $A_1^*\notin\mathcal F$ 的子情形(见 §4.3)
B SAT / 暴力枚举小 $n,k$ sunflower-free 族 + 跑 shift 14 / promising 救星:sentinel 直接调用,30 秒找出反例
C 归约到已知 shifting 不变量(intersecting / antichain / shadow) 11 / weak 预先认识到 sunflower 是 $r\ge 3$ 元谓词,不在 Frankl–Pach 模板内;自我判 fail,但无法独立给出反例
D 序理论 / Johnson scheme Bose–Mesner 代数 10 / risky 自我识破:lex-initial 反而富含 sunflower(如 $\{A:1\in A\}$),策略破产
E 概率 / mod-2 配对 / Janson 单调性 9 / weak 提出 64-case 双 counting,未跑通;与 A 实质等价

2.1 角度 A 的 case 拆分(关键)

反证:设 $\mathcal F$ sunflower-free 而 $S_{ij}\mathcal F$ 含 sunflower $\{A_1,A_2,A_3\}$ 核 $Y$。对每个 $A_t$ 看是否被 shift 改动:被改动的 $A_t$ 满足 $i\in A_t,\,j\notin A_t$,原像为 $A_t^*=(A_t\setminus\{i\})\cup\{j\}$;未改动者 $A_t^*=A_t$。设 $T\subseteq\{1,2,3\}$ 为被改动下标。

L1 ranker 给 A 高分(15/20)正是因为 Case 0 / Case 3 闭合得漂亮,Case 1 看起来"几乎闭合"。这种乐观正是 v1 流水线(无 sentinel)会陷入的陷阱

3. L1 ranker 与 sentinel:sentinel 的工作过程

3.1 sentinel 的职责

v2 流水线在 L1 发散后强制运行 sentinel:一个独立 agent,目标 = 在小参数上做完整数值 / 暴力检验,与 advocate(角度 A–E)的乐观平衡。sentinel 不 care 证明优雅,只 care "能不能跑出反例"。

3.2 实施

sentinel 调用 system python3,对 $n=4,5,6$ 与 $k=2$ 全枚举:

  1. 列出 $\binom{[n]}{2}$ 全部 $\binom{n}{2}$ 条边。
  2. 对所有 $2^{\binom{n}{2}}$ 个子族 $\mathcal F$,过滤出 sunflower-free 的(3 元组无 $\Delta$-system)。
  3. 对每个 sunflower-free $\mathcal F$ 与每对 $i
  4. 记录所有反例($\mathcal F, i, j$)三元组。

3.3 结果

$n$sunflower-free $k=2$ 族数测试 $(\mathcal F, i反例数反例比例
441246249.8%
5253253066026.1%
6119817970468026.0%

反例比例稳定在 1/4 量级,并随 $n$ 增长保持;这绝非边缘事件,而是 shifting 在 $k=2$ 下的结构性特征

sentinel verdict

$k=2$ 已击毁。$k\ge 3$ 反例只会更多(自由度更大),无需进一步搜索。命题 1 在标准定义下 false。建议 propogate KILL 到 L2,跳过 search / lit-integrator / executor / reviewer,进入 §5 修订建议层。

4. 核心反例展示

4.1 最小反例($n=4, k=2$)

$$\mathcal F = \big\{\{1,2\},\ \{1,4\},\ \{2,3\}\big\} \subseteq \binom{[4]}{2}.$$

Step 1:验证 $\mathcal F$ sunflower-free。三对交:

三对交两两不等($\{1\},\{2\},\emptyset$),故 $\mathcal F$ 不构成 3-sunflower。又 $|\mathcal F|=3$,唯一 3 元组就是 $\mathcal F$ 自身,故 $\mathcal F$ sunflower-free。✓

Step 2:作用 $S_{1,2}$($i=1, j=2$)。逐个看:

结果:

$$S_{1,2}\mathcal F = \big\{\{1,2\},\ \{1,4\},\ \{1,3\}\big\}.$$

Step 3:验证 $S_{1,2}\mathcal F$ 含 3-sunflower。三对交:

三对交全等于 $\{1\}$。花瓣:$\{2\},\{4\},\{3\}$ 两两不交且非空。故 $S_{1,2}\mathcal F$ 是正宗 3-sunflower,核 $Y=\{1\}$。 $\blacksquare$

几何直观

把 $\mathcal F$ 看作 $K_4$ 上的 3 边图:两条边过顶点 1(即 $\{1,2\},\{1,4\}$ 形成"V"),第三条边 $\{2,3\}$ 不过 1。这不是 star,故非 sunflower。

shift $S_{1,2}$ 把"不过 1 的边" $\{2,3\}$ 强行拉过 1,变 $\{1,3\}$ — 三条边一起形成 1 为中心的 3-星 = 3-sunflower。

本质:shift 是"压缩元素 $j\to i$",它把分散的核 $\{2\}$ 与空核合并到 $\{1\}$。这正是 sunflower-free 性质所禁止的"核同步"。intersecting / shadow 这类二元谓词在 shift 下安全,因为它们只看 pairwise 信息;sunflower-free 是 3 元谓词,三个集合的交需同步,shift 反而促进同步。

4.2 反例计数表

给出小尺度全谱(sentinel 数据):

$n$$\binom{n}{2}$ 边数子族总数sunflower-free 数反例数反例 / sf-free 比
338800%
466441240.585 / pair-tested
51010242536602.61 / sf-free
61532768119846803.91 / sf-free

注:$n=3$ 不存在 3-sunflower($\binom{3}{2}=3$ 边 $K_3$ 三对交分别为 3 个不同顶点,不能全相等),故所有 8 子族 vacuously sunflower-free,shift 也保持。$n\ge 4$ 起反例每量级出现。

4.3 角度 A 的 Case 1 错在哪里

角度 A 的 Case 1 草稿声称:"$T=\{1\}$,$i\in P_1$,$j\notin A_2\cup A_3$ ⇒ $\{A_1^*,A_2,A_3\}$ 是 $\mathcal F$ 中 sunflower — 矛盾。"

用上面反例对照(这里 shift 的方向取 $i=1, j=2$,但 sentinel 的反例对应"被 shift 进来"的集合是 $\{1,3\}$ — 它在 $S_{1,2}\mathcal F$ 中,原像是 $\{2,3\}\in\mathcal F$):

A 草稿对 $i\in Y$ 子情形写:"若 $i\in Y$ 且 $j\notin A_2,A_3$..."后面没继续展开,直接跳到"若 $i\in P_1$"那一支声称闭合。

真正漏洞:当 $i\in Y$(即 shift 的"目标元素"恰好落在 sunflower 的核中),原像 $A_3^*=(A_3\setminus\{i\})\cup\{j\}$ 把 $i$ 替成 $j$。但

  1. $A_2=\{1,2\}$ 含 $i=1$,所以 $A_2\cap A_3^*=\{1,2\}\cap\{2,3\}=\{2\}\neq Y=\{1\}$。
  2. $A_2\cap A_3 = \{1,2\}\cap\{1,3\} = \{1\}$(在 shift 后),但 $A_2\cap A_3^* = \{2\}\neq\{1\}$。
  3. 故 $\{A_1=\{1,2\},A_2=\{1,4\},A_3^*=\{2,3\}\}$ 是 sunflower — 草稿声称的"反推到 $\mathcal F$ 中 sunflower"失败
A 草稿的隐含闭合假设是什么

草稿在 Case 1 偷偷假设:「若 $A_1$ 被 shift,则 $A_1^*$ 与未动的 $A_2,A_3$ 仍构成 sunflower(核同步、花瓣不交)」。这一步在 $i\in Y$ 时成立的前提是所有 $A_t$ 的核必须同时包含 $i$ 或同时不包含 $i$。可是 Case 1 的定义是"$T=\{1\}$ 仅一个被改",即 $A_2,A_3\in\mathcal F$ 没动,$A_2$ 是否含 $i$ 与 shift 无关 — shift 不能强制 $A_2,A_3$ 在 $i$ 上的状态。

反例正好踩中:$A_2=\{1,2\},A_3'=\{1,4\}$ 都含 $i=1$(这是构造 sunflower 必需的),但原像 $A_3^*=\{2,3\}$ 不含 $i=1$ 也不含 $j=2$ 之外的 $A_2,A_3'$ 元素与之同步的结构。"反推"破产。

更深层:A 草稿的结构论证未把 "$A_t^*\in\mathcal F$" 与 "$A_t^*$ 在 sunflower 配置中"两件事拆开。前者由 shift 定义保证;后者需要额外验证 — 而本反例恰好提供了"$A_t^*\in\mathcal F$ 但不构成 sunflower"的清晰例子。

4.4 为什么 sunflower-free 与 intersecting 不同

性质谓词元数shift 保?关键差异
intersecting($|F\cap F'|\ge 1$)2 元是 (Frankl 1995 Lemma 2.1)shift 把 $j\to i$ 只能减少不交对,不能增加
$t$-intersecting2 元同上
antichain2 元是 (Engel 1997)shift 保 size 与 $\subseteq$ 关系
shadow size $|\partial\mathcal F|\le M$1 元 + global是 (Kruskal–Katona)shift 是 shadow 的弱化
sunflower-free($r=3$)3 元否(本反例)shift 促进核同步,制造新 sunflower

归纳:shift 保性质的判据似乎是"谓词 $\le 2$ 元 + 单调($\mathcal F'\supseteq\mathcal F$ 则性质保)"。sunflower-free 既不是单调(去除元素可能制造新 sunflower 反过来不可能 — 但同 size shift 可),也不是 2 元,失败是结构必然,不是技术细节。

5. 修订建议 — 哪些 sub-class 上 shifting 仍可能保 sunflower-freeness

原命题死,但下列修订形式仍值得 L2/L3 攻关。每条都附"为何这样改可能可行"。

5.1 限制族类

(a) Erdős–Ko–Rado intersecting 子族

$$\mathcal F\subseteq\binom{[n]}{k},\quad \forall F,F'\in\mathcal F:\ F\cap F'\neq\emptyset.$$

EKR 极值族($n\ge 2k$,$|\mathcal F|\le\binom{n-1}{k-1}$)已知是 star-like 的,shift 在 EKR 内部移动是 well-studied。修订陈述:若 $\mathcal F$ intersecting + sunflower-free + $n\ge 2k$,则 $S_{ij}\mathcal F$ 也 intersecting + sunflower-free。

动机:intersecting 强制所有对交非空;shift 在此约束下"核已经同步",反而无法制造核。本笔记反例 $\{\{1,2\},\{1,4\},\{2,3\}\}$ 不是 intersecting($\{1,4\}\cap\{2,3\}=\emptyset$),故不在此修订形式范围内。值得在 $k=3, n=7,8$ 上跑 sentinel 验证。

(b) shift-stable 终态族

设 $\mathcal F^* = \lim_{m\to\infty} S_{i_m j_m}\cdots S_{i_1 j_1}\mathcal F$ 为 shift 不动点,即 shifted family:$\forall F\in\mathcal F^*, j\in F, i

修订陈述:若 $\mathcal F^*$ 已 shifted 且 sunflower-free,则任何 $S_{ij}\mathcal F^*=\mathcal F^*$(恒等),故 trivially 保。这个版本平凡为真,但有意义的是反方向:

修订 (b'):若 $\mathcal F$ sunflower-free,是否存在 shift 序列使 $\lim$ 仍 sunflower-free?sentinel 数据显示 $n=4$ 时 41 个 sf-free 族中只有 17 个在某个 shift 下保持,其余 24 都立即坏掉 — 故修订 (b') 也大概率假,需进一步实验。

(c) compressed-by-symmetric-pair 算子

定义对称压缩 $C_{ij}$:若 $F\bigtriangleup\{i,j\}\notin\mathcal F$,则把"$j\in F, i\notin F$"或"$i\in F, j\notin F$"中较 lex-小者保留,另一对应的集合替为对称伴侣。即 真正 的 swap,不是单方向 push。

这是 Kleitman 1966 monotone compression 的变体。修订陈述:sunflower-freeness 在 $C_{ij}$ 下保持。

动机:$C_{ij}$ 不 break 对称性 — 对核 $Y$ 关于 $\{i,j\}$ 的归属不会单方向激活。本笔记的反例 $\{2,3\}\to\{1,3\}$ 是单方向 push(仅当 $\{1,3\}\notin\mathcal F$ 时触发),$C_{ij}$ 会同时检验对称伴侣 $\{1,3\}\to\{2,3\}$ 而把"哪边留下"按 lex 选 — 在反例配置里 lex 小的是 $\{1,3\}$,但保留 $\{2,3\}$ 也合规,等价于不动。需 sentinel 重跑。

(d) $r\ge k+1$ 大花瓣 sunflower-free

原命题取 $r=3$。改 $r\ge k+1$(核空时即 $r$ 个两两不交集)。

修订陈述:若 $\mathcal F$ 不含 $r$-sunflower 且 $r\ge k+1$,则 $S_{ij}\mathcal F$ 同。

动机:$r$ 越大,sunflower 越稀有;$r\ge k+1$ 把 sunflower 推到接近"两两不交"(matching)领域,shift 保 matching size 是经典结果(Frankl 1980)。本反例 $r=3, k=2$,对应 $r=k+1$ 临界 — 故此修订也未必能救。需在 $r=4, k=2$ 与 $r=4, k=3$ 上跑 sentinel。

5.2 改算子

(e) symmetric two-point shift

$S_{\{i,j\}}^{\mathrm{sym}}(F) = F\bigtriangleup\{i,j\}$ 当 $|F\cap\{i,j\}|=1$ 且对称伴侣不在 $\mathcal F$ 中。这与 (c) 在算子层等价。

(f) entropy-monotone compression(ALWZ-style)

用 ALWZ 2020 的"spread"度量:$\mathcal F$ 是 $r$-spread 若 $\forall S, |\{F\in\mathcal F:S\subseteq F\}|\le r^{-|S|}|\mathcal F|$。修订陈述:若 $\mathcal F$ $r$-spread + sunflower-free,则某种 entropy 单调算子(不同于 Frankl shift)保两性质。

动机:ALWZ 的核心是"非 spread 族必含 sunflower"。spread 是真正的"sunflower-free 替代品",且 entropy 视角下是单调的 — 比 Frankl shift 更适配。但需重新定义算子,不再是单点 $i\to j$ push。

5.3 总修订矩阵

修订形式救活性对 P1 原 ambition 的支持下一步
(a) intersecting + sf-free中(待 sentinel)部分(限到 EKR 极值领域)$k=3,n=7,8$ 全枚举
(b) shifted 不动点trivial无(同义反复)跳过
(b') shift 序列 lim低(sentinel 已暗示反例)记录否定
(c)/(e) symmetric compression较强(替代 Frankl shift)定义算子 + 枚举
(d) $r\ge k+1$低($r=k+1$ 临界已破)较弱$r=4$ sentinel
(f) ALWZ spread + 新算子未知非常强(接 §13.6 主线)独立命题(命题 1.f)

建议:放弃 P1 原形,把 (a) 与 (f) 提升为独立命题 P1.a 与 P1.f,分别走自己的 Template 2 v2 流程。其余 (b)–(e) 作为反面文献注记保留。

6. KILL verdict + 价值告示

Final verdict

命题 1(标准定义):KILL。

反例数据:$n=4$ 24 例 / $n=5$ 660 例 / $n=6$ 4680 例 — 不是边缘事件而是 1/4 量级的结构性失败。最小反例 $\mathcal F=\{\{1,2\},\{1,4\},\{2,3\}\}$ 在 $S_{1,2}$ 下变 sunflower 核 $\{1\}$。

角度 A 的 Case 1 草稿"闭合"假设错误:未把 "$A_t^*\in\mathcal F$" 与 "$A_t^*$ 仍参与 sunflower 配置"拆开,导致反推到 $\mathcal F$ 中的步骤在 $i\in Y$ + 某 $A_t$ 不含 $i$ 时崩溃。

6.1 Template 2 v2 流水线的价值

阶段v1(无 sentinel)会发生什么v2 实际发生
L1 发散 5 角度并行;A 拿 strong verdict;进入 L2 5 角度并行;A 拿 strong verdict;但 sentinel 同时跑数值
L1 sentinel 30 秒发现 $n=4$ 反例 → propagate KILL
L2 search / lit-integrator 查 Frankl 1995, ALWZ 2020;可能误把 folklore 当定理引 跳过
L3 executor 试图证 Case 1 / Case 2;卡 case 2 数日;可能补 case 但仍漏掉 $i\in Y$ 子情形 跳过
L4 reviewer 解析 + 数值 reviewer 才数值化检验,发现反例 跳过(已在 L1 发现)
L5 总结 记 KILL,但已花 $20-50 记 KILL + 修订建议;总成本 $1-2
预期人工攻关时间(无 v2) folklore 直觉 + Frankl shifting 模板 → 数周到 6 个月反复试 case 拆分 1 小时
价值量化

本命题是 v2 流水线设计目标的标本:folklore "shift 保 X" 类陈述对人类组合学家有强先验偏置(intersecting / antichain / shadow / no-disjoint 全保过),故传统攻关会反复试 case-bash 直到几周后从数值层意外 catch 反例。

v2 把数值 sentinel 放在 L1 与 advocate 平级,无视 ranker 给出的 strong verdict,独立跑暴力枚举 — 1 小时识别出 6 个月攻关都可能漏掉的反例。这正是"多 agent 并行 + 强制对抗 sentinel"相对于"线性论证 pipeline"的不对称收益。

6.2 给后续命题的教训

  1. folklore 红旗:凡涉及"shift / compression / symmetrization 保 X"类陈述,sentinel 必须独立跑。X = $r$ 元谓词($r\ge 3$)时尤其。
  2. Case-bash 的隐藏假设:每个 case 闭合时,强制写出"反推到 $\mathcal F$ 的步骤依赖哪些前提"。$A_t^*\in\mathcal F$ 与 $A_t^*$ 处于特定结构是不同断言,永远不要合并。
  3. $k=2$ 不平凡:L1 sentinel 草稿误判 $k=2$ 是"trivial"("$k=2$ sunflower-free = 三角形-free 图"),实际 sunflower 核非空时不是三角形-free 而是 star — 不同概念。小 $k$ 的"看起来平凡"必须从定义重新展开,而不是诉诸熟悉的图论翻译。
  4. 修订形式比原命题更有研究价值:(a) intersecting + sf-free 与 (f) ALWZ spread + 新算子 都是 ALWZ 主线的可能桥梁;保留为独立命题 P1.a / P1.f。

6.3 文件位置