交叉数

${\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]