五角形が強化予想を反証する —— 和集合閉集合予想・攻略ノート（3）

本稿の位置づけ

第3稿。第2稿は、Frankl 予想より強い予想F2'（包含単射版：ある $x$ と単射 $\phi :{\mathcal{F}}_{\neg x}\to {\mathcal{F}}_x$、$A\subseteq \phi (A)$、が常に存在する）が $n=3$ の全120族と $n=4$ の全4958族で無敗であることを確認し、「強化予想は反例で反証されるのが常」という歴史の教訓に従って、次の一手を反例の探索と定めた。

本稿はその探索の記録である。結果として、反例は出た。強化予想F2'は偽であり、しかも反例の正体は、数学でもっとも親しまれた図形の一つである五角形だった。ただし倒れたのは第2稿で立てた強化版だけである。見つかった反例族でも Frankl 予想そのものは成立しており、45年ものの本体は未解決のまま残る。反証された予想から学べることは多い。解剖と一般則、そして方針の再設定までを行う。

前提知識：探索の準備

0.1 何を探すか

予想F2'の反例とは：和集合閉族 $\mathcal{F}$ であって、どの元 $x$ を選んでも、${\mathcal{F}}_{\neg x}$（$x$ を含まない集合たち）から ${\mathcal{F}}_x$（含む集合たち）への包含単射（$A\subseteq \phi (A)$）が存在しないもの。Hall の結婚定理により、これは「どの $x$ にも、$|S|>|N(S)|$ となる部分族 $S\subseteq {\mathcal{F}}_{\neg x}$（Hall 違反＝ボトルネック）が存在する」ことと同値である。ただし Frankl 予想本体は成立していなければならない（破れていたらそれは世紀の大発見か、まず間違いなくバグである。検証を最優先する）。

0.2 探索の三方面

第2稿で予告したランダム探索を軸に、三方面から探した。(a) ランダム：$n=\mathrm{5..8}$ でランダム生成集合の和集合閉包、計約6.8万有効試行。(b) 持ち上げ：$n=4$ で正準写像が折れた「困難な28族」に新しい元をランダムに追加して $n=5,6$ へ拡張。新元を含む生成集合を1〜3個ランダムに作り、元の族と合わせて和集合閉包を取る、という作り方で、28族 × 1族あたり600試行 × 2水準（$n=5,6$）＝33,600試行。(c) 構造化：Fano 平面の直線族・その補族、後述のグラフ辺族たち。

要旨

探索の結果。ランダム探索が3件の反例を出した（$n=5$ で2件、$n=7$ で1件；$n=6,8$ は該当なし）。持ち上げ探索も $n=6$ で2件を出した（$n=5$ では0件、Fano は該当なし）。第2稿の全数検証（$n=3$ の120族・$n=4$ の4958族）では反例が出なかったから、台集合5元が反例の最小サイズである（この点は全数による確定）。

解剖。$n=5$ の反例第1号（16集合）を精査した。(i) 和集合閉性 ✓、(ii) Frankl 本体は余裕で成立（全5元の頻度がすべて $10/16=5/8$ の完全対称な正則族）、(iii) しかし全5元で Hall 違反が起きる。パターンは一様で、どの $x$ でも「ある2元集合 $P$ のフィルター（$P$ とその上の3集合、計4集合）に対し、持ち上げ先が3つしかない」（$|S|=4>|N(S)|=3$）。原因は毎回同じで、$P\cup \{x\}$ が族に無い（持ち上げ先が一つ欠けている）のに、$P$ の上の3集合の持ち上げ先はちょうど尽きている。持ち上げ先3つに対し持ち上げるべき元が4つあり、鳩の巣原理から少なくとも一つは重複する。除去による極小化も試みたが、一つも削れない（16集合すべてが必要）。

同定。頻度の完全対称性が正体を告げていた。反例第1号は、五角形 $C_5$（サイクル $1\text{-}2\text{-}5\text{-}3\text{-}4\text{-}1$）の辺集合5本の和集合閉包と厳密に一致する（機械照合）。ここで辺は両端の2頂点からなる集合であり、族の台集合は5つの頂点、族の元は5本の辺から和集合で作れる集合すべてである。内訳は、5本の辺、5本の2辺パス、5枚の4点集合、全体集合の計16。

一般則（機械で確立）。ではサイクルが悪いのか。$C_3$ から $C_9$ まで、および対照群を検査した：

長さ5以上のサイクルはすべて F2' を反証する。機構も透明である。頂点 $x$ から距離2以上の辺 $P$ を取ると、$P\cup \{x\}$ は辺の和（パス）にならないので族に属さず、持ち上げ先が一つ欠ける。一方で $P$ のフィルターの持ち上げ先は、一つ上の層でちょうど尽きてしまう。$C_3,C_4$ が無害なのは、すべての辺が $x$ の隣まで届いている（遠い辺が存在しない）からである。

皮肉と教訓。これらの反例族は、辺（2元集合）を含む。つまり第2稿の定理F2(b)（二元補題）により Frankl 本体は二行で証明できる、最も易しいクラスの住人である。強化予想は、本体が自明な場所で崩れた。数えること（counting：$|{\mathcal{F}}_x|\ge |{\mathcal{F}}_{\neg x}|$、これが Frankl）と、構造を保って組み合わせること（matching：包含単射）は、本質的に別の問題である。五角形では counting に4集合分の余裕があるのに、matching は成り立たない。Frankl 予想は counting の問題であり、単射・マッチングの検討はここで打ち切る（文献上の既知性の確認は残課題としてフラグ）。

第一部　探索の記録

1. 統計

持ち上げの行は $28\times 600\times 2$ の内訳である（1族あたり600試行を $n=5$ と $n=6$ の両方で走らせた）。ヒット率はランダム $n=5$ で約 $7\times 10^{-5}$、持ち上げ $n=6$ で約 $1.2\times 10^{-4}$。反例は稀少だが実在する。

持ち上げの2件について言うべきことがある。この2件は、どちらも2元集合（辺）から生成される族で、長さ5のサイクルを含む——第三部で同定する反例第1号とまったく同じ種である（1件は辺の閉包そのもの、もう1件は辺の閉包に $\varnothing$ を足したもの）。つまり困難28族の延長線上にサイクルは現れる。ただし現れたのは新元を2つ足した $n=6$ の水準だけで、$n=5$ は16,800試行すべて空振りだった。$n=4$ の困難族は、それ自体としては反例の芽ではない。台集合を2つ広げたときに初めて、ランダムな追加がサイクルを踏む。

2. 検証の優先順位

反例候補が出た瞬間に最初に行ったのは、Frankl 本体の検証である（0.1 の警告）。3件とも本体は成立した（それどころか頻度 $5/8$ で余裕がある）。持ち上げの2件も同様で、最大頻度は $24/37$ と $24/36$、いずれも半分を上回る。破れていたのは強化だけである。バグ検査（和集合閉性の全対照合・マッチング算法の既知ケース照合）も通過した。

第二部　解剖：持ち上げ先の不足

3. 反例第1号の全貌

（数字列は集合の略記）。16集合、全元の頻度 $10/16$。$x=1$ での Hall 違反：

$|S|=4>3=|N(S)|$。原因は $135\notin \mathcal{F}$（$\{3,5\}$ の持ち上げの欠落）である。$S$ は $\{3,5\}$ のフィルター（それを含む ${\mathcal{F}}_{\neg 1}$ の全集合）であり、その持ち上げ先はちょうど3つ。持ち上げるべき元4つに対し行き先が3つなので、鳩の巣原理から重複が生じる。同じパターンが全5元で起きる（違反集合の表は機械出力の通り、すべて $|S|=4>|N(S)|=3$）。

4. 極小性

16集合から任意の1集合を除くと、和集合閉性が壊れるか、F2' が復活する。つまり除去極小である（貪欲除去の全試行で確認）。この族は無駄なく設計された最小限の反例である。

第三部　同定と一般則：サイクルの遠い辺

5. 五角形との一致

頻度の完全対称（全元 $10/16$）は頂点推移的な構造を示唆する。照合の結果、反例第1号 $=$ サイクル $1\text{-}2\text{-}5\text{-}3\text{-}4\text{-}1$ の辺5本の和集合閉包である（機械で集合として厳密一致）。内訳：辺5、2辺パス（3元集合）5、4元集合5（互いに素な辺対の和＝各頂点の補集合）、全体1の計16。

6. 一般則と機構

$C_3$〜$C_9$・完全グラフ・パス・スター・Petersen の検査結果は要旨の表の通り。長さ $\ge 5$ のサイクルはすべて反例になり、内周5の Petersen も同様である。機構を一段丁寧に言う：

• 頂点 $x$ を消すと、${\mathcal{F}}_{\neg x}$ は残りのパス（$C_k$ から $x$ を除いた $k-1$ 頂点のパス）の辺族の閉包になる。
• パスの中央の辺 $P$（$x$ から距離 $\ge 2$）に対し、$P\cup \{x\}$ は $x$ を通るパスではない（$x$ と $P$ が隣接しない）ので、$\mathcal{F}$ に属さない。持ち上げ先が一つ欠ける。
• 一方 $P$ のフィルター（$P$ を含む ${\mathcal{F}}_{\neg x}$ の集合たち）の持ち上げ先は一つ上の層でちょうど尽きる。Hall 違反が確定する。
• $C_3,C_4$ では全ての辺が $x$ の隣接圏内にあり、遠い辺が存在しないため無害。

7. 定理F3（余原子は行儀がよい）

探索の過程で確立した小さな構造定理を記録する：

定理F3　和集合閉族の任意の二つの余原子（最大元 $T$ の直下の極大元）の和は $T$ である。したがって各元 $x\in T$ を欠く余原子は高々一つ。

証明　余原子 $A\ne B$ の和 $A\cup B\in \mathcal{F}$ は $A$ を真に含むから、極大性より $T$。もし $x$ を欠く余原子が二つあれば、その和 $T$ も $x$ を欠くが $x\in T$ に矛盾。$■$（全4958族＋Fano閉包で機械照合：欠け数の分布 $\{0:5688,1:13671\}$、2以上は皆無 ✓）

この定理が禁じているのは、$x$ を欠く余原子が二つ以上あることだけである。裏返せば ${\mathcal{F}}_{\neg x}$ に入る余原子は高々一つで、余原子2つ以上からなるボトルネック $S$ は構造的にありえない。言えるのはここまでである。最上層に別の形のボトルネック（たとえば余原子1つと下層の集合を混ぜた $S$）が存在しないことは、この定理からは出ない。五角形の違反が最上層の一つ下（フィルターの下端）で起きているのは、少なくともこの禁止則と矛盾しない。

第四部　教訓と方針の再設定

8. counting と matching の分水嶺

本稿最大の教訓を式の形で書いておく。五角形では：

Frankl 予想が要求するのは counting だけである。第2稿でマッチングに向かったのは「counting を示す手段として」だったが、五角形は手段が目的より真に強いことを教えた。倒れたのは手段の側であって、目的である Frankl 予想は無傷のまま未解決で残る。しかも舞台は、本体が二元補題で自明に落ちる最易クラスだった。強化・単射・構造保存の道はここで正式に打ち切り（文献上、包含単射版の既知の反例があるかの確認は残課題）、数える方法そのものに議論を戻す。

9. 結果の記録と次稿への計画

F-3.（第3稿）予想F2'は偽。反例＝長さ5以上のサイクルの辺族の閉包（最小例：$C_5$、$n=5$・16集合・除去極小・全数により台集合サイズ最小）、Petersen も反例。機構＝「遠い辺の持ち上げ欠落＋フィルター飽和」（鳩の巣原理による重複）。定理F3（余原子の対の和は $T$、各元の欠けは高々1、証明二行＋全数照合）。教訓＝counting と matching の分離；反例は Frankl 自明クラスに棲む。

次の課題：counting への直接の取り組み。(i) $n=4$ の等号達成51族と五角形型の「対称正則族」の構造論、すなわち頻度がちょうど・ほぼ $1/2$ に張り付く極値族の分類。(ii) 平均化の限界（平均集合サイズ $\ge n/2$ なら自明、という古典事実の周辺）と、エントロピー論法（第1稿）への構造情報の注入。五角形が教えた「持ち上げの欠落」は、Chase–Lovett の近似反例が突く隙間と同じ形をしている。二つの方向の合流点を探す。

10. 結び

探索に出て、反例は見つかり、予想のほうが反証された。反証された予想から一般則と定理を回収して戻った。攻略ノートとして満点の成果である。それにしても五角形とは。正五角形は正多角形の中で唯一、対角線が黄金比を刻む図形であり、前シリーズでは Painlevé I の貼り合わせの整合条件に黄金比が現れた（第5部第1章）。偶然だろう。偶然だろうが、記録はしておく。偶然を記録しておくことの価値は、前シリーズの応答曲面（暗合がすべて等高線だった・第7部第7章）が教えてくれた。

三稿を終えての現在地を書いておく。第1稿でエントロピー論法の限界を自分の手で確かめ、第2稿で遺伝性から単射・マッチングの道へ入り、第3稿でその道が五角形に塞がれた。手元に残ったのは、限界の座標、小さな台集合の全数検証系、定理F1・F2・F3、そして「counting と matching は別物である」という一行である。Frankl 予想そのものは、45年前と変わらず未解決のまま目の前にある。数える問題に戻る。

参考文献

• H. Bruhn & O. Schaudt, The journey of the union-closed sets conjecture, Graphs Combin. 31 (2015)：総説（単射型強化の議論を含む；本稿の反例の既知性の確認先）
• E. Knill, Graph generated union-closed families of sets（1994）：グラフ生成族という古典的クラス（本稿の反例の棲息地）
• P. Hall (1935)：結婚定理
• D. G. Sarvate & J.-C. Renaud (1989)：強化予想が反例で反証される先例