Delcourt, Michelle Jeannette.
Viewing extremal and structural problems through a probabilistic lens.
Degree: PhD, Mathematics, 2017, University of Illinois – Urbana-Champaign
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 S3
, 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 S3
-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 1010
log n-connected graph admits a spanning, bipartite k-connected subgraph.
Advisors/Committee Members: Balogh, Jozsef (advisor), Kostochka, Alexandr (Committee Chair), Kirkpatrick, Kay (committee member), Tserunyan, Anush (committee member).
Subjects/Keywords: Small subgraph conditioning method; Random regular graph; Intersecting families; Star decomposition; Structural graph theory; Extremal combinatorcs
…finding solutions to
challenging problems from extremal combinatorics and structural graph… …1.2
Viewing Extremal Problems through a Probabilistic Lens
The field of extremal… …combinatorics encompasses a wide variety of results. Fundamentally speaking, extremal
combinatorics is… …the study of finite objects, such as graphs, sets, etc., that are extremal, meaning that… …they
are maximal (or minimal) with respect to a certain property. In extremal graph…
to Zotero / EndNote / Reference
APA (6th Edition):
Delcourt, M. J. (2017). Viewing extremal and structural problems through a probabilistic lens. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/97669
Chicago Manual of Style (16th Edition):
Delcourt, Michelle Jeannette. “Viewing extremal and structural problems through a probabilistic lens.” 2017. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed July 16, 2020.
MLA Handbook (7th Edition):
Delcourt, Michelle Jeannette. “Viewing extremal and structural problems through a probabilistic lens.” 2017. Web. 16 Jul 2020.
Delcourt MJ. Viewing extremal and structural problems through a probabilistic lens. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2017. [cited 2020 Jul 16].
Available from: http://hdl.handle.net/2142/97669.
Council of Science Editors:
Delcourt MJ. Viewing extremal and structural problems through a probabilistic lens. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2017. Available from: http://hdl.handle.net/2142/97669