BORCA · Borel combinatorics and Approximations

Infinite graphs and their combinatorics model large real-life networks, like the internet, but are also an essential tool to understand mathematical structures that are intrinsically infinite, like the geometry of the Euclidean spaces. The project concerns research in descriptive set theory and its interactions with measure theory, dynamical systems, graph limits and theoretical computer science through the study of regularity properties of combinatorial problems on infinite graphs. These considerations played a fundamental role in the spectacular results on the circle squaring problem and form a new field, measurable graph theory.In the last years, an explosion of activity has brought new exciting ideas to this field: formal connections with the theory of distributed computing and random processes, the notion of asymptotic dimension from geometric group theory, or a generalization of the determinacy method of Marks. These ideas have already found several groundbreaking applications and are highly promising in gaining new perspectives on old problems. We propose to employ, combine and further develop these methods with particular emphasis on applications to the study of central questions of descriptive set theory, that is, Borel hyperfiniteness, equidecomposition problems, or the abstract classification problem, as well as on finding new links and applications to classical graph theory, in particular, to algorithmic aspects of partition problems on finite graphs.The fellowship will be carried out over 26 months: 14 at UCLA, 6 at MU and 6 at Leipzig University. The supervisors, Itay Neeman at UCLA and Dan Kráľ, currently at Masaryk University and moving to Leipzig University in April 2025, are leading figures in their respective fields of interest, descriptive set theory and combinatorics. Together with the expertise of the fellow, the project promises a unique potential for bridging these fields, solving deep problems in both areas, developing the fellow's research profile and bringing the contemporary trends of descriptive set theory to Central Europe.