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(X) 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.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.106
Classification: 05B05,  05B07,  05B35,  05E45,  14F35,  20M10
Keywords: Matroid, boolean representable simplicial complex, truncation, pairwise balanced design, Wilson monoid.
Margolis, Stuart 1; Rhodes, John 2; Silva, Pedro V. 3

1 Department of Mathematics Bar Ilan University 52900 Ramat Gan, Israel
2 Department of Mathematics University of California Berkeley California 94720, U.S.A.
3 Centro de Matemática Faculdade de Ciências Universidade do Porto R. Campo Alegre 687 4169-007 Porto, Portugal
@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},
     pages = {637--665},
     publisher = {MathOA foundation},
     volume = {3},
     number = {3},
     year = {2020},
     doi = {10.5802/alco.106},
     mrnumber = {4113601},
     zbl = {1441.05030},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.106/}
}
TY  - JOUR
TI  - On the Wilson monoid of a pairwise balanced design
JO  - Algebraic Combinatorics
PY  - 2020
DA  - 2020///
SP  - 637
EP  - 665
VL  - 3
IS  - 3
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.106/
UR  - https://www.ams.org/mathscinet-getitem?mr=4113601
UR  - https://zbmath.org/?q=an%3A1441.05030
UR  - https://doi.org/10.5802/alco.106
DO  - 10.5802/alco.106
LA  - en
ID  - ALCO_2020__3_3_637_0
ER  - 
%0 Journal Article
%T On the Wilson monoid of a pairwise balanced design
%J Algebraic Combinatorics
%D 2020
%P 637-665
%V 3
%N 3
%I MathOA foundation
%U https://doi.org/10.5802/alco.106
%R 10.5802/alco.106
%G en
%F 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/articles/10.5802/alco.106/

[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, 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 no. 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

Cited by Sources: