{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/107931"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/107931","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Enumerating combinatorial objects with limited sub-configurations","abstract":"Many well-studied problems in extremal combinatorics concern the number and the typical structure of discrete objects with forbidden substructures. Over the past decades, such problems have been extensively studied for various objects by many notable researchers. This thesis focuses on several problems of this type using various techniques. In Chapter 2, we investigate the family of linear hypergraphs with forbidden linear cycles. A substantial part of the work indeed focuses on a closely related problem, the study of the family of graphs with limited short even cycles, which may be of independent interest. To attack this problem, we introduce a new variant of the graph container algorithm. Another application of it to additive combinatorics is presented in Chapter 3 on generalized Sidon sets. In Chapter 4, we investigate an enumeration problem on Gallai colorings, i.e. rainbow triangle-free colorings. In particular, we describe the typical structure of Gallai r-colorings of complete graphs, and complete the characterization of the extremal graphs for Gallai colorings. This work heavily relies on the hypergraph container method, and some ad-hoc stability analysis. Another closely related problem is the study of sparse analogue of classical extremal results in random graphs, for example, the Erdős-Stone theorem, as it can also be interpreted as counting graphs in the corresponding probability space. In Chapter 5, we show a random analogue of the famous Erdős-Gallai theorem on extremal functions of paths.","abstract_html":"Many well-studied problems in extremal combinatorics concern the number and the typical structure of discrete objects with forbidden substructures. Over the past decades, such problems have been extensively studied for various objects by many notable researchers. This thesis focuses on several problems of this type using various techniques. In Chapter 2, we investigate the family of linear hypergraphs with forbidden linear cycles. A substantial part of the work indeed focuses on a closely related problem, the study of the family of graphs with limited short even cycles, which may be of independent interest. To attack this problem, we introduce a new variant of the graph container algorithm. Another application of it to additive combinatorics is presented in Chapter 3 on generalized Sidon sets. In Chapter 4, we investigate an enumeration problem on Gallai colorings, i.e. rainbow triangle-free colorings. In particular, we describe the typical structure of Gallai r-colorings of complete graphs, and complete the characterization of the extremal graphs for Gallai colorings. This work heavily relies on the hypergraph container method, and some ad-hoc stability analysis. Another closely related problem is the study of sparse analogue of classical extremal results in random graphs, for example, the Erdős-Stone theorem, as it can also be interpreted as counting graphs in the corresponding probability space. In Chapter 5, we show a random analogue of the famous Erdős-Gallai theorem on extremal functions of paths.","abstract_has_math":false,"creators":["Li, Lina"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Balogh, József","Kostochka, Alexandr","Ford, Kevin","Lavrov, Mikhail"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-08-26T21:54:32Z","date_published":"2020-08-26T21:54:32Z","updated_at":"2026-07-22T22:24:47Z","subjects":["Combinatorics","Graph theory","container method"],"languages":["en"],"rights":["2020 by Lina Li. All rights reserved."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/107931","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Balogh, József","Kostochka, Alexandr","Ford, Kevin","Lavrov, Mikhail"]},{"key":"dc:creator","label":"Author","values":["Li, Lina"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-08-26T21:54:32Z","2020-04-30","2020-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"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":["Combinatorics","Graph theory","container method"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["2020 by Lina Li. All rights reserved."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/107931"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Many well-studied problems in extremal combinatorics concern the number and the typical structure of discrete objects with forbidden substructures. Over the past decades, such problems have been extensively studied for various objects by many notable researchers. This thesis focuses on several problems of this type using various techniques. In Chapter 2, we investigate the family of linear hypergraphs with forbidden linear cycles. A substantial part of the work indeed focuses on a closely related problem, the study of the family of graphs with limited short even cycles, which may be of independent interest. To attack this problem, we introduce a new variant of the graph container algorithm. Another application of it to additive combinatorics is presented in Chapter 3 on generalized Sidon sets. In Chapter 4, we investigate an enumeration problem on Gallai colorings, i.e. rainbow triangle-free colorings. In particular, we describe the typical structure of Gallai r-colorings of complete graphs, and complete the characterization of the extremal graphs for Gallai colorings. This work heavily relies on the hypergraph container method, and some ad-hoc stability analysis. Another closely related problem is the study of sparse analogue of classical extremal results in random graphs, for example, the Erdős-Stone theorem, as it can also be interpreted as counting graphs in the corresponding probability space. In Chapter 5, we show a random analogue of the famous Erdős-Gallai theorem on extremal functions of paths.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-08-25 without embargo terms","The student, Lina Li, accepted the attached license on 2020-04-27 at 17:19.","The student, Lina Li, submitted this Dissertation for approval on 2020-04-27 at 17:32.","This Dissertation was approved for publication on 2020-04-30 at 16:52.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15091 on 2020-08-25 at 17:09:06","Made available in DSpace on 2020-08-26T21:54:32Z (GMT). No. of bitstreams: 3 LI-DISSERTATION-2020.pdf: 683139 bytes, checksum: 1760edc4f2cf94a8ff662cddaccbb962 (MD5) LICENSE.txt: 4204 bytes, checksum: a708b5c7cef51833d430466d7b4a6714 (MD5) PROQUEST_LICENSE.txt: 4550 bytes, checksum: a0637892659d9f1396c68f76841776ae (MD5) Previous issue date: 2020-04-30"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Enumerating combinatorial objects with limited sub-configurations"]}]}],"canonical_facts":{"dc:contributor":["Balogh, József","Kostochka, Alexandr","Ford, Kevin","Lavrov, Mikhail"],"dc:creator":["Li, Lina"],"dc:date":["2020-08-26T21:54:32Z","2020-04-30","2020-05"],"dc:description":["Many well-studied problems in extremal combinatorics concern the number and the typical structure of discrete objects with forbidden substructures. Over the past decades, such problems have been extensively studied for various objects by many notable researchers. This thesis focuses on several problems of this type using various techniques. In Chapter 2, we investigate the family of linear hypergraphs with forbidden linear cycles. A substantial part of the work indeed focuses on a closely related problem, the study of the family of graphs with limited short even cycles, which may be of independent interest. To attack this problem, we introduce a new variant of the graph container algorithm. Another application of it to additive combinatorics is presented in Chapter 3 on generalized Sidon sets. In Chapter 4, we investigate an enumeration problem on Gallai colorings, i.e. rainbow triangle-free colorings. In particular, we describe the typical structure of Gallai r-colorings of complete graphs, and complete the characterization of the extremal graphs for Gallai colorings. This work heavily relies on the hypergraph container method, and some ad-hoc stability analysis. Another closely related problem is the study of sparse analogue of classical extremal results in random graphs, for example, the Erdős-Stone theorem, as it can also be interpreted as counting graphs in the corresponding probability space. In Chapter 5, we show a random analogue of the famous Erdős-Gallai theorem on extremal functions of paths.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-08-25 without embargo terms","The student, Lina Li, accepted the attached license on 2020-04-27 at 17:19.","The student, Lina Li, submitted this Dissertation for approval on 2020-04-27 at 17:32.","This Dissertation was approved for publication on 2020-04-30 at 16:52.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15091 on 2020-08-25 at 17:09:06","Made available in DSpace on 2020-08-26T21:54:32Z (GMT). No. of bitstreams: 3 LI-DISSERTATION-2020.pdf: 683139 bytes, checksum: 1760edc4f2cf94a8ff662cddaccbb962 (MD5) LICENSE.txt: 4204 bytes, checksum: a708b5c7cef51833d430466d7b4a6714 (MD5) PROQUEST_LICENSE.txt: 4550 bytes, checksum: a0637892659d9f1396c68f76841776ae (MD5) Previous issue date: 2020-04-30"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/107931"],"dc:language":["en"],"dc:rights":["2020 by Lina Li. All rights reserved."],"dc:subject":["Combinatorics","Graph theory","container method"],"dc:title":["Enumerating combinatorial objects with limited sub-configurations"],"dc:type":["text","Thesis"],"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:24:47Z"}