Spectral and Extremal Graph Theory

Villanova University, Villanova PA

Investigators

Abstract

This project is in graph theory, where properties and structures of a network are explored. The PI will focus on extremal graph theory which attempts to quantify what combinatorial properties a graph must have when it gets large (where size can be defined by several graph parameters, each giving an interesting theory). The project has two main thrusts. First to study classical Turan and Ramsey theory, two central areas in combinatorics. And second to study extremal problems in spectral graph theory, where one uses linear algebra to deduce combinatorial properties of the graph via matrices. These problems are fundamental ones in graph theory and additionally have applications to finite geometry, combinatorial number theory, combinatorial matrix theory, and theoretical computer science. The project will will also have a specific focus on advising student research. The project will first attempt two notoriously difficult problems in extremal graph theory: finding constructions of graphs certifying lower bounds for bipartite Turan numbers and finding constructions of Ramsey graphs. The PI will develop the recent trend of combining algebraic and geometric objects with probabilistic methods to make progress on these two difficult areas. Second, the project will attempt to solve several long-standing conjectures in spectral graph theory regarding for example spectral gaps of graphs, Nordhaus-Gaddum type problems, and spectral versions of Turan-type problems. Additionally, applications in discrete geometry and combinatorial number theory will be explored using graph theoretic methods. 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.