{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/97294"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/97294","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Sufficient conditions for the existence of specified subgraphs in graphs","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.","abstract_html":"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.","abstract_has_math":false,"creators":["McConvey, Andrew Ross"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Kostochka, Alexandr","Balogh, József","Kirkpatrick, Kay","Molla, Theodore"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-08-10T19:14:41Z","date_published":"2017-08-10T19:14:41Z","updated_at":"2026-07-22T22:24:32Z","subjects":["Stable marriage","Turán number","List packing","Matching","Stable matching","Combinatorics","Graph theory","Extremal graph theory","Cycles","Disjoint cycles","Graph packing"],"languages":["en"],"rights":["Copyright 2017 Andrew McConvey"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/97294","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kostochka, Alexandr","Balogh, József","Kirkpatrick, Kay","Molla, Theodore"]},{"key":"dc:creator","label":"Author","values":["McConvey, Andrew Ross"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-08-10T19:14:41Z","2017-04-05","2017-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Stable marriage","Turán number","List packing","Matching","Stable matching","Combinatorics","Graph theory","Extremal graph theory","Cycles","Disjoint cycles","Graph packing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Andrew McConvey"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/97294"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-08-10 without embargo terms","The student, Andrew McConvey, accepted the attached license on 2017-04-03 at 16:20.","The student, Andrew McConvey, submitted this Dissertation for approval on 2017-04-03 at 17:02.","This Dissertation was approved for publication on 2017-04-05 at 09:34.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10640 on 2017-08-10 at 13:38:39","Made available in DSpace on 2017-08-10T19:14:41Z (GMT). No. of bitstreams: 11 MCCONVEY-DISSERTATION-2017.pdf: 941996 bytes, checksum: d7fce7d2045f92cedc49507378e89a91 (MD5) AlonYuster.tex: 30927 bytes, checksum: c97c8754a82c31566b83b29cd05663e3 (MD5) Cycles.tex: 51406 bytes, checksum: bbf79f196754aae8da28284acd198fd8 (MD5) Cycles_2k.tex: 18687 bytes, checksum: 2061c0213e5f0b90af3c6dbb8de1f40a (MD5) Introduction.tex: 47917 bytes, checksum: 80407b15c38af6a9745dffdd59153333 (MD5) Matching.tex: 36392 bytes, checksum: 3e7a20b15291d3a982e8808f27526eca (MD5) Packing.tex: 22326 bytes, checksum: bbaf9b088a5c6eafc595b84b18214335 (MD5) Thesis20170331.tex: 15863 bytes, checksum: d397138fda27ecb1a9a3a76bc1754b8b (MD5) Zak.tex: 76847 bytes, checksum: af165e333834fd3aad2833768a9426f0 (MD5) LICENSE.txt: 4212 bytes, checksum: 277df79c7ec46ba0ea6a1c8bdd3400d5 (MD5) PROQUEST_LICENSE.txt: 4558 bytes, checksum: 0827bc056baf634a71b30acb5b91e450 (MD5) Previous issue date: 2017-04-05"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Sufficient conditions for the existence of specified subgraphs in graphs"]}]}],"canonical_facts":{"dc:contributor":["Kostochka, Alexandr","Balogh, József","Kirkpatrick, Kay","Molla, Theodore"],"dc:creator":["McConvey, Andrew Ross"],"dc:date":["2017-08-10T19:14:41Z","2017-04-05","2017-05"],"dc:description":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-08-10 without embargo terms","The student, Andrew McConvey, accepted the attached license on 2017-04-03 at 16:20.","The student, Andrew McConvey, submitted this Dissertation for approval on 2017-04-03 at 17:02.","This Dissertation was approved for publication on 2017-04-05 at 09:34.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10640 on 2017-08-10 at 13:38:39","Made available in DSpace on 2017-08-10T19:14:41Z (GMT). No. of bitstreams: 11 MCCONVEY-DISSERTATION-2017.pdf: 941996 bytes, checksum: d7fce7d2045f92cedc49507378e89a91 (MD5) AlonYuster.tex: 30927 bytes, checksum: c97c8754a82c31566b83b29cd05663e3 (MD5) Cycles.tex: 51406 bytes, checksum: bbf79f196754aae8da28284acd198fd8 (MD5) Cycles_2k.tex: 18687 bytes, checksum: 2061c0213e5f0b90af3c6dbb8de1f40a (MD5) Introduction.tex: 47917 bytes, checksum: 80407b15c38af6a9745dffdd59153333 (MD5) Matching.tex: 36392 bytes, checksum: 3e7a20b15291d3a982e8808f27526eca (MD5) Packing.tex: 22326 bytes, checksum: bbaf9b088a5c6eafc595b84b18214335 (MD5) Thesis20170331.tex: 15863 bytes, checksum: d397138fda27ecb1a9a3a76bc1754b8b (MD5) Zak.tex: 76847 bytes, checksum: af165e333834fd3aad2833768a9426f0 (MD5) LICENSE.txt: 4212 bytes, checksum: 277df79c7ec46ba0ea6a1c8bdd3400d5 (MD5) PROQUEST_LICENSE.txt: 4558 bytes, checksum: 0827bc056baf634a71b30acb5b91e450 (MD5) Previous issue date: 2017-04-05"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/97294"],"dc:language":["en"],"dc:rights":["Copyright 2017 Andrew McConvey"],"dc:subject":["Stable marriage","Turán number","List packing","Matching","Stable matching","Combinatorics","Graph theory","Extremal graph theory","Cycles","Disjoint cycles","Graph packing"],"dc:title":["Sufficient conditions for the existence of specified subgraphs in graphs"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:32Z"}