Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

Algebraic Graph Theory International Webinar (21.6.2022)

v utorok 21.6.2022 o 19:00 hod.

20. 06. 2022 08.45 hod.
Od: Róbert Jajcay

The organizers of the Algebraic Graph Theory International Webinar would like to invite you to join us and other colleagues on June 21, 2022, at 7pm Central European Summer Time (= 5pm UTC), for the next presentation delivered by Martin Macaj. 

The title of Martin's talk: On the defect of vertex-transitive graphs of given degree and diameter

The Degree/Diameter Problem is the problem of finding the largest order n(Delta,D) of a graph of maximum degree Delta and diameter D. The well-known Moore bound, M(Delta,D)=1+Delta((Delta-1)^D-1)/(Delta-2), provides a natural upper bound on n(Delta,D), and graphs that attain this bound are called Moore graphs. To avoid trivialities we will assume Delta > 2 and D > 1, in which case Moore graphs are very rare. Any graph G of maximum degree Delta and diameter D (a (Delta,D)-graph) is said to have the defect delta(G) = M(Delta,D) - |V(G)|.

We present bounds on the number of cycles of length 2D+1 in graph with prescribed degree Delta, diameter D and defect delta which besides the term Delta(Delta-1)^D/2 depend only on degree Delta and defect delta.

Using two classical number theory results due to Niven and Erdos, we prove that for any fixed degree Delta > 2 and any positive integer delta, the order of a largest vertex-transitive Delta-regular graph of diameter D differs from the Moore bound by more than delta for (asymptotically) almost all diameters D > 1. We also obtain an estimate for the growth of this difference, or defect, as a function of D.

This talk is based on a joint work with G. Exoo, R. Jajcay and J. Siran.

The Zoom link for this semester is: 
Meeting ID: 871 9332 0713
Passcode: 653250

Further details may be found at http://euler.doa.fmph.uniba.sk/AGTIW.html

where you can also find the slides and the recordings of our previous presentations. Also, if you wish to advertise an AGT friendly conference on this page, please send us the link.  

Hoping to see you at the webinar, and wishing you all the best. 

Isabel HubardRobert Jajcay and Primoz Potocnik