Graph structure, Vertex-minors, and Logic

A graph is a mathematical object that models real-life networks such as road networks, communication networks, and supply networks. In structural graph theory, the goal is to understand the large-scale behavior of graphs whose local behavior is somehow restricted. This project focuses on developing structural techniques for dense graphs, that is, graphs with many connections. The PI will focus on two ways of restricting the local behavior: by forbidding a vertex-minor, and by asking for a dependent first-order theory. These restrictions have applications to other domains such as quantum computing, algorithms and complexity, discrete geometry, and extremal combinatorics. Graduate students will be trained as part of the project. This project will develop structural techniques for dense classes of graphs, focusing on classes with a forbidden vertex-minor or a dependent first-order theory. For classes with a forbidden vertex-minor, the goal is to obtain a complete understanding of the structure relative to a tour graph. This will be a key step towards proving a conjecture of Geelen, which would give a very precise structural description of graphs with a forbidden vertex-minor. For classes with a dependent first-order theory, the focus is on a well-known dichotomy conjecture. This conjecture roughly states that for classes that are closed under vertex deletion, having a dependent first-order theory is equivalent to admitting an efficient algorithm for checking the first-order properties of graphs in the class. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.