Summary
"Combinatorics is a fundamental mathematical discipline whose study has experienced unprecedented growth during the past few decades. Its rapid development can be partially explained by spectacular applications of extremal combinatorics in additive number theory, information theory, theoretical computer science, and elsewhere. Asymptotic results in extremal and probabilistic combinatorics have proved to be powerful tools in the structural and algorithmic analysis of huge networks such as the internet graph, brain maps, social networks, and integrated circuits. We have deep, well developed algebraic, topological, and probabilistic techniques to tackle some basic problems of modern combinatorics, but many classic Ramsey-, Turán-, and Szemerédi-type questions remained open.
The main goal of the proposed work is to attack some hard problems for large classes of graphs and hypergraphs arising in geometric, algebraic, and practical applications. These structures escape the ""curse of dimensionality”: they can be embedded in a bounded-dimensional space, or they have small VC-dimension, or a short algebraic description. The work of the principal investigator, his collaborators and students has played a significant role in the introduction of modern combinatorial tools in geometry. In the present project, he aims to explore the reverse direction: to develop and apply geometric techniques to settle important special cases of notoriously difficult combinatorial problems on (1) bounded degree semi-algebraic graphs and hypergraphs, (2) graphs and hypergraph of bounded VC-dimension, (3) ordered graphs, 0-1 matrices, and graphs embedded in the plane or in other surfaces. Progress on the problems described in the proposal is expected to lead closer to the solution of some classical problems such as the Erdős-Hajnal conjecture, the Danzer-Rogers conjecture, the Schur-Erdős problem, and to the development of improved algorithms for clustering and property testing in huge graphs."
The main goal of the proposed work is to attack some hard problems for large classes of graphs and hypergraphs arising in geometric, algebraic, and practical applications. These structures escape the ""curse of dimensionality”: they can be embedded in a bounded-dimensional space, or they have small VC-dimension, or a short algebraic description. The work of the principal investigator, his collaborators and students has played a significant role in the introduction of modern combinatorial tools in geometry. In the present project, he aims to explore the reverse direction: to develop and apply geometric techniques to settle important special cases of notoriously difficult combinatorial problems on (1) bounded degree semi-algebraic graphs and hypergraphs, (2) graphs and hypergraph of bounded VC-dimension, (3) ordered graphs, 0-1 matrices, and graphs embedded in the plane or in other surfaces. Progress on the problems described in the proposal is expected to lead closer to the solution of some classical problems such as the Erdős-Hajnal conjecture, the Danzer-Rogers conjecture, the Schur-Erdős problem, and to the development of improved algorithms for clustering and property testing in huge graphs."
Unfold all
/
Fold all
More information & hyperlinks
| Web resources: | https://cordis.europa.eu/project/id/882971 |
| Start date: | 01-09-2020 |
| End date: | 28-02-2026 |
| Total budget - Public funding: | 2 009 433,75 Euro - 2 009 433,00 Euro |
Cordis data
Original description
"Combinatorics is a fundamental mathematical discipline whose study has experienced unprecedented growth during the past few decades. Its rapid development can be partially explained by spectacular applications of extremal combinatorics in additive number theory, information theory, theoretical computer science, and elsewhere. Asymptotic results in extremal and probabilistic combinatorics have proved to be powerful tools in the structural and algorithmic analysis of huge networks such as the internet graph, brain maps, social networks, and integrated circuits. We have deep, well developed algebraic, topological, and probabilistic techniques to tackle some basic problems of modern combinatorics, but many classic Ramsey-, Turán-, and Szemerédi-type questions remained open.The main goal of the proposed work is to attack some hard problems for large classes of graphs and hypergraphs arising in geometric, algebraic, and practical applications. These structures escape the ""curse of dimensionality”: they can be embedded in a bounded-dimensional space, or they have small VC-dimension, or a short algebraic description. The work of the principal investigator, his collaborators and students has played a significant role in the introduction of modern combinatorial tools in geometry. In the present project, he aims to explore the reverse direction: to develop and apply geometric techniques to settle important special cases of notoriously difficult combinatorial problems on (1) bounded degree semi-algebraic graphs and hypergraphs, (2) graphs and hypergraph of bounded VC-dimension, (3) ordered graphs, 0-1 matrices, and graphs embedded in the plane or in other surfaces. Progress on the problems described in the proposal is expected to lead closer to the solution of some classical problems such as the Erdős-Hajnal conjecture, the Danzer-Rogers conjecture, the Schur-Erdős problem, and to the development of improved algorithms for clustering and property testing in huge graphs."
Status
SIGNEDCall topic
ERC-2019-ADGUpdate Date
27-04-2024
Images
No images available.
Geographical location(s)
