Files in this item
Files  Description  Format 

application/pdf MCCONVEYDISSERTATION2017.pdf (942kB)  (no description provided) 
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 UrbanaChampaign 
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 2k2, then G contains k vertexdisjoint 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 sdimensions and purely cyclic preferences (cyclic sDSM). In 2004, Boros et al. showed that if there are at most s agents of each gender, then every instance of cyclic sDSM 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 sDSM admits a stable matching. We also provide a minimal example of an instance of sDSM which admits no strongly stable matching. 
Issue Date:  20170405 
Type:  Thesis 
URI:  http://hdl.handle.net/2142/97294 
Rights Information:  Copyright 2017 Andrew McConvey 
Date Available in IDEALS:  20170810 
Date Deposited:  201705 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois