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

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

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

第二次世界大戦中、ハンガリーの数学者パール・トゥランは、レンガ工場で窯から貯蔵場所までレンガを満載した荷車を押す仕事を強いられた。工場には各窯から各貯蔵場所まで線路が敷かれており、線路が交差する地点では荷車を押すのが困難だった。トゥランはこの状況から、線路の交差回数を最小限に抑えるように工場をどのように再設計できるかを考えるようになった。^{[ 1 ]}

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

この問題の Turán による定式化は、グラフの交差数に関する最初の研究の 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 以上の場合のみです。

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

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

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

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