Spanning Structures in Random Graphs

University Of Nebraska-Lincoln, Lincoln NE

Investigators

Abstract

Random graphs are graphs of typically large size generated by a random mechanism associated to a probability distribution. They provide simplified abstract models for large complex networks — such as telecommunication networks, social networks, the Internet, and neural networks — for which an explicit deterministic description is often impractical or not available. Interest in the subject has grown in recent years due to the ubiquitous proliferation of such networks and the need of a theoretical framework for their analysis. Many fundamental properties of graphs can be formulated in terms of their spanning substructures — such as spanning trees, Hamilton cycles and perfect matchings. Such structures are quintessential in graph theory and play a central role in other fields such as computer science, combinatorial optimization, and statistical physics. This research project aims to extend mathematical understanding of spanning structures in several models of random graphs by addressing fundamental open questions in the field. In addition, this project provides research training opportunities for graduate students. The analysis of spanning structures in random graphs is a central theme with a long tradition in probabilistic combinatorics. However, many basic questions that are well understood for the classical Erdős-Rényi graphs remain wide open for other fundamental models of random graphs. The investigator plans to settle some of these open questions concerning the existence, emergence, and packing of spanning structures (and their rainbow counterparts) in several models of random graphs, including random geometric graphs, preferential attachment graphs, and random lifts. The constrained nature of these models makes their analysis significantly different from (and often more challenging than) that of Erdős-Rényi graphs. To overcome these obstacles, the research incorporates novel approaches that combine geometric, probabilistic, and combinatorial ingredients. This project is jointly funded by the Combinatorics program and the Established Program to Stimulate Competitive Research (EPSCoR). 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.