{"id":{"repo_id":"washington","oai_identifier":"oai:digital.lib.washington.edu:1773/25221"},"canonical_url":"https://search.dev.ndltd.org/etd/washington/oai:digital.lib.washington.edu:1773/25221","repository":{"repo_id":"washington","name":"University of Washington","base_url":"https://digital.lib.washington.edu/server/oai/request"},"display":{"title":"Four Problems in Probability and Optimization","abstract":"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=\\theta=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.","abstract_html":"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 <span class=\"etd-inline-math\">d=&theta;=3</span> we exhibit a framework for deriving exact results within the scaling window using Poisson approximation. In the chapters on combinatorial optimization, we consider the <span class=\"etd-inline-math\">K<sub>i</sub></span>-cover problem and the max cut problem. We show that a family of facets arising from <span class=\"etd-inline-math\">K<sub>i</sub></span>-$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&#x27;s theta bodies to converge in the case <span class=\"etd-inline-math\">G = K<sub>n</sub></span>. We introduce a criterion for an invariant polynomial to be a sum of squares on the hypercube. This gives a simple proof of Laurent&#x27;s result that the theta body heirarchy requires at least $n/4$ steps to converge to the max cut polytope of <span class=\"etd-inline-math\">K<sub>n</sub></span>. It also allows us to give the first lower bounds on degrees of denominators in Hilbert&#x27;s 17th problem. In the last chapter, we consider the <span class=\"etd-inline-math\">S<sub>n</sub></span>-irreducible decomposition of the space of matchings on <span class=\"etd-inline-math\">K<sub>n</sub></span> 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.","abstract_has_math":true,"creators":["Pfeiffer, James"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Thomas, Rekha"],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-02-24","date_published":"2014-02-24","updated_at":"2026-07-24T05:58:23Z","subjects":["combinatorics; optimization; probability"],"languages":["en_US"],"rights":["Copyright is held by the individual authors."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1773/25221","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Thomas, Rekha"]},{"key":"dc:creator","label":"Author","values":["Pfeiffer, James"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-02-24T18:31:57Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-02-24T18:31:57Z"]},{"key":"dc:date.issued","label":"Date","values":["2014-02-24"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["combinatorics; optimization; probability"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright is held by the individual authors."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["Pfeiffer_washington_0250E_12513.pdf"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1773/25221"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (Ph.D.)--University of Washington, 2013"]},{"key":"dc:description.abstract","label":"Abstract","values":["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=\\theta=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."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Four Problems in Probability and Optimization"]}]}],"canonical_facts":{"dc:contributor.advisor":["Thomas, Rekha"],"dc:creator":["Pfeiffer, James"],"dc:date.accessioned":["2014-02-24T18:31:57Z"],"dc:date.available":["2014-02-24T18:31:57Z"],"dc:date.issued":["2014-02-24"],"dc:description":["Thesis (Ph.D.)--University of Washington, 2013"],"dc:description.abstract":["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=\\theta=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."],"dc:format.mimetype":["application/pdf"],"dc:identifier.other":["Pfeiffer_washington_0250E_12513.pdf"],"dc:identifier.uri":["http://hdl.handle.net/1773/25221"],"dc:language.iso":["en_US"],"dc:rights":["Copyright is held by the individual authors."],"dc:subject":["combinatorics; optimization; probability"],"dc:title":["Four Problems in Probability and Optimization"],"dc:type":["Thesis"]},"updated_at":"2026-07-24T05:58:23Z"}