Gabor Sarkozy - US grants

Extremal Problems in Graph Theory

The PI plans to continue his research in the area of developing
and applying a method in extremal graph theory based on the
Regularity Lemma and the Blow-up Lemma. The method finds certain
special subgraphs in dense graphs. The main idea of the method is
to reduce the general embedding problem in the original graph to
embedding into (Szemeredi-) regular graphs. For the purpose of
finishing the embedding once this reduction is achieved, a general
tool, called the Blow-up Lemma, was developed to find bounded
degree spanning subgraphs in these regular graphs. The PI proposes
to develop this method further. He plans to improve on some of
earlier applications of the method, to apply the method to new
problems, and to extend it into new directions.

This research is in the area of extremal combinatorics. The
central question of this field has the following form: determine
the maximum (or minimum) size of a discrete mathematical object
that satisfies a certain condition. It turns out that this general
topic has connections to very diverse fields (geometry, design
theory, number theory, algebra, topology, etc.) and to areas with
important concrete applications in everyday life (computer
science, coding theory, cryptography, optimization and scheduling
problems, communication and networking problems, etc.). Therefore
the broader impact of this proposal is that developing the method
further and achieving results on the proposed research problems
will have serious implications in these applications as well.

Recently graph partitioning (clustering) algorithms have received a lot of attention because of their applications in data mining and web search. In this proposal the PI will focus on graph partitions and their applications. The PI will continue his research in the area of developing and applying a method in extremal graph theory based on the Regularity Lemma and the Blow-up Lemma. Roughly speaking here the Regularity Lemma finds the graph partition and then the Blow-up Lemma tells us how to use this partition. A recent development on the method is the new "de-regularization" technique that helps to eliminate the use of the Regularity Lemma from these proofs, while maintaining other key elements, and thus the results are much more applicable (since the Regularity Lemma applies only for very large graphs).

This research is in the area of extremal discrete mathematics. The fundamental question of this field has the following form: determine the maximum (or minimum) size of a discrete mathematical object that satisfies a certain condition. It turns out that this general problem has connections to very diverse fields (geometry, design theory, number theory, algebra, topology, etc.) and to areas with important concrete applications in everyday life (computer science, coding theory, cryptography, optimization and scheduling problems, communication and networking problems, etc.). Therefore achieving results on these research problems will have serious implications in these applications as well.

The Alfred Renyi Institute of Mathematics, together with the Hungarian Academy of Sciences, the Eotvos Lorand University and the Janos Bolyai Mathematical Society are organizing a conference in the summer of 2013 to celebrate the 100th birthday of Paul Erdos, one of the most influential mathematicians of the 20th century. The conference will be held July 1-5, 2013, in Budapest, Hungary, in the historical building of the Hungarian Academy of Sciences. There will be only invited talks by outstanding mathematicians who will create a scientic program with intellectual merit on a par with Erdos's incredible research achievements. Invited speakers who have accepted our invitation include several winners of the Fields Medal, Wolf Prize, Nevanlinna Prize, and other major prizes. One of our underlying goals, in addition to honoring Paul Erdos, is to bring together these exceptional researchers and study the relationships between their work and Erdos's work. We are confident that the meeting will inspire new insights and further collaborations from these "mathematical giants". There is no doubt that Erdos's work will continue to be the source of beautiful developments in mathematics and in other fields.