交叉數

${\displaystyle K_{4,7}}$的一個最優畫法，顯示圖蘭磚廠問題中，若有4個倉（黃點）和7個窯（藍點），則需要18個交叉（紅點）。

在第二次世界大戰期間，匈牙利數學家圖蘭·帕爾被迫在磚廠工作，要將一車車的磚從窯爐推到貨倉。工廠的每個窯爐到每個貨倉之間各有一條路軌，而磚車在路軌交叉處特別難推。於是，圖蘭提出其磚廠問題：窯爐、貨倉和路軌應如何安排，才能使交叉的數目最少？數學上，窯爐和貨倉可視為完全二部圖的頂點，而路軌則是二部圖的邊。於是工廠的佈局就是該圖在平面上的一個畫法，換言之問題變成： 完全二部圖的畫法中，交叉的最少數目是多少？[8]

卡齊米日·扎蘭凱維奇嘗試解決圖蘭磚廠問題，[9]但其證明有錯。不過，他成功推導出完全二部圖${\displaystyle K_{m,n}}$交叉數的一個上界：

${\displaystyle {\textrm {cr}}(K_{m,n})\leq \left\lfloor {\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {m}{2}}\right\rfloor \left\lfloor {\frac {m-1}{2}}\right\rfloor .}$

一個猜想是，上述上界確實是所有完全二部圖的交叉數。[10]

完全圖的交叉數問題最先由安東尼·希爾提出，並於1960年出版。[11]希爾及其合作者約翰·恩斯特皆為對數學甚感興趣的構成主義藝術家。兩位不僅提出了問題，還猜想了該交叉數的公式，公式由理查·蓋於1960年出版。[11]具體來說，已知${\displaystyle K_{p}}$總有一種畫法，其交叉的數目為

${\displaystyle {\frac {1}{4}}\left\lfloor {\frac {p}{2}}\right\rfloor \left\lfloor {\frac {p-1}{2}}\right\rfloor \left\lfloor {\frac {p-2}{2}}\right\rfloor \left\lfloor {\frac {p-3}{2}}\right\rfloor .}$

上式在${\displaystyle p=5,6,\cdots ,12}$時，取值分別為${\displaystyle 1,3,9,18,36,60,100,150}$，見整數數列線上大全的A000241號數列。希爾等人猜想，不存在更好的畫法，即上式給出了完全圖的交叉數${\displaystyle {\text{cr}}(K_{p})}$。湯瑪士·沙提於1964年獨立地作出了同一個猜想。[12]

對於${\displaystyle p\leq 10}$，沙提驗證了上式確實給出交叉的最小可能數目。潘（Shengjun Pan)和布魯斯·里希特（Bruce Richter）驗證了${\displaystyle p=11,12}$的情況。[13]

2007年，米高·艾伯森（Michael O. Albertson）提出了艾伯森猜想，其斷言：在所有色數為${\displaystyle p}$的圖之中，完全圖${\displaystyle K_{p}}$的交叉數最小。換言之，若此猜想與上段的猜想均成立，則每個染色數為${\displaystyle p}$的圖，交叉數皆不小於上段的公式。現已證明，艾伯森猜想對於${\displaystyle p\leq 16}$成立。[14]

已知交叉數為${\displaystyle 1}$至${\displaystyle 11}$的最小的立方圖，其頂點數分別為${\displaystyle 6,10,14,16,18,20,22,24,26,28,28}$（OEIS數列A110507），如下表所記：

交叉數	最小立方圖例子	頂點數
1	完全二部圖${\displaystyle K_{3,3}}$	6
2	佩特森圖	10
3	希伍德圖	14
4	莫比烏斯－坎特圖	16
5	帕普斯圖	18
6	笛沙格圖	20
7	有4個不同構的例子，但並無熟知命名[15]	22
8	瑙魯圖、麥基圖、(3,7)-籠圖[16]	24
9	麥基圖加某一條邊[17]	26
10	麥基圖加某兩條邊[17]	28
11	考克斯特圖[18]	28

2009年，愛德華·柏奇和Geoffrey Exoo猜想交叉數為13的最小立方圖為塔特－考克斯特圖，以及交叉數為170的最小立方圖為塔特12-籠。[16][19]