Graph Puzzles II.1: Counterexamples to Jain's Second Unit Vector Flows Conjecture

この論文は、Tutte の 5-フロー予想を導く可能性があった Jain の第 2 単位ベクトル流予想に対する 2 つの反例を構成し、その値域にさらに$\{-5, 5\}$が必要となることを示しています。

要約

🌍 物語の舞台：「球体（地球）」と「魔法の数字」

まず、想像してみてください。
私たちが住んでいる**「地球（球体）」があります。この地球の表面（球面）には、無数の「点（場所）」**があります。

ある天才数学者（ジャインさん）は、こんなことを言いました。

「もし、この地球の表面のすべての点に、**『-4 から 4 までの整数（0 は使わない）』**という『魔法の数字』を割り当てることができれば、世の中のあらゆる『橋のない道（グラフ）』の問題を解決できるよ！」

この「魔法の数字」には、2 つの厳しいルールがありました。

1. 対極のルール：地球の真裏にある 2 つの点（北極と南極のような関係）は、「足して 0 になる数字」（例：+3 と -3）でなければいけない。
2. 三角形のルール：地球の表面をぐるっと回る大きな円（大円）の上に並んだ、等間隔の 3 つの点は、**「足して 0 になる数字」**でなければいけない。

ジャインさんは、「このルールを満たす数字の割り当て方は、必ず存在するはずだ！」と信じていました。もしこれが本当なら、数学の長年の難問（テュットの 5-フロー予想）も解決してしまうのです。

🔍 主人公の挑戦：「2 つの反例」を見つける

しかし、この論文の著者（ウリャノフさん）は、「本当にそうかな？ちょっと疑ってみよう」と考えました。
彼は、ジャインさんの予想が**「嘘（反例）」**になるような、特殊な「点の集まり」を 2 つ作り出しました。

1 つ目の反例：「50 個の点の迷路」

著者は、正二十面体（20 面体の宝石のような形）の頂点をヒントに、地球の表面に50 個の点を配置しました。
これらは、複雑に絡み合った「大円（大きな円）」のネットワークを作っています。

• 何が起きた？
  この 50 個の点に、ジャインさんのルール（-4 から 4 までの数字）で数字を割り当てようとすると、**「どうやっても矛盾してしまう」ことがわかりました。
  無理やり数字を当てはめようとすると、どうしても「+5」や「-5」**という、ルール外（許されていない）の数字が必要になってしまうのです。
  つまり、「-4 から 4 までの数字だけでは、このパズルは解けない！」という証明になりました。

2 つ目の反例：「36 個の点のトリック」

もっと小さな、36 個の点の集まりでも、同じことが起こることがわかりました。
これもまた、-4 から 4 までの数字では埋め尽くすことができず、**「±5」**が必要になることが証明されました。

💡 結論：「魔法の数字」はもっと大きかった

この論文の結論はシンプルです。

「ジャインさんの『-4 から 4 までの数字で全部解決できる』という予想は間違いでした。
実際には、**『±5』**という、もっと大きな数字が必要になる点の集まりが存在します。」

🧩 なぜこれが重要なのか？（日常への例え）

これを**「パズル」**に例えてみましょう。

• ジャインさんの予想：「どんな複雑なパズルでも、**『1 色のピース』**だけで完成するはずだ！」
• この論文の結果：「いや、実は**『2 色目のピース（±5）』**がないと完成しないパズルが存在するよ！」

もしジャインさんの予想が正しければ、「1 色だけで全部解決できる」という素晴らしい定理が生まれていました。しかし、この論文によって「いや、もっと複雑な世界（±5 が必要）があるよ」ということがわかりました。

🚀 今後の展開

著者は、「じゃあ、この予想は完全に無駄だったのか？」と言っているわけではありません。
「±5 が必要になる点の集まりは発見したが、**『±6』**が必要になるような、もっとすごい反例はあるのか？」や、「じゃあ、どうすればテュットの予想（数学の難問）を解決できるのか？」という新しい謎が生まれました。

この論文は、**「数学のパズルは、私たちが思っていたよりももっと奥深く、複雑で、面白い」**ということを教えてくれる、ワクワクする発見の報告書なのです。

---

まとめ

• テーマ：地球の表面に数字を割り当てるパズル。
• 予想：「-4 から 4 までの数字で全部解決できるはず！」
• 結果：「いや、±5が必要になるパズルが 2 つ見つかったよ！」
• 意味：数学の難問への道筋が変わり、新しい冒険が始まりました。

技術概要

以下は、Nikolay Ulyanov による論文「Graph Puzzles II.1: Counterexamples to Jain's second unit vector flows conjecture」の技術的な要約です。

1. 問題の背景と定義

本論文は、グラフ理論における**「単位ベクトルフロー（Unit Vector Flows）」**と、それに関連する K. Jain による 2 つの予想、および有名な Tutte の 5-フロー予想との関係性について扱っています。

• 単位ベクトルフロー（Conjecture 1.1）: すべての橋（bridge）を持たないグラフ $G$ に対して、各辺に 3 次元単位ベクトル（球面 $S^2$ 上の点）を割り当て、各頂点における流入ベクトルの和が流出ベクトルの和と等しくなるようなフローが存在する。
• $S^2$ 上の非ゼロ 5-フロー予想（Conjecture 1.2）: 球面 $S^2$ から整数集合 $\{-4, -3, -2, -1, 1, 2, 3, 4\}$ への写像 $q$ が存在し、以下の条件を満たす。
  1. 対蹠点（antipodal points）の値は互いに逆数になる（$q(-p) = -q(p)$）。
  2. 大円（great circle）上で等間隔に配置された任意の 3 点の値の和が 0 になる。
• Tutte の 5-フロー予想（Conjecture 1.3）: すべての橋を持たない 3 正則グラフは、非ゼロ 5-フローを持つ。

論理的関係: もし Conjecture 1.1 と Conjecture 1.2 の両方が真であれば、Tutte の 5-フロー予想（Conjecture 1.3）が導かれることが知られています。したがって、Conjecture 1.2 が偽であることを示すことは、この証明アプローチの限界を示す重要な意味を持ちます。

2. 手法とアプローチ

著者は、Conjecture 1.2 が偽であることを示すために、**「$\{-4, \dots, 4\}$ の範囲では条件を満たすラベル付けが存在せず、$\pm 5$（つまり非ゼロ 6-フロー）が必要となるような、球面 $S^2$ 上の有限点集合」**を 2 つ構築しました。

検証手法としては、**ブール充足可能性問題（SAT）**への定式化が用いられました。

• 各点（対蹠点の代表）に対して、許可された値 $\{-4, \dots, 4\}$ のそれぞれに対応する変数を導入。
• 「1 つの点に 1 つの値のみ割り当てられる」「対蹠点の値が逆」「大円上の 3 点の和が 0」という制約を CNF（節の積）形式で記述。
• SAT ソルバー（PicoSAT/pycosat）を用いて、この制約を満たす解が存在しないことを証明。

3. 主要な貢献と結果

著者は Jain の第 2 予想に対する 2 つの反例を提示しました。

反例 1: 二十面十二面体（Icosidodecahedron）の 50 点拡張

• 構成: 正二十面十二面体の 30 頂点を基盤とします。各頂点に対応する小さな円（球面上）を定義し、特定の球面距離を持つ頂点対に対応する円の交点を追加することで、合計 50 点の集合を構築しました。
• 構造: この 50 点は、元の Petersen グラフと、10 頂点の Möbius ラダー（Möbius ladder）の組み合わせとして解釈できます。
• 結果: 25 対の対蹠点（50 点）と 40 組の大円上の 3 点の組に対して、$\{-4, \dots, 4\}$ の範囲でのラベル付けは SAT ソルバーにより**充足不可能（unsatisfiable）**であることが確認されました。つまり、この集合に対しては $\pm 5$ の値が必要となり、Conjecture 1.2 は成立しません。

反例 2: 平方根算術に基づく 36 点構成

• 構成: 異なるアプローチとして、$\sqrt{v_1}, \sqrt{v_2}$ などの平方根を含む座標値を生成し、単位球面上の点（$x^2+y^2+z^2=1$）を探索しました。
• 最適化: 生成された 126 点の連結成分から、条件を満たさない点や冗長な点を剪定（pruning）し、最終的に36 点と 13 組の 3 点の組からなる最小の反例集合を導き出しました。
• 結果: 同様に SAT ソルバーを用いた検証により、$\{-4, \dots, 4\}$ の範囲でのラベル付けは不可能であることが証明されました。ただし、$\{-5, \dots, 5\}$（非ゼロ 6-フロー）の範囲であれば解が存在することが確認されました。

4. 意義と今後の課題

• 予想の否定: Jain の第 2 予想（$S^2$ 上の非ゼロ 5-フローの存在）は、有限点集合の存在によって反証されました。これにより、Conjecture 1.1 と 1.2 の組み合わせによる Tutte 予想の証明アプローチは、この特定の経路では成立しないことが示されました。
• 数値的厳密性: 計算には数値誤差を考慮した許容誤差（$\epsilon = 10^{-7}$）が用いられましたが、結果は Lean 4 による形式的検証や厳密算術でもクロスチェックされています。
• 残された問い:
  • $\pm 6$ 以上の値を必要とする点集合は存在するか？（現時点では $\pm 5$ が最大）
  • Conjecture 1.2 を修正し、Tutte 予想の証明に使えるような、より良い点集合（例えば代数的な性質を持つ無限集合など）は存在するか？
  • 「非ゼロ $k$-フロー」と「モジュロ $k$-フロー」の最小値が常に一致するかどうか。

結論

本論文は、Jain の単位ベクトルフローに関する第 2 予想が誤りであることを、具体的な幾何学的構成（50 点および 36 点の集合）と計算機証明（SAT ソルバー）によって示しました。これは、グラフフロー理論における高次元フローの性質と、古典的な Tutte 予想との関係性に関する重要な知見を提供しています。