扎蘭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)

對於所有正數 。