2026-05-24T17:15:07Zhttps://keep.lib.asu.edu/oai/requestoai:keep.lib.asu.edu:node-1500382024-12-20T18:25:12Zoai_pmh:alloai_pmh:repo_items150038
https://hdl.handle.net/2286/R.I.9334
http://rightsstatements.org/vocab/InC/1.0/
All Rights Reserved
2011
viii, 158 p. : ill
Doctoral Dissertation
Academic theses
Text
eng
DeBiasio, Louis
Kierstead, Henry A
Czygrinow, Andrzej
Hurlbert, Glenn
Kadell, Kevin
Fishel, Susanna
Arizona State University
Partial requirement for: Ph.D., Arizona State University, 2011
Includes bibliographical references (p. 155-158)
Field of study: Mathematics
In a large network (graph) it would be desirable to guarantee the existence of some local property based only on global knowledge of the network. Consider the following classical example: how many connections are necessary to guarantee that the network contains three nodes which are pairwise adjacent? It turns out that more than n^2/4 connections are needed, and no smaller number will suffice in general. Problems of this type fall into the category of ``extremal graph theory.'' Generally speaking, extremal graph theory is the study of how global parameters of a graph are related to local properties. This dissertation deals with the relationship between minimum degree conditions of a host graph G and the property that G contains a specified spanning subgraph (or class of subgraphs). The goal is to find the optimal minimum degree which guarantees the existence of a desired spanning subgraph. This goal is achieved in four different settings, with the main tools being Szemeredi's Regularity Lemma; the Blow-up Lemma of Komlos, Sarkozy, and Szemeredi; and some basic probabilistic techniques.
Mathematics
Graph Theory
Extremal problems (Mathematics)
Optimal degree conditions for spanning subgraphs