Ponente: Robert Jajcay
Institución: Comenius University, Bratislava, Slovakia
07/10/2025
de 12:00 a 13:00
Dónde Auditorio "Alfonso Nápoles Gándara"
The majority of problems in Extremal Graph Theory call for optimization of one of several inter-related graph theoretical parameters within a class of graphs specified via these parameters. Even though the parameters most often do not include any restriction on the number of symmetries of the considered graphs, optimal or extremal members of the class nevertheless exhibit a large number of symmetries. This phenomenon is not fully understood, but appears connected to the `mysterious' effectiveness of the use of mathematics in real world applications.
In our talk, we will investigate the role of symmetries in the optimization of orders of graphs with prescribed degree and diameter (the Degree/Diameter Problem) or prescribed degree and girth (the Cage Problem). We will consider both the original problems that do not put any restrictions on the automorphism groups of the considered graphs, as well as restrictions of the original problems to the classes of vertex-transitive or Cayley graphs.