Page 258 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 258
COMBINATORIAL DESIGNS (MS-16)
Kirkman triple systems with many symmetries
Marco Buratti, buratti@dmi.unipg.it
Università di Perugia, Italy
Coauthors: Simona Bonvicini, Martino Garonzi, Gloria Rinaldi, Tommaso Traetta
A Steiner triple system of order v, STS(v) for short, is a set V with v points together with a
collection B of 3-subsets of V (blocks) such that that any pair of distinct points is contained in
exactly one block. A Kirkman triple system of order v, KTS(v) for short, is a STS(v) whose
blocks are partitioned in parallel classes each of which is a partition of the point-set V .
Steiner and Kirkman triple systems are among the most popular objects in combinatorics
and their existence has been established a long time ago. Yet, very little is known about the
automorphism groups of KTSs of an arbitrary order. In particular, from the very beginning
of my research in design theory, I found surprising that there was no known pair (r, n) for
which whenever v ≡ r (mod n) one may claim that there exists a KTS(v) with a number of
automorphisms at least close to v.
After pursuing the target of getting such a pair (r, n) for more than twenty years, we recently
managed to find the following: (39, 72) and (4e48 + 3, 4e96) for any e ≥ 0. Indeed, for v ≡ r
(mod n) with (r, n) as above, we are able to exhibit, concretely, a KTS(v) with an automorphism
group of order at least equal to v − 3. The proof is very long and elaborated; so I will try to
speak about the main ideas which led us to this result as for instance the invention of some
variants of well known combinatorial objects which could be also used in the search of other
combinatorial designs.
Mutually orthogonal cycle systems
Andrea C. Burgess, aburges2@unb.ca
University of New Brunswick, Canada
Coauthors: Nicholas Cavenagh, David A. Pike
An -cycle system of order n is a set of -cycles whose edges partition the edge set of Kn. We
say that two cycle systems, say C and C , are orthogonal if any cycle of C and any cycle of C
share at most one edge. Orthogonal cycle systems arise naturally from simple Heffter arrays
and biembeddings of cycle decompositions.
A collection of cycle systems is mutually orthogonal if any two of the systems are orthogo-
nal. In this talk, we give bounds on the number of mutually orthogonal -cycle systems of order
n, and provide constructions for sets of mutually orthogonal cyclic cycle systems.
Testing Arrays for Fault Localization
Charles Colbourn, Charles.Colbourn@asu.edu
Arizona State University, United States
A separating hash family SHFλ(N ; k, v, {w1, . . . , ws}) is an N × k array on v symbols, with
the property that no matter how we choose disjoint sets C1, . . . , Cs of columns with |Ci| = wi,
there are at least λ rows in which, for every 1 ≤ i < j ≤ s, no entry in a column of Ci equals
that in a column of Cj. (That is, there are λ rows in which sets {C1, . . . , Cs} are separated.)
256
Kirkman triple systems with many symmetries
Marco Buratti, buratti@dmi.unipg.it
Università di Perugia, Italy
Coauthors: Simona Bonvicini, Martino Garonzi, Gloria Rinaldi, Tommaso Traetta
A Steiner triple system of order v, STS(v) for short, is a set V with v points together with a
collection B of 3-subsets of V (blocks) such that that any pair of distinct points is contained in
exactly one block. A Kirkman triple system of order v, KTS(v) for short, is a STS(v) whose
blocks are partitioned in parallel classes each of which is a partition of the point-set V .
Steiner and Kirkman triple systems are among the most popular objects in combinatorics
and their existence has been established a long time ago. Yet, very little is known about the
automorphism groups of KTSs of an arbitrary order. In particular, from the very beginning
of my research in design theory, I found surprising that there was no known pair (r, n) for
which whenever v ≡ r (mod n) one may claim that there exists a KTS(v) with a number of
automorphisms at least close to v.
After pursuing the target of getting such a pair (r, n) for more than twenty years, we recently
managed to find the following: (39, 72) and (4e48 + 3, 4e96) for any e ≥ 0. Indeed, for v ≡ r
(mod n) with (r, n) as above, we are able to exhibit, concretely, a KTS(v) with an automorphism
group of order at least equal to v − 3. The proof is very long and elaborated; so I will try to
speak about the main ideas which led us to this result as for instance the invention of some
variants of well known combinatorial objects which could be also used in the search of other
combinatorial designs.
Mutually orthogonal cycle systems
Andrea C. Burgess, aburges2@unb.ca
University of New Brunswick, Canada
Coauthors: Nicholas Cavenagh, David A. Pike
An -cycle system of order n is a set of -cycles whose edges partition the edge set of Kn. We
say that two cycle systems, say C and C , are orthogonal if any cycle of C and any cycle of C
share at most one edge. Orthogonal cycle systems arise naturally from simple Heffter arrays
and biembeddings of cycle decompositions.
A collection of cycle systems is mutually orthogonal if any two of the systems are orthogo-
nal. In this talk, we give bounds on the number of mutually orthogonal -cycle systems of order
n, and provide constructions for sets of mutually orthogonal cyclic cycle systems.
Testing Arrays for Fault Localization
Charles Colbourn, Charles.Colbourn@asu.edu
Arizona State University, United States
A separating hash family SHFλ(N ; k, v, {w1, . . . , ws}) is an N × k array on v symbols, with
the property that no matter how we choose disjoint sets C1, . . . , Cs of columns with |Ci| = wi,
there are at least λ rows in which, for every 1 ≤ i < j ≤ s, no entry in a column of Ci equals
that in a column of Cj. (That is, there are λ rows in which sets {C1, . . . , Cs} are separated.)
256
