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).
Past events
Minicourse:
Topics in Automorphisms of Cayley Graphs
by Joy Morris
Topics in Automorphisms of Cayley Graphs
by Joy Morris
Joy Morris completed her PhD at Simon Fraser University in British Columbia (Canada) in 2000 under the supervision of Brian Alspach. She has been working at the University of Lethbridge in Alberta (Canada) ever since, where she is now a Professor, and where she has won the students’ union’s teaching award. Her research revolves around group actions on graphs. She has an interest in math outreach and math education; she has written or co-written a couple of open access math text books, and developed a math outreach program aimed at parents of middle school kids that she led for several years before it was interrupted by the pandemic.
Materials
October 9, 2024
Lecture 1. Cayley graphs and digraphs; Circulant graphs
In this lecture I present basic definitions and background about Cayley graphs and digraphs as a special class of vertex-transitive graphs, with a light emphasis on circulant graphs. In particular, we look at automorphisms that these graphs always admit.
Slides & video
In this lecture I present basic definitions and background about Cayley graphs and digraphs as a special class of vertex-transitive graphs, with a light emphasis on circulant graphs. In particular, we look at automorphisms that these graphs always admit.
Slides & video
October 23, 2024
Lecture 2. Automorphism groups of Circulant graphs; Burnside
This lecture goes into detail about how to compute the automorphism group of any Cayley graph of prime order (such a graph is always circulant). For composite orders, a relevant result by Burnside is discussed, and lexicographic (wreath) products are introduced. This allows us to extend the algorithm to circulant graphs of order pq, where p and q are distinct primes. Although these algorithms can be further extended to the square-free case, describing the general situation is beyond the scope of these lectures.
Slides & video
This lecture goes into detail about how to compute the automorphism group of any Cayley graph of prime order (such a graph is always circulant). For composite orders, a relevant result by Burnside is discussed, and lexicographic (wreath) products are introduced. This allows us to extend the algorithm to circulant graphs of order pq, where p and q are distinct primes. Although these algorithms can be further extended to the square-free case, describing the general situation is beyond the scope of these lectures.
Slides & video
November 6, 2024
Lecture 3. Regular Representations
Cayley graphs always contain a regular subgroup in their automorphism group. When this is the entire automorphism group, the graph is called a Graphical Regular Representation (GRR); in the case of a digraph, a DRR. This lecture provides an introduction to the topic of GRRs and DRRs, including presenting results about which groups admit such (di)graphs, and their frequency among all Cayley (di)graphs. Other regular representations (in addition to graphs and digraphs) are also touched on.
Slides (video will be published soon)
Cayley graphs always contain a regular subgroup in their automorphism group. When this is the entire automorphism group, the graph is called a Graphical Regular Representation (GRR); in the case of a digraph, a DRR. This lecture provides an introduction to the topic of GRRs and DRRs, including presenting results about which groups admit such (di)graphs, and their frequency among all Cayley (di)graphs. Other regular representations (in addition to graphs and digraphs) are also touched on.
Slides (video will be published soon)
Minicourse:
Geometrical topics in the theory of self-similar fractals
by Andrei Tetenov
Geometrical topics in the theory of self-similar fractals
by Andrei Tetenov
Andrei Tetenov received his DPhil from Sobolev Institute of Mathematics in 2011. He is currently a Leading Researcher at Sobolev Institute of Mathematics and Professor at Novosibirsk State University. His research interests include Kleinian groups, geometric topology and fractal geometry.
Materials
April 18, 2024
Lecture 1. Convex hulls of self-similar sets
The lecture is devoted to the interaction of self-similarity and convexity. The convex Hutchinson operator and its attractor. Special features of its action on the extreme set of the convex attractor and the set of outer normals. Finiteness conditions for the extreme set. Open convex set condition and Hausdorff dimension of the extreme set. Natural examples of Cantor sets of zero dimension.
Video
The lecture is devoted to the interaction of self-similarity and convexity. The convex Hutchinson operator and its attractor. Special features of its action on the extreme set of the convex attractor and the set of outer normals. Finiteness conditions for the extreme set. Open convex set condition and Hausdorff dimension of the extreme set. Natural examples of Cantor sets of zero dimension.
Video
May 16, 2024
Lecture 2. Weak separation property and self-similar Jordan arcs
Strange behavior of the measure of intersections for some self-similar sets. Open set condition and weak separation property, their effects upon dimension, measure and geometry of the attractor. Small quasitranslations and smoothness of self-similar Jordan arcs. Multizipper representation of self-similar arcs. Smooth self-affine arcs.
Video
Strange behavior of the measure of intersections for some self-similar sets. Open set condition and weak separation property, their effects upon dimension, measure and geometry of the attractor. Small quasitranslations and smoothness of self-similar Jordan arcs. Multizipper representation of self-similar arcs. Smooth self-affine arcs.
Video
May 30, 2024
Lecture 3. The general position theorem and some long-awaited counterexamples
General position theorem. Special dense 2-generator subgroups in C. An example of self-similar Jordan arc in space that does not satisfy the open set condition. An example of totally disconnected self-similar set with a unique one-point intersection that does not satisfy the OSC.
Video
General position theorem. Special dense 2-generator subgroups in C. An example of self-similar Jordan arc in space that does not satisfy the open set condition. An example of totally disconnected self-similar set with a unique one-point intersection that does not satisfy the OSC.
Video
September 2024
Lecture 4. Topology of self-similar dendrites
Postcritically finite self-similar dendrites. The main tree and the intersection graph. Weak separation property for self-similar dendrites in the plane. Intersection of pieces in a subdendrite. 7 types of the main trees for Bedford-McMullen carpet dendrites.
Postcritically finite self-similar dendrites. The main tree and the intersection graph. Weak separation property for self-similar dendrites in the plane. Intersection of pieces in a subdendrite. 7 types of the main trees for Bedford-McMullen carpet dendrites.
Lecture 1.
[1] Peter M. Gruber. Convex and Discrete Geometry. Springer Verlag Berlin Heidelberg. 2007
[2] A. V. Tetenov. On the length of the set of extreme points for self-similar sets in R2. Siberian Electronic Mathematical Reports. 2009. v.6. P. 542–545.
Lecture 2.
[3] Ch. Bandt, S. Graf. Self-similar sets 7. A characterization of self-similar fractals with positive Hausdorff measure. // Proc. Amer. Math. Soc., 1992, V. 114, No. 4, pp. 995–1001.
[4] M. P. W. Zerner, Weak separation properties for self-similar sets. Proc.Amer.Math.Soc. 1996, V. 124, No. 11, pp. 3529–3539.
[5] A.V. Tetenov, Self-similar Jordan arcs and graph-directed systems of similarities. Siberian Math. J. 47 (2006), no. 5, 940–949 MR2266525.
[6] A.V. Tetenov, A.R. Kutlimuratov. On the structure of self-affine Jordan arcs in ℝ^2. Demonstratio Mathematica. – 2023. – Т. 56. – №. 1. – С. 20220228
Lecture 3.
[7] A. V. Tetenov K.G. Kamalutdinov Even unique intersection point can break OSC: an example. Nonlinearity 33 (2020), 408–417
Lecture 4.
[8] A.V.Tetenov, D.A.Drozdov, On the classification of fractal square dendrites. (2023). Advances in the Theory of Nonlinear Analysis and Its Application, 7(3), 79–96.
[1] Peter M. Gruber. Convex and Discrete Geometry. Springer Verlag Berlin Heidelberg. 2007
[2] A. V. Tetenov. On the length of the set of extreme points for self-similar sets in R2. Siberian Electronic Mathematical Reports. 2009. v.6. P. 542–545.
Lecture 2.
[3] Ch. Bandt, S. Graf. Self-similar sets 7. A characterization of self-similar fractals with positive Hausdorff measure. // Proc. Amer. Math. Soc., 1992, V. 114, No. 4, pp. 995–1001.
[4] M. P. W. Zerner, Weak separation properties for self-similar sets. Proc.Amer.Math.Soc. 1996, V. 124, No. 11, pp. 3529–3539.
[5] A.V. Tetenov, Self-similar Jordan arcs and graph-directed systems of similarities. Siberian Math. J. 47 (2006), no. 5, 940–949 MR2266525.
[6] A.V. Tetenov, A.R. Kutlimuratov. On the structure of self-affine Jordan arcs in ℝ^2. Demonstratio Mathematica. – 2023. – Т. 56. – №. 1. – С. 20220228
Lecture 3.
[7] A. V. Tetenov K.G. Kamalutdinov Even unique intersection point can break OSC: an example. Nonlinearity 33 (2020), 408–417
Lecture 4.
[8] A.V.Tetenov, D.A.Drozdov, On the classification of fractal square dendrites. (2023). Advances in the Theory of Nonlinear Analysis and Its Application, 7(3), 79–96.
Minicourse:
Difference methods in combinatorial design theory
by Tao Feng
Difference methods in combinatorial design theory
by Tao Feng
Tao Feng received his PhD from Beijing Jiaotong University in 2008. He is currently a Professor at the School of Mathematics and Statistics, Beijing Jiaotong University.
His research interests include design theory, coding theory, algebraic graph theory, extremal set theory and their interactions.
His research interests include design theory, coding theory, algebraic graph theory, extremal set theory and their interactions.
Materials
March 19, 2024
Lecture 1. A brief introduction to difference families: constructions and applications
A difference family in an additive (not necessarily abelian) group G is a collection F of nonempty subsets (called base blocks) of G such that all non-zero elements of G have the same multiplicity λ in the list of differences of F that is the multiset of all possible differences between two distinct elements of a block of F. This lecture provides a brief history on difference families and focuses on constructions for cyclic designs from cyclic difference families. Cyclotomic constructions for difference families by means of strong diference famlies are discussed in details. By exploring the underlying structure of difference families, it is shown that a cyclic (v, 4, 1)-design exists if and only if v ≡ 1, 4 (mod 12) and v ≠ 16, 25, 28. The same technique is used to show that there exists an optimal (v, 4, 1)-optical orthogonal code attaining the Johnson bound for any positive integer v ≠ 25. Novak conjectured in 1974 that for any cyclic Steiner triple systems of order v with v ≡ 1 (mod 6), it is always possible to choose one block from each block orbit so that the chosen blocks are pairwise disjoint. This conjecture is confirmed by using Combinatorial Nullstellensatz and proper edge-colouring of hypergraphs.
Slides & video
A difference family in an additive (not necessarily abelian) group G is a collection F of nonempty subsets (called base blocks) of G such that all non-zero elements of G have the same multiplicity λ in the list of differences of F that is the multiset of all possible differences between two distinct elements of a block of F. This lecture provides a brief history on difference families and focuses on constructions for cyclic designs from cyclic difference families. Cyclotomic constructions for difference families by means of strong diference famlies are discussed in details. By exploring the underlying structure of difference families, it is shown that a cyclic (v, 4, 1)-design exists if and only if v ≡ 1, 4 (mod 12) and v ≠ 16, 25, 28. The same technique is used to show that there exists an optimal (v, 4, 1)-optical orthogonal code attaining the Johnson bound for any positive integer v ≠ 25. Novak conjectured in 1974 that for any cyclic Steiner triple systems of order v with v ≡ 1 (mod 6), it is always possible to choose one block from each block orbit so that the chosen blocks are pairwise disjoint. This conjecture is confirmed by using Combinatorial Nullstellensatz and proper edge-colouring of hypergraphs.
Slides & video
April 2, 2024
Lecture 2. Difference matrices and orthogonal orthomorphisms of groups
Let G be a finite group of order v and k > 1 be an integer. A (v, k,)-difference matrix (DM) over G, briefly (G, k, λ)-DM, is a k matrix D = (dij) with entries from G, such that for any two distinct rows x and y, the multiset of differences } contains each element of G exactly times. Difference matrices have a close relationship with orthogonal orthomorphisms of groups. A bijection θ from a finite group G to itself is said to be an orthomorphism of G if the mapping from x to θ(x) is also a bijection, and two orthomorphisms θ and φ of G are orthogonal if the mapping from x to φ(x) is a bijection. There exists a set of k pairwise orthogonal orthomorphisms of G if and only if there exists a (G, k + 2, 1)-DM. This lecture provides a brief introduction on difference matrices and focuses on Hall-Paige's conjecture and its possible generalizations.
Slides & video
Let G be a finite group of order v and k > 1 be an integer. A (v, k,)-difference matrix (DM) over G, briefly (G, k, λ)-DM, is a k matrix D = (dij) with entries from G, such that for any two distinct rows x and y, the multiset of differences } contains each element of G exactly times. Difference matrices have a close relationship with orthogonal orthomorphisms of groups. A bijection θ from a finite group G to itself is said to be an orthomorphism of G if the mapping from x to θ(x) is also a bijection, and two orthomorphisms θ and φ of G are orthogonal if the mapping from x to φ(x) is a bijection. There exists a set of k pairwise orthogonal orthomorphisms of G if and only if there exists a (G, k + 2, 1)-DM. This lecture provides a brief introduction on difference matrices and focuses on Hall-Paige's conjecture and its possible generalizations.
Slides & video
Minicourse:
Paley Graphs and Theory of Directions
by Shamil Asgarli
Paley Graphs and Theory of Directions
by Shamil Asgarli
Shamil Asgarli received his Ph.D. from Brown University in 2019. Afterwards, he held a three-year postdoctoral fellowship at the University of British Columbia. In Fall 2022, he joined Santa Clara University as an assistant professor.
Shamil's research interests revolve around algebraic, arithmetic, and finite geometry. He is particularly interested in algebraic varieties defined over finite fields, with emphasis on how the F_q-points on such objects are distributed. He is also interested in algebraic graph theory, especially Paley graphs and other Cayley graphs that arise from finite fields.
Shamil's research interests revolve around algebraic, arithmetic, and finite geometry. He is particularly interested in algebraic varieties defined over finite fields, with emphasis on how the F_q-points on such objects are distributed. He is also interested in algebraic graph theory, especially Paley graphs and other Cayley graphs that arise from finite fields.
Materials
October 17, 2023
Lecture 1. Introduction to Paley graphs
In this lecture, we introduce Paley graphs and discuss their elementary properties with a central focus on their clique numbers. Let q=1 (mod 4) be an odd prime power. Consider the graph Pq , whose vertices are elements of the finite field F_q, where the two vertices x and y are adjacent if x–y is a square in F_q.The resulting graph P_q is called the Paley graph of order q. Paley graphs possess a high degree of symmetry; for example, they are strongly regular (see Section 5.8 in [GM16]). Recall that the clique number of a given graph G, denoted by ω(G), is the size of the largest clique contained in G. Finding reasonable upper bounds on ω(Pq) is a notoriously difficult and open problem. As the first step, we discuss the so-called trivial upper bound ω(Pq) ≤ q. We also mention the lower bound ω(P_q)≫ log(q) obtained by S. Cohen where q is an odd power of a prime. If q=p is a prime, Graham and Ringrose showed the stronger result ω(P_p)≫Ω(log p log log log p) in [GR90]. Returning to the upper bound, Hanson and Petridis [HP21] proved that ω(P_p) ≤ p/2 + 1. The latter result is a recent breakthrough, and our eventual goal in this lecture series is to present a proof of this result.
Slides & video
In this lecture, we introduce Paley graphs and discuss their elementary properties with a central focus on their clique numbers. Let q=1 (mod 4) be an odd prime power. Consider the graph Pq , whose vertices are elements of the finite field F_q, where the two vertices x and y are adjacent if x–y is a square in F_q.The resulting graph P_q is called the Paley graph of order q. Paley graphs possess a high degree of symmetry; for example, they are strongly regular (see Section 5.8 in [GM16]). Recall that the clique number of a given graph G, denoted by ω(G), is the size of the largest clique contained in G. Finding reasonable upper bounds on ω(Pq) is a notoriously difficult and open problem. As the first step, we discuss the so-called trivial upper bound ω(Pq) ≤ q. We also mention the lower bound ω(P_q)≫ log(q) obtained by S. Cohen where q is an odd power of a prime. If q=p is a prime, Graham and Ringrose showed the stronger result ω(P_p)≫Ω(log p log log log p) in [GR90]. Returning to the upper bound, Hanson and Petridis [HP21] proved that ω(P_p) ≤ p/2 + 1. The latter result is a recent breakthrough, and our eventual goal in this lecture series is to present a proof of this result.
Slides & video
October 31, 2023
Lecture 2. Introduction to the theory of directions
In this lecture, we discuss fully reducible lacunary polynomials over finite fields. Fully reducible means that the polynomial splits into a product of linear factors, whereas lacunary implies that the polynomial has a long run of zeros in its coefficients. Rédei used such polynomials to prove several new results in finite geometry [Red70]; these ideas and further refinements are instances of thepolynomial method. For example, Blokhuis used Rédei polynomials to prove the celebrated result that the size of a non-trivial blocking set in PG(2, p) is at least 3(p+1)/2 when p is a prime [Blo94]. We follow the exposition in Szönyi's excellent article [Szo99] to discuss an application of Rédei polynomials in the theory of directions. In particular, we derive a lower bound on the number of directions (also called "slopes") determined by a finite point set in a finite projective plane. Assuming that the point set arises from a graph of a function y=f(x), the problem is about estimating the number of different values difference quotient (f(x)-f(y))/(x-y) takes as x, y range over elements of a finite field F_q. Fortunately, there is a genuine connection between the theory of directions and maximum cliques in Paley graphs.
Slides & video
In this lecture, we discuss fully reducible lacunary polynomials over finite fields. Fully reducible means that the polynomial splits into a product of linear factors, whereas lacunary implies that the polynomial has a long run of zeros in its coefficients. Rédei used such polynomials to prove several new results in finite geometry [Red70]; these ideas and further refinements are instances of thepolynomial method. For example, Blokhuis used Rédei polynomials to prove the celebrated result that the size of a non-trivial blocking set in PG(2, p) is at least 3(p+1)/2 when p is a prime [Blo94]. We follow the exposition in Szönyi's excellent article [Szo99] to discuss an application of Rédei polynomials in the theory of directions. In particular, we derive a lower bound on the number of directions (also called "slopes") determined by a finite point set in a finite projective plane. Assuming that the point set arises from a graph of a function y=f(x), the problem is about estimating the number of different values difference quotient (f(x)-f(y))/(x-y) takes as x, y range over elements of a finite field F_q. Fortunately, there is a genuine connection between the theory of directions and maximum cliques in Paley graphs.
Slides & video
November 14, 2023
Lecture 3. Upper bounds on the clique number
We present detailed proof of the Hanson-Petridis upper bound for the clique number of Paley graphs. We follow a different proof by Di Benedetto, Solymosi, and White that uses the polynomial method [DSW21], namely Rédei polynomials with Szönyi's extension [Szo96]. The main idea is to give a lower bound on the number of directions determined by a Cartesian product of two point sets. We also examine Hanson-Petridis bound for other graphs which generalize Paley graphs, and mention exciting new results by Chi Hoi Yip in this area.
Slides & video
We present detailed proof of the Hanson-Petridis upper bound for the clique number of Paley graphs. We follow a different proof by Di Benedetto, Solymosi, and White that uses the polynomial method [DSW21], namely Rédei polynomials with Szönyi's extension [Szo96]. The main idea is to give a lower bound on the number of directions determined by a Cartesian product of two point sets. We also examine Hanson-Petridis bound for other graphs which generalize Paley graphs, and mention exciting new results by Chi Hoi Yip in this area.
Slides & video
Lecture 1:
[Coh98] S. Cohen, Clique numbers of Paley graphs, Quaestiones Math., 11 (1988), 225-231
[GM16] C. Godsil and K. Meagher, Erdos-Ko-Rado theorems: algebraic approaches, Cambridge Studies in Advanced Mathematics, vol. 149, Cambridge University Press, Cambridge, 2016.
[GR90] S. Graham, C. Ringrose, Lower bounds for least quadratic non-residues, Analytic Number Theory: Proceedings of a Conference in Honor of Paul T. Bateman, 269-309 (1990).
[HP21] B. Hanson, G. Petridis, Refined estimates concerning sumsets contained in the roots of unity, Proc. Lond. Math. Soc. (3) 122 (2021), no. 3, 353–358.
Lecture 2:
[Blo94] A. Blokhuis, On the size of a blocking set in PG(2; p), Combinatorica 14 (1994) 111–114.
[LS81] L. Lovasz, A. Schrijver, Remarks on a theorem of Redei, Studia Scient. Math. Hungar. 16 (1981) 449–454.
[Szo99] T. Szönyi, Around Redei's theorem, Discrete Math, 208/209 (1999), 557-575.
[Red70] L. Rédei, Luckenhafte Polynome über endlichen Korpern, Birkhauser Verlag, Basel (1970) (English translation: Lacunary polynomials over finite fields, North-Holland, Amsterdam, 1973).
Lecture 3:
[DSW21] D. Di Benedetto, J. Solymosi, and E. P. White, On the directions determined by a Cartesian product in an affine Galois plane. Combinatorica, 41(6):755–763, 2021.
[HP21] B. Hanson, G. Petridis, Refined estimates concerning sumsets contained in the roots of unity, Proc. Lond. Math. Soc. (3) 122 (2021), no. 3, 353–358.
[Szo96] T. Szönyi, On the number of directions determined by a set of points in a Galois plane, J. Combin. Theory Ser. A 74 (1996) 141–146.
[Yip23] C. H. Yip, Refined Estimates on the clique number of cyclotomic graphs. ArXiv preprint available at https://arxiv.org/abs/2304.13213
[Coh98] S. Cohen, Clique numbers of Paley graphs, Quaestiones Math., 11 (1988), 225-231
[GM16] C. Godsil and K. Meagher, Erdos-Ko-Rado theorems: algebraic approaches, Cambridge Studies in Advanced Mathematics, vol. 149, Cambridge University Press, Cambridge, 2016.
[GR90] S. Graham, C. Ringrose, Lower bounds for least quadratic non-residues, Analytic Number Theory: Proceedings of a Conference in Honor of Paul T. Bateman, 269-309 (1990).
[HP21] B. Hanson, G. Petridis, Refined estimates concerning sumsets contained in the roots of unity, Proc. Lond. Math. Soc. (3) 122 (2021), no. 3, 353–358.
Lecture 2:
[Blo94] A. Blokhuis, On the size of a blocking set in PG(2; p), Combinatorica 14 (1994) 111–114.
[LS81] L. Lovasz, A. Schrijver, Remarks on a theorem of Redei, Studia Scient. Math. Hungar. 16 (1981) 449–454.
[Szo99] T. Szönyi, Around Redei's theorem, Discrete Math, 208/209 (1999), 557-575.
[Red70] L. Rédei, Luckenhafte Polynome über endlichen Korpern, Birkhauser Verlag, Basel (1970) (English translation: Lacunary polynomials over finite fields, North-Holland, Amsterdam, 1973).
Lecture 3:
[DSW21] D. Di Benedetto, J. Solymosi, and E. P. White, On the directions determined by a Cartesian product in an affine Galois plane. Combinatorica, 41(6):755–763, 2021.
[HP21] B. Hanson, G. Petridis, Refined estimates concerning sumsets contained in the roots of unity, Proc. Lond. Math. Soc. (3) 122 (2021), no. 3, 353–358.
[Szo96] T. Szönyi, On the number of directions determined by a set of points in a Galois plane, J. Combin. Theory Ser. A 74 (1996) 141–146.
[Yip23] C. H. Yip, Refined Estimates on the clique number of cyclotomic graphs. ArXiv preprint available at https://arxiv.org/abs/2304.13213
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.
Materials
April 11, 2023
Lecture 1. A conjecture by van Lint & MacWilliams and its confirmation by Blokhuis
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
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
Lecture 2. EKR properties of graphs
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
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
Lecture 3.
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
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
Lecture 4. Extremal Peisert-type graphs without strict-EKR property
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
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
Lecture 1:
[1] A. Blokhuis, On subsets of GF(q^2) with square differences, Indag. Math. 46 (1984) 369--372.
[2] J. H. van Lint, F. J. MacWilliams, Generalized Quadratic Residue Codes, IEEE Transactions on Information Theory, IT 24, 730--737 (1978).
[3] L. Lovász, A. Schrijver, Remarks on a theorem of Rédei, Studia Scientiarum Mathematicarum Hungarica 16, 449--454 (1981).
[4] L. Rédei, Lűckenhafte Polynome űber endlichen Kőrpern, Birkhäuser Verlag, Base und Stuttgart, 1970.
Lecture 2:
[5] S. Asgarli, S. Goryainov, H. Lin, C. H. Yip, The EKR-module property of pseudo-Paley graphs of square order, The Electronic Journal of Combinatorics, 29(4) (2022), \#P4.33.
[6] C. D. Godsil, K. Meagher, Erdős-Ko-Rado Theorems: Algebraic Approaches, Cambridge University Press (2015).
Lecture 3:
[7] R. D. Baker, G. L. Ebert, J. Hemmeter, A. J. Woldar, Maximal cliques in the Paley graph of square order, J. Statist. Plann. Inference 56 (1996), 33–38.
[8] A. E. Brouwer, private communication.
[9] S. V. Goryainov, V. V. Kabanov, L. V. Shalaginov, A. A. Valyuzhenich, On eigenfunctions and maximal cliques of Paley graphs of square order, Finite Fields and Their Applications, Volume 52, 361--369, 2018.
[10] S. Goryainov, A. Masley, L. Shalaginov, On a correspondence between maximal cliques in Paley graphs of square order, Discrete Mathematics, Volume 345, Issue 6, June 2022, 112853.
[11] C. H. Yip, private communication.
Lecture 4:
[12] S. Asgarli, S. Goryainov, H. Lin, C. H. Yip, The EKR-module property of pseudo-Paley graphs of square order, The Electronic Journal of Combinatorics, 29(4) (2022), \#P4.33.
[13] C. H. Yip, Erdős—Ko—Rado theorem in Peisert-type graphs, arXiv:2302.00745
[14] S. Goryainov, C. H. Yip, Extremal Peisert-type graphs without strict-EKR property, The 8th Workshop "Algebraic Graph Theory and its Applications".
[1] A. Blokhuis, On subsets of GF(q^2) with square differences, Indag. Math. 46 (1984) 369--372.
[2] J. H. van Lint, F. J. MacWilliams, Generalized Quadratic Residue Codes, IEEE Transactions on Information Theory, IT 24, 730--737 (1978).
[3] L. Lovász, A. Schrijver, Remarks on a theorem of Rédei, Studia Scientiarum Mathematicarum Hungarica 16, 449--454 (1981).
[4] L. Rédei, Lűckenhafte Polynome űber endlichen Kőrpern, Birkhäuser Verlag, Base und Stuttgart, 1970.
Lecture 2:
[5] S. Asgarli, S. Goryainov, H. Lin, C. H. Yip, The EKR-module property of pseudo-Paley graphs of square order, The Electronic Journal of Combinatorics, 29(4) (2022), \#P4.33.
[6] C. D. Godsil, K. Meagher, Erdős-Ko-Rado Theorems: Algebraic Approaches, Cambridge University Press (2015).
Lecture 3:
[7] R. D. Baker, G. L. Ebert, J. Hemmeter, A. J. Woldar, Maximal cliques in the Paley graph of square order, J. Statist. Plann. Inference 56 (1996), 33–38.
[8] A. E. Brouwer, private communication.
[9] S. V. Goryainov, V. V. Kabanov, L. V. Shalaginov, A. A. Valyuzhenich, On eigenfunctions and maximal cliques of Paley graphs of square order, Finite Fields and Their Applications, Volume 52, 361--369, 2018.
[10] S. Goryainov, A. Masley, L. Shalaginov, On a correspondence between maximal cliques in Paley graphs of square order, Discrete Mathematics, Volume 345, Issue 6, June 2022, 112853.
[11] C. H. Yip, private communication.
Lecture 4:
[12] S. Asgarli, S. Goryainov, H. Lin, C. H. Yip, The EKR-module property of pseudo-Paley graphs of square order, The Electronic Journal of Combinatorics, 29(4) (2022), \#P4.33.
[13] C. H. Yip, Erdős—Ko—Rado theorem in Peisert-type graphs, arXiv:2302.00745
[14] S. Goryainov, C. H. Yip, Extremal Peisert-type graphs without strict-EKR property, The 8th Workshop "Algebraic Graph Theory and its Applications".
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.
Materials
October 4, 2022
Lecture 1. Geometry of knots and links
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
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
Lecture 2. Polyhedra in spaces of constant curvature
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
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
Lecture 3. Counting spanning forests and trees in a graph
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
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
Lecture 4. Isospectrality of Graphs and Riemann Surfaces
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
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
Lecture 5. Dessins d'enfants (maps on Riemann surfaces)
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
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
Lecture 1:
1. N. Abrosimov, A. Mednykh, Geometry of knots and links, IRMA Lectures in Mathematics and Theoretical Physics, 33, Topology and Geometry, 2021, 433–454.
2. A. D. Mednykh, B. Vuong, On hyperelliptic Euclidean 3-manifolds, J. Knot Theory Ramifications, 30:10 (2021) 2140001.
3. A. D. Mednykh, Volumes of two-bridge cone manifolds in spaces of constant curvature, Transform. Groups, 26:2 (2021) 601–629.
Lecture 2:
1. N. V. Abrosimov, A. D. Mednykh, Area and volume in non-Euclidean geometry. ighteen essays in non-Euclidean geometry, 151–189, IRMA Lect. Math. Theor. Phys., 29, Eur. Math. Soc., Zürich, 2019.
2. A. D. Mednykh, Brahmagupta formula for cyclic quadrilaterals in the hyperbolic plane, Sib. Elektron. Mat. Izv., 9 (2012), 247–255.
3. P. Buser, A. D. Mednykh, A. Yu. Vesnin, Lambert cubes and the Loebell polyhedron revisited, Adv. Geom., 12:3 (2012) 525–548.
4. A. A. Kolpakov, A. D. Mednykh, M. G. Pashkevich, Volume formula for a Z_2-symmetric spherical tetrahedron through its edge lengths, Ark. Mat., 51:1 (2013) 99–123.
Lecture 3:
1. A. D. Mednykh, I. A. Mednykh, The number of spanning trees in circulant graphs, its arithmetic properties and asymptotics, Discrete Math., 342 (2019) 1772–1781.
2. G. A. Baigonakova, A. D. Mednykh, Elementary formulas for Kirchhoff index of Mobius ladder and Prism graphs, Sib. Electron. Mat. Rep., 16 (2019) 1654–1661.
3. A. D. Mednykh, I. A. Mednykh, Kirchhoff index for circulant graphs and its asymptotics, Doklady Mathematics, 102:2 (2020) 392–395.
4. L. A. Grunwald, I. A. Mednykh, The number of rooted forests in circulant graphs, Ars Math. Contemp. 22 (2022) #P4.10.
Lecture 4:
1. A. D. Mednykh, I. A. Mednykh, Isospectral genus two graphs are isomorphic, Ars Math. Contemp., 10:2 (2016) 223–235.
2. A. K. Kel′mans, V. M. Chelnokov, A certain polynomial of a graph and graphs with an extremal number of trees. J. Combin. Theory, Ser. B 16, 197–214 (1974).
Lecture 5:
1. A. D. Mednykh, R. Nedela, Enumeration of unrooted maps of a given genus, J. Comb. Theory, Ser. B, 96:5 (2006) 706–729.
2. A. D. Mednykh, R. Nedela, Enumeration of unrooted hypermaps of a given genus, Discrete Math., 310:3 (2010) 518–526.
3. A. Breda, A. D. Mednykh, R. Nedela, Enumeration of maps regardless of genus: geometric approach, Discrete Math., 310:6-7 (2010) 1184–1203.
1. N. Abrosimov, A. Mednykh, Geometry of knots and links, IRMA Lectures in Mathematics and Theoretical Physics, 33, Topology and Geometry, 2021, 433–454.
2. A. D. Mednykh, B. Vuong, On hyperelliptic Euclidean 3-manifolds, J. Knot Theory Ramifications, 30:10 (2021) 2140001.
3. A. D. Mednykh, Volumes of two-bridge cone manifolds in spaces of constant curvature, Transform. Groups, 26:2 (2021) 601–629.
Lecture 2:
1. N. V. Abrosimov, A. D. Mednykh, Area and volume in non-Euclidean geometry. ighteen essays in non-Euclidean geometry, 151–189, IRMA Lect. Math. Theor. Phys., 29, Eur. Math. Soc., Zürich, 2019.
2. A. D. Mednykh, Brahmagupta formula for cyclic quadrilaterals in the hyperbolic plane, Sib. Elektron. Mat. Izv., 9 (2012), 247–255.
3. P. Buser, A. D. Mednykh, A. Yu. Vesnin, Lambert cubes and the Loebell polyhedron revisited, Adv. Geom., 12:3 (2012) 525–548.
4. A. A. Kolpakov, A. D. Mednykh, M. G. Pashkevich, Volume formula for a Z_2-symmetric spherical tetrahedron through its edge lengths, Ark. Mat., 51:1 (2013) 99–123.
Lecture 3:
1. A. D. Mednykh, I. A. Mednykh, The number of spanning trees in circulant graphs, its arithmetic properties and asymptotics, Discrete Math., 342 (2019) 1772–1781.
2. G. A. Baigonakova, A. D. Mednykh, Elementary formulas for Kirchhoff index of Mobius ladder and Prism graphs, Sib. Electron. Mat. Rep., 16 (2019) 1654–1661.
3. A. D. Mednykh, I. A. Mednykh, Kirchhoff index for circulant graphs and its asymptotics, Doklady Mathematics, 102:2 (2020) 392–395.
4. L. A. Grunwald, I. A. Mednykh, The number of rooted forests in circulant graphs, Ars Math. Contemp. 22 (2022) #P4.10.
Lecture 4:
1. A. D. Mednykh, I. A. Mednykh, Isospectral genus two graphs are isomorphic, Ars Math. Contemp., 10:2 (2016) 223–235.
2. A. K. Kel′mans, V. M. Chelnokov, A certain polynomial of a graph and graphs with an extremal number of trees. J. Combin. Theory, Ser. B 16, 197–214 (1974).
Lecture 5:
1. A. D. Mednykh, R. Nedela, Enumeration of unrooted maps of a given genus, J. Comb. Theory, Ser. B, 96:5 (2006) 706–729.
2. A. D. Mednykh, R. Nedela, Enumeration of unrooted hypermaps of a given genus, Discrete Math., 310:3 (2010) 518–526.
3. A. Breda, A. D. Mednykh, R. Nedela, Enumeration of maps regardless of genus: geometric approach, Discrete Math., 310:6-7 (2010) 1184–1203.
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.
Materials
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.
References
- 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.
References
- 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
Contacts
Organizer
e_konsta@math.nsc.ru
e_konsta@math.nsc.ru
Organizer
goryainov@hebtu.edu.cn
goryainov@hebtu.edu.cn
Nikolay Abrosimov
Organizer
abrosimov@math.nsc.ru
abrosimov@math.nsc.ru
Supported by Mathematical Center in Akademgorodok under agreement No. 075-15-2022-281 with the Ministry of Science and Higher Education of the Russian Federation