{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/122166"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/122166","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Semi-algebraic graphs and hypergraphs in incidence geometry","abstract":"A (hyper)graph is semi-algebraic if its vertices are points in some Euclidean spaces and the (hyper)edge relation is defined by a finite set of polynomial inequalities. Semi-algebraic (hyper)graphs have been studied extensively in recent years, and many classical results in (hyper)graph theory such as Ramsey's theorem and Szemerédi's regularity lemma can be significantly improved in the semi-algebraic setting. In this dissertation, we discuss three problems in incidence geometry where the bounds for semi-algebraic (hyper)graphs are generally better than the ones for arbitrary (hyper)graphs : (1) what is the maximum number of hyperedges in a hypergraph forbidding some pattern? (2) what is the most compact way to decompose a graph by complete bipartite subgraphs? and (3) what is the maximum number of edges in a graph where no two neighbor sets have a large intersection? As most graphs and hypergraphs arising from problems in discrete geometry are semi-algebraic, our results have applications to discrete geometry. The main tools used in our proofs include some version of polynomial partitioning, a Milnor-Thom-type result from topology and a packing-type result in set system theory.","abstract_html":"A (hyper)graph is semi-algebraic if its vertices are points in some Euclidean spaces and the (hyper)edge relation is defined by a finite set of polynomial inequalities. Semi-algebraic (hyper)graphs have been studied extensively in recent years, and many classical results in (hyper)graph theory such as Ramsey's theorem and Szemerédi's regularity lemma can be significantly improved in the semi-algebraic setting. In this dissertation, we discuss three problems in incidence geometry where the bounds for semi-algebraic (hyper)graphs are generally better than the ones for arbitrary (hyper)graphs : (1) what is the maximum number of hyperedges in a hypergraph forbidding some pattern? (2) what is the most compact way to decompose a graph by complete bipartite subgraphs? and (3) what is the maximum number of edges in a graph where no two neighbor sets have a large intersection? As most graphs and hypergraphs arising from problems in discrete geometry are semi-algebraic, our results have applications to discrete geometry. The main tools used in our proofs include some version of polynomial partitioning, a Milnor-Thom-type result from topology and a packing-type result in set system theory.","abstract_has_math":false,"creators":["Do, Thao Thi Thu."],"institution":"Massachusetts Institute of Technology","degree_name":"Doctoral","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Mathematics","school":null,"contributors":[],"advisors":["Larry Guth."],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019","date_published":"2019","updated_at":"2026-07-22T22:21:32Z","subjects":["Mathematics."],"languages":["eng"],"rights":["MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/122166","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Larry Guth."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Mathematics","Math"]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Department of Mathematics."]},{"key":"dc:creator","label":"Author","values":["Do, Thao Thi Thu."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2019-09-16T22:33:51Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2019-09-16T22:33:51Z"]},{"key":"dc:date.issued","label":"Date","values":["2019"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctoral"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/122166"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2019","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 63-68)."]},{"key":"dc:description.abstract","label":"Abstract","values":["A (hyper)graph is semi-algebraic if its vertices are points in some Euclidean spaces and the (hyper)edge relation is defined by a finite set of polynomial inequalities. Semi-algebraic (hyper)graphs have been studied extensively in recent years, and many classical results in (hyper)graph theory such as Ramsey's theorem and Szemerédi's regularity lemma can be significantly improved in the semi-algebraic setting. In this dissertation, we discuss three problems in incidence geometry where the bounds for semi-algebraic (hyper)graphs are generally better than the ones for arbitrary (hyper)graphs : (1) what is the maximum number of hyperedges in a hypergraph forbidding some pattern? (2) what is the most compact way to decompose a graph by complete bipartite subgraphs? and (3) what is the maximum number of edges in a graph where no two neighbor sets have a large intersection? As most graphs and hypergraphs arising from problems in discrete geometry are semi-algebraic, our results have applications to discrete geometry. The main tools used in our proofs include some version of polynomial partitioning, a Milnor-Thom-type result from topology and a packing-type result in set system theory."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph. D."]},{"key":"dc:title","label":"Title","values":["Semi-algebraic graphs and hypergraphs in incidence geometry"]}]}],"canonical_facts":{"dc:contributor.advisor":["Larry Guth."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Mathematics","Math"],"dc:contributor.other":["Massachusetts Institute of Technology. Department of Mathematics."],"dc:creator":["Do, Thao Thi Thu."],"dc:date.accessioned":["2019-09-16T22:33:51Z"],"dc:date.available":["2019-09-16T22:33:51Z"],"dc:date.issued":["2019"],"dc:description":["Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2019","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 63-68)."],"dc:description.abstract":["A (hyper)graph is semi-algebraic if its vertices are points in some Euclidean spaces and the (hyper)edge relation is defined by a finite set of polynomial inequalities. Semi-algebraic (hyper)graphs have been studied extensively in recent years, and many classical results in (hyper)graph theory such as Ramsey's theorem and Szemerédi's regularity lemma can be significantly improved in the semi-algebraic setting. In this dissertation, we discuss three problems in incidence geometry where the bounds for semi-algebraic (hyper)graphs are generally better than the ones for arbitrary (hyper)graphs : (1) what is the maximum number of hyperedges in a hypergraph forbidding some pattern? (2) what is the most compact way to decompose a graph by complete bipartite subgraphs? and (3) what is the maximum number of edges in a graph where no two neighbor sets have a large intersection? As most graphs and hypergraphs arising from problems in discrete geometry are semi-algebraic, our results have applications to discrete geometry. The main tools used in our proofs include some version of polynomial partitioning, a Milnor-Thom-type result from topology and a packing-type result in set system theory."],"dc:description.degree":["Ph. D."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/122166"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Mathematics."],"dc:title":["Semi-algebraic graphs and hypergraphs in incidence geometry"],"dc:type":["Thesis"],"thesis:degree_name":["Doctoral"]},"updated_at":"2026-07-22T22:21:32Z"}