Topics in extremal and algebraic combinatorics

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 γ(G_{k, 2}), for fixed $k$ and $n\rightarrow\infty$. Additionally, we prove a general lower bound for γ(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²}{4}\rfloor}\le T_k\le k(k-1)²/2. We almost close the gap between the upper and lower bounds by proving that T_k \le k²e^{(\ln\ln k)2(1+o(1))}. Conlon, Fox and Sudakov have independently shown a stronger statement that T_k=O(k²\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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Linz, William

Contributors dc:contributor

• Balogh, Jozsef
• Kostochka, Alexandr
• Yong, Alexander
• English, Sean

• Combinatorics
• Erdos-Ko-Rado
• Catalan

Statement dc:rights

• Copyright 2022 William Linz

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/116150

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F116150