Sufficient conditions for the existence of specified subgraphs in graphs

McConvey, Andrew Ross

Permalink

https://hdl.handle.net/2142/97294 Copy

Description

Title

Sufficient conditions for the existence of specified subgraphs in graphs

Author(s)

McConvey, Andrew Ross

Issue Date

2017-04-05

Director of Research (if dissertation) or Advisor (if thesis)

Kostochka, Alexandr

Doctoral Committee Chair(s)

Balogh, József

Committee Member(s)

• Kirkpatrick, Kay
• Molla, Theodore

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(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.

Graduation Semester

2017-05

Type of Resource

text

Permalink

http://hdl.handle.net/2142/97294

Copyright and License Information

Copyright 2017 Andrew McConvey

Owning Collections