The Local Lemma has been a powerful tool in probabilistic combinatorics. Recent advances by Moser and Tardos have provided an algorithmic variant of the Local Lemma. We provide an overview of the analysis of their algorithm, and provide an implementation of the algorithm to a hypergraph coloring problem.
","abstract_html":"<p>The Local Lemma has been a powerful tool in probabilistic combinatorics. Recent advances by Moser and Tardos have provided an algorithmic variant of the Local Lemma. We provide an overview of the analysis of their algorithm, and provide an implementation of the algorithm to a hypergraph coloring problem.</p>","abstract_has_math":false,"creators":["Kay, William"],"institution":null,"degree_name":"M.A.","degree_level":"Campus Access Thesis","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Joshua Cooper"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012-01-01T08:00:00Z","date_published":"2012-01-01T08:00:00Z","updated_at":"2026-07-24T04:38:14Z","subjects":["Mathematics","Physical Sciences and Mathematics","Algorithms","Hypergraphs","Local Lemma","Pythagorean Triples"],"languages":[],"rights":["© 2012, William Kay"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://scholarcommons.sc.edu/etd/1602","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Joshua Cooper"]},{"key":"dc:creator","label":"Author","values":["Kay, William"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Campus Access Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.A."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics","Physical Sciences and Mathematics","Algorithms","Hypergraphs","Local Lemma","Pythagorean Triples"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["© 2012, William Kay"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://scholarcommons.sc.edu/etd/1602"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["The Local Lemma has been a powerful tool in probabilistic combinatorics. Recent advances by Moser and Tardos have provided an algorithmic variant of the Local Lemma. We provide an overview of the analysis of their algorithm, and provide an implementation of the algorithm to a hypergraph coloring problem.
"]},{"key":"dc:title","label":"Title","values":["An Overview of the Constructive Local Lemma"]}]}],"canonical_facts":{"dc:contributor":["Joshua Cooper"],"dc:creator":["Kay, William"],"dc:description.abstract":["The Local Lemma has been a powerful tool in probabilistic combinatorics. Recent advances by Moser and Tardos have provided an algorithmic variant of the Local Lemma. We provide an overview of the analysis of their algorithm, and provide an implementation of the algorithm to a hypergraph coloring problem.
"],"dc:identifier":["https://scholarcommons.sc.edu/etd/1602"],"dc:rights":["© 2012, William Kay"],"dc:subject":["Mathematics","Physical Sciences and Mathematics","Algorithms","Hypergraphs","Local Lemma","Pythagorean Triples"],"dc:title":["An Overview of the Constructive Local Lemma"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Campus Access Thesis"],"thesis:degree_name":["M.A."]},"updated_at":"2026-07-24T04:38:14Z"}