Full Record

New Search | Similar Records

Title Viewing extremal and structural problems through a probabilistic lens
Publication Date
Date Accessioned
Degree PhD
Discipline/Department Mathematics
Degree Level doctoral
University/Publisher University of Illinois – Urbana-Champaign
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.
Subjects/Keywords Small subgraph conditioning method; Random regular graph; Intersecting families; Star decomposition; Structural graph theory; Extremal combinatorcs
Contributors Balogh, Jozsef (advisor); Kostochka, Alexandr (Committee Chair); Kirkpatrick, Kay (committee member); Tserunyan, Anush (committee member)
Language en
Rights Copyright 2017 Michelle Delcourt
Country of Publication us
Record ID handle:2142/97669
Repository uiuc
Date Indexed 2020-03-09
Grantor University of Illinois at Urbana-Champaign
Issued Date 2017-03-27 00:00:00

Sample Search Hits | Sample Images | Cited Works

…further direction; the same can be said about certain structural problems. Star Decompositions of Random Regular Graphs As Barát and Thomassen [11] note, decompositions of the edges of a graph G into copies of a small fixed subgraph can be…

…translate this structural problem to the setting of random d-regular graphs: Theorem 3.1.8. A random 4-regular graph on n vertices has an orientation with out-degrees 0 or 3 asymptotically almost surely, provided that 2n is divisible by 3. Although this…

…appears to be a straightforward application of the second moment method [4], standard probabilistic techniques do not work here; if Y = Y (n) is the number of orientations of a random 4-regular q 2 ] 3 graph on n vertices with out…

…families of subgraphs). A recent line of investigation is extending classical results to the so-called “sparse random setting”. If fn,m (H) is the number of labeled H-free graphs on n labeled vertices with precisely m edges, then the…

…also enumerate such systems and explore the sparse random setting. As demonstrated in this thesis for permutations and vector spaces, this work fits into a more general framework that could be adapted for a variety of other settings provided the…

…trivial, and there are nt t! + o(1) 2(n−t)! t-intersecting families. Additionally, we prove two results in the sparse random setting. First we obtain the following sparse extension of Theorem 2.3.4. Let (Sn )p denote the p…

random subset of Sn , where each permutation in 3 Sn is included independently with probability p. Provided p is not too small, we show that with high probability the largest t-intersecting family in (Sn )p is trivial. Note that the work by…

…n, p) denote the p-random k-uniform hypergraph on [n], in which every edge in [n] k is included independently at random with probability p. Balogh, Bohman, and Mubayi [7] initiated the study of intersecting…