Page 336 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 336
SYMMETRY OF GRAPHS, MAPS AND POLYTOPES (MS-9)
automorphism. The distinguishing number is the smallest size of such a set.
I will present new results about the base sizes for two non-standard actions of the symmetric
group Sym(n): its action on partitions, and its action on subsets of a fixed cardinality. For the
first of these, I will also present results about the corresponding base sizes for the alternating
group.
A family of non-Cayley cores that are constructed from vertex-transitive
or strongly regular self-complementary graphs
Marko Orel, marko.orel@upr.si
University of Primorska, Slovenia, and IMFM, Slovenia
Let Γ be a finite simple graph on n vertices. In the talk I will consider the graph Γ ≡ Γ¯ on 2n
vertices, which is obtained as the disjoint union of Γ and its complement Γ¯, where we add a
perfect matching such that each its edge joins two copies of the same vertex in Γ and Γ¯. The
graph Γ ≡ Γ¯ generalizes the Petersen graph, which is obtained if Γ is the pentagon. It is a
non-Cayley graph if n > 1, and is vertex-transitive if and only if Γ is vertex-transitive and
self-complementary. In this case Γ ≡ Γ¯ is Hamiltonian-connected whenever n > 5. It is shown
that the fraction between the cardinalities of the automorphism groups of Γ ≡ Γ¯ and Γ can
attain only values 1, 2, 4, or 12, and the corresponding four classes of graphs are described. The
spectrum of the adjacency matrix of Γ ≡ Γ¯ is computed whenever Γ is regular. The main results
involve the endomorphisms of Γ ≡ Γ¯. It is shown that the graph Γ ≡ Γ¯ is a core, i.e. all its
endomorphisms are automorphisms, whenever Γ is strongly regular and self-complementary.
The same type of a result is obtained for many cases, where Γ is vertex-transitive and self-
complementary.
Having fun with designs
Cheryl Praeger, cheryl.praeger@uwa.edu.au
University of Western Australia, Australia
The kind of design we explore is a finite 2-design: a point-block incidence structure where each
block is a k-subset of points, and each pair of points lies in a constant number λ of blocks. We
ask that the design admits a block-transitive group G of automorphisms which preserves also
a nontrivial partition of the point set. One famous study of these designs, by Delandtsheer and
Doyen in 1989 introduced two parameters, now called Delandtsheer–Doyen parameters, that
linked the design structure with the point-partition. Another even earlier study, by Davies in
1987, showed that, if G is transitive on flags (incident point-block pairs) then the number of
points is bounded above by some function of λ (but no function was specified).
Recently, with Alice Devillers, we have been exploring these two results.
For flag-transitive designs: we showed that 4λ6 could be taken for the Davies function –
though this is not a tight upper bound. Moreover, while investigating possible examples with
small parameters, we found a rather beautiful flag-transitive design where the point set is a 6 × 6
grid, the block size is 8, λ = 4, and the full automorphism group is the symmetric group S6.
Then, with Carmen Amarra and Alice Devillers, while exploring bounds and several ex-
treme cases of the Delandtsheer–Doyen parameters, we constructed a (probably infinite) new
334
automorphism. The distinguishing number is the smallest size of such a set.
I will present new results about the base sizes for two non-standard actions of the symmetric
group Sym(n): its action on partitions, and its action on subsets of a fixed cardinality. For the
first of these, I will also present results about the corresponding base sizes for the alternating
group.
A family of non-Cayley cores that are constructed from vertex-transitive
or strongly regular self-complementary graphs
Marko Orel, marko.orel@upr.si
University of Primorska, Slovenia, and IMFM, Slovenia
Let Γ be a finite simple graph on n vertices. In the talk I will consider the graph Γ ≡ Γ¯ on 2n
vertices, which is obtained as the disjoint union of Γ and its complement Γ¯, where we add a
perfect matching such that each its edge joins two copies of the same vertex in Γ and Γ¯. The
graph Γ ≡ Γ¯ generalizes the Petersen graph, which is obtained if Γ is the pentagon. It is a
non-Cayley graph if n > 1, and is vertex-transitive if and only if Γ is vertex-transitive and
self-complementary. In this case Γ ≡ Γ¯ is Hamiltonian-connected whenever n > 5. It is shown
that the fraction between the cardinalities of the automorphism groups of Γ ≡ Γ¯ and Γ can
attain only values 1, 2, 4, or 12, and the corresponding four classes of graphs are described. The
spectrum of the adjacency matrix of Γ ≡ Γ¯ is computed whenever Γ is regular. The main results
involve the endomorphisms of Γ ≡ Γ¯. It is shown that the graph Γ ≡ Γ¯ is a core, i.e. all its
endomorphisms are automorphisms, whenever Γ is strongly regular and self-complementary.
The same type of a result is obtained for many cases, where Γ is vertex-transitive and self-
complementary.
Having fun with designs
Cheryl Praeger, cheryl.praeger@uwa.edu.au
University of Western Australia, Australia
The kind of design we explore is a finite 2-design: a point-block incidence structure where each
block is a k-subset of points, and each pair of points lies in a constant number λ of blocks. We
ask that the design admits a block-transitive group G of automorphisms which preserves also
a nontrivial partition of the point set. One famous study of these designs, by Delandtsheer and
Doyen in 1989 introduced two parameters, now called Delandtsheer–Doyen parameters, that
linked the design structure with the point-partition. Another even earlier study, by Davies in
1987, showed that, if G is transitive on flags (incident point-block pairs) then the number of
points is bounded above by some function of λ (but no function was specified).
Recently, with Alice Devillers, we have been exploring these two results.
For flag-transitive designs: we showed that 4λ6 could be taken for the Davies function –
though this is not a tight upper bound. Moreover, while investigating possible examples with
small parameters, we found a rather beautiful flag-transitive design where the point set is a 6 × 6
grid, the block size is 8, λ = 4, and the full automorphism group is the symmetric group S6.
Then, with Carmen Amarra and Alice Devillers, while exploring bounds and several ex-
treme cases of the Delandtsheer–Doyen parameters, we constructed a (probably infinite) new
334
