Topics in extremal and algebraic combinatorics

Linz, William

Permalink

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

Description

Title

Topics in extremal and algebraic combinatorics

Author(s)

Linz, William

Issue Date

2022-06-03

Director of Research (if dissertation) or Advisor (if thesis)

Balogh, Jozsef

Doctoral Committee Chair(s)

Kostochka, Alexandr

Committee Member(s)

• Yong, Alexander
• English, Sean

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Combinatorics
• Erdos-Ko-Rado
• Catalan

Abstract

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.

Graduation Semester

2022-08

Type of Resource

Thesis

Copyright and License Information

Copyright 2022 William Linz

Owning Collections