{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/100954"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/100954","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"On some problems in extremal, probabilistic and enumerative combinatorics","abstract":"This is a study of a small selection of problems from various areas of Combinatorics and Graph Theory, a fast developing field that provides a diverse spectrum of powerful tools with numerous applications to computer science, optimization theory and economics. In this thesis, we focus on extremal, probabilistic and enumerative problems in this field. A central theorem in combinatorics is Sperner's Theorem, which determines the maximum size of a family $\\F\\subseteq \\P(n)$ that does not contain a $2$-chain $F_1\\subsetneq F_2$. Erd\\H{o}s later extended this result and determined the largest family not containing a $k$-chain $F_1\\subsetneq \\ldots \\subsetneq F_k$. Erd\\H{o}s and Katona and later Kleitman asked how many such chains must appear in families whose size is larger than the corresponding extremal result. In Chapter 2 we answer their question for all families of size at most $(1-\\eps)2^n$, provided $n$ is sufficiently larger compared to $k$ and $\\eps$. The result of Chapter 2 is an example of a supersaturation, or Erd\\H{o}s--Rademacher type result, which seeks to answer how many forbidden objects must appear in a set whose size is larger than the corresponding result. These supersaturation results are a key ingredient to a very recently discovered proof method, called the Container method. Chapters 3 and 4 show various examples of this method in action. In Chapter 3 we, among others, give tight bounds on the logarithm of the number of $t$-error correcting codes and illustrate how the Container method can be used to prove random analoges of classical extremal results. In Chapter 4 we solve a conjecture of Burosch--Demetrovics--Katona--Kleitman--Sapozhenko about estimating the number of families in $\\{0,1\\}^n$ which do not contain two sets and their union. In Chapter 5 we improve an old result of Erd\\H{o}s and Spencer. Folkman's theorem asserts that for each $k \\in \\N$, there exists a natural number $n = F(k)$ such that whenever the elements of $[n]$ are two-colored, there exists a set $A \\subset [n]$ of size $k$ with the property that all the sums of the form $\\sum_{x \\in B} x$, where $B$ is a nonempty subset of $A$, are contained in $[n]$ and have the same color. In 1989, Erd\\H{o}s and Spencer showed that $F(k) \\ge 2^{ck^2/ \\log k}$, where $c >0$ is an absolute constant; here, we improve this bound significantly by showing that $F(k) \\ge 2^{2^{k-1}/k}$ for all $k\\in \\N$. Fox--Grinshpun--Pach showed that every $3$-coloring of the complete graph on $n$ vertices without a rainbow triangle contains a clique of size $\\Omega\\left(n^{1/3}\\log^2 n\\right)$ which uses at most two colors, and this bound is tight up to the constant factor. We show that if instead of looking for large cliques one only tries to find subgraphs of large chromatic number, one can do much better. In Chapter 6 we show, amongst others, that every such coloring contains a $2$-colored subgraph with chromatic number at least $n^{2/3}$, and this is best possible. As a direct corollary of our result we obtain a generalisation of the celebrated theorem of Erd\\H{o}s-Szekeres, which states that any sequence of $n$ numbers contains a monotone subsequence of length at least $\\sqrt{n}$.","abstract_html":"This is a study of a small selection of problems from various areas of Combinatorics and Graph Theory, a fast developing field that provides a diverse spectrum of powerful tools with numerous applications to computer science, optimization theory and economics. In this thesis, we focus on extremal, probabilistic and enumerative problems in this field. A central theorem in combinatorics is Sperner&#x27;s Theorem, which determines the maximum size of a family $\\F\\subseteq \\P(n)$ that does not contain a $2$-chain <span class=\"etd-inline-math\">F<sub>1</sub>\\subsetneq F<sub>2</sub></span>. Erd\\H{o}s later extended this result and determined the largest family not containing a $k$-chain <span class=\"etd-inline-math\">F<sub>1</sub>\\subsetneq \\ldots \\subsetneq F<sub>k</sub></span>. Erd\\H{o}s and Katona and later Kleitman asked how many such chains must appear in families whose size is larger than the corresponding extremal result. In Chapter 2 we answer their question for all families of size at most <span class=\"etd-inline-math\">(1-\\eps)2<sup>n</sup></span>, provided $n$ is sufficiently larger compared to $k$ and $\\eps$. The result of Chapter 2 is an example of a supersaturation, or Erd\\H{o}s--Rademacher type result, which seeks to answer how many forbidden objects must appear in a set whose size is larger than the corresponding result. These supersaturation results are a key ingredient to a very recently discovered proof method, called the Container method. Chapters 3 and 4 show various examples of this method in action. In Chapter 3 we, among others, give tight bounds on the logarithm of the number of $t$-error correcting codes and illustrate how the Container method can be used to prove random analoges of classical extremal results. In Chapter 4 we solve a conjecture of Burosch--Demetrovics--Katona--Kleitman--Sapozhenko about estimating the number of families in <span class=\"etd-inline-math\">\\{0,1\\}<sup>n</sup></span> which do not contain two sets and their union. In Chapter 5 we improve an old result of Erd\\H{o}s and Spencer. Folkman&#x27;s theorem asserts that for each $k \\in \\N$, there exists a natural number $n = F(k)$ such that whenever the elements of $[n]$ are two-colored, there exists a set $A \\subset [n]$ of size $k$ with the property that all the sums of the form <span class=\"etd-inline-math\">\\sum<sub>x \\in B</sub> x</span>, where $B$ is a nonempty subset of $A$, are contained in $[n]$ and have the same color. In 1989, Erd\\H{o}s and Spencer showed that <span class=\"etd-inline-math\">F(k) \\ge 2<sup>ck<sup>2</sup>/ \\log k</sup></span>, where $c &gt;0$ is an absolute constant; here, we improve this bound significantly by showing that <span class=\"etd-inline-math\">F(k) \\ge 2<sup>2<sup>k-1</sup>/k</sup></span> for all $k\\in \\N$. Fox--Grinshpun--Pach showed that every $3$-coloring of the complete graph on $n$ vertices without a rainbow triangle contains a clique of size <span class=\"etd-inline-math\">\\Omega\\left(n<sup>1/3</sup>\\log<sup>2</sup> n\\right)</span> which uses at most two colors, and this bound is tight up to the constant factor. We show that if instead of looking for large cliques one only tries to find subgraphs of large chromatic number, one can do much better. In Chapter 6 we show, amongst others, that every such coloring contains a $2$-colored subgraph with chromatic number at least <span class=\"etd-inline-math\">n<sup>2/3</sup></span>, and this is best possible. As a direct corollary of our result we obtain a generalisation of the celebrated theorem of Erd\\H{o}s-Szekeres, which states that any sequence of $n$ numbers contains a monotone subsequence of length at least $\\sqrt{n}$.","abstract_has_math":true,"creators":["Wagner, Zsolt Adam"],"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.","Tserunyan, Anush","Lavrov, Mikhail"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-09-04T20:26:59Z","date_published":"2018-09-04T20:26:59Z","updated_at":"2026-07-22T22:24:38Z","subjects":["extremal combinatorics","probabilistic combinatorics","enumerative combinatorics"],"languages":["en"],"rights":["Copyright 2018 Zsolt Wagner"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/100954","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.","Tserunyan, Anush","Lavrov, Mikhail"]},{"key":"dc:creator","label":"Author","values":["Wagner, Zsolt Adam"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018-09-04T20:26:59Z","2018-04-11","2018-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 combinatorics","probabilistic combinatorics","enumerative 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 2018 Zsolt Wagner"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/100954"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This is a study of a small selection of problems from various areas of Combinatorics and Graph Theory, a fast developing field that provides a diverse spectrum of powerful tools with numerous applications to computer science, optimization theory and economics. In this thesis, we focus on extremal, probabilistic and enumerative problems in this field. A central theorem in combinatorics is Sperner's Theorem, which determines the maximum size of a family $\\F\\subseteq \\P(n)$ that does not contain a $2$-chain $F_1\\subsetneq F_2$. Erd\\H{o}s later extended this result and determined the largest family not containing a $k$-chain $F_1\\subsetneq \\ldots \\subsetneq F_k$. Erd\\H{o}s and Katona and later Kleitman asked how many such chains must appear in families whose size is larger than the corresponding extremal result. In Chapter 2 we answer their question for all families of size at most $(1-\\eps)2^n$, provided $n$ is sufficiently larger compared to $k$ and $\\eps$. The result of Chapter 2 is an example of a supersaturation, or Erd\\H{o}s--Rademacher type result, which seeks to answer how many forbidden objects must appear in a set whose size is larger than the corresponding result. These supersaturation results are a key ingredient to a very recently discovered proof method, called the Container method. Chapters 3 and 4 show various examples of this method in action. In Chapter 3 we, among others, give tight bounds on the logarithm of the number of $t$-error correcting codes and illustrate how the Container method can be used to prove random analoges of classical extremal results. In Chapter 4 we solve a conjecture of Burosch--Demetrovics--Katona--Kleitman--Sapozhenko about estimating the number of families in $\\{0,1\\}^n$ which do not contain two sets and their union. In Chapter 5 we improve an old result of Erd\\H{o}s and Spencer. Folkman's theorem asserts that for each $k \\in \\N$, there exists a natural number $n = F(k)$ such that whenever the elements of $[n]$ are two-colored, there exists a set $A \\subset [n]$ of size $k$ with the property that all the sums of the form $\\sum_{x \\in B} x$, where $B$ is a nonempty subset of $A$, are contained in $[n]$ and have the same color. In 1989, Erd\\H{o}s and Spencer showed that $F(k) \\ge 2^{ck^2/ \\log k}$, where $c >0$ is an absolute constant; here, we improve this bound significantly by showing that $F(k) \\ge 2^{2^{k-1}/k}$ for all $k\\in \\N$. Fox--Grinshpun--Pach showed that every $3$-coloring of the complete graph on $n$ vertices without a rainbow triangle contains a clique of size $\\Omega\\left(n^{1/3}\\log^2 n\\right)$ which uses at most two colors, and this bound is tight up to the constant factor. We show that if instead of looking for large cliques one only tries to find subgraphs of large chromatic number, one can do much better. In Chapter 6 we show, amongst others, that every such coloring contains a $2$-colored subgraph with chromatic number at least $n^{2/3}$, and this is best possible. As a direct corollary of our result we obtain a generalisation of the celebrated theorem of Erd\\H{o}s-Szekeres, which states that any sequence of $n$ numbers contains a monotone subsequence of length at least $\\sqrt{n}$.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2018-08-31 without embargo terms","The student, Zsolt Wagner, accepted the attached license on 2018-04-10 at 16:19.","The student, Zsolt Wagner, submitted this Dissertation for approval on 2018-04-10 at 16:32.","This Dissertation was approved for publication on 2018-04-11 at 14:58.","DSpace SAF Submission Ingestion Package generated from Vireo submission #12176 on 2018-08-31 at 17:11:50","Made available in DSpace on 2018-09-04T20:26:59Z (GMT). No. of bitstreams: 9 WAGNER-DISSERTATION-2018.pdf: 776997 bytes, checksum: 251d2511c07c2c296620ffc75cead94b (MD5) 1-introduction.tex: 13080 bytes, checksum: ee5398a32a3bafe14d070ff8b96bd8ab (MD5) 2-kleitmankchains.tex: 65636 bytes, checksum: cc915df7a7983c3bfb03f3f88c623dc3 (MD5) 3-unionfree.tex: 42334 bytes, checksum: afa48f76f4ebabd517c1dbfc289cb6dc (MD5) 4-containersboolean.tex: 110844 bytes, checksum: c453546049eef50180bcffd430ffa118 (MD5) 6-folkman.tex: 12265 bytes, checksum: 1d7e7084ea41b8718bddd2f7fd9b6e76 (MD5) 7-rainbow.tex: 20503 bytes, checksum: e58fd3e884f8a869a39053ef786a71df (MD5) thesis_final_wagner1.tex: 25893 bytes, checksum: 3cc01ec281daae960462331b8b424602 (MD5) LICENSE.txt: 4209 bytes, checksum: 01d5c3e240c0c6d5ec860402716b7062 (MD5) Previous issue date: 2018-04-11"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["On some problems in extremal, probabilistic and enumerative combinatorics"]}]}],"canonical_facts":{"dc:contributor":["Balogh, József","Kostochka, Alexandr V.","Tserunyan, Anush","Lavrov, Mikhail"],"dc:creator":["Wagner, Zsolt Adam"],"dc:date":["2018-09-04T20:26:59Z","2018-04-11","2018-05"],"dc:description":["This is a study of a small selection of problems from various areas of Combinatorics and Graph Theory, a fast developing field that provides a diverse spectrum of powerful tools with numerous applications to computer science, optimization theory and economics. In this thesis, we focus on extremal, probabilistic and enumerative problems in this field. A central theorem in combinatorics is Sperner's Theorem, which determines the maximum size of a family $\\F\\subseteq \\P(n)$ that does not contain a $2$-chain $F_1\\subsetneq F_2$. Erd\\H{o}s later extended this result and determined the largest family not containing a $k$-chain $F_1\\subsetneq \\ldots \\subsetneq F_k$. Erd\\H{o}s and Katona and later Kleitman asked how many such chains must appear in families whose size is larger than the corresponding extremal result. In Chapter 2 we answer their question for all families of size at most $(1-\\eps)2^n$, provided $n$ is sufficiently larger compared to $k$ and $\\eps$. The result of Chapter 2 is an example of a supersaturation, or Erd\\H{o}s--Rademacher type result, which seeks to answer how many forbidden objects must appear in a set whose size is larger than the corresponding result. These supersaturation results are a key ingredient to a very recently discovered proof method, called the Container method. Chapters 3 and 4 show various examples of this method in action. In Chapter 3 we, among others, give tight bounds on the logarithm of the number of $t$-error correcting codes and illustrate how the Container method can be used to prove random analoges of classical extremal results. In Chapter 4 we solve a conjecture of Burosch--Demetrovics--Katona--Kleitman--Sapozhenko about estimating the number of families in $\\{0,1\\}^n$ which do not contain two sets and their union. In Chapter 5 we improve an old result of Erd\\H{o}s and Spencer. Folkman's theorem asserts that for each $k \\in \\N$, there exists a natural number $n = F(k)$ such that whenever the elements of $[n]$ are two-colored, there exists a set $A \\subset [n]$ of size $k$ with the property that all the sums of the form $\\sum_{x \\in B} x$, where $B$ is a nonempty subset of $A$, are contained in $[n]$ and have the same color. In 1989, Erd\\H{o}s and Spencer showed that $F(k) \\ge 2^{ck^2/ \\log k}$, where $c >0$ is an absolute constant; here, we improve this bound significantly by showing that $F(k) \\ge 2^{2^{k-1}/k}$ for all $k\\in \\N$. Fox--Grinshpun--Pach showed that every $3$-coloring of the complete graph on $n$ vertices without a rainbow triangle contains a clique of size $\\Omega\\left(n^{1/3}\\log^2 n\\right)$ which uses at most two colors, and this bound is tight up to the constant factor. We show that if instead of looking for large cliques one only tries to find subgraphs of large chromatic number, one can do much better. In Chapter 6 we show, amongst others, that every such coloring contains a $2$-colored subgraph with chromatic number at least $n^{2/3}$, and this is best possible. As a direct corollary of our result we obtain a generalisation of the celebrated theorem of Erd\\H{o}s-Szekeres, which states that any sequence of $n$ numbers contains a monotone subsequence of length at least $\\sqrt{n}$.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2018-08-31 without embargo terms","The student, Zsolt Wagner, accepted the attached license on 2018-04-10 at 16:19.","The student, Zsolt Wagner, submitted this Dissertation for approval on 2018-04-10 at 16:32.","This Dissertation was approved for publication on 2018-04-11 at 14:58.","DSpace SAF Submission Ingestion Package generated from Vireo submission #12176 on 2018-08-31 at 17:11:50","Made available in DSpace on 2018-09-04T20:26:59Z (GMT). No. of bitstreams: 9 WAGNER-DISSERTATION-2018.pdf: 776997 bytes, checksum: 251d2511c07c2c296620ffc75cead94b (MD5) 1-introduction.tex: 13080 bytes, checksum: ee5398a32a3bafe14d070ff8b96bd8ab (MD5) 2-kleitmankchains.tex: 65636 bytes, checksum: cc915df7a7983c3bfb03f3f88c623dc3 (MD5) 3-unionfree.tex: 42334 bytes, checksum: afa48f76f4ebabd517c1dbfc289cb6dc (MD5) 4-containersboolean.tex: 110844 bytes, checksum: c453546049eef50180bcffd430ffa118 (MD5) 6-folkman.tex: 12265 bytes, checksum: 1d7e7084ea41b8718bddd2f7fd9b6e76 (MD5) 7-rainbow.tex: 20503 bytes, checksum: e58fd3e884f8a869a39053ef786a71df (MD5) thesis_final_wagner1.tex: 25893 bytes, checksum: 3cc01ec281daae960462331b8b424602 (MD5) LICENSE.txt: 4209 bytes, checksum: 01d5c3e240c0c6d5ec860402716b7062 (MD5) Previous issue date: 2018-04-11"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/100954"],"dc:language":["en"],"dc:rights":["Copyright 2018 Zsolt Wagner"],"dc:subject":["extremal combinatorics","probabilistic combinatorics","enumerative combinatorics"],"dc:title":["On some problems in extremal, probabilistic and enumerative combinatorics"],"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:38Z"}