Extremal properties of some random combinatorial systems

Krueger, Robert A

Permalink

https://hdl.handle.net/2142/125565 Copy

Description

Title

Extremal properties of some random combinatorial systems

Author(s)

Krueger, Robert A

Issue Date

2024-07-07

Director of Research (if dissertation) or Advisor (if thesis)

Balogh, Jozsef

Doctoral Committee Chair(s)

Kostochka, Alexandr

Committee Member(s)

• Dey, Partha S
• Bradshaw, Peter

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• combinatorics
• extremal combinatorics
• probabilistic combinatorics
• transference
• hitting time
• Hamiltonian cycles
• digraphs
• graph container method
• random poset

Abstract

A popular trend in combinatorics research of the past few decades is the study of probabilistic variants of classical combinatorial theorems. In this dissertation, we study a random variant of each of three classical theorems in extremal combinatorics: the Erdős--Ko--Rado Theorem, Sperner's Theorem, and Dirac's Theorem. Such study improves our understanding of the discrete systems underlying extremal combinatorics, in some sense measuring how robust such systems are to random perturbation. The Erdős--Ko--Rado Theorem, a cornerstone result in extremal set theory, states that, of all families of subsets of [n] of size k which contain no pair of disjoint sets, the largest have all sets containing a fixed i in [n], when n is at least 2k+1. This theorem is naturally encoded into the Kneser graph K(n,k), which is the graph on all subsets of [n] of size k where two sets are adjacent exactly when they are disjoint. In this set-up, the Erdős--Ko--Rado Theorem determines the largest independent sets of K(n,k), that is, a set of vertices of K(n,k) containing no edge of K(n,k). Bollobás, Narayanan, and Raigorodskii asked for what p are the largest independent sets of K(n,k) the same as those of K_p(n,k) with high probability, where K_p(n,k) is the random subgraph of K(n,k) where we keep each edge independently with probability p. In Chapter 2, together with Balogh and Luo, we answer this question, extending partial progress of Das--Tran and Devlin--Kahn. Our main technique is a graph container argument. Sperner's Theorem, a cornerstone result in extremal poset theory, states that, of all families of subsets of [n] of which none is a subset of another in the family, the largest consist of all sets of size n/2, all sets of size (n+1)/2, or all sets of size (n-1)/2. Considering an earlier question of Balogh, Bohman, and Mubayi on a random variant of the Erdős--Ko--Rado Theorem (different from the above), Hamm and Kahn asked for what p does the largest subfamily of P(n,p) where no set is a subset of another in the family consist of all sets of size n/2, all sets of size (n+1)/2, or all sets of size (n-1)/2 with high probability, where P(n,p) is the random subfamily of subsets of [n] where we keep each subset independently with probability p. In Chapter 3, together with Balogh, we answer this question, extending partial progress of Hamm and Kahn. Our main technique is a refinement of Hamm and Kahn's graph container argument, which is a variation of Sapozhenko's graph containers. Dirac's Theorem, a cornerstone result in extremal graph theory, states that every n-vertex graph with minimum degree at least n/2>1 contains a cycle on n vertices, and this n/2 cannot be made any smaller. There are several well-studied probabilistic variants of Dirac's Theorem; the one relevant to this dissertation is by Bohman, Frieze, and Martin, who proved that for every α > 0, there exists C such that every n-vertex graph with minimum degree at least αn, upon the addition of Cn random edges, contains a cycle on n vertices with high probability. They also prove a directed version, where minimum degree is replaced by minimum in- and out-degree and cycle on n vertices is replaced by a directed cycle on n vertices where all the edges point in the same direction around the cycle. In Chapter 4, together with Araujo, Balogh, Piga, and Treglown, we generalize their result to obtain cycles of every length and orientation, simultaneously with high probability. Our main technique is a variant of an absorbing method of Montgomery, combined with a pseudorandomness condition and coupling technique of McDiarmid.

Graduation Semester

2024-08

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

© 2024 Robert A. Krueger

Owning Collections