University of Illinois Urbana-Champaign

Viewing extremal and structural problems through a probabilistic lens

Delcourt, Michelle Jeannette

Content Files
DELCOURT-DISSERTATION-2017.pdf

Permalink

https://hdl.handle.net/2142/97669

Description

Title
Viewing extremal and structural problems through a probabilistic lens
Author(s)
Delcourt, Michelle Jeannette
Issue Date
2017-03-27
Director of Research (if dissertation) or Advisor (if thesis)
Balogh, József
Doctoral Committee Chair(s)
Kostochka, Alexandr
Committee Member(s)
  • Kirkpatrick, Kay
  • Tserunyan, Anush
Department of Study
Mathematics
Discipline
Mathematics
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Date of Ingest
2017-08-10T20:32:42Z
Keyword(s)
  • Small subgraph conditioning method
  • Random regular graph
  • Intersecting families
  • Star decomposition
  • Structural graph theory
  • Extremal combinatorcs
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.
Graduation Semester
2017-05
Type of Resource
text
Permalink
http://hdl.handle.net/2142/97669
Copyright and License Information
Copyright 2017 Michelle Delcourt

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Mathematics