扎兰kiewicz猜想

扎兰kiewicz猜想断言，图交叉数 对于 完全二分图 是

(1)

其中 是 向下取整函数。Zarankiewicz (1954) 的原始证明包含一个错误，但后来 Guy (1969) 在某些特殊情况下解决了这个问题。Zarankiewicz (1954) 表明，一般来说，该公式提供了实际数字的上限。

该猜想解决的问题有时被称为砖厂问题，因为它由 Turán (1977) 描述如下：“我们在布达佩斯附近的一家砖厂工作。那里有一些窑炉用于烧砖，还有一些露天堆场用于存放砖块。所有的窑炉都与所有的堆场相连。砖块是用小型轮式卡车运到堆场的。我们所要做的就是在窑炉处将砖块装上卡车，将卡车推到堆场，然后在那里卸下它们。我们卡车的计件工资还算合理，工作本身并不困难；问题出在交叉口。卡车通常会在那里脱轨，砖块会从车上掉下来，简而言之，这造成了很多麻烦和时间损失，这对我们所有人来说都很宝贵。在这种情况下，我们都汗流浃背，咒骂着，我也是；但‘身不由己’，我想到，如果轨道的交叉次数被最小化，这种时间损失就可以最小化。但是交叉次数的最小值是多少呢？几天后我意识到，实际情况是可以改进的，但是对于 个窑炉和 个堆场的一般问题的确切解决方案似乎非常困难。我在第一次访问波兰时再次想到了这个问题，在那里我遇到了 Zarankiewicz。我向他提到了我的‘砖厂’问题，Zarankiewicz 认为他已经解决了它。但是 Gerhard Ringel 在他发表的证明中发现了一个漏洞，尽管付出了很大的努力，但至今没有人能够弥补这个漏洞。这个问题也已成为一个臭名昭著的未解决难题。”

该猜想已被证明对于所有 成立。Woodall (1993) 解决了 的情况，截至 2009 年 2 月，最小的未解决情况是 和 。下表给出了已知结果。

Richter 和 Širáň (1996) 计算了 完全二分图 的交叉数，如下所示

(2)

Kleitman (1970, 1976) 表明，, , , 和 的交叉数满足

(3)

给出具体方程

			(4)
			(5)
			(6)
			(7)

对于所有正数 。