Embeddings in Sparse Graphs

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

Extremal combinatorics has witnessed a rapid growth in the past few decades. An archetype problem in this field is to study the structure of subgraphs appearing in different classes of graphs. Such problems are much better understand when the host graphs are dense thanks to a variety of tools applicable to dense graphs. This proposal will focus on such problems for sparse host graphs. In practice, almost all the graphs used to model real-life networks, such as facebook graphs, (artificial) neural networks, are sparse. The goal is to develop a theory of certain sublinear expanders that can be used to construct subgraphs with various properties in graphs with (sufficiently large) constant average degree. This project will connect sublinear expanders with two other central notions in combinatorics: cycles and topological minors. The theory developed will make decisive progress on central problems concerning embedding sparse subgraphs with additional arithmetic properties. Some of such problems have remained wide open since the 60s despite active attempts from various researchers. Further links will be sought via considering analogous problems in other areas such as number theory.