Page 301 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 301
GRAPHS AND GROUPS, GEOMETRIES AND GAP - G2G2 (MS-7)
On coverings and perfect colorings of hypergraphs
Anna Taranenko, taa@math.nsc.ru
Sobolev Institute of Mathematics, Russian Federation
In this talk, we consider perfect colorings (also known as equitable partitions) of hypergraphs.
A perfect k-coloring of a hypergraph is a coloring of its vertices into k colors such that colors
of hyperedges incident to a vertex is defined by its color. A transversal of a hypergraph is one of
the simplest examples of perfect 2-colorings. While perfect colorings of graphs are well known
and extensively applied, similar objects for hypergraphs are hardly studied. The main aim of the
talk is to show that perfect colorings of hypergraphs have most of the nice algebraic properties
of colorings of graphs.
Firstly, we define the multidimensional parameter matrix of a perfect coloring of a hyper-
graph, study its eigenvalues, and connect them with the parameters of the corresponding perfect
coloring of the bipartite representation. Next, we introduce coverings of hypergraphs and show
that for a vast class of hypergraphs there exist coverings that can be partitioned into perfect
matchings. At last, we establish that if two hypergraphs have the same minimal perfect coloring
then there is a hypergraph covering both of them.
Vertex-transitive distance-regular antipodal covers of complete graphs
Ludmila Tsiovkina, l.tsiovkina@gmail.com
IMM UB RAS, Russian Federation
Distance-regular antipodal covers of complete graphs are closely related to various important
algebraic, geometric, or combinatorial objects, such as generalized Hadamard matrices, projec-
tive planes, generalized quadrangles, divisible designs, and codes. A recent surge of interest
for their study is motivated by their applications in discrete geometry and quantum information
theory, since those covers that are abelian turn out to be a potential source of new sets of equian-
gular lines (ETFs, SIC-POVMs). The general problem of classification of all distance-regular
antipodal covers of complete graphs seems to be unsolvable. Nevertheless, a promising task in
this direction is to describe vertex-transitive representatives, since they admit group-theoretic
characterisations. To date, the following vertex-transitive distance-regular antipodal covers of
complete graphs have been classified: (i) covers with distance-transitive automorphism groups
(complete description); (ii) covers with arc-transitive automorphism groups (almost complete
description). Much less is known in general case.
The aim of this talk is to present a classification of edge-transitive distance-regular antipo-
dal covers of complete graphs. The automorphism group of such a cover is transitive, and by
a combination of results of Kantor and Burnside, it induces either a 2-transitive almost simple
group, or an affine 2-homogeneous group on the set of fibres. Using the classification of fi-
nite 2-transitive permutation groups, we will prove that every such cover with µ > 1 is either
arc-transitive, or a Cayley graph whose automorphism group induces a one-dimensional affine
permutation group on the set of its fibres. Then we will present a general construction of cov-
ers with antipodality index greater than 2 in the almost simple case in terms of graphs of basis
relations of some association schemes related to quasi-simple groups.
We will also discuss some recent results on classification of abelian distance-regular antipo-
dal covers of a complete graph which possess a transitive group of automorphisms that induces
an almost simple primitive rank 3 permutation group on the set of fibres of the corresponding
299
On coverings and perfect colorings of hypergraphs
Anna Taranenko, taa@math.nsc.ru
Sobolev Institute of Mathematics, Russian Federation
In this talk, we consider perfect colorings (also known as equitable partitions) of hypergraphs.
A perfect k-coloring of a hypergraph is a coloring of its vertices into k colors such that colors
of hyperedges incident to a vertex is defined by its color. A transversal of a hypergraph is one of
the simplest examples of perfect 2-colorings. While perfect colorings of graphs are well known
and extensively applied, similar objects for hypergraphs are hardly studied. The main aim of the
talk is to show that perfect colorings of hypergraphs have most of the nice algebraic properties
of colorings of graphs.
Firstly, we define the multidimensional parameter matrix of a perfect coloring of a hyper-
graph, study its eigenvalues, and connect them with the parameters of the corresponding perfect
coloring of the bipartite representation. Next, we introduce coverings of hypergraphs and show
that for a vast class of hypergraphs there exist coverings that can be partitioned into perfect
matchings. At last, we establish that if two hypergraphs have the same minimal perfect coloring
then there is a hypergraph covering both of them.
Vertex-transitive distance-regular antipodal covers of complete graphs
Ludmila Tsiovkina, l.tsiovkina@gmail.com
IMM UB RAS, Russian Federation
Distance-regular antipodal covers of complete graphs are closely related to various important
algebraic, geometric, or combinatorial objects, such as generalized Hadamard matrices, projec-
tive planes, generalized quadrangles, divisible designs, and codes. A recent surge of interest
for their study is motivated by their applications in discrete geometry and quantum information
theory, since those covers that are abelian turn out to be a potential source of new sets of equian-
gular lines (ETFs, SIC-POVMs). The general problem of classification of all distance-regular
antipodal covers of complete graphs seems to be unsolvable. Nevertheless, a promising task in
this direction is to describe vertex-transitive representatives, since they admit group-theoretic
characterisations. To date, the following vertex-transitive distance-regular antipodal covers of
complete graphs have been classified: (i) covers with distance-transitive automorphism groups
(complete description); (ii) covers with arc-transitive automorphism groups (almost complete
description). Much less is known in general case.
The aim of this talk is to present a classification of edge-transitive distance-regular antipo-
dal covers of complete graphs. The automorphism group of such a cover is transitive, and by
a combination of results of Kantor and Burnside, it induces either a 2-transitive almost simple
group, or an affine 2-homogeneous group on the set of fibres. Using the classification of fi-
nite 2-transitive permutation groups, we will prove that every such cover with µ > 1 is either
arc-transitive, or a Cayley graph whose automorphism group induces a one-dimensional affine
permutation group on the set of its fibres. Then we will present a general construction of cov-
ers with antipodality index greater than 2 in the almost simple case in terms of graphs of basis
relations of some association schemes related to quasi-simple groups.
We will also discuss some recent results on classification of abelian distance-regular antipo-
dal covers of a complete graph which possess a transitive group of automorphisms that induces
an almost simple primitive rank 3 permutation group on the set of fibres of the corresponding
299
