### Description

TitleA few results regarding thresholds

Date Created2020

Other Date2020-10 (degree)

Extent1 online resource (ix, 64 pages)

DescriptionThis 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 speciﬁc graph theoretic thresholds (in the case of Chapter 5), or showing how diﬀerent 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 veriﬁed 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 signiﬁcantly: 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 ﬁnite 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 diﬃcult 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 “Sunﬂower 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 ﬁnite 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 ﬁxed 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 ﬁxed choice of λ).

NotePh.D.

NoteIncludes bibliographical references

Genretheses, ETD doctoral

LanguageEnglish

CollectionSchool of Graduate Studies Electronic Theses and Dissertations

Organization NameRutgers, The State University of New Jersey

RightsThe author owns the copyright to this work.