Coloquio del IMUNAM - C. U., octubre 2025

The Role of Symmetry in Extremal Graph Theory
Robert Jajcay, Comenius University, Bratislava, Slovakia

https://www.matem.unam.mx/actividades/coloquio/cu/actividades/the-role-of-symmetry-in-extremal-graph-theory

Resumen:

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.

Coloquio del IMUNAM - C. U., octubre 2025

Auditorio Alfonso Nápoles Gándara