Advanced search options

You searched for `subject:(Extremal combinatorcs)`

. One record found.

▼ Search Limiters

1.
Delcourt, Michelle Jeannette.
Viewing *extremal* and structural problems through a probabilistic lens.

Degree: PhD, Mathematics, 2017, University of Illinois – Urbana-Champaign

URL: http://hdl.handle.net/2142/97669

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.
*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…

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} 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 (16^{th} 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. http://hdl.handle.net/2142/97669.

MLA Handbook (7^{th} Edition):

Delcourt, Michelle Jeannette. “Viewing extremal and structural problems through a probabilistic lens.” 2017. Web. 16 Jul 2020.

Vancouver:

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