Description
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.
Download count: 2
Details
Title
- Optimal degree conditions for spanning subgraphs
Contributors
- DeBiasio, Louis (Author)
- Kierstead, Henry A (Thesis advisor)
- Czygrinow, Andrzej (Thesis advisor)
- Hurlbert, Glenn (Committee member)
- Kadell, Kevin (Committee member)
- Fishel, Susanna (Committee member)
- Arizona State University (Publisher)
Date Created
The date the item was original created (prior to any relationship with the ASU Digital Repositories.)
2011
Resource Type
Collections this item is in
Note
-
thesisPartial requirement for: Ph.D., Arizona State University, 2011
-
bibliographyIncludes bibliographical references (p. 155-158)
-
Field of study: Mathematics
Citation and reuse
Statement of Responsibility
by Louis DeBiasio