{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/89148"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/89148","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Extremal graph theory: supersaturation and enumeration","abstract":"In this thesis, we study supersaturation and enumeration problems in extremal combinatorics. In Chapter 2, with Balogh, we disprove a conjecture of Erdos and Tuza concerning the number of different ways one can create a copy of K_4, a complete graph on 4 vertices, in a K_4-free graph. In Chapter 3, we extend a classical result of Kolaitis, Promel and Rothschild on the typical structure of graphs forbidding a clique of fixed order as a subgraph, showing that the order of the forbidden clique can be as large as some polylogarithmic function of the order of the host graph. This is based on joint work with Balogh, Bushaw, Collares Neto, Morris and Sharifzadeh. In Chapter 4 and Chapter 5, we study the number of maximal sum-free subsets of the set [n] := {1, 2, . . . , n}. Together with Balogh, Sharifzadeh and Treglown, we show that, for each 1 ≤ i ≤ 4, there are constants Ci such that the number of maximal sum-free subsets in [n] is (C_i + o(1))2^{n/4}, where i ≡ n mod 4. This resolves a conjecture of Cameron and Erdos. In Chapter 6, with Balogh and Sharifzadeh, we study the number of subsets of [n] which does not contain an arithmetic progression of a fixed length. This addresses another question of Cameron and Erdos and provides an optimal bound for infinitely many n. As corollaries, we improve the known transference results on arithmetic progressions.","abstract_html":"In this thesis, we study supersaturation and enumeration problems in extremal combinatorics. In Chapter 2, with Balogh, we disprove a conjecture of Erdos and Tuza concerning the number of different ways one can create a copy of K_4, a complete graph on 4 vertices, in a K_4-free graph. In Chapter 3, we extend a classical result of Kolaitis, Promel and Rothschild on the typical structure of graphs forbidding a clique of fixed order as a subgraph, showing that the order of the forbidden clique can be as large as some polylogarithmic function of the order of the host graph. This is based on joint work with Balogh, Bushaw, Collares Neto, Morris and Sharifzadeh. In Chapter 4 and Chapter 5, we study the number of maximal sum-free subsets of the set [n] := {1, 2, . . . , n}. Together with Balogh, Sharifzadeh and Treglown, we show that, for each 1 ≤ i ≤ 4, there are constants Ci such that the number of maximal sum-free subsets in [n] is (C_i + o(1))2^{n/4}, where i ≡ n mod 4. This resolves a conjecture of Cameron and Erdos. In Chapter 6, with Balogh and Sharifzadeh, we study the number of subsets of [n] which does not contain an arithmetic progression of a fixed length. This addresses another question of Cameron and Erdos and provides an optimal bound for infinitely many n. As corollaries, we improve the known transference results on arithmetic progressions.","abstract_has_math":false,"creators":["Liu, Hong"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Balogh, Jozsef","Kostochka, Alexandr","Reznick, Bruce","Molla, Theo"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-03-02T20:24:13Z","date_published":"2016-03-02T20:24:13Z","updated_at":"2026-07-22T22:26:32Z","subjects":["Supersaturation","Enumeration","Typical Structure","Extremal Combinatorics"],"languages":["en"],"rights":["Copyright 2015 Hong Liu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/89148","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Balogh, Jozsef","Kostochka, Alexandr","Reznick, Bruce","Molla, Theo"]},{"key":"dc:creator","label":"Author","values":["Liu, Hong"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2016-03-02T20:24:13Z","2018-03-03T10:15:22Z","2015-12-04","2015-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Supersaturation","Enumeration","Typical Structure","Extremal Combinatorics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2015 Hong Liu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/89148"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this thesis, we study supersaturation and enumeration problems in extremal combinatorics. In Chapter 2, with Balogh, we disprove a conjecture of Erdos and Tuza concerning the number of different ways one can create a copy of K_4, a complete graph on 4 vertices, in a K_4-free graph. In Chapter 3, we extend a classical result of Kolaitis, Promel and Rothschild on the typical structure of graphs forbidding a clique of fixed order as a subgraph, showing that the order of the forbidden clique can be as large as some polylogarithmic function of the order of the host graph. This is based on joint work with Balogh, Bushaw, Collares Neto, Morris and Sharifzadeh. In Chapter 4 and Chapter 5, we study the number of maximal sum-free subsets of the set [n] := {1, 2, . . . , n}. Together with Balogh, Sharifzadeh and Treglown, we show that, for each 1 ≤ i ≤ 4, there are constants Ci such that the number of maximal sum-free subsets in [n] is (C_i + o(1))2^{n/4}, where i ≡ n mod 4. This resolves a conjecture of Cameron and Erdos. In Chapter 6, with Balogh and Sharifzadeh, we study the number of subsets of [n] which does not contain an arithmetic progression of a fixed length. This addresses another question of Cameron and Erdos and provides an optimal bound for infinitely many n. As corollaries, we improve the known transference results on arithmetic progressions.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2017-12-01","The student, Hong Liu, accepted the attached license on 2015-12-03 at 15:07.","The student, Hong Liu, submitted this Dissertation for approval on 2015-12-03 at 15:23.","This Dissertation was approved for publication on 2015-12-04 at 10:20.","DSpace SAF Submission Ingestion Package generated from Vireo submission #8926 on 2016-03-02 at 14:07:47","Made available in DSpace on 2016-03-02T20:24:13Z (GMT). No. of bitstreams: 2 LIU-DISSERTATION-2015.pdf: 649375 bytes, checksum: e31048aed7fc98a0b6909b622025628b (MD5) LICENSE.txt: 4205 bytes, checksum: 61c7841dee7bd251956c403163af5fab (MD5) Previous issue date: 2015-12-04","Embargo set by: Seth Robbins for item 91350 Lift date: 2018-03-02T20:24:31Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 91350 on 2018-03-03T10:15:22Z."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Extremal graph theory: supersaturation and enumeration"]}]}],"canonical_facts":{"dc:contributor":["Balogh, Jozsef","Kostochka, Alexandr","Reznick, Bruce","Molla, Theo"],"dc:creator":["Liu, Hong"],"dc:date":["2016-03-02T20:24:13Z","2018-03-03T10:15:22Z","2015-12-04","2015-12"],"dc:description":["In this thesis, we study supersaturation and enumeration problems in extremal combinatorics. In Chapter 2, with Balogh, we disprove a conjecture of Erdos and Tuza concerning the number of different ways one can create a copy of K_4, a complete graph on 4 vertices, in a K_4-free graph. In Chapter 3, we extend a classical result of Kolaitis, Promel and Rothschild on the typical structure of graphs forbidding a clique of fixed order as a subgraph, showing that the order of the forbidden clique can be as large as some polylogarithmic function of the order of the host graph. This is based on joint work with Balogh, Bushaw, Collares Neto, Morris and Sharifzadeh. In Chapter 4 and Chapter 5, we study the number of maximal sum-free subsets of the set [n] := {1, 2, . . . , n}. Together with Balogh, Sharifzadeh and Treglown, we show that, for each 1 ≤ i ≤ 4, there are constants Ci such that the number of maximal sum-free subsets in [n] is (C_i + o(1))2^{n/4}, where i ≡ n mod 4. This resolves a conjecture of Cameron and Erdos. In Chapter 6, with Balogh and Sharifzadeh, we study the number of subsets of [n] which does not contain an arithmetic progression of a fixed length. This addresses another question of Cameron and Erdos and provides an optimal bound for infinitely many n. As corollaries, we improve the known transference results on arithmetic progressions.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2017-12-01","The student, Hong Liu, accepted the attached license on 2015-12-03 at 15:07.","The student, Hong Liu, submitted this Dissertation for approval on 2015-12-03 at 15:23.","This Dissertation was approved for publication on 2015-12-04 at 10:20.","DSpace SAF Submission Ingestion Package generated from Vireo submission #8926 on 2016-03-02 at 14:07:47","Made available in DSpace on 2016-03-02T20:24:13Z (GMT). No. of bitstreams: 2 LIU-DISSERTATION-2015.pdf: 649375 bytes, checksum: e31048aed7fc98a0b6909b622025628b (MD5) LICENSE.txt: 4205 bytes, checksum: 61c7841dee7bd251956c403163af5fab (MD5) Previous issue date: 2015-12-04","Embargo set by: Seth Robbins for item 91350 Lift date: 2018-03-02T20:24:31Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 91350 on 2018-03-03T10:15:22Z."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/89148"],"dc:language":["en"],"dc:rights":["Copyright 2015 Hong Liu"],"dc:subject":["Supersaturation","Enumeration","Typical Structure","Extremal Combinatorics"],"dc:title":["Extremal graph theory: supersaturation and enumeration"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:32Z"}