GeoScape
Financiado
From Geometry to Combinatorics and Back Escaping the Curse of Dimensionality
"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 combina...
"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."
ver más
Duración del proyecto: 66 meses
Fecha Inicio: 2020-08-17
Fecha Fin: 2026-02-28
Fecha Fin: 2026-02-28
Línea de financiación: concedida
El organismo H2020 notifico la concesión del proyecto el día 2020-08-17
Línea de financiación objetivo
El proyecto se financió a través de la siguiente ayuda:
ERC-2019-ADG:
ERC Advanced Grant
Cerrada
hace 5 años
Presupuesto
El presupuesto total del proyecto asciende a
2M€
Líder del proyecto
HUNREN RENYI ALFRED MATEMATIKAI KUTATOINTEZET
No se ha especificado una descripción o un objeto social para esta compañía.
Perfil tecnológico
TRL
4-5
Perfil tecnológico
TRL
4-5
189.69K€ |
Participante