ALGEBRAIC COMBINATORICS

no. 3
On the Wilson monoid of a pairwise balanced design
Margolis, Stuart1; Rhodes, John2; 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
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
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@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
AU  - Margolis, Stuart
AU  - Rhodes, John
AU  - Silva, Pedro V.
TI  - On the Wilson monoid of a pairwise balanced design
JO  - Algebraic Combinatorics
PY  - 2020
SP  - 637
EP  - 665
VL  - 3
IS  - 3
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.106/
DO  - 10.5802/alco.106
LA  - en
ID  - ALCO_2020__3_3_637_0
ER  - 
%0 Journal Article
%A Margolis, Stuart
%A Rhodes, John
%A Silva, Pedro V.
%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://alco.centre-mersenne.org/articles/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 | Zbl

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

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

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

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

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

[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 | Zbl

[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

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

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

[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 | Zbl

[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 | Zbl

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

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

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

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

[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

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

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

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

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

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

[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 | Zbl

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

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

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

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

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

[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 | DOI | MR

[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 | DOI | MR

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

Cited by Sources: