Page 283 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 283
EXTREMAL AND PROBABILISTIC COMBINATORICS (MS-20)
A solution to Erdo˝s and Hajnal’s odd cycle problem
Richard Montgomery, r.h.montgomery@bham.ac.uk
University of Birmingham, United Kingdom
Coauthor: Hong Liu
This talk will address how to construct cycles of many different lengths in graphs, in particular
answering the following two problems on odd and even cycles. Erdo˝s and Hajnal asked in 1981
whether the sum of the reciprocals of the odd cycle lengths in a graph diverges as the chromatic
number increases, while, in 1984, Erdo˝s asked whether there is a constant C such that every
graph with average degree at least C contains a cycle whose length is a power of 2.
This is joint work with Hong Liu.
Counting transversals in group multiplication tables
Rudi Mrazovic´, Rudi.Mrazovic@math.hr
University of Zagreb, Croatia
Coauthors: Sean Eberhard, Freddie Manners
Hall and Paige conjectured in 1955 that the multiplication table of a finite group G has a
transversal (a set of |G| cells in distinct rows and columns and having different symbols) if and
only if G satisfies a straightforward necessary condition. This was proved in 2009 by Wilcox,
Evans, and Bray using the classification of finite simple groups and extensive computer algebra.
I will discuss joint work with Sean Eberhard and Freddie Manners in which we approach the
problem in a more analytic way that enables us to asymptotically count transversals.
Recent advances in Ramsey theory
Dhruv Mubayi, mubayi@uic.edu
University of Illinois at Chicago, United States
For many decades, randomness has been the central idea to address the question of determining
growth rates of graph Ramsey numbers. Recently, we proved a theorem which suggests that
“pseudo-randomness” and not complete randomness may in fact be a more important concept
for this area. Consequently, we reduce one of the main open problems in graph Ramsey theory
to the possibly simpler question of constructing certain pseudorandom graphs. This new con-
nection widens the possibility to use tools from algebra, geometry, and number theory to address
the fundamental questions in Ramsey theory. This is joint work with Jacques Verstraete.
281
A solution to Erdo˝s and Hajnal’s odd cycle problem
Richard Montgomery, r.h.montgomery@bham.ac.uk
University of Birmingham, United Kingdom
Coauthor: Hong Liu
This talk will address how to construct cycles of many different lengths in graphs, in particular
answering the following two problems on odd and even cycles. Erdo˝s and Hajnal asked in 1981
whether the sum of the reciprocals of the odd cycle lengths in a graph diverges as the chromatic
number increases, while, in 1984, Erdo˝s asked whether there is a constant C such that every
graph with average degree at least C contains a cycle whose length is a power of 2.
This is joint work with Hong Liu.
Counting transversals in group multiplication tables
Rudi Mrazovic´, Rudi.Mrazovic@math.hr
University of Zagreb, Croatia
Coauthors: Sean Eberhard, Freddie Manners
Hall and Paige conjectured in 1955 that the multiplication table of a finite group G has a
transversal (a set of |G| cells in distinct rows and columns and having different symbols) if and
only if G satisfies a straightforward necessary condition. This was proved in 2009 by Wilcox,
Evans, and Bray using the classification of finite simple groups and extensive computer algebra.
I will discuss joint work with Sean Eberhard and Freddie Manners in which we approach the
problem in a more analytic way that enables us to asymptotically count transversals.
Recent advances in Ramsey theory
Dhruv Mubayi, mubayi@uic.edu
University of Illinois at Chicago, United States
For many decades, randomness has been the central idea to address the question of determining
growth rates of graph Ramsey numbers. Recently, we proved a theorem which suggests that
“pseudo-randomness” and not complete randomness may in fact be a more important concept
for this area. Consequently, we reduce one of the main open problems in graph Ramsey theory
to the possibly simpler question of constructing certain pseudorandom graphs. This new con-
nection widens the possibility to use tools from algebra, geometry, and number theory to address
the fundamental questions in Ramsey theory. This is joint work with Jacques Verstraete.
281
