Text

theses

ETD doctoral

This thesis consists of four parts, each regarding a topic from extremal combinatorics. While only Chapters 3 and 4 are directly related, each in some way concerns the concept of thresholds, whether providing a new sharp threshold result for regular properties (in the case of Chapter 2), proving specific graph theoretic thresholds (in the case of Chapter 5), or showing how different thresholds are related (as in Chapters 3 and 4).

In Chapter 2, we answer a question of Cameron, Frankl, and Kantor from 1989, extending a result of Ellis and Narayanan. They verified a conjecture of Frankl, that any 3-wise intersecting family of subsets of {1, 2,..., n} admitting a transitive automorphism group has cardinality o(2n). However, a construction of Frankl demonstrates that the same conclusion need not hold under the weaker constraint of being regular. We show that the restriction of admitting a transitive automorphism group may be relaxed significantly: we prove that any 3-wise intersecting family of subsets of {1, 2,..., n} that is regular and increasing has cardinality o(2n). In Chapter 3, we prove a conjecture of Talagrand, itself a fractional version of the “expectation-threshold” conjecture of Kahn and Kalai. We show that for any increasing family F on a finite set X, we have p_c(F) = O(q_f(F) ln ℓ(F)), where p_c(F) and q_f (F) are the threshold and “fractional expectation-threshold” of F, and ℓ(F) is the maximum size of a minimal member of F. This easily implies several heretofore difficult results and conjectures in probabilistic combinatorics, including thresholds for perfect hypergraph matchings (Johansson–Kahn–Vu), bounded degree spanning trees (Montgomery), and bounded degree graphs (new). We also resolve (and vastly extend) the “axial” version of the random multi-dimensional assignment problem (earlier considered by Martin–Mézard–Rivoire and Frieze–Sorkin). Our approach builds on a breakthrough of Alweiss, Lovett, Wu and Zhang on the Erdős–Rado “Sunflower Conjecture.”

In Chapter 4, we address a special case of a conjecture of Talagrand relating the “expectation” and “fractional-expectation” thresholds of an increasing family F of a finite set X. The full conjecture implies the equivalence of the so-called “fractional expectation-threshold” conjecture shown in Chapter 3 to the “expectation-threshold” conjecture of Kahn and Kalai. The conjecture discussed in this chapter states there is a fixed J such that if p ∈ [0, 1] admits λ : X → [0, 1] with

Sum_{S⊆F} λ_S ≥ 1 ∀F ∈ F

and

Sum_S λ_S p^|S| ≤ 1/2

(a.k.a. F is weakly p-small), then p/J admits such a λ taking values in {0, 1} (F is (p/J)-small). Talagrand showed this when λ is supported on singletons and suggested, as a more challenging test case, proving it when λ is supported on pairs. This chapter presents such a proof.

Expanding on work on the rigidity of random graph structures going back to Erdős and Rényi, Chapter 5 introduces a new notion of “local” rigidity. Say H is locally t-rigid if all its induced subgraphs on t vertices are rigid. Then for what t = t(n, p) is Gn,p is locally t-rigid? To answer this question, we produce machinery which allows for more careful analysis of the probability of appearance of non-trivial automorphisms based on their “type.” In particular, for any cycle type, λ, we give a threshold t(λ) for the appearance of automorphisms of that type such that, if m(λ) is the size of the largest induced subgraph of G_(n, 1/2) whose automorphism group has a permutation of type λ, then with high probability m < t + sqrt(5n log n) for all λ (and with high probability |t − m| < sqrt(5n log n) for any fixed choice of λ).

ETD_11220

Ph.D.

Includes bibliographical references

doi:10.7282/t3-txt9-bq08

The author owns the copyright to this work.