Menu
MapConnectionsTopicsBulgariaThe Night (K-TRIO)Marie Skłodowska-CurieFor studentsFor teachersMethodologySurprise me
HEIndividual fellowship2023–2025

BORCA · Borel combinatorics and Approximations

Horizon Europe — Marie Skłodowska-Curie Actions

Duration
2023-08-01 → 2025-09-30
EU contribution
€196,102
Participants
3
Scheme
HORIZON-TMA-MSCA-PF-GF

Lines connect the coordinator with its partners.

Results in brief

Borel combinatorics and Approximations

This project concerns research on the boundary between analysis, logic and combinatorics, more specifically, investigates problems in descriptive set theory and their interactions with measure theory, dynamical systems, computer science and graph limits, through the study of measurability properties of combinatorial problems on infinite graphs. The basic objects of study in descriptive set theory are constructible (definable) subsets of the real line, more abstractly, objects that can be encoded with a countably infinite amount of information. Such objects are ample throughout mathematics which makes descriptive set theory a versatile tool for combining various techniques and perspectives from different areas, and providing connections between seemingly unrelated problems. An important aspect of combinatorial problems on finite graphs, motivated by applications in computer science, is to understand when there is an efficient algorithm that computes a solution. Embracing these algorithmic aspects of graph problems in the study of infinite graphs in recent years led to novel methods and breakthrough results. The main goal of this project will be to exploit and further develop this connection with particular emphasis on applications to the study of the central questions of descriptive set theory. Particular topics that are studied in the project concern problems around approximations of analytic objects such as (Borel) hyperfiniteness and graph limits, as well as some classical tiling problems in Euclidean spaces.

Data: CORDIS, © European Union

Project objective

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.

Original text from CORDIS.

Participants

  • UNIVERSITAET LEIPZIG · LeipzigCoordinatorGermany
  • Masarykova univerzita · BrnoCzechia
  • THE REGENTS OF THE UNIVERSITY OF CALIFORNIA · OaklandUnited States

Links

Data: CORDIS, © European Union