Extremal and Probabilistic Graph Theory: Spectra, Subgraph Counts, and Graph Sequences

University Of Memphis, Memphis TN

Investigators

Abstract

ABSTRACT Principal Investigator: Bollobas, Bela Co-Principal Investigator: Vladimir Nikiforov Proposal Number: DMS - 0906634 Institution: University of Memphis Title: Extremal and Probabilistic Graph Theory: Spectra, Subgraph Counts, and Graph Sequences This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5). In the past decade `global' questions, questions concerning classes and sequences of graphs have come to the fore in graph theory. Hereditary properties of graphs, sequences of dense and sparse graphs, classes of inhomogeneous random graphs, graph algebras, families of supersaturated graphs, and spectra of families of graphs have been studied by Alon, Chung, Borgs, Chayes, Lovasz, Balogh, Morris, Bollobas, Razborov, Nikiforov, and Riordan, among many others. The main goal of the present investigators is to develop spectral, analytical and random techniques to attack some of the major open problems in these fields. In particular, the investigators will focus on problems of convergent sequences of sparse graphs, subgraph counts, and relations of spectra to the structure of graphs and their classical invariants. Graph theory is one of the youngest branches of mathematics and is still far from maturity. Although it has been acquiring tools for decades, for much of its progress it still has to rely on ingenious ad hoc methods. Any move that makes the methods of well-established branches of mathematics relevant to major problems of graph theory must be welcome. By showing how tools of classical analysis and probability theory can be brought to bear on problems of graph theory, the investigators will attempt to bring substantial areas of modern graph theory into the fold of traditional mathematics. Most of these areas are much studied by computer scientists as well, and have applications to networking and the design and analysis of efficient algorithms.