Text

theses

ETD_7935

Ph.D.

Includes bibliographical references

This dissertation discusses four problems taken from various areas of combinatorics— stability results, extremal set systems, information theory, and hypergraph matchings. Though diverse in content, the unifying theme throughout is that each proof relies on the machinery of probabilistic combinatorics. The first chapter offers a summary.
In the second chapter, we prove a stability version of a general result that bounds the permanent of a matrix in terms of its operator norm. More specifically, suppose A is an n × n matrix over C (resp. R), and let P denote the set of n × n matrices over C (resp. R) that can be written as a permutation matrix times a unitary diagonal matrix. Then it is known that the permanent of A satisfies |perm(A)| ≤ kAk n 2 with equality iff A/kAk2 ∈ P (where kAk2 is the operator 2-norm of A). We show a stability version of this result asserting that unless A is very close (in a particular sense) to one of these extremal matrices, its permanent is exponentially smaller (as a function of n) than kAk n 2 . In particular, for any fixed α, β > 0, we show that |perm(A)| is exponentially smaller than kAk n 2 unless all but at most αn rows contain entries of modulus at least kAk2(1 − β).
In the third chapter, we prove a randomized result extending the classical Erdos– Ko–Rado theorem. Namely, let Kp(n, k) denote the random subgraph of the usual Kneser graph K(n, k) in which edges appear independently, each with probability p. Answering a question of Bollobas, Narayanan, and Raigorodskii, we show that there is a fixed p < 1 such that almost surely (i.e., with probability tending to 1) the maximum independent sets of Kp(2k + 1, k) are precisely the sets {A ∈ V (K(2k + 1, k)) : x ∈ A} (x ∈ [2k + 1]). We also complete the determination of the order of magnitude of the “threshold” for the above property for general k and n ≥ 2k + 2. This is new for k ∼ n/2, while for smaller k it is a recent result of Das and Tran.
In the fourth chapter, we prove the following conjecture of Leighton and Moitra. If σ is a random (not necessarily uniform) permutation of [n] such that for all i, j |P(σ(i) < σ(j)) − 1/2| > ε, then the binary entropy of σ is at most (1 − ϑε) log2 n! for some (fixed) positive ϑε. If we further assume P(σ(i) < σ(j)) > 1/2 + ε for all i < j, the theorem is due to Leighton and Moitra; for this case we give a short proof with a better ϑε.
Finally, in the fifth chapter, we extend the notion of (random) k-out graphs and consider when a k-out hypergraph is likely to have a perfect fractional matching. In particular, we show that for each r there is a k = k(r) such that the k-out r-uniform hypergraph on n vertices almost surely has a perfect fractional matching and prove an analogous result for r-uniform r-partite hypergraphs. This is based on a new notion of hypergraph expansion and the observation that sufficiently expansive hypergraphs admit perfect fractional matchings. As a further application, we give a short proof of a stopping-time result originally due to Krivelevich.

by Patrick Devlin

doi:10.7282/T3G163SM

ETD doctoral

The author owns the copyright to this work.