Structural Graph Theory and Additive Combinatorics

点击翻译按钮获取中文摘要

My primary research area is structural graph theory. This is a deep mathematical subject with important ties to real world problems. For instance, one of the foundational theorems of this subject is the Kuratowski-Wagner Theorem which characterizes exactly which graphs can be drawn in the plane without crossings. Not only is this a beautiful mathematical theorem in its own right, it is also a vital concept when creating circuit boards: The networks that can be constructed on one side of a circuit board are precisely those which have such a drawing. More generally, networks are ubiquitous objects in the modern world (the internet, social networks, road networks, etc.) and abstract theorems which give global information about their structure can be powerful tools. Structural graph theory has developed tremendously over the past half century, and some aspects of this theory are now quite well established and understood. Notably, there is a grand (albeit rough) generalization of the Kuratowski-Wagner theorem due to Robertson and Seymour which gives a global description of all graphs not containing a certain substructure called a forbidden minor. This deep theorem has profound consequences in graph theory, significant connections to other subjects in mathematics, as well as applications in the form of new graph algorithms. Although the structure of graphs with a forbidden minor is now well-established, there are many important avenues still to explore. The primary long-term goal of my research program is to establish powerful new structure theory to transform our understanding of graphs, directed graphs, and other combinatorial objects. One aim is to determine the structure of a graph not containing another type of substructure called a forbidden immersion. This is a natural analogue of the Robertson-Seymour theory that could have similarly broad based impact. Another aim is to improve our structural understanding of small product sets. This is a subject in additive combinatorics which is intimately related to graph theory, but also has important connections to many other parts of mathematics. My short-term objectives are to pursue structure theory in three settings. First, I hope to prove a global structure theorem for any k-edge-connected graph G not containing a fixed graph H of maximum degree k as an immersion. This is an important step in realizing the long-term goal of an effective structure theory for forbidden immersions. A second goal is to establish a strong structure theorem for pairs of sets A,B in a group for which |AB| < |A| + |B| + c for a fixed constant c. Such a theorem would be highly influential within additive combinatorics. Last but not least, I plan to study expansion in graphs by adapting some tools from combinatorial group theory. This is a first step toward a structural understanding of directed graphs with small growth.