Tuesday, 6 pm

Novosibirsk, Time zone UTC+7

Novosibirsk, Time zone UTC+7

Lectorium on Algebraic

Graph Theory

Graph Theory

Mathematical Center in Akademgorodok,

Novosibirsk, Russia

Novosibirsk, Russia

Lectorium on Algebraic Graph Theory is an International Educational Program of the Mathematical Center in Akademgorodok. The main goal of the program is to educate students and young researchers in the main aspects, directions and problems of algebraic graph theory. In the frame of the program famous young researchers and professors over the world give lectures on a wide range of topics in algebraic graph theory and its application.

The current lectures are held in cooperation with the Sino-Russian Mathematics Center at Peking University (Beijing) and The Three Gorges Mathematical Research Center at China Three Gorges University (Yichang).

The current lectures are held in cooperation with the Sino-Russian Mathematics Center at Peking University (Beijing) and The Three Gorges Mathematical Research Center at China Three Gorges University (Yichang).

Minicourse:

EKR-type results for graphs defined on finite fields and related problems

by Sergey Goryainov

EKR-type results for graphs defined on finite fields and related problems

by Sergey Goryainov

Sergey Goryainov obtained his PhD in 2015 at the Krasovskii Institute of Mathematics and Mechanics in Yekaterinburg, Russia. From 2017 to 2020 he had a position of a postdoctoral researcher at Shanghai Jiao Tong University, China. Since 2021 he is affiliated with Hebei Normal University, China, as Associate Professor. His research interests include discrete mathematics, algebraic combinatorics, strongly regular graphs and their generalizations, Cayley graphs, finite fields.

April 11, 2023

Let q be an odd prime power. In [2], van Lint and MacWilliams conjectured that the only q-subset X if GF(q^2), with the properties 0,1 belong X and x-y is a square for all x,y from X, is the set GF(q). For q a prime this is a consequence (due to van Lint and MacWilliams) of a theorem of Rédei, [4, p. 237 Satz 24']. This case was also proved in an elementary way by Lovász and Schrijver [3]. The problem arose in an attempt to characterise the vectors of minimum weight in certain quadratic residue-codes. In [1], Blokhuis confirmed the conjecture.

In this lecture, we discuss the Blokhuis' proof in detail.

Slides & Video

April 25, 2023

Given any graph X for which we can describe its canonical cliques (that is, typically cliques with large size and simple structure), we can ask whether X has any of the following three related Erdős-Ko-Rado (EKR) properties (see [5] for more details):

• EKR property: the clique number of X equals the size of canonical cliques.

• EKR-module property: the characteristic vector of each maximum clique in X is a Q-linear combination of characteristic vectors of canonical cliques in X.

• strict-EKR property: each maximum clique in X is a canonical clique.

In particular, the Blokhuis' result discussed in Lecture 1 can be viewed as establishing the strict-EKR property of Paley graphs of square order [6].

In this lecture, we overview results on the EKR properties (the three properties described above) of graphs and discuss some further directions.

Slides & Video

May 23, 2023

Possible analogues of the Hilton-Milner theorem for Paley graphs of square order and Peisert graphs

In [7], a family of maximal but not maximum cliques in Paley graphs of square order was constructed. Moreover, it was conjectured that these cliques are second largest. In [9] a different family of maximal cliques with the proposed size we was constructed (the construction is based on an oval). However, recently it was shown in [10] that these two constructions are equivalent up to fractional transformation. Numerical experiments showed that when 25 ≤ q ≤ 83, these two families give rise to all maximal cliques with the proposed size (there are some extra cliques of the proposed size when 9 ≤ q ≤ 23). Thus, we propose the following stronger conjecture: if q ≥ 25, then each second largest maximal clique in the Paley graph P(q^2) is equivalent to a clique from the constructions proposed in [7] and [9].

In [8], it was noted that the fractional transformation from [10] can be described as a certain automorphism of the local subgraph of P(q^2).

In [11], it was noted that our conjecture is an analogue of the Hilton-Milner theorem.

In this lecture we discuss the details of this conjecture. We also discuss a similar conjecture for a special subclass of Peisert graphs.

Slides & Video

June 6, 2023

In [12], a family of so-called Peisert-type graphs is discussed. These graphs generalise Paley graphs of square order and the subclass of Peisert graphs discussed in Lecture 3, can also be viewed as fusions of certain amorphic cyclotomic association schemes and are important from the point of view of EKR properties since canonical cliques in these graphs can be naturally defined. In [13], it was recently shown that the EKR theorem for Paley graphs of square order extends to almost all pseudo-Paley graphs of Peisert-type.

In this final lecture we give a detailed description of recent results on extremal Peisert-type graphs without strict-EKR property presented in [14].

Slides & Video

Minicourse: Combinatorial topics in low dimensional topology and geometry

by Alexander Mednykh

by Alexander Mednykh

Alexander Mednykh is the world's leading expert in the theory of discrete groups, hyperbolic geometry, complex and combinatorial analysis, and geometric graph theory. Currently, he is a member of the Sobolev Institute of Mathematics and Novosibirsk State University. He is the author of more than 150 scientific papers, two monographs, and has 15 defended PhD students.

The main scientific results of Alexander Mednykh are:

1) a solution of the Hurwitz problem on the enumeration of branched coverings over a Riemann surface;

2) developed new methods for finding solutions of the discrete Cauchy-Riemann equation and general linear difference equations with polynomial coefficients;

3) created a geometric theory of knots in spaces of constant curvature, developed new methods for explicit calculation of volumes of knots in Euclidean, spherical and hyperbolic spaces;

4) counting the conjugacy classes of subgroups in a finitely generated group, on their basis the coverings of three-dimensional Euclidean manifolds are completely enumerated;

5) solved the Tutte problem of counting of maps on the surface of a given genus up to homeomorphism;

6) created a theory of groups acting harmonically on a graph;

7) established discrete versions of theorems on automorphism groups of Riemann surfaces given by Hurwitz, Wiman, Accola, MacLachlan, Kulkarni, and others.

1) a solution of the Hurwitz problem on the enumeration of branched coverings over a Riemann surface;

2) developed new methods for finding solutions of the discrete Cauchy-Riemann equation and general linear difference equations with polynomial coefficients;

3) created a geometric theory of knots in spaces of constant curvature, developed new methods for explicit calculation of volumes of knots in Euclidean, spherical and hyperbolic spaces;

4) counting the conjugacy classes of subgroups in a finitely generated group, on their basis the coverings of three-dimensional Euclidean manifolds are completely enumerated;

5) solved the Tutte problem of counting of maps on the surface of a given genus up to homeomorphism;

6) created a theory of groups acting harmonically on a graph;

7) established discrete versions of theorems on automorphism groups of Riemann surfaces given by Hurwitz, Wiman, Accola, MacLachlan, Kulkarni, and others.

October 4, 2022

The geometry of knots and links arose in the 70s of the last century in the works of the English mathematician Robert Riley and the American mathematician William Thurston. The main idea was to introduce a geometric structure on the complement to a knot or link. Surprisingly, the Lobachevsky geometry turned out to be the most suitable geometry for this purpose. The same geometry embraces "almost all" 3-manifolds. For this result, W. Thurston received the Fields Prize in 1983. However, there are seven more geometries that describe three-dimensional manifolds and, in particular, the nodes located in them. The purpose of this lecture is to tell how Euclidean, spherical and hyperbolic geometries arise at the knot theory. Exact analytical formulas are shown for calculating the volumes of the cone manifolds whose singular set is a given knot or link.

Slides & video

October 18, 2022

A historical review of the results on the calculation of areas and volumes in spaces of constant curvature is given. Non-Euclidean analogues of the classical formulas of Heron and Brahmagupta for triangles and quadrilaterals are considered. Problems associated with calculating the volumes of non-Euclidean tetrahedra are discussed in details. Formulas for the volumes of tetrahedra obtained by Lobachevsky, Bolyai, Coxeter and Milnor are given. The main emphasis is placed on the results obtained by modern authors - Kim and Cho, Murakami and Yano, Ushijima, Derevnin and Mednykh. It is shown that the presence of nontrivial symmetries on a polyhedron greatly simplifies the derivation of formulas for the volume.

Slides & video

November 15, 2022

The spectrum of the Laplace operator of a connected graph on n vertices is given by its eigenvalues. Three important geometric characteristics based on the spectrum are associated with such a graph are the number of spanning trees t(n), the number of rooted spanning forests f(n), and the Kirchhoff index Kf(n). In applications of graph theory to crystallography and statistical physics, the most interesting cases arise when n tends to infinity. We consider graphs admitting the action of a large cyclic group of automorphisms with a small number of orbits. The class of such graphs is quite wide. It includes circulant graphs, Haar graphs, generalized Petersen graphs, I-,Y-,H-graphs, discrete tori, and circulant bundles. In all these cases, the quantities t(n),f(n) and Kf(n) are expressed in terms of Chebyshev polynomials of the first and second kind. This allows to find their asymptotic and explore their arithmetic properties.

Slides & video

December 13, 2022

Classical work by Mark Katz (1966) "Can you hear the shape of the drum?" initiated the study of the geometric properties of manifolds defined by their spectrum. In particular, Wolpert (1979) showed that a general Riemann surface is defined by its spectrum of the Laplace operator. Despite this, pairs of isospectral Riemann surfaces are known for any genus ≥ 4 (see Buser (1986), Brooks and Tse (1987), and others). There are also examples of isospectral but non-isometric two and three subsurfaces with variable curvature shown by Barden and Hyunsuk Kang (2012). At the same time, isospectral surfaces of genus one (flat tori) are isometric (Brooks, 1988). A similar result for Klein bottles was obtained by R. Isangulov (2000). An overview of the relevant results for graphs can be found in the paper by E.R. van Dam and W.H. Haemers (2003). Peter Buser (1992) posed the following interesting problem: will two isospectral Riemann surfaces of genus two be isometric? This problem for Riemann surfaces is still open. The purpose of the lecture is to give a positive solution to this problem for graphs of homological genus two.

Slides & video

December 13, 2022

Dessins d'enfants as a subject of mathematical research appeared in the well-known program of A. Grothendieck (1984), where approaches were outlined for their study, covering Galois theory, the theory of Fuchsian groups, permutation groups, Teichmüller theory, algebraic geometry and many other sections of modern mathematics. A "children's drawing" is usually drawn on a closed Riemann surface in such a way that its complement is a finite set of topological disks, that is, regions homeomorphic to a circle. This allows to use the theory of uniformization of Riemann surfaces as one of the ways to describe the object of interest to us. Different patterns on the surface correspond to different subgroups of the unifying Fuchsian group. Moreover, drawings are homeomorphic if and only if the corresponding subgroups are conjugate. This allows to reduce the problem of enumeration of "dessins d'enfants" up to homeomorphism to the problem of enumeration of classes of conjugate subgroups of a given index in a given Fuchsian group. Both problems were solved by the lecturer and his colleagues.

Slides & video

Minicourse: Coverings of graphs and maps

by Roman Nedela

by Roman Nedela

Roman Nedela obtained his PhD in 1991 at Comenius University, Bratislava, under the supervision of Professor Stefan Znam. Most of his career he spent at the Department of Mathematics, Matej Bel University first at the position of associated professor, since 1996 at the position of professor. In the period 2001-2006 he was employed by the Math. institute of the Slovak Academy of Siences, where he has a part time job till

nowadays. Since 2018 he is a full professor at the Department of Mathematics, University of West Bohemia, Pilsen. His research interests include graph theory, combinatorics, algebraic graph theory, theory of finite groups and geometry. He is a (co)author of 110 research papers.

nowadays. Since 2018 he is a full professor at the Department of Mathematics, University of West Bohemia, Pilsen. His research interests include graph theory, combinatorics, algebraic graph theory, theory of finite groups and geometry. He is a (co)author of 110 research papers.

Description of the course

A covering between two graphs is a graph epimorphism which is locally bijective. Although the concept of coverings of topological spaces was well known in algebraic topology for a long time, a systematic combinatorial approach to graph coverings is related to the solution of the Heawood map colouring problem by Ringel and Youngs. Nowadays the concept of graph coverings forms an integral part of graph theory well established in the monograph by Gross and Tucker (1987) and has found dozen of applications, in particular, as a strong construction technique.

The aim of the course is to explain foundations of the combinatorial theory of graph coverings and its extension to branched coverings between 1-dimensional and 2-dimensional orbifolds.

The aim of the course is to explain foundations of the combinatorial theory of graph coverings and its extension to branched coverings between 1-dimensional and 2-dimensional orbifolds.

February 8, 2022

1. Graphs and Groups

Basic concepts. Graphs with semiedges and their fundamental groups. Graph coverings. Groups acting on graphs. Group of covering transformations. Subgroup enumeration in some finitely generated groups. Enumeration of conjugacy classes of subgroups. Universal covers.

Slides & video

Basic concepts. Graphs with semiedges and their fundamental groups. Graph coverings. Groups acting on graphs. Group of covering transformations. Subgroup enumeration in some finitely generated groups. Enumeration of conjugacy classes of subgroups. Universal covers.

Slides & video

February 22, 2022

3. Applications of graph coverings

Regular graphs with large girth. Large graphs of given degree and diameter. Nowhere-zero flows and coverings. 3-edge colourings of cubic graphs.

Regular graphs with large girth. Large graphs of given degree and diameter. Nowhere-zero flows and coverings. 3-edge colourings of cubic graphs.

4. Coverings between embedded graphs

Lift of a graph and lift of a map. Heawood map coloring problem. Construction of (near) triangular embeddings of Kn. Riemann-Hurwitz theorem. Maps on orbifolds. Voltages at vertices. Discrete actions of groups on surfaces. Equivalence of actions and equivalence of coverings. Cyclic actions and map enumeration.

Lift of a graph and lift of a map. Heawood map coloring problem. Construction of (near) triangular embeddings of Kn. Riemann-Hurwitz theorem. Maps on orbifolds. Voltages at vertices. Discrete actions of groups on surfaces. Equivalence of actions and equivalence of coverings. Cyclic actions and map enumeration.

5. Lifting automorphism problem

Classical approach Lifting of graph automorphisms in terms of voltages. Lifting problem, case of abelian CT(p). Elementary abelian CT(p).

Classical approach Lifting of graph automorphisms in terms of voltages. Lifting problem, case of abelian CT(p). Elementary abelian CT(p).

6. Branched coverings of graphs

Harmonic morphisms of graphs. Riemann-Hurwitz theorem for Graphs. Laplacian of a graph and the Matrix-Tree Theorem. Jacobian of a graph.

Harmonic morphisms of graphs. Riemann-Hurwitz theorem for Graphs. Laplacian of a graph and the Matrix-Tree Theorem. Jacobian of a graph.

- A. Gross, Jonathan L.; Tucker, Thomas W. Topological graph theory. Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1987. xvi+351 pp. ISBN: 0-471-04926-3.
- A. Mednykh, R. Nedela, Harmonic morphisms of graphs, Part I: Graph Coverings, Matej Bel University, 2015.

Minicourse: Right-angled Artin groups and the R-infinity property

by Pieter Senden

by Pieter Senden

Pieter Senden is a talented young researcher, who obtained his Master's degree at KU Leuven, Belgium, under the supervision of Professor Karel Dekimpe, in the year 2019. After graduation from the master's program he got a position of the PhD student, funded by The Research Foundation – Flanders (FWO). At the moment he is finishing his PhD thesis at KU Leuven, Kulak Kortrijk Campus.

Description of the course

In this mini-course we explore the relation between the properties of a right-angled Artin group (RAAG) and the properties of its defining graph, which we then use to discuss the R-infinity property for RAAGs. In the first part we introduce RAAGs and provide a (non-exhaustive) dictionary to see how graph theoretical properties translate into algebraic properties of the groups and vice versa. In the second part we give an introduction to twisted conjugacy and the R-infinity property after which we use the aforementioned dictionary to prove that certain families of RAAGs have the R-infinity property. We illustrate both parts with concrete examples.

Minicourse: **Generalized quadrangles and applications**

by Leo Storme

by Leo Storme

Leo Storme obtained his PhD in 1991 at Ghent University, Belgium, under the supervision of Professor Joseph A. Thas. He started in 1988 his research career with the Fund for Scientific Research — Flandres, Belgium. On October 1, 2000, he became assistant professor at Ghent University. Since 2006, he is full professor at Ghent University and he has been a Fellow of the Alexander von Humboldt Foundation in 2006. He works on problems on substructures in finite geometry, and also on links with coding theory. He is a (co)author of 170 research papers.

Description of the course

In this minicourse we will give an introduction to finite generalized quadrangles, embedded in finite geometries, and applications to graph theory and coding theory. We start with an introduction to finite geometry, discuss the polarities and the corresponding finite classical polar spaces. We then introduce finite generalized quadrangles and present the finite classical generalized quadrangles as being the finite classical polar spaces of rank two.

The finite generalized quadrangles are first of all investigated because of their geometrical interest. But they are also of interest for other research domains. We present applications in graph theory, and we also discuss linear codes defined by finite generalized quadrangles.

The finite generalized quadrangles are first of all investigated because of their geometrical interest. But they are also of interest for other research domains. We present applications in graph theory, and we also discuss linear codes defined by finite generalized quadrangles.

- A. Cossidente and F. Pavese, Strongly regular graphs from classical generalized quadrangles.
*Des. Codes Cryptogr*. 85 (2017), no. 3, 457–470. - S. Gravier, A. Parreau, S. Rottey, L. Storme, and É. Vandomme, Identifying codes in vertex-transitive graphs and strongly regular graphs.
*Electron. J. Combin*. 22 (2015), no. 4, Paper 4.6, 26 pp. - T. Héger and L. Hernandez Lucas, Dominating sets in finite generalized quadrangles.
*Ars. Math. Contemporanea*19 (2020), 61–76. - J.W.P. Hirschfeld and J.A. Thas, General Galois geometries. Springer Monographs in Mathematics.
*Springer, London,*2016. - J.-L. Kim, K.E. Mellinger, and L. Storme, Small weight codewords in LDPC codes defined by (dual) classical generalized quadrangles.
*Des. Codes Cryptogr*. 42 (2007), no. 1, 73–92. - M. Lavrauw and G. Van de Voorde, Locally repairable codes with high availability based on generalised quadrangles. (arXiv:1912.06372)
- Z. Liu and D.A. Pados, LDPC codes from generalized polygons
*.**IEEE Trans. Inform. Theory*51 (2005), no. 11, 3890–3898. - S.E. Payne and J.A. Thas, Finite generalized quadrangles. Second edition. EMS Series of Lectures in Mathematics.
*European Mathematical Society (EMS), Zürich,*2009. - V. Pepe, L. Storme, and G. Van de Voorde, On codewords in the dual code of classical generalised quadrangles and classical polar spaces.
*Discrete Math***.**310 (2010), no. 22, 3132–3148.

Minicourse: Construction of combinatorial structures from finite groups

by Andrea Švob

by Andrea Švob

Andrea Švob obtained her PhD thesis at the University of Zagreb, Croatia, under the supervision of Professor Dean Crnković, in the year 2013. Since November 2007, she had been employed at the Department of Mathematics of the University of Rijeka and currenty works there as an assistant professor. She is a (co)author of 24 research papers.

Description of the course

In this minicourse we give an introduction to one of the methods for construction of combinatorial structures from finite groups. The focus is on distance-regular graphs and combinatorial designs. In the first part of the course we give a construction of transitive combinatorial structures i.e. the structures on which finite groups act transitively. In the second part we extend and generalize the method to obtain non-transitive structures. The methods are followed up with various examples. Finally, we show some of the applications of the constructed structures.

Minicourse: A not so short introduction into Algebraic Graph Theory

by Štefan Gyürki

by Štefan Gyürki

Štefan Gyürki received his PhD from Comenius University (Bratislava, Slovakia) in 2009. He spent a year as a postdoc student at Ben-Gurion University of the Negev (Beer-Sheva, Israel) under the guidance of Prof. Mikhail Klin. He is a (co)author of 10 research publications. He currently works at the Slovak University of Technology as a researcher.

Description of the course

This minicourse provides a gentle introduction into the theory of coherent configurations and association schemes. We start the considerations with the theory of permutation groups and their actions. After that we introduce the terms of a coherent configuration and association scheme. A significant family of coherent configurations and associations schemes arose with the aid of permutation groups, these are called Schurian. We spend some time on the investigations of a few objects which are non-Schurian, while at the end of the minicourse we will approach the most symmetric (in the sense of the number of automorphisms) strongly regular graph with parameters (26,10,3,4).

Basic knowledge of algebra is required, but all other concepts are explained in the course.

Basic knowledge of algebra is required, but all other concepts are explained in the course.

Materials

March 23, 2021

Permutation groups (basics)

Video

Slides

Assignment

Video

Slides

Assignment

April 6, 2021

Invariant relations of permutation groups

Video

Slides

Assignment

Video

Slides

Assignment

April 20, 2021

Coherent configurations and association schemes

Video

Slides

Assignment

Video

Slides

Assignment

May 4, 2021

Coherent closure

Video

Slides

Assignment

Video

Slides

Assignment

Useful links

We would be glad to see you as a participant of our future events.

Videos of talks given on workshops, seminars and conferences on algebraic graph theory organized by our team:

https://www.youtube.com/playlist?list=PLaX3n04-uUZr9jVGOCYzPsB9L0Qzo9KeN

Videos of talks given on Lectorium on Algebraic Graph Theory are submitted to the playlist.

Videos of talks given on workshops, seminars and conferences on algebraic graph theory organized by our team:

https://www.youtube.com/playlist?list=PLaX3n04-uUZr9jVGOCYzPsB9L0Qzo9KeN

Videos of talks given on Lectorium on Algebraic Graph Theory are submitted to the playlist.

Lectorium is organized by

Organizer

e_konsta@math.nsc.ru

e_konsta@math.nsc.ru

Organizer

ntr@math.nsc.ru

ntr@math.nsc.ru

Nikolay Abrosimov

Organizer

abrosimov@math.nsc.ru

abrosimov@math.nsc.ru

Supported by Mathematical Center in Akademgorodok under agreement No. 075-15-2019-1675 with the Ministry of Science and Higher Education of the Russian Federation