PECTA · Extremal Problems in Combinatorics and Their Applications
7РП — „Хора“ (Действия „Мария Кюри“)
- Период
- 2012-04-01 → 2016-03-31
- Финансиране от ЕС
- 100 000 €
- Участници
- 1
- Схема
- MC-CIG
Линиите свързват координатора с партньорите.
Накратко на български
Екстремалните проблеми в комбинаториката изследват границите на математически структури, като например оптималното разделяне на графи на подграфи. Тези открития помагат за създаването на по-ефективни алгоритми и по-доброто разбиране на теорията на хиперграфите.
Кратко обяснение, генерирано от езиков модел по текста на CORDIS. Оригиналът е по-долу.
Резултати накратко
Extremal Problems in Combinatorics and Their Applications
The main objective of the present CIG grant was to facilitate my integration into Tel-Aviv University as a permanent faculty member and to help me build a successful research group. As I elaborate below, I think that in both cases the outcomes were positive. First, I was promoted to the rank of Associate Professor with tenure about 3 years ago. Second, last year I received an ERC-Starting grant. Third, I now have 2 PhD students, 2 Post-doc researchers and 2 MSc students. Our joint projects have resulted in publications in some of the top mathematical journals. Let me describe 4 of the main results we obtained in the past 2 years. 1. In a joint work with my PhD student G. Moshkovitz and with Lovett-Hosseini we improved a result of B. Greene by proving a tight lower bound for the arithmetic regularity lemma. 2. I a joint work with my PhD student G. Moshkovitz we proved a general result on the limitations of partions of a graph into expanding subgraphs. This general result allowed us to prove that numerous results in pure and algorithmic graph theory are optimal. 3. In a joint work with my MSc student L. Gishboliner we resolved an open problem of Lovasz and Vesztergombi regarding efficient algorithms called property testers. This is related to the fastly growing are of graph limits. 4. In a joint work with my PhD student G. Moshkovitz we resolved an open problem raised by Fox-Pach-Sudakov-Suk regarding a general Ramsey-type problem in the theory of hypergraphs.
Текст от CORDIS, на английски · Данни: CORDIS, © Европейски съюз
Цел на проекта
In this proposal we describe a variety of problems in Extremal Combinatorics which we intend to study. These problems belong to the following two areas:1. Additive Combinatorics: We intend to investigate different aspects of Green's variant of the classical Removal Lemma from Graph Theory.Besides being a fundamental problem, we have recently shown that certain variants of Green's result have applications in Theoretical Computer Science. We are working on extending this work to more general settings with the hope of resolving several open problems.2. Quasi-Randomness: The theory of Quasi-Randomness is one of the most interesting ways in which combinatorics interacts with other areas ofmathematics. The main goal is to come up with conditions under which deterministic structures behave like random ones. This concept turned out to be extremely useful for tackling a variety of open problems in different areas. We intend to consider several problem related to graphs and hypergraphs and to further extend this theory.
Оригинален текст от CORDIS (на английски).
Участници
- TEL AVIV UNIVERSITY · Tel AvivКоординаторИзраел
Връзки
Данни: CORDIS, © Европейски съюз