Spanning Trees In Graphs Without Large Bipartite Holes

Determining the minimum degree threshold for the existence of spanning subgraphs is a central problem in extremal graph theory.It has a long history and can be traced back to Dirac’s theorem in 1952.Since then,people have begun to explore different types of spanning subgraphs(trees,factors,etc.)and construct corresponding extremal graphs to ensure the optimality of the minimum degree conditions.The extremal graphs have a very regular topological structure.For example,Turán graph is a balanced complete multipartite graph,which contains many independent sets of linear size.This has triggered a new trend in extremal graph theory,which focuses on limiting the edge distribution and studying the change of the corresponding extremal value when the edge distribution characteristics are closer to the random graph.For example,Erd(?)s and Sós initiated the Ramsey-Turán theory in the late 1970s.In this thesis,we mainly study the embedding problem of bounded-degree spanning trees under the condition of linear minimum degree and sublinear bipartite independence number.Given a graph G,an(s,t)-bipartite hole in G consists of two disjoint sets S,T (?) V(G)with |S|=s and |T|=t such that there are no edges between S and T.The bipartite independence number α*(G)is the maximum integer s such that G contains an(s,s)-bipartite hole.We prove that if a graph has linear minimum degree and does not contain large bipartite holes,then it contains all spanning trees with maximum degree at most Δ.This strengthens a result of Bottcher et al and and solves a problem raised by Krivelevich,Kwan and Sudakov from a new perspective.