トゥランのレンガ工場の問題

グラフ描画の数学において、トゥランのレンガ工場問題は、完全な二部グラフの描画における交差数の最小値を求める問題である。この問題は、第二次世界大戦中にレンガ工場で強制的に働かされていたときにこの問題を考案したパル・トゥランにちなんで名付けられた。^[1]

カジミエシュ・ザランキエヴィチによって発見された描画法は、あらゆる完全二部グラフに対して正しい答えを与えると予想されており、これが正しいという主張はザランキエヴィチ交差数予想として知られるようになった。この予想は未解決のままであり、いくつかの特殊なケースのみが解決されている。^[2]

第二次世界大戦中、ハンガリーの数学者パル・トゥランはレンガ工場で強制的に働かされ、窯から貯蔵場所まで荷車に積んだレンガを運んでいた。工場には窯から貯蔵場所まで線路が通っていたが、線路が交差する箇所では荷車を押すのが大変だった。トゥランはこの状況に触発され、線路の交差回数を最小限に抑えるために工場をどのように再設計すればよいか考えた。^[1]

数学的には、この問題は、頂点が窯と貯蔵所、辺が各窯から各貯蔵所までの線路を表す完全な二部グラフのグラフ描画を求めるものとして定式化できます。グラフは、各頂点を点として、各辺をその 2 つの端点を結ぶ曲線として平面上に描画し、頂点が接していない辺には頂点を配置しないようにする必要があります。グラフ内で互いに交わらない 2 つの辺が平面内で空でない交差点を持つ場合は、交差が 1 つカウントされます。では、このような描画における交差の最小数はいくつになるかという疑問が生じます。^{[2] [3]}

トゥランによるこの問題の定式化は、グラフの交差数に関する最初の研究の 1 つとしてよく知られています。^[4] (同じ概念の別の独立した定式化は、社会学の社会図を描く方法において行われました。^[5]また、はるかに古いパズルである3 つのユーティリティ問題は、3 つの窯と 3 つの貯蔵施設を持つレンガ工場問題の特殊なケースと見なすことができます。^{[6] ) 交差数は、}グラフ描画の中心的な研究対象として^{[7] 、} VLSI設計^[8] および離散幾何学^[9] の重要なツールとして、それ以来重要性を増しています。

ザランキエヴィチとカジミエシュ・ウルバニクは、1952年にポーランドでトゥランがレンガ工場問題について話すのをそれぞれ別の講演で聞いており^[3] 、それぞれ独立して問題の解決法を発表し、交差の数について同等の公式を示していた^{[10] [11]。} 両者が示したように、交差の数が次の数に等しい完全な二部グラフK _m,n （片側にm個の頂点、もう片側にn個の頂点、そして両側を結ぶmn本の辺を持つグラフ）を描くことは常に可能である。

${\displaystyle \operatorname {cr} (K_{m,n})\leq {\biggl \lfloor }{\frac {n}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-1}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {m}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {m-1}{2}}{\biggr \rfloor }.}$

構築は簡単です。平面のx軸上に、原点を避けてm個の頂点を配置し、 y軸の左右の点の数が等しいかほぼ等しいようにします。同様に、平面のy軸上に、原点を避けてn個の頂点を配置し、 x軸の上下の点の数が等しいかほぼ等しいようにします。次に、 x軸上のすべての点をy軸上のすべての点に直線で接続します。^[3]

しかし、この式が最適であること、つまり交差数が少ない描画はあり得ないという彼らの証明は誤りであった。このギャップは、発表から11年後、ゲルハルト・リンゲルとポール・カイネンによってほぼ同時に発見された。^[12] それでも、ザランキエヴィチとアーバニクの式は最適であると推測されている。これはザランキエヴィチ交差数予想として知られるようになった。いくつかの特殊なケースが正しいことが知られているが、一般的なケースは未解決である。^[2]

K _m,nとK _{n,m は}同型なので、 m ≤ nの場合を考えれば十分です。さらに、m ≤ 2 の場合、ザランキエヴィチの構成では交差は発生しませんが、もちろんこれを上回ることはできません。したがって、非自明なケースは、 mとnが両方とも≥ 3 の場合のみです。

Zarankiewicz のこの予想の証明は、K _{m , n}の一般的な場合には無効であるが、 m = 3の場合には有効である。これはその後、 mのその他の小さな値に拡張され、 Zarankiewicz 予想はm ≤ 6の完全二部グラフK _m,nに対して成り立つことが知られている。^{[13]この予想は、} K _7,7、K _7,8、およびK _7,9 に対しても成り立つことが知られている。^[14] 反例、つまり Zarankiewicz 境界よりも少ない交差を必要とするグラフK _m,nが存在する場合、最小の反例ではmとn の両方が奇数でなければならない。^[13]

mの固定された選択ごとに、すべてのK _m,nに対する予想の真偽は、有限個のnの選択のみをテストすることによって検証できます。^[15] より一般的には、すべての完全な二部グラフには、（十分に大きなグラフの場合）ザランキエヴィチの境界によって与えられた数の少なくとも83%の交差数が必要であることが証明されています。この下限と上限の間のギャップを埋めることは未解決の問題のままです。^[16]

辺を任意の曲線ではなく直線として描く必要がある場合、一部のグラフでは曲線の辺で描く場合よりも多くの交差が必要になります。しかし、ザランキエヴィチが確立した完全二部グラフの交差数の上限は、直線の辺のみを使用して達成できます。したがって、ザランキエヴィチの予想が正しければ、完全二部グラフの直線交差数は交差数に等しくなります。^[17]

• ワイスシュタイン、エリック W.、「ザランキエヴィチの予想」、MathWorld