Algebraic Graph Theory Seminar - György Kiss (10.5.2024)

Friday 10.5.2024 at 13:00, Lecture room M/IX (online too)

---

György Kiss (ELTE, Budapest, Hungary and University of Primorska, Koper, Slovenia):
Geometric constructions of small regular graphs with girth 5 and 7

Abstract:
The cage problem is a classical problem in extremal graph theory. A (k,g)-graph is a k-regular graph with girth g. A (k,g)-cage is a (k,g)-graph of minimum order. A general lower bound on n(k,g), known as the Moore bound, is obtained by counting the vertices whose distance from a vertex (if g is odd), or an edge (if g is even) is at most |(g-1)/2|. Graphs attaining this bound are called Moore graphs. For g=3,4 Moore graphs are the complete, and complete bipartite graphs, respectively. Moore graphs are rare for g>4. When g is even, then there exists a k-regular Moore graph with girth g=2r>4 if and only if there exists a finite generalized r-gon of order (k-1,k-1), and the graphs are the incidence graphs of the generalized polygons. When g>4 odd, then there exist Moore graphs only for g=5 and k=3,7 and possibly 57.
 When g=5, several graphs were constructed by complicated manipulations of the incidence graph of PG(2,q), the finite projective plane of order q. Some vertices are removed from these (q+1,6)-cages, after that matchings or cycles are added to the neighbours of the removed vertices to get back regularity.
In this talk we briefly summarize the most important geometric properties of generalized quadrangles, projective, affine and biaffine planes and present some simple constructions for small (k,5)- and (k,7)-graphs.

Those of you who are not able to attend in person or who are still uncertain about the safety of attending in person are welcome to attend via MS Teams. In either case, we hope to see as many of you as possible (either in person or virtually) at our Friday gatherings.

 

 

---