{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/97401"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/97401","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Extremal problems on counting combinatorial structures","abstract":"The fast developing field of extremal combinatorics provides a diverse spectrum of powerful tools with many applications to economics, computer science, and optimization theory. In this thesis, we focus on counting and coloring problems in this field. The complete balanced bipartite graph on $n$ vertices has $\\floor{n^2/4}$ edges. Since all of its subgraphs are triangle-free, the number of (labeled) triangle-free graphs on $n$ vertices is at least $2^{\\floor{n^2/4}}$. This was shown to be the correct order of magnitude in a celebrated paper Erd\\H{o}s, Kleitman, and Rothschild from 1976, where the authors furthermore proved that almost all triangle-free graphs are bipartite. In Chapters 2 and 3 we study analogous problems for triangle-free graphs that are maximal with respect to inclusion. In Chapter 2, we solve the following problem of Paul Erd\\H{o}s: Determine or estimate the number of maximal triangle-free graphs on $n$ vertices. We show that the number of maximal triangle-free graphs is at most $2^{n^2/8+o(n^2)}$, which matches the previously known lower bound. Our proof uses among other tools the Ruzsa-Szemer\\'{e}di Triangle Removal Lemma and recent results on characterizing of the structure of independent sets in hypergraphs. This is a joint work with J\\'{o}zsef Balogh. In Chapter 3, we investigate the structure of maximal triangle-free graphs. We prove that almost all maximal triangle-free graphs admit a vertex partition $(X, Y)$ such that $G[X]$ is a perfect matching and $Y$ is an independent set. Our proof uses the Ruzsa-Szemer\\'{e}di Removal Lemma, the Erd\\H{o}s-Simonovits stability theorem, and recent results of Balogh-Morris-Samotij and Saxton-Thomason on the characterization of the structure of independent sets in hypergraphs. The proof also relies on a new bound on the number of maximal independent sets in triangle-free graphs with many vertex-disjoint $P_3$'s, which is of independent interest. This is a joint work with J\\'{o}zsef Balogh, Hong Liu, and Maryam Sharifzadeh. In Chapte 4, we seek families in posets with the smallest number of comparable pairs. Given a poset $P$, a family $\\F\\subseteq P$ is \\emph{centered} if it is obtained by `taking sets as close to the middle layer as possible'. A poset $P$ is said to have the \\emph{centeredness property} if for any $M$, among all families of size $M$ in $P$, centered families contain the minimum number of comparable pairs. Kleitman showed that the Boolean lattice $\\{0,1\\}^n$ has the centeredness property. It was conjectured by Noel, Scott, and Sudakov, and by Balogh and Wagner, that the poset $\\{0,1,\\ldots,k\\}^n$ also has the centeredness property, provided $n$ is sufficiently large compared to $k$. We show that this conjecture is false for all $k\\geq 2$ and investigate the range of $M$ for which it holds. Further, we improve a result of Noel, Scott, and Sudakov by showing that the poset of subspaces of $\\mathbb{F}_q^n$ has the centeredness property. Several open problems are also given. This is a joint result with J\\'{o}zsef Balogh and Adam Zsolt Wagner. In Chapter 5, we consider a graph coloring problem. Kim and Park have found an infinite family of graphs whose squares are not chromatic-choosable. Xuding Zhu asked whether there is some $k$ such that all $k$-th power graphs are chromatic-choosable. We answer this question in the negative: we show that there is a positive constant $c$ such that for any $k$ there is a family of graphs $G$ with $\\chi(G^k)$ unbounded and $\\chi_{\\ell}(G^k)\\geq c \\chi(G^k) \\log \\chi(G^k)$. We also provide an upper bound, $\\chi_{\\ell}(G^k)<\\chi(G^k)^3$ for $k>1$. This is a joint work with Nicholas Kosar, Benjamin Reiniger, and Elyse Yeager.","abstract_html":"The fast developing field of extremal combinatorics provides a diverse spectrum of powerful tools with many applications to economics, computer science, and optimization theory. In this thesis, we focus on counting and coloring problems in this field. The complete balanced bipartite graph on $n$ vertices has <span class=\"etd-inline-math\">\\floor{n<sup>2</sup>/4}</span> edges. Since all of its subgraphs are triangle-free, the number of (labeled) triangle-free graphs on $n$ vertices is at least <span class=\"etd-inline-math\">2<sup>\\floor{n<sup>2</sup>/4}</sup></span>. This was shown to be the correct order of magnitude in a celebrated paper Erd\\H{o}s, Kleitman, and Rothschild from 1976, where the authors furthermore proved that almost all triangle-free graphs are bipartite. In Chapters 2 and 3 we study analogous problems for triangle-free graphs that are maximal with respect to inclusion. In Chapter 2, we solve the following problem of Paul Erd\\H{o}s: Determine or estimate the number of maximal triangle-free graphs on $n$ vertices. We show that the number of maximal triangle-free graphs is at most <span class=\"etd-inline-math\">2<sup>n<sup>2</sup>/8+o(n<sup>2</sup>)</sup></span>, which matches the previously known lower bound. Our proof uses among other tools the Ruzsa-Szemer\\&#x27;{e}di Triangle Removal Lemma and recent results on characterizing of the structure of independent sets in hypergraphs. This is a joint work with J\\&#x27;{o}zsef Balogh. In Chapter 3, we investigate the structure of maximal triangle-free graphs. We prove that almost all maximal triangle-free graphs admit a vertex partition $(X, Y)$ such that $G[X]$ is a perfect matching and $Y$ is an independent set. Our proof uses the Ruzsa-Szemer\\&#x27;{e}di Removal Lemma, the Erd\\H{o}s-Simonovits stability theorem, and recent results of Balogh-Morris-Samotij and Saxton-Thomason on the characterization of the structure of independent sets in hypergraphs. The proof also relies on a new bound on the number of maximal independent sets in triangle-free graphs with many vertex-disjoint <span class=\"etd-inline-math\">P<sub>3</sub></span>&#x27;s, which is of independent interest. This is a joint work with J\\&#x27;{o}zsef Balogh, Hong Liu, and Maryam Sharifzadeh. In Chapte 4, we seek families in posets with the smallest number of comparable pairs. Given a poset $P$, a family $\\F\\subseteq P$ is \\emph{centered} if it is obtained by `taking sets as close to the middle layer as possible&#x27;. A poset $P$ is said to have the \\emph{centeredness property} if for any $M$, among all families of size $M$ in $P$, centered families contain the minimum number of comparable pairs. Kleitman showed that the Boolean lattice <span class=\"etd-inline-math\">\\{0,1\\}<sup>n</sup></span> has the centeredness property. It was conjectured by Noel, Scott, and Sudakov, and by Balogh and Wagner, that the poset <span class=\"etd-inline-math\">\\{0,1,\\ldots,k\\}<sup>n</sup></span> also has the centeredness property, provided $n$ is sufficiently large compared to $k$. We show that this conjecture is false for all $k\\geq 2$ and investigate the range of $M$ for which it holds. Further, we improve a result of Noel, Scott, and Sudakov by showing that the poset of subspaces of <span class=\"etd-inline-math\">\\mathbb{F}<sub>q</sub><sup>n</sup></span> has the centeredness property. Several open problems are also given. This is a joint result with J\\&#x27;{o}zsef Balogh and Adam Zsolt Wagner. In Chapter 5, we consider a graph coloring problem. Kim and Park have found an infinite family of graphs whose squares are not chromatic-choosable. Xuding Zhu asked whether there is some $k$ such that all $k$-th power graphs are chromatic-choosable. We answer this question in the negative: we show that there is a positive constant $c$ such that for any $k$ there is a family of graphs $G$ with <span class=\"etd-inline-math\">\\chi(G<sup>k</sup>)</span> unbounded and <span class=\"etd-inline-math\">\\chi<sub>\\ell</sub>(G<sup>k</sup>)\\geq c \\chi(G<sup>k</sup>) \\log \\chi(G<sup>k</sup>)</span>. We also provide an upper bound, <span class=\"etd-inline-math\">\\chi<sub>\\ell</sub>(G<sup>k</sup>)&lt;\\chi(G<sup>k</sup>)<sup>3</sup></span> for $k&gt;1$. This is a joint work with Nicholas Kosar, Benjamin Reiniger, and Elyse Yeager.","abstract_has_math":true,"creators":["Petrickova, Sarka"],"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 V.","Kirkpatrick, Kay","Molla, Theodore"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-08-10T19:15:25Z","date_published":"2017-08-10T19:15:25Z","updated_at":"2026-07-22T22:24:34Z","subjects":["Extremal","Counting","Triangle-free","Maximal","Structure","Poset","Comparable pair","Chromatic number","Choosability"],"languages":["en"],"rights":["Copyright 2017 Sarka Petrickova"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/97401","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 V.","Kirkpatrick, Kay","Molla, Theodore"]},{"key":"dc:creator","label":"Author","values":["Petrickova, Sarka"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-08-10T19:15:25Z","2017-04-19","2017-05"]},{"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":["Extremal","Counting","Triangle-free","Maximal","Structure","Poset","Comparable pair","Chromatic number","Choosability"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Sarka Petrickova"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/97401"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The fast developing field of extremal combinatorics provides a diverse spectrum of powerful tools with many applications to economics, computer science, and optimization theory. In this thesis, we focus on counting and coloring problems in this field. The complete balanced bipartite graph on $n$ vertices has $\\floor{n^2/4}$ edges. Since all of its subgraphs are triangle-free, the number of (labeled) triangle-free graphs on $n$ vertices is at least $2^{\\floor{n^2/4}}$. This was shown to be the correct order of magnitude in a celebrated paper Erd\\H{o}s, Kleitman, and Rothschild from 1976, where the authors furthermore proved that almost all triangle-free graphs are bipartite. In Chapters 2 and 3 we study analogous problems for triangle-free graphs that are maximal with respect to inclusion. In Chapter 2, we solve the following problem of Paul Erd\\H{o}s: Determine or estimate the number of maximal triangle-free graphs on $n$ vertices. We show that the number of maximal triangle-free graphs is at most $2^{n^2/8+o(n^2)}$, which matches the previously known lower bound. Our proof uses among other tools the Ruzsa-Szemer\\'{e}di Triangle Removal Lemma and recent results on characterizing of the structure of independent sets in hypergraphs. This is a joint work with J\\'{o}zsef Balogh. In Chapter 3, we investigate the structure of maximal triangle-free graphs. We prove that almost all maximal triangle-free graphs admit a vertex partition $(X, Y)$ such that $G[X]$ is a perfect matching and $Y$ is an independent set. Our proof uses the Ruzsa-Szemer\\'{e}di Removal Lemma, the Erd\\H{o}s-Simonovits stability theorem, and recent results of Balogh-Morris-Samotij and Saxton-Thomason on the characterization of the structure of independent sets in hypergraphs. The proof also relies on a new bound on the number of maximal independent sets in triangle-free graphs with many vertex-disjoint $P_3$'s, which is of independent interest. This is a joint work with J\\'{o}zsef Balogh, Hong Liu, and Maryam Sharifzadeh. In Chapte 4, we seek families in posets with the smallest number of comparable pairs. Given a poset $P$, a family $\\F\\subseteq P$ is \\emph{centered} if it is obtained by `taking sets as close to the middle layer as possible'. A poset $P$ is said to have the \\emph{centeredness property} if for any $M$, among all families of size $M$ in $P$, centered families contain the minimum number of comparable pairs. Kleitman showed that the Boolean lattice $\\{0,1\\}^n$ has the centeredness property. It was conjectured by Noel, Scott, and Sudakov, and by Balogh and Wagner, that the poset $\\{0,1,\\ldots,k\\}^n$ also has the centeredness property, provided $n$ is sufficiently large compared to $k$. We show that this conjecture is false for all $k\\geq 2$ and investigate the range of $M$ for which it holds. Further, we improve a result of Noel, Scott, and Sudakov by showing that the poset of subspaces of $\\mathbb{F}_q^n$ has the centeredness property. Several open problems are also given. This is a joint result with J\\'{o}zsef Balogh and Adam Zsolt Wagner. In Chapter 5, we consider a graph coloring problem. Kim and Park have found an infinite family of graphs whose squares are not chromatic-choosable. Xuding Zhu asked whether there is some $k$ such that all $k$-th power graphs are chromatic-choosable. We answer this question in the negative: we show that there is a positive constant $c$ such that for any $k$ there is a family of graphs $G$ with $\\chi(G^k)$ unbounded and $\\chi_{\\ell}(G^k)\\geq c \\chi(G^k) \\log \\chi(G^k)$. We also provide an upper bound, $\\chi_{\\ell}(G^k)<\\chi(G^k)^3$ for $k>1$. This is a joint work with Nicholas Kosar, Benjamin Reiniger, and Elyse Yeager.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-08-10 without embargo terms","The student, Sarka Petrickova, accepted the attached license on 2017-04-18 at 22:18.","The student, Sarka Petrickova, submitted this Dissertation for approval on 2017-04-18 at 22:38.","This Dissertation was approved for publication on 2017-04-19 at 17:35.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10879 on 2017-08-10 at 13:42:18","Made available in DSpace on 2017-08-10T19:15:25Z (GMT). No. of bitstreams: 2 PETRICKOVA-DISSERTATION-2017.pdf: 983778 bytes, checksum: c88020010e40e186b310658c9c2eaf7f (MD5) LICENSE.txt: 4213 bytes, checksum: 22c35ed49111e7923f4f4403832a9423 (MD5) Previous issue date: 2017-04-19"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Extremal problems on counting combinatorial structures"]}]}],"canonical_facts":{"dc:contributor":["Balogh, József","Kostochka, Alexandr V.","Kirkpatrick, Kay","Molla, Theodore"],"dc:creator":["Petrickova, Sarka"],"dc:date":["2017-08-10T19:15:25Z","2017-04-19","2017-05"],"dc:description":["The fast developing field of extremal combinatorics provides a diverse spectrum of powerful tools with many applications to economics, computer science, and optimization theory. In this thesis, we focus on counting and coloring problems in this field. The complete balanced bipartite graph on $n$ vertices has $\\floor{n^2/4}$ edges. Since all of its subgraphs are triangle-free, the number of (labeled) triangle-free graphs on $n$ vertices is at least $2^{\\floor{n^2/4}}$. This was shown to be the correct order of magnitude in a celebrated paper Erd\\H{o}s, Kleitman, and Rothschild from 1976, where the authors furthermore proved that almost all triangle-free graphs are bipartite. In Chapters 2 and 3 we study analogous problems for triangle-free graphs that are maximal with respect to inclusion. In Chapter 2, we solve the following problem of Paul Erd\\H{o}s: Determine or estimate the number of maximal triangle-free graphs on $n$ vertices. We show that the number of maximal triangle-free graphs is at most $2^{n^2/8+o(n^2)}$, which matches the previously known lower bound. Our proof uses among other tools the Ruzsa-Szemer\\'{e}di Triangle Removal Lemma and recent results on characterizing of the structure of independent sets in hypergraphs. This is a joint work with J\\'{o}zsef Balogh. In Chapter 3, we investigate the structure of maximal triangle-free graphs. We prove that almost all maximal triangle-free graphs admit a vertex partition $(X, Y)$ such that $G[X]$ is a perfect matching and $Y$ is an independent set. Our proof uses the Ruzsa-Szemer\\'{e}di Removal Lemma, the Erd\\H{o}s-Simonovits stability theorem, and recent results of Balogh-Morris-Samotij and Saxton-Thomason on the characterization of the structure of independent sets in hypergraphs. The proof also relies on a new bound on the number of maximal independent sets in triangle-free graphs with many vertex-disjoint $P_3$'s, which is of independent interest. This is a joint work with J\\'{o}zsef Balogh, Hong Liu, and Maryam Sharifzadeh. In Chapte 4, we seek families in posets with the smallest number of comparable pairs. Given a poset $P$, a family $\\F\\subseteq P$ is \\emph{centered} if it is obtained by `taking sets as close to the middle layer as possible'. A poset $P$ is said to have the \\emph{centeredness property} if for any $M$, among all families of size $M$ in $P$, centered families contain the minimum number of comparable pairs. Kleitman showed that the Boolean lattice $\\{0,1\\}^n$ has the centeredness property. It was conjectured by Noel, Scott, and Sudakov, and by Balogh and Wagner, that the poset $\\{0,1,\\ldots,k\\}^n$ also has the centeredness property, provided $n$ is sufficiently large compared to $k$. We show that this conjecture is false for all $k\\geq 2$ and investigate the range of $M$ for which it holds. Further, we improve a result of Noel, Scott, and Sudakov by showing that the poset of subspaces of $\\mathbb{F}_q^n$ has the centeredness property. Several open problems are also given. This is a joint result with J\\'{o}zsef Balogh and Adam Zsolt Wagner. In Chapter 5, we consider a graph coloring problem. Kim and Park have found an infinite family of graphs whose squares are not chromatic-choosable. Xuding Zhu asked whether there is some $k$ such that all $k$-th power graphs are chromatic-choosable. We answer this question in the negative: we show that there is a positive constant $c$ such that for any $k$ there is a family of graphs $G$ with $\\chi(G^k)$ unbounded and $\\chi_{\\ell}(G^k)\\geq c \\chi(G^k) \\log \\chi(G^k)$. We also provide an upper bound, $\\chi_{\\ell}(G^k)<\\chi(G^k)^3$ for $k>1$. This is a joint work with Nicholas Kosar, Benjamin Reiniger, and Elyse Yeager.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-08-10 without embargo terms","The student, Sarka Petrickova, accepted the attached license on 2017-04-18 at 22:18.","The student, Sarka Petrickova, submitted this Dissertation for approval on 2017-04-18 at 22:38.","This Dissertation was approved for publication on 2017-04-19 at 17:35.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10879 on 2017-08-10 at 13:42:18","Made available in DSpace on 2017-08-10T19:15:25Z (GMT). No. of bitstreams: 2 PETRICKOVA-DISSERTATION-2017.pdf: 983778 bytes, checksum: c88020010e40e186b310658c9c2eaf7f (MD5) LICENSE.txt: 4213 bytes, checksum: 22c35ed49111e7923f4f4403832a9423 (MD5) Previous issue date: 2017-04-19"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/97401"],"dc:language":["en"],"dc:rights":["Copyright 2017 Sarka Petrickova"],"dc:subject":["Extremal","Counting","Triangle-free","Maximal","Structure","Poset","Comparable pair","Chromatic number","Choosability"],"dc:title":["Extremal problems on counting combinatorial structures"],"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:24:34Z"}