主题
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. 贡献

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上引用

Witt 设计

请引用为

Pegg, Ed Jr. "Witt 设计。" 来自 MathWorld--Wolfram Web 资源,由 Eric W. Weisstein 创建。 https://mathworld.net.cn/WittDesign.html

学科分类