Combinatorial Designs

有限集合の部分集合族である性質を持つものを (combinatorial) design という。 正確には, \(n\) 元集合 \(X\) の \(q\) 元部分集合の成す集合 \(S\) で, 任意の \(X\) の \(r\) 元部分集合は, ちょうど \(\lambda \) 個の \(S\) の元に含まれるもの, という条件である。 このような \(S\) をパラメータ \((n,q,r,\lambda )\) の design という。

Malestein, Rivin, Theran [MRT14] は, Stinson の本 [Sti04] を参照している。

パラメータ \((n,q,r,1)\) の design には, Steiner system という名前が付いている。パラメータ \((n,q,r)\) の Steiner system という。

• Steiner system

パラメータ \((n,3,3)\) や \((n,4,3)\) の Steiner system は Steiner triple system や Steiner quadruple system と呼ばれるようである。

パラメータ \((5,8,24)\) の Steiner system が Mathieu 群 \(M_{24}\) の構成に使えることを発見したのは, Curtis [Cur76] であるが, 任意の有限群が Steiner triple system の authomorphism group として表せることは, Mendelsohn [Men78] により証明されている。その精密化が Doyen と Kantor [DK22] により考えられている。

Kalai の blog post によると, Steiner system や design の存在は, 組み合せ論の最も古く重要な問題の一つである。 その blog によると, 19世紀に Plücker や Kirkman や Steiner により, 提起されている。

Kalai の blog post では Keevash の結果 [Kee] が紹介されている。その論文は未だに preprint のようであるが, 正しい結果として認められているようである。 Steiner system や degin の存在問題の歴史については, Glock らの [Glo+23] の §1.1 を見るとよい。この monograph も desgin の存在に関するものである。

有限体上のベクトル空間の部分ベクトル空間を考えることにより, \(q\)-analogue を考えることもできる。Etzion の [Etz] など。

References

[Cur76]

R. T. Curtis. “A new combinatorial approach to \(M_{24}\)”. In: Math. Proc. Cambridge Philos. Soc. 79.1 (1976), pp. 25–42. url: https://doi.org/10.1017/S0305004100052075.

[DK22]

Jean Doyen and William M. Kantor. “Automorphism groups of Steiner triple systems”. In: Algebr. Comb. 5.4 (2022), pp. 593–608. arXiv: 1808.03615. url: https://doi.org/10.5802/alco.240.

[Etz]

Tuvi Etzion. Problems on q-Analogs in Coding Theory. arXiv: 1305. 6126.

[Glo+23]

Stefan Glock, Daniela Kühn, Allan Lo, and Deryk Osthus. “The existence of designs via iterative absorption: hypergraph \(F\)-designs for arbitrary \(F\)”. In: Mem. Amer. Math. Soc. 284.1406 (2023), pp. v+131. arXiv: 1611.06827. url: https://doi.org/10.1090/memo/1406.

[Kee]

Peter Keevash. The existence of designs. arXiv: 1401.3665.

[Men78]

Eric Mendelsohn. “On the groups of automorphisms of Steiner triple and quadruple systems”. In: J. Combin. Theory Ser. A 25.2 (1978), pp. 97–104. url: https://doi.org/10.1016/0097-3165(78)90072-9.

[MRT14]

Justin Malestein, Igor Rivin, and Louis Theran. “Topological designs”. In: Geom. Dedicata 168 (2014), pp. 221–233. arXiv: 1008. 3710. url: http://dx.doi.org/10.1007/s10711-012-9827-9.

[Sti04]

Douglas R. Stinson. Combinatorial designs. Constructions and analysis, With a foreword by Charles J. Colbourn. New York: Springer-Verlag, 2004, pp. xvi+300. isbn: 0-387-95487-2.