Structure and Randomness in Extremal Combinatorics

• Applicant: Professor Dr. Stefan Glock
• Subject Area: Mathematics
• Term: since 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 542321564

One of the most fascinating phenomena in discrete mathematics, and other areas of mathematics as well, is the interplay of structure and randomness, which manifests itself in many different guises. Objects that are purely deterministic by nature, for example the prime numbers, can still exhibit a very random behavior. The probabilistic method is an intriguing way to show existence of a certain structure, by designing a suitable probability space in which the desired structure appears with positive probability. The regularity lemma allows to split graphs into a structured part and a random part. Understanding the interplay of structure and randomness has already been very fruitful. On the other hand, many aspects of it remain mysterious. The overarching goal of this project is, put simply, to gain more understanding of it, specifically with regards to extremal combinatorics, and by doing so solve major open problems in this field. The fundamental questions which shall be investigated, captured through several concrete problems, are for instance: What are the thresholds for the emergence of certain substructures in random models? Can we formulate pseudorandom versions of such results? How can we blend structural and probabilistic arguments together to split given graphs into pieces that inherit important properties, such as high connectivity? Can a structure be partitioned in a perfectly balanced way, or will there always be some discrepancy? Can we decompose hypergraphs with certain cut properties into a random part and a structured part? Answering these questions will not only require the solution of major research problems, but also the development of novel methods which will be beneficial beyond the scope of this project. While the main focus lies on extremal and probabilistic combinatorics, there is also a significant overlap with other areas like structural graph theory and theoretical computer science.

• DFG Programme: Independent Junior Research Groups