{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/97669"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/97669","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Viewing extremal and structural problems through a probabilistic lens","abstract":"This thesis focuses on using techniques from probability to solve problems from extremal and structural combinatorics. The main problem in Chapter 2 is determining the typical structure of $t$-intersecting families in various settings and enumerating such systems. The analogous sparse random versions of our extremal results are also obtained. The proofs follow the same general framework, in each case using a version of the Bollobás Set-Pairs Inequality to bound the number of maximal intersecting families, which then can be combined with known stability theorems. Following this framework from joint work with Balogh, Das, Liu, and Sharifzadeh, similar results for permutations, uniform hypergraphs, and vector spaces are obtained. In 2006, Barát and Thomassen conjectured that the edges of every planar 4-edge-connected 4-regular graph can be decomposed into disjoint copies of $S_3$, the star with three leaves. Shortly afterward, Lai constructed a counterexample to this conjecture. Following joint work with Postle, in Chapter 3 using the Small Subgraph Conditioning Method of Robinson and Wormald, we find that a random 4-regular graph has an $S_3$-decomposition asymptotically almost surely, provided we have the obvious necessary divisibility conditions. In 1988, Thomassen showed that if $G$ is at least $(2k-1)$-edge-connected then $G$ has a spanning, bipartite $k$-connected subgraph. In 1989, Thomassen asked whether a similar phenomenon holds for vertex-connectivity; more precisely: is there an integer-valued function $f(k)$ such that every $f(k)$-connected graph admits a spanning, bipartite $k$-connected subgraph? In Chapter 4, as in joint work with Ferber, we show that every $10^{10}k^3 \\log n$-connected graph admits a spanning, bipartite $k$-connected subgraph.","abstract_html":"This thesis focuses on using techniques from probability to solve problems from extremal and structural combinatorics. The main problem in Chapter 2 is determining the typical structure of $t$-intersecting families in various settings and enumerating such systems. The analogous sparse random versions of our extremal results are also obtained. The proofs follow the same general framework, in each case using a version of the Bollobás Set-Pairs Inequality to bound the number of maximal intersecting families, which then can be combined with known stability theorems. Following this framework from joint work with Balogh, Das, Liu, and Sharifzadeh, similar results for permutations, uniform hypergraphs, and vector spaces are obtained. In 2006, Barát and Thomassen conjectured that the edges of every planar 4-edge-connected 4-regular graph can be decomposed into disjoint copies of <span class=\"etd-inline-math\">S<sub>3</sub></span>, the star with three leaves. Shortly afterward, Lai constructed a counterexample to this conjecture. Following joint work with Postle, in Chapter 3 using the Small Subgraph Conditioning Method of Robinson and Wormald, we find that a random 4-regular graph has an <span class=\"etd-inline-math\">S<sub>3</sub></span>-decomposition asymptotically almost surely, provided we have the obvious necessary divisibility conditions. In 1988, Thomassen showed that if $G$ is at least $(2k-1)$-edge-connected then $G$ has a spanning, bipartite $k$-connected subgraph. In 1989, Thomassen asked whether a similar phenomenon holds for vertex-connectivity; more precisely: is there an integer-valued function $f(k)$ such that every $f(k)$-connected graph admits a spanning, bipartite $k$-connected subgraph? In Chapter 4, as in joint work with Ferber, we show that every <span class=\"etd-inline-math\">10<sup>10</sup>k<sup>3</sup> \\log n</span>-connected graph admits a spanning, bipartite $k$-connected subgraph.","abstract_has_math":true,"creators":["Delcourt, Michelle Jeannette"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Balogh, József","Kostochka, Alexandr","Kirkpatrick, Kay","Tserunyan, Anush"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-08-10T20:32:42Z","date_published":"2017-08-10T20:32:42Z","updated_at":"2026-07-22T22:24:34Z","subjects":["Small subgraph conditioning method","Random regular graph","Intersecting families","Star decomposition","Structural graph theory","Extremal combinatorcs"],"languages":["en"],"rights":["Copyright 2017 Michelle Delcourt"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/97669","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Balogh, József","Kostochka, Alexandr","Kirkpatrick, Kay","Tserunyan, Anush"]},{"key":"dc:creator","label":"Author","values":["Delcourt, Michelle Jeannette"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-08-10T20:32:42Z","2019-08-11T09:15:09Z","2017-03-27","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":["Small subgraph conditioning method","Random regular graph","Intersecting families","Star decomposition","Structural graph theory","Extremal combinatorcs"]}]},{"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 Michelle Delcourt"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/97669"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis focuses on using techniques from probability to solve problems from extremal and structural combinatorics. The main problem in Chapter 2 is determining the typical structure of $t$-intersecting families in various settings and enumerating such systems. The analogous sparse random versions of our extremal results are also obtained. The proofs follow the same general framework, in each case using a version of the Bollobás Set-Pairs Inequality to bound the number of maximal intersecting families, which then can be combined with known stability theorems. Following this framework from joint work with Balogh, Das, Liu, and Sharifzadeh, similar results for permutations, uniform hypergraphs, and vector spaces are obtained. In 2006, Barát and Thomassen conjectured that the edges of every planar 4-edge-connected 4-regular graph can be decomposed into disjoint copies of $S_3$, the star with three leaves. Shortly afterward, Lai constructed a counterexample to this conjecture. Following joint work with Postle, in Chapter 3 using the Small Subgraph Conditioning Method of Robinson and Wormald, we find that a random 4-regular graph has an $S_3$-decomposition asymptotically almost surely, provided we have the obvious necessary divisibility conditions. In 1988, Thomassen showed that if $G$ is at least $(2k-1)$-edge-connected then $G$ has a spanning, bipartite $k$-connected subgraph. In 1989, Thomassen asked whether a similar phenomenon holds for vertex-connectivity; more precisely: is there an integer-valued function $f(k)$ such that every $f(k)$-connected graph admits a spanning, bipartite $k$-connected subgraph? In Chapter 4, as in joint work with Ferber, we show that every $10^{10}k^3 \\log n$-connected graph admits a spanning, bipartite $k$-connected subgraph.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2019-05-01","The student, Michelle Delcourt, accepted the attached license on 2017-03-24 at 16:02.","The student, Michelle Delcourt, submitted this Dissertation for approval on 2017-03-26 at 10:09.","This Dissertation was approved for publication on 2017-03-27 at 13:56.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10618 on 2017-08-10 at 15:05:04","Made available in DSpace on 2017-08-10T20:32:42Z (GMT). No. of bitstreams: 2 DELCOURT-DISSERTATION-2017.pdf: 740688 bytes, checksum: a7dea968c4253e97b06eb4c329fc6814 (MD5) LICENSE.txt: 4214 bytes, checksum: c1d756a0591364be63f15688a89e6c86 (MD5) Previous issue date: 2017-03-27","Embargo set by: Colleen Fallaw for item 102722 Lift date: 2019-08-10T21:27:21Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 102722 on 2019-08-11T09:15:09Z."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Viewing extremal and structural problems through a probabilistic lens"]}]}],"canonical_facts":{"dc:contributor":["Balogh, József","Kostochka, Alexandr","Kirkpatrick, Kay","Tserunyan, Anush"],"dc:creator":["Delcourt, Michelle Jeannette"],"dc:date":["2017-08-10T20:32:42Z","2019-08-11T09:15:09Z","2017-03-27","2017-05"],"dc:description":["This thesis focuses on using techniques from probability to solve problems from extremal and structural combinatorics. The main problem in Chapter 2 is determining the typical structure of $t$-intersecting families in various settings and enumerating such systems. The analogous sparse random versions of our extremal results are also obtained. The proofs follow the same general framework, in each case using a version of the Bollobás Set-Pairs Inequality to bound the number of maximal intersecting families, which then can be combined with known stability theorems. Following this framework from joint work with Balogh, Das, Liu, and Sharifzadeh, similar results for permutations, uniform hypergraphs, and vector spaces are obtained. In 2006, Barát and Thomassen conjectured that the edges of every planar 4-edge-connected 4-regular graph can be decomposed into disjoint copies of $S_3$, the star with three leaves. Shortly afterward, Lai constructed a counterexample to this conjecture. Following joint work with Postle, in Chapter 3 using the Small Subgraph Conditioning Method of Robinson and Wormald, we find that a random 4-regular graph has an $S_3$-decomposition asymptotically almost surely, provided we have the obvious necessary divisibility conditions. In 1988, Thomassen showed that if $G$ is at least $(2k-1)$-edge-connected then $G$ has a spanning, bipartite $k$-connected subgraph. In 1989, Thomassen asked whether a similar phenomenon holds for vertex-connectivity; more precisely: is there an integer-valued function $f(k)$ such that every $f(k)$-connected graph admits a spanning, bipartite $k$-connected subgraph? In Chapter 4, as in joint work with Ferber, we show that every $10^{10}k^3 \\log n$-connected graph admits a spanning, bipartite $k$-connected subgraph.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2019-05-01","The student, Michelle Delcourt, accepted the attached license on 2017-03-24 at 16:02.","The student, Michelle Delcourt, submitted this Dissertation for approval on 2017-03-26 at 10:09.","This Dissertation was approved for publication on 2017-03-27 at 13:56.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10618 on 2017-08-10 at 15:05:04","Made available in DSpace on 2017-08-10T20:32:42Z (GMT). No. of bitstreams: 2 DELCOURT-DISSERTATION-2017.pdf: 740688 bytes, checksum: a7dea968c4253e97b06eb4c329fc6814 (MD5) LICENSE.txt: 4214 bytes, checksum: c1d756a0591364be63f15688a89e6c86 (MD5) Previous issue date: 2017-03-27","Embargo set by: Colleen Fallaw for item 102722 Lift date: 2019-08-10T21:27:21Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 102722 on 2019-08-11T09:15:09Z."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/97669"],"dc:language":["en"],"dc:rights":["Copyright 2017 Michelle Delcourt"],"dc:subject":["Small subgraph conditioning method","Random regular graph","Intersecting families","Star decomposition","Structural graph theory","Extremal combinatorcs"],"dc:title":["Viewing extremal and structural problems through a probabilistic lens"],"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:34Z"}