主題
Search

Witt 設計


給定一個從 23 個數字中選取 7 個數字的彩票,如果匹配至少 4 個數字即可獲得獎金,則存在一組 253 張彩票,保證中獎。這組彩票對應於 Witt 設計。

更正式地,23 個點上的 Witt 設計是一個 4-(23,7,1) 區組設計 (Witt 1938)。它是組合數學中最引人注目的結構之一 (Godsil and Royle 2001)。它可以透過將 x^(23)-1 在 GF(2) 上分解為 (x-1)g_2(x)(x^(11)g_2(x^(-1))) 來構造,其中

 g_2(x)=x^(11)+x^9+x^7+x^6+x^5+x+1.

然後計算 2048 個冪 g_2^0(x)g_2^1(x)g_2^2(x)、 ...、 g_2^(2047)(x),模 x^(23)-1。這組向量恰好是 [23,12,7] 格雷碼,具有 253 個權重為 7 的向量、1288 個權重為 11 的向量和 506 個權重為 15 的向量。例如,g_2(x)^1={0,1,5,6,7,9,11} 是一個權重為 7 的向量。

Witt 設計是作用於 23 個點的 253 個權重為 7 的向量的集合。

考慮頂點為 253 個向量 (v in V) 和 23 個點 (p in P)。設定邊,使得如果 p not in v,則 p&v 相鄰;如果 v_j&v_k 共享一個項,則它們相鄰。選擇一個任意頂點。對於該頂點的所有 176 個鄰居,將邊更改為非邊,將非邊更改為邊。消除現在孤立的頂點,剩下的 275 個頂點圖是 McLaughlin 圖,一個 距離正則圖

從 Witt 設計中,77 個向量包含 0(0 是從 0-22 中任意選擇的)。消除 0(0,1,5,6,7,9,11->1,5,6,7,9,11)得到大小為 77 的唯一 Steiner 系統 S(3,6,22),作用於點 1 到 22。考慮頂點為 77 個向量 (v in V),如果 v_j&v_k 不共享項則相鄰。這給出了一個 77 頂點圖,稱為 M22 圖

考慮頂點為 77 個向量 (v in V)、22 個點 (p in P) 和新符號 Omega。設定邊,使得 Omega 與所有 p 相鄰;如果 p in v,則 p&v 相鄰;如果 v_j&v_k 不共享項,則它們相鄰。得到的 100 頂點圖是 Higman-Sims 圖,一個 距離正則圖

從上面 77 個向量上的 V 中,令不包含任意選擇的點 22 的 56 個向量為頂點,並連線不相交的頂點。這構建了 Gewirtz 圖,一個具有相交陣列 {10,9;1,2} 的 56 個節點的 距離正則圖

大 Witt 設計是 格雷碼 的 759 個權重為 8 的向量,通常稱為八元組。大 Witt 圖 將大 Witt 設計的 759 個向量視為頂點,邊連線不相交的向量。這是一個具有相交陣列 {30,28,24;1,3,15}距離正則圖

截斷 Witt 圖 在 506 個點上構建,方法是刪除大 Witt 設計中包含任意選擇的符號的所有向量。這產生了一個具有相交陣列 {15,14,12;1,1,9}距離正則圖

雙重截斷 Witt 圖 在 330 個點上構建,方法是刪除大 Witt 設計中包含任意選擇的兩個符號的所有向量。這是一個具有相交陣列 {7,6,4,4;1,1,1,6}距離正則圖

類似的構造在 GF(2^2) 上分解 x^(23)-1,產生 Leech 格196560 個向量 (Conway and Sloane 1999)。


另請參閱

雙重截斷 Witt 圖, Gewirtz 圖, 格雷碼, Higman-Sims 圖, Ivanov-Ivanov-Faradjev 圖, 大 Witt 圖, Leech 格, M22 圖, 馬蒂厄群, McLaughlin 圖, 截斷 Witt 圖

此條目由 Ed Pegg, Jr. 貢獻

使用 探索

參考文獻

Brouwer, A. E. 和 Haemers, W. H. "Gewirtz 圖:圖譜理論中的一個練習。" Eur. J. Comb. 14, 397-407, 1993.Brouwer, A. E.; Cohen, A. M.; 和 Neumaier, A. "與 Witt 設計相關的圖。" §11.4 in 距離正則圖。 New York: Springer-Verlag, pp. 366-373, 1989.Cameron, P. J. 和 van Lint, J. H. 設計、圖、程式碼及其聯絡。 Cambridge: Cambridge University Press, 1996.Conway, J. H. 和 Sloane, N. J. A. 球體堆積、格和群,第 2 版。 New York: Springer-Verlag, 1993.Godsil, C. In 有趣的圖及其著色。 未出版的手稿。 2004.Godsil, C. 和 Royle, G. "23 個點上的 Witt 設計。" §10.11 in 代數圖論。 New York: Springer-Verlag, pp. 241-242, 2001.Havelicek, H. 和 Lenz, H. "Witt 小設計的存在的另一個簡單證明。" http://dmg.tuwien.ac.at/havlicek/anothersimple.pdf.Heumann, S. "格雷碼。" http://www.mdstud.chalmers.se/~md7sharo/coding/main/node34.html.van Lint, J. H. 編碼理論導論,第 2 版。 New York: Springer-Verlag, 1992.Witt, E. "馬蒂厄的 5 重傳遞群。" Abh. Math. Sem. Univ. Hamburg 12, 256-264, 1938.

在 上引用

Witt 設計

請引用為

Pegg, Ed Jr. "Witt 設計。" 來自 Web 資源,由 Eric W. Weisstein 建立。 https://mathworld.tw/WittDesign.html

學科分類