Four Problems in Probability and Optimization

This thesis studies bootstrap percolation, a problem in probability, as well as several topics in the application of sums of squares to combinatorial optimization. In the chapter on percolation, we bound the critical probability for bootstrap percolation on the Hamming torus, as well as the critical probability for $i$-dimensional subgraphs to percolate. In the case d=θ=3 we exhibit a framework for deriving exact results within the scaling window using Poisson approximation. In the chapters on combinatorial optimization, we consider the K_i-cover problem and the max cut problem. We show that a family of facets arising from K_i-$p$-holes is valid on the $i/2$ theta body. We also prove an integrality gap of $1/2$ for the triangle free problem, and show that at least $n/2$ steps are required for the triangle free problem's theta bodies to converge in the case G = K_n. We introduce a criterion for an invariant polynomial to be a sum of squares on the hypercube. This gives a simple proof of Laurent's result that the theta body heirarchy requires at least $n/4$ steps to converge to the max cut polytope of K_n. It also allows us to give the first lower bounds on degrees of denominators in Hilbert's 17th problem. In the last chapter, we consider the S_n-irreducible decomposition of the space of matchings on K_n as given by Barbasch and Vogan. We give an explicit map of the isomorphism in their result. We also generalize their approach to matchings on hypergraphs.

Author dc:creator

• Pfeiffer, James

Advisor dc:contributor.advisor

• Thomas, Rekha

• combinatorics; optimization; probability

Statement dc:rights

• Copyright is held by the individual authors.

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/1773/25221

OAI identifier oai:identifier

oai:digital.lib.washington.edu:1773/25221