Graph Partitions and their Applications

Worcester Polytechnic Institute, Worcester MA

Investigators

Abstract

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.