Files in this item

FilesDescriptionFormat

application/pdf

application/pdfMCCONVEY-DISSERTATION-2017.pdf (942kB)
(no description provided)PDF

Description

Title:Sufficient conditions for the existence of specified subgraphs in graphs
Author(s):McConvey, Andrew Ross
Director of Research:Kostochka, Alexandr
Doctoral Committee Chair(s):Balogh, József
Doctoral Committee Member(s):Kirkpatrick, Kay; Molla, Theodore
Department / Program:Mathematics
Discipline:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):Combinatorics
Graph theory
Extremal graph theory
Cycles
Disjoint cycles
Graph packing
Turán number
List packing
Matching
Stable matching
Stable marriage
Abstract:A classical problem in combinatorics is, given graphs G and H, to determine if H is a subgraph of G. It is usually computationally complex to determine if H is a subgraph of G. Therefore, we often prove conditions that are sufficient to guarantee that a graph G contains H as a subgraph. In Chapter 2, we consider a theorem of Dirac and Erdős from 1963 that considers when a graph contains many disjoint cycles. Generalizing the seminal result of Corrádi and Hajnal, they prove that if a graph G contains many more vertices of degree at least 2k than vertices of degree at most 2k-2, then G contains k vertex-disjoint cycles. We strengthen their result, proving that if G contains 3k more vertices of high degree than vertices of low degree, then G contains k disjoint cycles and that this bound is sharp. Moreover, when G has many vertices, G is planar, or G contains few triangles, this value can be improved to 2k. The value 2k is the best possible, as shown by examples of Dirac and Erdős. In Chapter 3, we rephrase the problem of subgraphs in the language of graph packing. Two graphs G and G' pack if G is a subgraph of the complement of G' or, equivalently, if G' is a subgraph of the complement of G. Graph packing is a restatement of the subgraph problem that does not require one graph to be specified as the underlying graph and the other as the subgraph. Theorems of Sauer and Spencer and, independently, Bollobás and Eldridge prove that if G and G' together have few edges or if the maximum degree of G and the maximum degree of G' are small, then G and G' pack. We explore two results that combine bounds on the maximum degrees and number of edges in G and G'. Recently, Alon and Yuster proved that if G and G' are graphs on n vertices such that G has a bounded number of edges and G' has bounded degree, then G and G' pack. We characterize the pairs of graphs for which their theorem is sharp. In particular, we show that for sufficiently large n, if the vertex of maximum degree in G can be appropriately placed, then G can contain more edges and still pack with G'. We also consider a conjecture of Żak that states if the sum of the number of edges in G, the number of edges in G', and the degree of the largest vertex in G or G' is bounded above by 3n - 7, then G and G' pack. We prove that, up to an additive constant, this conjecture is correct. Using the notion of list packing, we prove that there is a constant C such that if the same sum is bounded above by 3n - C, then G and G' pack. This improves a theorem of Żak from 2014. Finally, we consider a generalization of finding a matching in a graph. The stable marriage problem was introduced by Gale and Shapley in 1962 and the generalization to multiple dimensions was first mentioned by Knuth in 1976. We consider a generalization of the Stable Marriage problem with s-dimensions and purely cyclic preferences (cyclic s-DSM). In 2004, Boros et al. showed that if there are at most s agents of each gender, then every instance of cyclic s-DSM admits a stable matching. In 2006, Eriksson et al. showed this is also true when s = 3 and there are 4 agents of each gender. We extend their result, proving that when there are s+1 agents of each gender, each instance of s-DSM admits a stable matching. We also provide a minimal example of an instance of s-DSM which admits no strongly stable matching.
Issue Date:2017-04-05
Type:Thesis
URI:http://hdl.handle.net/2142/97294
Rights Information:Copyright 2017 Andrew McConvey
Date Available in IDEALS:2017-08-10
Date Deposited:2017-05


This item appears in the following Collection(s)

Item Statistics