遺伝する構造 —— 吸収写像と生き残った強化予想 —— 和集合閉集合予想・攻略ノート（2）

遺伝する構造 —— 吸収写像と生き残った強化予想

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

本稿の位置づけ

第2稿。第1稿はエントロピー論法の天井 $\psi \approx 0.382$ を測量し、使い残されている厳密構造の候補として反復（→定理F1で袋小路と判明）・束構造・遺伝性を挙げた。本稿は遺伝性を攻める。元 $x$ を含まない集合の族 ${\mathcal{F}}_{\neg x}$ もまた和集合閉であり、族の中に同じ問題の小さいコピーが入れ子になっている。

武器は第1稿で築いた橋頭堡（$n\le 4$ の全 4958 族の検証系）である。仮説を立てるたび、まず 4958 族に当てて即座に棄却検査をする。本稿では三つの実験を行い、一つの古典的定理を自前で確立し、生き残った強化予想を一つ手に入れた。

前提知識：遺伝分解と単射戦略

0.1 遺伝分解

元 $x$ を固定すると、和集合閉族 $\mathcal{F}$ は二つに割れる：

三つの事実（いずれも一行で確認できる）：(i) ${\mathcal{F}}_{\neg x}$ は和集合閉（$x$ を含まない二つの和は $x$ を含まない）。(ii) ${\mathcal{F}}_x^{\prime }:=\{A\setminus \{x\}:A\in {\mathcal{F}}_x\}$ も和集合閉。(iii) 吸収：$A\in {\mathcal{F}}_{\neg x}$、$B\in {\mathcal{F}}_x^{\prime }$ なら $A\cup B\in {\mathcal{F}}_x^{\prime }$（なぜなら $A\cup B\cup \{x\}\in \mathcal{F}$）。

予想は「ある $x$ で $|{\mathcal{F}}_x^{\prime }|\ge |{\mathcal{F}}_{\neg x}|$」と同値である。したがって単射 $\phi :{\mathcal{F}}_{\neg x}\to {\mathcal{F}}_x^{\prime }$ を一つ作れば勝ちである。これが単射戦略であり、遺伝性攻撃の基本形である。

0.2 歴史上の単射戦略

単射戦略の成功例と限界は古くから知られている（総説：Bruhn–Schaudt 2015）。成功例が次節の定理F2（単元・二元補題）である。一方、「最小の集合の元から証人を探す」方向には Sarvate–Renaud（1989）の警告がある。最小集合が3元のとき、その3元がすべて落第する族が存在する。単射戦略は万能ではないが、どこまで届き、どこで折れるかの定量的な地図は（著者の知る限り）整備されていない。本稿はその地図を、小世界の全数データで描く。

要旨

定理F2（古典・自前で再確立）。(a) $\{x\}\in \mathcal{F}$ なら $x$ は証人（頻度 $\ge 1/2$）。(b) $\{x,y\}\in \mathcal{F}$ なら $x$ か $y$ が証人。証明はそれぞれ一行と四行（本文）。全数照合：$n=4$ の全族で単元補題 5864 件・二元補題 11208 件、例外なし。

実験（吸収写像の定量化）。単射戦略の正準候補（$B_0\in {\mathcal{F}}_x^{\prime }$ を最小サイズ元として $\phi (A)=A\cup B_0$）を全 4958 族で検査した。結果：最良の $x$ を選べば 99.4%（4915/4943）の族で単射になり、そのまま証明が完結する。失敗するのは29族だけ（$B_0$ の全候補・全 $x$ を試しても救えない「困難な核」；最悪の像比率 $0.500$）。Frankl 予想の難しさは、小世界では全体の 0.6% に濃縮されている。

発見（生き残った強化予想）。正準写像の失敗は、写像の固定が原因かもしれない。そこで $A$ ごとに相手 $B^{\prime }\in {\mathcal{F}}_x^{\prime }$ を自由に選ぶマッチング版を検査した：二部グラフ（左 ${\mathcal{F}}_{\neg x}$、右 ${\mathcal{F}}_x^{\prime }$、辺 $A$—$A\cup B^{\prime }$、これは「$A\subseteq D$ なる $D\in {\mathcal{F}}_x^{\prime }$」と同値）に ${\mathcal{F}}_{\neg x}$ を飽和するマッチングはあるか。結果：

予想F2'（マッチング版・包含単射版）　任意の和集合閉族（$\ne \{\varnothing \}$）に対し、ある元 $x$ が存在して、単射 $\phi :{\mathcal{F}}_{\neg x}\to {\mathcal{F}}_x$ で $A\subseteq \phi (A)$ なるものが存在する。

検証状況：$n=3$（120族）・$n=4$（4958族）の全数で失敗ゼロ。Frankl 予想より強い命題が、小世界で無敗のまま生き残った。

これは文献で「包含単射による強化」として議論されてきた方向と同型であり（Bruhn–Schaudt 総説の周辺）、大きな台集合での既知の反例の有無は要文献確認として次稿の第一工程に置く。反例が知られていなければ、攻撃面は明確である。Hall の結婚定理により、予想F2' は「全ての部分族 $S\subseteq {\mathcal{F}}_{\neg x}$ に対し $|N(S)|\ge |S|$（$N(S)=\{D\in {\mathcal{F}}_x^{\prime }:\exists A\in S,A\subseteq D\}$）」と同値であり、和集合閉性が $N(S)$ に課す下界の解析という、純粋に組合せ的な問題に変わる。

副実験（Sarvate–Renaud 現象の希少性）。最小3元集合の全元が落第する族は、$n=4$ の全数で 0、$n=6,7$ のランダム8万試行でも 0。現象は実在する（文献）が、強く構造化された大きな族に限られる。最小集合攻撃の障害は、小世界には存在しない。

第一部　定理F2：単射戦略の成功例

1. 単元補題（一行）

$\{x\}\in \mathcal{F}$ とする。$\phi (A)=A\cup \{x\}$ は ${\mathcal{F}}_{\neg x}\to {\mathcal{F}}_x$ の単射（$A\cup \{x\}\in \mathcal{F}$ は和集合閉性、単射性は $A=\phi (A)\setminus \{x\}$ で復元できるから）。よって $|{\mathcal{F}}_x|\ge |{\mathcal{F}}_{\neg x}|$、$x$ は証人。$■$

2. 二元補題（四行）

$\{x,y\}\in \mathcal{F}$ とする。$\mathcal{F}$ を $x,y$ の所属で四分割し、個数を $m_{00},m_{x0},m_{0y},m_{xy}$ と書く。$\phi (A)=A\cup \{x,y\}$ は「どちらも含まない」クラスから「両方含む」クラスへの単射だから $m_{00}\le m_{xy}$。すると

平均が $1/2$ 以上なら最大も $1/2$ 以上。$x$ か $y$ が証人。$■$

（両補題とも古典的な結果である。全数照合：単元 5864 件・二元 11208 件、例外なし。なお三元集合では同じ議論が破綻することが知られている。Sarvate–Renaud の反例である。ただし本稿の探索の通り、その反例は小世界には棲めない。）

第二部　吸収写像の地図：難しさは 0.6% に濃縮されている

3. 正準写像の成績

吸収（前提 0.1(iii)）が示唆する正準の単射候補は $\phi (A)=A\cup B_0$（$B_0$＝${\mathcal{F}}_x^{\prime }$ の最小サイズ元）である。全 4958 族 × 全 $x$ × $B_0$ 全候補での成績：

像比率の分布は $\{1.0:4915,0.8:16,0.7:9,0.5:3\}$。失敗するときも像は半分以上残る。難しさの在り処は特定できた。小世界の Frankl 予想は「29 族の困難な核」に濃縮されており、残り 99.4% は一行の写像で落ちる。

4. 衝突の解剖

衝突 $A_1\cup B_0=A_2\cup B_0$（$A_1\ne A_2$）が起きるのは、$A_1,A_2$ の差分が $B_0$ に飲み込まれるとき、すなわち $A_1△A_2\subseteq B_0$ のときである。正準写像の弱点は一つの $B_0$ を全員に使うことにある。$A$ ごとに相手を変えれば、衝突は避けられるかもしれない。これが次部のマッチング版である。

第三部　マッチング版：生き残った強化予想

5. 検査と結果

二部グラフ $G_x$：左 ${\mathcal{F}}_{\neg x}$、右 ${\mathcal{F}}_x^{\prime }$、辺は $A$—$D$（$A\subseteq D$、$D\in {\mathcal{F}}_x^{\prime }$；吸収により $A\cup B^{\prime }$ の形の全てがこれ）。増加路アルゴリズムで最大マッチングを計算し、「ある $x$ で ${\mathcal{F}}_{\neg x}$ 飽和マッチングが存在するか」を全数検査した：

正準写像が折れた29族も、マッチングは全て生き延びた。 予想F2'（要旨）は小世界で無敗である。

6. これが意味すること・しないこと

意味すること：(a) Frankl 予想は、小世界ではより強い包含単射版のかたちで成り立っている。(b) 攻撃面が変わる。Hall の定理により、予想F2' は近傍条件 $|N(S)|\ge |S|$ の証明に帰着し、$N(S)$（$S$ のどれかを含む ${\mathcal{F}}_x^{\prime }$ の元たち）には和集合閉性からの下界（例えば $N(S)$ は $S$ の和集合たちを $B_0$ 経由で含む）が使える。エントロピーの土俵から、マッチング理論の土俵への転線である。

意味しないこと：小世界の無敗は証明ではない。しかも包含単射型の強化は文献で議論されてきた方向であり、大きな台集合での反例が既に知られている可能性がある（強化予想は往々にして反例で死ぬ。Sarvate–Renaud がその教訓である）。次稿の第一工程は、(i) ランダム探索による反例狩り（$n=\mathrm{5..8}$）と (ii) 文献状況の確認に充てる。反例が出れば「どの構造が単射を殺すか」が学べ、出なければ Hall 条件の解析に進む。どちらでも前進である。

第四部　帳簿と次稿への計画

7. 帳簿

F-2.（第2稿）定理F2（単元・二元補題、証明つき、全数照合 5864＋11208 件）。吸収写像の地図：正準写像は 99.4% で単射、困難な核は 29 族（0.6%）、衝突機構 $A_1△A_2\subseteq B_0$ の同定。予想F2'（マッチング版＝包含単射版）が $n\le 4$ 全数で無敗。Frankl より強い命題の生存を確認。Sarvate–Renaud 現象は $n=4$ 全数・$n=6,7$ ランダム8万試行で不在（現象は大きく構造化された族に限る）。

未解決の的：予想F2' の反例狩り（$n=\mathrm{5..8}$）と文献確認 → 生存なら Hall 条件 $|N(S)|\ge |S|$ の解析。

8. 結び

第1稿の壁（$\psi$）はエントロピーという解析の言葉で立っていた。本稿で戦線は組合せの言葉に転じ、そこで見えた景色は意外に明るい。小世界では、予想は強化版のかたちでゆとりを持って成り立ち、難しさは 0.6% の核に濃縮され、核もマッチングの自由度で溶ける。もちろん、小さな世界の明るさが大きな世界まで続く保証はどこにもない（それを最もよく知っているのは、45年間この問題に挑んできた人々である）。だが攻撃面は一つ具体化した。$|N(S)|\ge |S|$、つまり和集合閉性は部分族の「上にあるもの」をどれだけ豊かにするか、である。次稿で狩りに出る。

参考文献

• H. Bruhn & O. Schaudt, The journey of the union-closed sets conjecture, Graphs Combin. 31 (2015)：総説（単射戦略・強化予想の系譜を含む）
• D. G. Sarvate & J.-C. Renaud, On the union-closed sets conjecture, Ars Combin. 27 (1989)：二元補題の周辺と、三元最小集合の反例
• P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935)：結婚定理（マッチング版の攻撃面）
• J. Gilmer (arXiv:2211.09055, 2022) ほか第1稿の文献：エントロピー戦線の現状