Full metadata
Title
Optimal degree conditions for spanning subgraphs
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.
Date Created
2011
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)
Topical Subject
Resource Type
Extent
viii, 158 p. : ill
Language
eng
Copyright Statement
In Copyright
Primary Member of
Peer-reviewed
No
Open Access
No
Handle
https://hdl.handle.net/2286/R.I.9334
Statement of Responsibility
by Louis DeBiasio
Description Source
Retrieved on Sept. 14, 2012
Level of coding
full
Note
thesis
Partial requirement for: Ph.D., Arizona State University, 2011
bibliography
Includes bibliographical references (p. 155-158)
Field of study: Mathematics
System Created
- 2011-08-12 04:55:33
System Modified
- 2021-08-30 01:51:56
- 3 years 2 months ago
Additional Formats