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.
