{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/116150"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/116150","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Topics in extremal and algebraic combinatorics","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms","abstract_has_math":false,"creators":["Linz, William"],"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","Yong, Alexander","English, Sean"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-08","date_published":"2022-08","updated_at":"2026-07-22T22:24:55Z","subjects":["Combinatorics","Erdos-Ko-Rado","Catalan"],"languages":["en","eng"],"rights":["Copyright 2022 William Linz"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/116150","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Balogh, Jozsef","Kostochka, Alexandr","Yong, Alexander","English, Sean"]},{"key":"dc:creator","label":"Author","values":["Linz, William"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-08","2022-06-03"]},{"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","Erdos-Ko-Rado","Catalan"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2022 William Linz"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/116150"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms","The student, William Linz, accepted the attached license on 2022-05-31 at 11:38.","The student, William Linz, submitted this Dissertation for approval on 2022-05-31 at 11:55.","This Dissertation was approved for publication on 2022-06-03 at 15:10.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18049 on 2022-11-15 at 17:37:30","In this thesis, I make a number of contributions to several areas of extremal and algebraic combinatorics, namely extremal set theory, Ramsey theory, enumerative combinatorics and spectral graph theory. I believe combinatorics is a unified field and am interested in a broad range of areas within combinatorics. We begin in Chapter 1 with a summary of our results and make a broad overview of topics from these fields. In particular, we include a fairly detailed discussion on generalizations of the famous Erd\\H{o}s-Ko-Rado theorem. In Chapter 2, we give short proofs of three theorems about intersection problems. The first one is a determination of the maximum size of a nontrivial $k$-uniform, $d$-wise intersecting family for $n\\ge \\left(1+\\frac{d}{2}\\right)(k-d+2)$, which improves upon a recent result of O'Neill and Verstra\\\"{e}te. Our proof also extends to $d$-wise, $t$-intersecting families, and from this result we obtain a version of the Erd\\H{o}s-Ko-Rado theorem for $d$-wise, $t$-intersecting families. The second result partially proves a conjecture of Frankl and Tokushige about $k$-uniform families with restricted pairwise intersection sizes. The third result concerns graph intersections. Answering a question of Ellis, we construct $K_{s, t}$-intersecting families of graphs which have size larger than the Erd\\H{o}s-Ko-Rado-type construction whenever $t$ is sufficiently large in terms of $s$. In Chapter 3, we prove some results on a two-sided analogue of an old result of Erd\\H{o}s and Hanani about covering systems. Let $n > k > \\ell \\ge 1$ be positive integers, and define a bipartite graph $G_{k, \\ell}=(V, E)$ by $V(G_{k, \\ell})=(\\binom{[n]}{k}, \\binom{[n]}{\\ell})$ and $(A, B) \\in E(G_{k, \\ell})$ if and only if $A \\in \\binom{[n]}{\\ell}$, $B\\in \\binom{[n]}{k}$, and $A\\subset B$. We confirm a conjecture of Badakhshian, Katona and Tuza for the two-sided covering number $\\gamma(G_{k, 2})$, for fixed $k$ and $n\\rightarrow\\infty$. Additionally, we prove a general lower bound for $\\gamma(G_{k, \\ell})$, with $k$ and $\\ell$ fixed and $n\\rightarrow \\infty$. Our proof uses the graph removal lemma and a Frankl-R\\\"odl nibble type theorem of Pippenger. In Chapter 4, we prove an almost optimal upper bound for the maximum size of an equinumerous $t$-coloring of a rainbow $k$-AP. More formally, define $T_k$ as the minimal $t\\in \\mathbb{N}$ for which there is a rainbow arithmetic progression of length $k$ in every equinumerous $t$-coloring of $[tn]$ for all $n\\in \\mathbb{N}$. Jungi\\'{c}, Licht (Fox), Mahdian, Ne\\u{s}et\\u{r}il and Radoi\\u{c}i\\'{c} proved that $\\lfloor{\\frac{k^2}{4}\\rfloor}\\le T_k\\le k(k-1)^2/2$. We almost close the gap between the upper and lower bounds by proving that $T_k \\le k^2e^{(\\ln\\ln k)^2(1+o(1))}$. Conlon, Fox and Sudakov have independently shown a stronger statement that $T_k=O(k^2\\log k)$. In Chapter 5, we study two generalizations of the Catalan numbers, namely the $s$-Catalan numbers and the spin $s$-Catalan numbers. These numbers first appeared in relation to quantum physics problems about spin multiplicities. We give a combinatorial description for these numbers in terms of Littlewood-Richardson coefficients, and explain some of the properties they exhibit in terms of Littlewood-Richardson polynomials. In Chapter 6, we state a conjectured inequality relating the sums of squares of the positive eigenvalues and the clique number of a graph. We verify this conjecture for Kneser graphs, Johnson graphs, and a certain class of strongly regular graphs. This conjecture, appearing in a paper with Elphick and Wocjan, is a generalization of a conjecture due to Bollob\\'as and Nikiforov, which is itself a conjectured generalization of the spectral Tur\\'an theorem of Nikiforov. We conclude in Chapter 7 by looking at future directions for this research."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Topics in extremal and algebraic combinatorics"]}]}],"canonical_facts":{"dc:contributor":["Balogh, Jozsef","Kostochka, Alexandr","Yong, Alexander","English, Sean"],"dc:creator":["Linz, William"],"dc:date":["2022-08","2022-06-03"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms","The student, William Linz, accepted the attached license on 2022-05-31 at 11:38.","The student, William Linz, submitted this Dissertation for approval on 2022-05-31 at 11:55.","This Dissertation was approved for publication on 2022-06-03 at 15:10.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18049 on 2022-11-15 at 17:37:30","In this thesis, I make a number of contributions to several areas of extremal and algebraic combinatorics, namely extremal set theory, Ramsey theory, enumerative combinatorics and spectral graph theory. I believe combinatorics is a unified field and am interested in a broad range of areas within combinatorics. We begin in Chapter 1 with a summary of our results and make a broad overview of topics from these fields. In particular, we include a fairly detailed discussion on generalizations of the famous Erd\\H{o}s-Ko-Rado theorem. In Chapter 2, we give short proofs of three theorems about intersection problems. The first one is a determination of the maximum size of a nontrivial $k$-uniform, $d$-wise intersecting family for $n\\ge \\left(1+\\frac{d}{2}\\right)(k-d+2)$, which improves upon a recent result of O'Neill and Verstra\\\"{e}te. Our proof also extends to $d$-wise, $t$-intersecting families, and from this result we obtain a version of the Erd\\H{o}s-Ko-Rado theorem for $d$-wise, $t$-intersecting families. The second result partially proves a conjecture of Frankl and Tokushige about $k$-uniform families with restricted pairwise intersection sizes. The third result concerns graph intersections. Answering a question of Ellis, we construct $K_{s, t}$-intersecting families of graphs which have size larger than the Erd\\H{o}s-Ko-Rado-type construction whenever $t$ is sufficiently large in terms of $s$. In Chapter 3, we prove some results on a two-sided analogue of an old result of Erd\\H{o}s and Hanani about covering systems. Let $n > k > \\ell \\ge 1$ be positive integers, and define a bipartite graph $G_{k, \\ell}=(V, E)$ by $V(G_{k, \\ell})=(\\binom{[n]}{k}, \\binom{[n]}{\\ell})$ and $(A, B) \\in E(G_{k, \\ell})$ if and only if $A \\in \\binom{[n]}{\\ell}$, $B\\in \\binom{[n]}{k}$, and $A\\subset B$. We confirm a conjecture of Badakhshian, Katona and Tuza for the two-sided covering number $\\gamma(G_{k, 2})$, for fixed $k$ and $n\\rightarrow\\infty$. Additionally, we prove a general lower bound for $\\gamma(G_{k, \\ell})$, with $k$ and $\\ell$ fixed and $n\\rightarrow \\infty$. Our proof uses the graph removal lemma and a Frankl-R\\\"odl nibble type theorem of Pippenger. In Chapter 4, we prove an almost optimal upper bound for the maximum size of an equinumerous $t$-coloring of a rainbow $k$-AP. More formally, define $T_k$ as the minimal $t\\in \\mathbb{N}$ for which there is a rainbow arithmetic progression of length $k$ in every equinumerous $t$-coloring of $[tn]$ for all $n\\in \\mathbb{N}$. Jungi\\'{c}, Licht (Fox), Mahdian, Ne\\u{s}et\\u{r}il and Radoi\\u{c}i\\'{c} proved that $\\lfloor{\\frac{k^2}{4}\\rfloor}\\le T_k\\le k(k-1)^2/2$. We almost close the gap between the upper and lower bounds by proving that $T_k \\le k^2e^{(\\ln\\ln k)^2(1+o(1))}$. Conlon, Fox and Sudakov have independently shown a stronger statement that $T_k=O(k^2\\log k)$. In Chapter 5, we study two generalizations of the Catalan numbers, namely the $s$-Catalan numbers and the spin $s$-Catalan numbers. These numbers first appeared in relation to quantum physics problems about spin multiplicities. We give a combinatorial description for these numbers in terms of Littlewood-Richardson coefficients, and explain some of the properties they exhibit in terms of Littlewood-Richardson polynomials. In Chapter 6, we state a conjectured inequality relating the sums of squares of the positive eigenvalues and the clique number of a graph. We verify this conjecture for Kneser graphs, Johnson graphs, and a certain class of strongly regular graphs. This conjecture, appearing in a paper with Elphick and Wocjan, is a generalization of a conjecture due to Bollob\\'as and Nikiforov, which is itself a conjectured generalization of the spectral Tur\\'an theorem of Nikiforov. We conclude in Chapter 7 by looking at future directions for this research."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/116150"],"dc:language":["en","eng"],"dc:rights":["Copyright 2022 William Linz"],"dc:subject":["Combinatorics","Erdos-Ko-Rado","Catalan"],"dc:title":["Topics in extremal and algebraic combinatorics"],"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:55Z"}