150038-Thumbnail Image.png
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

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.
Reuse Permissions


  • Download restricted.
    Download count: 2

    Details

    Title
    • Optimal degree conditions for spanning subgraphs
    Contributors
    Date Created
    2011
    Resource Type
  • Text
  • Collections this item is in
    Note
    • thesis
      Partial requirement for: Ph.D., Arizona State University, 2011
    • bibliography
      Includes bibliographical references (p. 155-158)
    • Field of study: Mathematics

    Citation and reuse

    Statement of Responsibility

    by Louis DeBiasio

    Machine-readable links