五角形が強化を殺す —— 反例の解剖と一般則 —— 和集合閉集合予想・攻略ノート（3）

五角形が強化を殺す —— 反例の解剖と一般則

—— 和集合閉集合予想・攻略ノート（3）——

本稿の位置づけ
第3稿。第2稿は、Frankl 予想より強い予想F2'（包含単射版：ある $x$ と単射 $φ : F_{\neg x} \to F_{x}$ 、 $A \subseteq φ (A)$ 、が常に存在する）が $n \leq 4$ の全 5078 族で無敗であることを確認し、「強化予想は反例で死ぬのが常」という歴史の教訓に従って、次の一手を反例狩りと定めた。
本稿はその狩りの記録である。結果として、獲物は出た。強化予想F2'は偽であり、しかも反例の正体は、数学でもっとも親しまれた図形の一つである五角形だった。倒れた強化から学べることは多い。解剖と一般則、そして戦線の再設定までを行う。

前提知識：狩りの装備

0.1 何を探すか

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

0.2 探索の三方面

第2稿の計画通り、三方面から探した。(a) ランダム： $n = 5..8$ でランダム生成集合の和集合閉包、計約6.8万有効試行。(b) 持ち上げ： $n = 4$ で正準写像が折れた「困難な29族」に新しい元をランダムに縫い込み $n = 5, 6$ へ拡張、1.74万試行。(c) 構造化：Fano 平面の直線族・その補族、後述のグラフ辺族たち。

要旨

狩りの結果。ランダム探索が3件の反例を出した（ $n = 5$ で2件、 $n = 7$ で1件； $n = 6, 8$ と持ち上げ・Fano は空振り）。 $n \leq 4$ は第2稿の全数検証で無敗だったから、台集合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集合の持ち上げはちょうど埋まっている。満室の屋根裏に、店子が一人多い。除去による極小化も試みたが、一つも削れない（16集合すべてが必要）。

同定。頻度の完全対称性が正体を告げていた。反例第1号は、五角形 $C_{5}$ （サイクル $1 - 2 - 5 - 3 - 4 - 1$ ）の辺集合5本の和集合閉包と厳密に一致する（機械照合）：5本の辺、5本の2辺パス、5枚の4点集合、全体集合の計16である。

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

生成グラフ	F2'	Frankl
$C_{3}$ （三角形）・ $C_{4}$	成立	✓
$C_{5}, C_{6}, C_{7}, C_{8}, C_{9}$	全て反例	✓（余裕で成立）
$K_{4}, K_{5}$ （完全グラフ）・パス $P_{5}$ ・スター	成立	✓
Petersen グラフ（内周5）	反例（ $∣ F ∣ = 578$ ）	✓

長さ5以上のサイクルはすべて F2' を殺す。機構も透明である。頂点 $x$ から距離2以上の辺 $P$ は、 $P \cup {x}$ が辺の和（パス）にならないため持ち上げを持たず、 $P$ のフィルターの持ち上げ枠は上の階でちょうど飽和する。 $C_{3}, C_{4}$ が無害なのは、すべての辺が $x$ の隣まで届いている（遠い辺が存在しない）からである。

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

第一部　狩りの記録

1. 統計

方面	試行	反例
ランダム $n = 5$	28,413	2
ランダム $n = 6$	19,535	0
ランダム $n = 7$	11,842	1
ランダム $n = 8$	7,938	0
困難29族の持ち上げ	17,400	0
Fano 直線族・補族	2	0
$n \leq 4$ （第2稿・全数）	5,078	0

ヒット率は $n = 5$ で約 $7 \times 1 0^{- 5}$ 。反例は稀少だが実在する。「持ち上げ」が空振りで「純ランダム」が当てたのは示唆的である：反例の構造（サイクル）は、 $n = 4$ の困難族の延長線上にはない新種だった。

2. 検証の優先順位

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

第二部　解剖：満室の屋根裏

3. 反例第1号の全貌

F = {12, 14, 25, 34, 35, 124, 125, 134, 235, 345, 1234, 1235, 1245, 1345, 2345, 12345}

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

S = {35, 235, 345, 2345} ⟶ N (S) = {23 5^{'}, 34 5^{'}, 234 5^{'}} (’ は \cup {1} 先の反映)

$∣ S ∣ = 4 > 3 = ∣ N (S) ∣$ 。犯人は $135 \in / F$ （ ${3, 5}$ の持ち上げの欠落）である。 $S$ は ${3, 5}$ のフィルター（それを含む $F_{\neg1}$ の全集合）であり、上の3つの持ち上げはちょうど3室。店子4人に部屋3室である。同じパターンが全5元で起きる（違反集合の表は機械出力の通り、すべて $∣ S ∣ = 4 > ∣ N (S) ∣ = 3$ ）。

4. 極小性

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

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

5. 五角形との一致

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

6. 一般則と機構

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

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

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

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

定理F3　和集合閉族の任意の二つの余原子（最大元 $T$ の直下の極大元）の和は $T$ である。したがって各元 $x \in T$ を欠く余原子は高々一つ。
証明　余原子 $A \neq = B$ の和 $A \cup B \in F$ は $A$ を真に含むから、極大性より $T$ 。もし $x$ を欠く余原子が二つあれば、その和 $T$ も $x$ を欠くが $x \in T$ に矛盾。 $■$ （全4958族＋Fano閉包で機械照合：欠け数の分布 ${0 : 5688, 1 : 13671}$ 、2以上は皆無 ✓）

これは「Hall 違反は族の最上階では起きられない」ことを意味する（余原子2つのボトルネックは構造的に禁止）。五角形の違反が最上階の一つ下（フィルターの床）で起きているのは、この定理と整合的である。違反が許されるのは、この禁止則が届く階のすぐ下からである。

第四部　教訓と戦線の再設定

8. counting と matching の分水嶺

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

counting ： 4 集合分の余裕で成立 ∣ F_{x} ∣ = 10 \geq 6 = ∣ F_{\neg x} ∣ しかし matching ：全 x で全滅 包含単射は存在しない

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

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) 平均化の限界（平均集合サイズ $\geq n /2$ なら自明、という古典事実の周辺）と、エントロピー戦線（第1稿）への構造情報の注入。五角形が教えた「持ち上げの欠落」は、Chase–Lovett の近似反例が突く隙間と同じ形をしている。二つの戦線の合流点を探す。

10. 結び

狩りに出て、獲物は見つかり、予想のほうが倒された。倒れた予想から一般則と定理を回収して戻った。攻略ノートとして満点の遠征である。それにしても五角形とは。ペンタゴンは正多角形の中で唯一、対角線が黄金比を刻む図形であり、前シリーズでは Painlevé I の縫い目の整合条件に黄金比が現れた（第18稿）。偶然だろう。偶然だろうが、記録はしておく。偶然を記録しておくことの価値は、前シリーズの応答曲面（暗合がすべて等高線だった・第38稿）が教えてくれた。数える戦いに戻る。

参考文献

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)：強化が反例で倒れる伝統の先例

五角形が強化を殺す —— 反例の解剖と一般則 —— 和集合閉集合予想・攻略ノート（3）