Structure in complex graphs

• Applicant: Dr. Raphael Mario Steiner
• Subject Area: Mathematics ; Theoretical Computer Science
• Term: since 2026
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 580116532

A universal meta-phenomenon in mathematics, studied across various disciplines (chaos theory, ergodic theory, statistical mechanics, combinatorics, …), is the emergence and necessity of structure in very complex and seemingly chaotic mathematical objects. Three important branches of combinatorics study this phenomenon from different angles: (1) The chromatic number is one of the most important complexity measures for graphs, whose roots go back almost two centuries. Guided by the above-mentioned meta-phenomenon, there has been much research on structure(s) that can be found in all graphs whose high complexity is certified by their high chromatic number. This line of research has a rich history and remains highly active, with many recent advances. (2) One of the most fundamental results in discrete mathematics is Ramsey's theorem from 1929. It states that in any, arbitrarily complex, partition of the edges of a large complete graph into a fixed number of parts, a copy of any given graph can always be found in one of the blocks of the partition. Ramsey's theorem marks the birth of a much broader and flourishing subfield of combinatorics, Ramsey theory, which studies structure in complex partitions of discrete objects. (3) Paths and cycles are amongst the most ubiquitous objects in graph theory and the related theory of Hamiltonicity forms one of its oldest branches. A typical question in this area seeks conditions which guarantee to find a large structured subgraph, concretely a long path or a long cycle, in a given, possibly very complex, graph. Despite lots of attention, our understanding of (the structure of) long paths and cycles remains limited today. The overarching goal of this project is to make substantial progress on selected open problems from each of these areas, thereby advancing our understanding of structure in complex graphs and eventually also making a significant contribution to the meta-question mentioned at the beginning. Concrete objectives include: - Tackling longstanding open problems on structure in and of graphs with high chromatic number, including progress on Hadwiger’s famous coloring conjecture from 1943. - Solution of central open problems on Ramsey properties of random discrete structures. - Progress on longstanding open problems on the structure of longest paths and cycles in graphs, with direct applications to a famous conjecture by Lovász from 1969.

• DFG Programme: Emmy Noether Independent Research Groups