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

本稿の位置づけ

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

道具は第1稿で築いた検証系（$n=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$）を $n=4$ の全 4958 族で走らせた。像比率が定義できるのは 4943 族である（残り 15 族は一つの集合だけからなる族 $\{A\}$ で、どの $x$ でも ${\mathcal{F}}_{\neg x}$ か ${\mathcal{F}}_x$ が空になり、比率の分母が消える。単射は空虚に成立する）。その 4943 族での結果：最良の $x$ を選べば 4915 族＝99.4% で単射になり、そのまま証明が完結する。失敗するのは 28 族だけ——これが「困難な核」である（最悪の像比率 $0.500$。$B_0$ を選び直すと 28 族中 17 族は単射に戻るが、どの $x$・どの単一の $B_0$ でも救えない 11 族が芯として残る）。Frankl 予想の難しさは、小世界では全体の 0.6% にあたるこの 28 族に濃縮されている。

発見（生き残った強化予想）。正準写像が折れるのは、行き先を一つに固定したせいかもしれない。そこで $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)$ なるものが存在する。

記号について：$A\in {\mathcal{F}}_{\neg x}$ は $x$ を含まないから、$D\in {\mathcal{F}}_x$ に対し $A\subseteq D$ と $A\subseteq D\setminus \{x\}$ は同値である。よって「${\mathcal{F}}_x$ への包含単射」と「${\mathcal{F}}_x^{\prime }$ への包含単射」は同じものを指す。以下、個数を数える文脈では ${\mathcal{F}}_x^{\prime }$、族そのものを指す文脈では ${\mathcal{F}}_x$ と書き分ける。

検証状況：$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 }$ の最小サイズ元。複数あるときは一つに固定する）である。$n=4$ の全 4958 族 × 全 $x$ で走らせた。ただし像比率が定義できるのは 4943 族である。残りの 15 族は一つの集合だけからなる族 $\{A\}$（空でない $A\subseteq [4]$ の 15 通り）で、どの $x$ を選んでも ${\mathcal{F}}_{\neg x}$ か ${\mathcal{F}}_x$ の一方が空になり、比率の分母が消える（単射は空虚に成立し、Frankl も自明）。以下の成績は、残る 4943 族についてのものである：

像比率（写した先に残る集合の個数を、写す前の個数で割った値）の分布は $\{1.0:4915,0.8:5,0.75:11,2/3:9,0.5:3\}$（合計 4943 族）。失敗族数 28 はこの分布の $1.0$ 未満の四段の和である。単射に失敗するときも、像は半分以上残っている。難しさの在り処は特定できた。小世界の Frankl 予想は「28 族の困難な核」に濃縮されており、残り 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$ を全員に使うことにある。実際、$B_0$ の選び直しだけでも部分的に効く：28 族のうち 14 族は同じ最小サイズの別候補で、さらに 3 族はより大きい $B_0$ で単射になる。それでも 11 族は、どの $x$・どの単一の $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}$ 飽和マッチングが存在するか」を全数検査した：

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

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

意味すること：(a) Frankl 予想は、小世界ではより強い包含単射版のかたちで成り立っている。(b) 攻略の切り口が変わる。Hall の定理により、予想F2' は近傍条件 $|N(S)|\ge |S|$ の証明に帰着する。問題は、和集合閉性が $N(S)$（$S$ のどれかを含む ${\mathcal{F}}_x^{\prime }$ の元たち）にどれだけの下界を課すか、である。吸収から直ちに出るのは $N(S)\supseteq \{A\cup B_0:A\in S\}$ だけで、これは正準写像の像そのものだから、衝突が起きた瞬間に $|S|$ を下回る——3節で見た通りである。使える下界の具体形はまだ得られていない。エントロピーの枠組みから、マッチング理論の枠組みへ土俵を移したところまでが本稿の到達点である。

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

第四部　結果の記録と次稿への計画

7. 結果の記録

F-2.（第2稿）定理F2（単元・二元補題、証明つき、全数照合 5864＋11208 件）。吸収写像の地図：$n=4$ で像比率を集計できた 4943 族のうち正準写像は 99.4%（4915族）で単射、困難な核は 28 族（0.6%）、衝突機構 $A_1△A_2\subseteq B_0$ の同定。予想F2'（マッチング版＝包含単射版）が $n=3$ の全120族・$n=4$ の全4958族で無敗。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稿の文献：エントロピー論法の現状