# ALGEBRAIC COMBINATORICS

On the Wilson monoid of a pairwise balanced design
Algebraic Combinatorics, Volume 3 (2020) no. 3, pp. 637-665.

We give a new perspective of the relationship between simple matroids of rank 3 and pairwise balanced designs, connecting Wilson’s theorems and tools with the theory of truncated boolean representable simplicial complexes. We also introduce the concept of Wilson monoid $W\left(X\right)$ of a pairwise balanced design $X$. We present some general algebraic properties and study in detail the cases of Steiner triple systems up to 19 points, as well as the case where a single block has more than 2 elements.

Revised: 2019-12-24
Accepted: 2019-12-24
Published online: 2020-06-02
DOI: https://doi.org/10.5802/alco.106
Classification: 05B05,  05B07,  05B35,  05E45,  14F35,  20M10
Keywords: Matroid, boolean representable simplicial complex, truncation, pairwise balanced design, Wilson monoid.
@article{ALCO_2020__3_3_637_0,
author = {Margolis, Stuart and Rhodes, John and Silva, Pedro V.},
title = {On the Wilson monoid of a pairwise balanced design},
journal = {Algebraic Combinatorics},
publisher = {MathOA foundation},
volume = {3},
number = {3},
year = {2020},
pages = {637-665},
doi = {10.5802/alco.106},
language = {en},
url = {alco.centre-mersenne.org/item/ALCO_2020__3_3_637_0/}
}
Margolis, Stuart; Rhodes, John; Silva, Pedro V. On the Wilson monoid of a pairwise balanced design. Algebraic Combinatorics, Volume 3 (2020) no. 3, pp. 637-665. doi : 10.5802/alco.106. https://alco.centre-mersenne.org/item/ALCO_2020__3_3_637_0/

[1] Artin, Emil Geometric Algebra, Wiley, New York, 2011

[2] Babai, László Almost all Steiner triple systems are asymmetric, Ann. Discrete Math., Volume 7 (1980), pp. 37-39 (Topics on Steiner systems) | Article | MR 584402 | Zbl 0462.05013

[3] Batten, Line M.; Beutelspacher, Albrecht The Theory of Finite Linear Spaces: Combinatorics of Points and Lines, Cambridge University Press, Cambridge, England, 1993 | Zbl 0806.51001

[4] Chang, Yanxun A bound for Wilson’s theorem. (I), J. Combin. Des., Volume 3 (1995) no. 1, pp. 25-39 | Article | MR 1305445 | Zbl 0821.05001

[5] Chang, Yanxun A bound for Wilson’s theorem. (II), J. Combin. Des., Volume 4 (1996) no. 1, pp. 11-26 | Article | MR 1364096 | Zbl 0913.05016

[6] Chang, Yanxun A bound for Wilson’s theorem. (III), J. Combin. Des., Volume 4 (1996) no. 2, pp. 83-93 | Article | MR 1373516 | Zbl 0913.05017

[7] Clifford, Alfred H.; Preston, Gordon B. The Algebraic Theory of Semigroups. Vol. I, Mathematical Surveys, American Mathematical Society, Providence, R.I., 1961 no. 7, xv+224 pages | MR 0132791 | Zbl 0111.03403

[8] Colbourn, Charles J.; Dinitz, Jeffrey H. Handbook of combinatorial designs, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2007, xxii+984 pages | Zbl 1101.05001

[9] Colbourn, Charles J.; Rosa, Alexander Triple Systems, Clarendon Press, Oxford England, 1999 | Zbl 0938.05009

[10] Crapo, Henry H. Erecting geometries, Ann. New York Acad. Sci., Volume 175 (1970), pp. 89-92 | Article | MR 277407 | Zbl 0268.05015

[11] Crapo, Henry H.; Rota, Gian-Carlo On the foundations of combinatorial theory: Combinatorial geometries, The M.I.T. Press, Cambridge, Mass.-London, 1970, iv+289 pages | MR 0290980 | Zbl 0231.05024

[12] Dinitz, Jeffrey H.; Margolis, Stuart Continuous maps in finite projective space, Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982), Volume 35 (1982), pp. 239-244 | MR 725884 | Zbl 0515.05016

[13] Dinitz, Jeffrey H.; Margolis, Stuart Continuous maps on block designs, Ars Combin., Volume 14 (1982), pp. 21-45 | MR 683974 | Zbl 0503.05006

[14] Doyen, Jean Sur la structure de certains systèmes triples de Steiner, Math. Z., Volume 111 (1969), pp. 289-300 | Article | MR 246784 | Zbl 0182.02702

[15] Hall, Marshall Projective planes, Trans. Amer. Math. Soc., Volume 54 (1943), pp. 229-277 | Article | MR 8892 | Zbl 0060.32209

[16] Kaski, Petteri; Östergård, Patric R. J. The Steiner triple systems of order 19, Math. Comp., Volume 73 (2004) no. 248, pp. 2075-2092 | Article | MR 2059752 | Zbl 1043.05020

[17] Kaski, Petteri; Östergård, Patric R. J.; Popa, Alexandru Enumeration of Steiner triple systems with subsystems, Math. Comp., Volume 84 (2015) no. 296, pp. 3051-3067 | Article | MR 3378862 | Zbl 1319.05023

[18] Kaski, Petteri; Östergård, Patric R. J.; Topalova, Svetlana; Zlatarski, Rosen Steiner triple systems of order 19 and 21 with subsystems of order 7, Discrete Math., Volume 308 (2008) no. 13, pp. 2732-2741 | Article | MR 2413971 | Zbl 1142.05005

[19] Keevash, Peter The existence of designs (2019) (https://arxiv.org/abs/1401.3665)

[20] Knuth, Donald E. Random matroids, Discrete Math., Volume 12 (1975) no. 4, pp. 341-358 | Article | MR 406837 | Zbl 0314.05012

[21] Krohn, Kenneth; Rhodes, John; Tilson, Bret R. Algebraic Theory of Machines, Languages, and Semigroups, Edited by Michael A. Arbib. With a major contribution by Kenneth Krohn and John L. Rhodes, Academic Press, New York, 1968, xvi+359 pages (Chapters 1, 5–9) | MR 0232875

[22] Mac Lane, Saunders Categories for the working mathematician, Graduate Texts in Mathematics, Volume 5, Springer-Verlag, New York, 1998, xii+314 pages | MR 1712872 | Zbl 0906.18001

[23] Margolis, Stuart; Dinitz, Jeffrey H. Translational hulls and block designs, Semigroup Forum, Volume 27 (1983) no. 1-4, pp. 247-263 | Article | MR 714676 | Zbl 0521.20049

[24] Margolis, Stuart; Rhodes, John; Silva, Pedro V. Truncated boolean representable simplicial complexes (2019) (https://arxiv.org/abs/1904.03843) | Zbl 1358.05316

[25] Nguyen, Hien Q. Constructing the free erection of a geometry, J. Combin. Theory Ser. B, Volume 27 (1979) no. 2, pp. 216-224 | Article | MR 546864 | Zbl 0426.05022

[26] Oxley, James G. Matroid theory, Oxford Science Publications, Oxford University Press, Oxford, England, 1992, xii+532 pages | Zbl 0784.05002

[27] Pendavingh, Rudi; van der Pol, Jorn Enumerating matroids of fixed rank, Electron. J. Combin., Volume 24 (2017) no. 1, Paper 1.8, 28 pages | MR 3609178 | Zbl 1355.05033

[28] Rhodes, John Some results on finite semigroups, J. Algebra, Volume 4 (1966), pp. 471-504 | Article | MR 201546 | Zbl 0163.02103

[29] Rhodes, John; Silva, Pedro V. Boolean representations of simplicial complexes and matroids, Springer Monographs in Mathematics, Springer, Cham, 2015, x+173 pages | Article | Zbl 1343.05003

[30] Rhodes, John; Steinberg, Benjamin The $q$-theory of finite semigroups, Springer Monographs in Mathematics, Springer, New York, 2009, xxii+666 pages | Article | Zbl 1186.20043

[31] Steinberg, Benjamin The Representation Theory of Finite Monoids, Springer, 2016 | Article | Zbl 1428.20003

[32] Stinson, Douglas R. Combinatorial Designs: Constructions and Analysis, Springer-Verlag, New York, 2004 | Zbl 1031.05001

[33] Tilson, Bret R. Complexity of Semigroups and Morphisms, Automata, Languages and Machines, Vol. B (Pure and Applied Mathematics) Volume 59, Academic Press, New York, 1976, pp. 313-384 | Article

[34] Tilson, Bret R. Depth Decomposition Theorem, Automata, Languages and Machines, Vol. B (Pure and Applied Mathematics) Volume 59, Academic Press, New York, 1976, pp. 287-312 | Article

[35] Wilson, Richard M. An existence theory for pairwise balanced designs. I. Composition theorems and morphisms, J. Combinatorial Theory Ser. A, Volume 13 (1972), pp. 220-245 | Article | MR 304203 | Zbl 0263.05014

[36] Wilson, Richard M. An existence theory for pairwise balanced designs. II. The structure of PBD-closed sets and the existence conjectures, J. Combinatorial Theory Ser. A, Volume 13 (1972), pp. 246-273 | Article | MR 304204 | Zbl 0263.05015

[37] Wilson, Richard M. Nonisomorphic Steiner triple systems, Math. Z., Volume 135 (1973/74), pp. 303-313 | Article | MR 340046 | Zbl 0264.05009

[38] Wilson, Richard M. An existence theory for pairwise balanced designs. III. Proof of the existence conjectures, J. Combinatorial Theory Ser. A, Volume 18 (1975), pp. 71-79 | Article | MR 366695 | Zbl 0295.05002

[39] Zeiger, Paul Yet another proof of the cascade decomposition theorem for finite automata, Math. Systems Theory, Volume 1 (1967) no. 3, pp. 225-228 | Article | MR 1555477 | Zbl 0164.32302