2026-09-22T04:12:49Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/116150 2023-07-11 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

Balogh, Jozsef Kostochka, Alexandr Yong, Alexander English, Sean 2022-08 application/pdf en text 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 Topics in extremal and algebraic combinatorics Linz, William 2022-06-03 Combinatorics Erdos-Ko-Rado Catalan 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. Thesis eng https://hdl.handle.net/2142/116150 Copyright 2022 William Linz Ph.D. Dissertation Mathematics University of Illinois at Urbana-Champaign Mathematics