Summary
Extremal and probabilistic combinatorics is a central and currently maybe the most active and fastest growing area in discrete mathematics. The field can be traced back to the work of Turán and it was established by Erdős through his fundamental contributions and his uncounted guiding questions. Since then it has grown into an important discipline with strong ties to other mathematical areas such as theoretical computer science, number theory, and ergodic theory.
The PI proposes a variety of extremal problems for hypergraphs and for sparse random and pseudorandom graphs. The work for hypergraphs is motivated by Turán’s problem, maybe the most prominent open problem in the area. After solving an analogous question for graphs, Turán asked to determine the maximum cardinality of a set E of three-element subsets of a given n-element set V such that for any 4 elements of V at least one triple is missing in E. This innocent looking problem seems to be out of reach by our current methods and despite a great deal of effort over the last 70 years, our knowledge is still very limited.
We suggest a variant of the problem by imposing additional restrictions on the distribution of the three-element subsets in E. These additional assumptions yield a finer control over the corresponding extremal problem. In fact, this leads to many interesting and hopefully more manageable subproblems, some of which were already considered by Erdős and Sós. We suggest a unifying framework for these problems and one of the main goals would be the development of new techniques for this type of problems. These additional assumptions on the hyperedge distribution are closely related to the theory of quasirandom discrete structures, which was pioneered by Szemerédi and became a central theme in the field. In fact, the hypergraph extension by Gowers and by Rödl et al. of the regularity lemma provide essential tools for this line of research.
The PI proposes a variety of extremal problems for hypergraphs and for sparse random and pseudorandom graphs. The work for hypergraphs is motivated by Turán’s problem, maybe the most prominent open problem in the area. After solving an analogous question for graphs, Turán asked to determine the maximum cardinality of a set E of three-element subsets of a given n-element set V such that for any 4 elements of V at least one triple is missing in E. This innocent looking problem seems to be out of reach by our current methods and despite a great deal of effort over the last 70 years, our knowledge is still very limited.
We suggest a variant of the problem by imposing additional restrictions on the distribution of the three-element subsets in E. These additional assumptions yield a finer control over the corresponding extremal problem. In fact, this leads to many interesting and hopefully more manageable subproblems, some of which were already considered by Erdős and Sós. We suggest a unifying framework for these problems and one of the main goals would be the development of new techniques for this type of problems. These additional assumptions on the hyperedge distribution are closely related to the theory of quasirandom discrete structures, which was pioneered by Szemerédi and became a central theme in the field. In fact, the hypergraph extension by Gowers and by Rödl et al. of the regularity lemma provide essential tools for this line of research.
Unfold all
/
Fold all
More information & hyperlinks
| Web resources: | https://cordis.europa.eu/project/id/724903 |
| Start date: | 01-10-2017 |
| End date: | 30-09-2022 |
| Total budget - Public funding: | 1 800 000,00 Euro - 1 800 000,00 Euro |
Cordis data
Original description
Extremal and probabilistic combinatorics is a central and currently maybe the most active and fastest growing area in discrete mathematics. The field can be traced back to the work of Turán and it was established by Erdős through his fundamental contributions and his uncounted guiding questions. Since then it has grown into an important discipline with strong ties to other mathematical areas such as theoretical computer science, number theory, and ergodic theory.The PI proposes a variety of extremal problems for hypergraphs and for sparse random and pseudorandom graphs. The work for hypergraphs is motivated by Turán’s problem, maybe the most prominent open problem in the area. After solving an analogous question for graphs, Turán asked to determine the maximum cardinality of a set E of three-element subsets of a given n-element set V such that for any 4 elements of V at least one triple is missing in E. This innocent looking problem seems to be out of reach by our current methods and despite a great deal of effort over the last 70 years, our knowledge is still very limited.
We suggest a variant of the problem by imposing additional restrictions on the distribution of the three-element subsets in E. These additional assumptions yield a finer control over the corresponding extremal problem. In fact, this leads to many interesting and hopefully more manageable subproblems, some of which were already considered by Erdős and Sós. We suggest a unifying framework for these problems and one of the main goals would be the development of new techniques for this type of problems. These additional assumptions on the hyperedge distribution are closely related to the theory of quasirandom discrete structures, which was pioneered by Szemerédi and became a central theme in the field. In fact, the hypergraph extension by Gowers and by Rödl et al. of the regularity lemma provide essential tools for this line of research.
Status
CLOSEDCall topic
ERC-2016-COGUpdate Date
27-04-2024
Images
No images available.
Geographical location(s)
