主題
Search

蓋伊猜想

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook

蓋伊猜想，尚未被證明或證偽，指出圖交叉數 對於 完全圖 K_n 是

Z(n)=1/4|_n/2_||_(n-1)/2_||_(n-2)/2_||_(n-3)/2_|,
(1)

其中 |_x_| 是向下取整函式，可以重寫為

Z(n)={1/(64)n(n-2)^2(n-4) for n even; 1/(64)(n-1)^2(n-3)^2 for n odd.
(2)

對於 n=1, 2, ... 的值由 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, 100, 150, 225, 315, 441, 588, ... (OEIS A000241) 給出。

Guy (1972) 證明了 n<=10 的猜想，Pan 和 Richter (2007) 將結果擴充套件到 n<=12。

已知

0.8594Z(n)<=nu(K_n)<=Z(n)
(3)

(Richter and Thomassen 1997, de Klerk et al. 2007, Pan and Richter 2007)。

另請參閱

完全二分圖, 完全圖, 圖交叉數, Zarankiewicz 猜想

使用 探索

參考文獻

Brodsky, A.; Durocher, S.; and Gethner, E. "K_(10) 的直線交叉數為 62。" 2000 年 9 月 22 日。 http://arxiv.org/abs/cs/0009023.de Klerk, E.; Pasechnik, D. V.; and Schrijver, A. "使用正則 *-表示 約簡對稱半定規劃。" Math Program. 109, 613-624, 2007.de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, R. B.; Salazar, G. "K_(m,n) 和 K_n 交叉數的改進界限。" 2004. https://arxiv.org/pdf/math/0404142.pdf.Guy, R. K. "完全圖的交叉數。" Bull. Malayan Math. Soc. 7, 68-72, 1960.Guy, R. K. "圖的交叉數。" In 圖論及其應用：1972 年 5 月 10-13 日在密歇根州卡拉馬祖西密歇根大學會議論文集 (Ed. Y. Alavi, D. R. Lick, and A. T. White). New York: Springer-Verlag, pp. 111-124, 1972.Harary, F. and Hill, A. "關於完全圖中交叉的數量。" Proc. Edinburgh Math. Soc. 13, 333-338, 1962/1963.Pan, S. and Richter, R. B. "K_(11) 的交叉數為 100。" J. Graph Th. 56, 128-134, 2007.Sloane, N. J. A. 序列 A000241/M2772 在 "整數序列線上百科全書" 中。

在 上被引用

蓋伊猜想

引用為

Weisstein, Eric W. "蓋伊猜想。" 來自 Web 資源。 https://mathworld.tw/GuysConjecture.html

主題分類