Page 335 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 335
SYMMETRY OF GRAPHS, MAPS AND POLYTOPES (MS-9)
Intersection densities of transitive permutation groups
Dragan Marušicˇ, dragan.marusic@upr.si
University of Primorska, Slovenia
Two elements g and h of a permutation group G acting on a set V are said to be intersecting if
g(v) = h(v) for some v ∈ V . More generally, a subset F of G is an intersecting set if every
pair of elements of F is intersecting. The intersection density ρ(G) of a transitive permutation
group G is the maximum value of the quotient |F|/|Gv| where F runs over all intersecting sets
in G and Gv is a stabilizer of v ∈ V .
In this talk intersection densities of transitive permutation groups of certain degrees are de-
termined, thus settling some of the problems and conjectures raised in [K. Meagher, A. S. Raza-
fimahatratra and P. Spiga, On triangles in derangement graphs, J. Combin. Theory, Ser. A 180
(2021), 105390.] and [A. S. Razafimahatratra, On multipartite derangement graphs, Ars Math.
Contemp. (2021), doi: 10.26493/1855-3974.2554.856.].
On automorphisms of direct products of abelian Cayley graphs
Dave Witte Morris, Dave.Morris@uleth.ca
University of Lethbridge, Canada
The direct product of two graphs X and Y is denoted X × Y . (It is also known as the “ten-
sor product” or “categorical product” or “Kronecker product” or “conjunction” of X and Y .)
This is a natural construction, so any isomorphism from X to X can be combined with any
isomorphism from Y to Y to obtain an isomorphism from X × Y to X × Y . Therefore, the
automorphism group Aut(X × Y ) contains a copy of (Aut X) × (Aut Y ). It is not known when
this inclusion is an equality, even for the special case where Y = K2 is the complete graph with
only 2 vertices. (The direct product X × K2 is also known as the “canonical bipartite double
cover” of X. The graph X is said to be “stable” if equality holds in this special case.)
When X is a circulant graph with an odd number of vertices (and Y = K2), recent work of
B. Fernandez and A. Hujdurovic´ shows that equality holds if and only if X is connected and no
two vertices of X have exactly the same neighbours. We will present a short, elementary proof
that generalizes this theorem to the case where X is a Cayley graph on an abelian group of odd
order.
Base sizes for the symmetric and alternating groups
Joy Morris, joy.morris@uleth.ca
University of Lethbridge, Canada
Coauthor: Pablo Spiga
A base of a permutation group is a set of the elements on which it is acting, that is only fixed
by the identity element of that permutation group. The base size of a permutation group is the
minimum possible size for a base.
These concepts have been rediscovered and studied in the context of automorphism groups
of combinatorial objects: if a permutation group is the automorphism group of an object, then
a distinguishing set is a collection of "points" of the object that are only fixed by the identity
333
Intersection densities of transitive permutation groups
Dragan Marušicˇ, dragan.marusic@upr.si
University of Primorska, Slovenia
Two elements g and h of a permutation group G acting on a set V are said to be intersecting if
g(v) = h(v) for some v ∈ V . More generally, a subset F of G is an intersecting set if every
pair of elements of F is intersecting. The intersection density ρ(G) of a transitive permutation
group G is the maximum value of the quotient |F|/|Gv| where F runs over all intersecting sets
in G and Gv is a stabilizer of v ∈ V .
In this talk intersection densities of transitive permutation groups of certain degrees are de-
termined, thus settling some of the problems and conjectures raised in [K. Meagher, A. S. Raza-
fimahatratra and P. Spiga, On triangles in derangement graphs, J. Combin. Theory, Ser. A 180
(2021), 105390.] and [A. S. Razafimahatratra, On multipartite derangement graphs, Ars Math.
Contemp. (2021), doi: 10.26493/1855-3974.2554.856.].
On automorphisms of direct products of abelian Cayley graphs
Dave Witte Morris, Dave.Morris@uleth.ca
University of Lethbridge, Canada
The direct product of two graphs X and Y is denoted X × Y . (It is also known as the “ten-
sor product” or “categorical product” or “Kronecker product” or “conjunction” of X and Y .)
This is a natural construction, so any isomorphism from X to X can be combined with any
isomorphism from Y to Y to obtain an isomorphism from X × Y to X × Y . Therefore, the
automorphism group Aut(X × Y ) contains a copy of (Aut X) × (Aut Y ). It is not known when
this inclusion is an equality, even for the special case where Y = K2 is the complete graph with
only 2 vertices. (The direct product X × K2 is also known as the “canonical bipartite double
cover” of X. The graph X is said to be “stable” if equality holds in this special case.)
When X is a circulant graph with an odd number of vertices (and Y = K2), recent work of
B. Fernandez and A. Hujdurovic´ shows that equality holds if and only if X is connected and no
two vertices of X have exactly the same neighbours. We will present a short, elementary proof
that generalizes this theorem to the case where X is a Cayley graph on an abelian group of odd
order.
Base sizes for the symmetric and alternating groups
Joy Morris, joy.morris@uleth.ca
University of Lethbridge, Canada
Coauthor: Pablo Spiga
A base of a permutation group is a set of the elements on which it is acting, that is only fixed
by the identity element of that permutation group. The base size of a permutation group is the
minimum possible size for a base.
These concepts have been rediscovered and studied in the context of automorphism groups
of combinatorial objects: if a permutation group is the automorphism group of an object, then
a distinguishing set is a collection of "points" of the object that are only fixed by the identity
333
