Speaker: Phillip Marmorino, University of Notre Dame
Will give a PhD Defense entitled:
Counting Independent Sets and Generalized Colorings in Graphs with Various Restrictions
Abstract:
An $n$-vertex, $d$-regular graph can have at most $2^{n/2+o_d(n)}$ independent sets. We address this upper bound when we impose the additional condition that the graph has independence number at most $\alpha$. In particular, we show that for a sequence of $d_n$-regular $n$-vertex graphs $G_n$ with independence number at most $\alpha_n$, if $d_n \rightarrow\infty$ and $\alpha/n\rightarrow c_\alpha$ where $0<c_\alpha\leq 1/2$, then $G_n$ has at most $k(c_\alpha)^{n+o(n)}$ independent sets, where $k(c_\alpha)$ is as small as possible. We also prove an analogous result when $1/2<c_\alpha< 1$, subject to the additional condition that $d_n/n\rightarrow c_d$, where $0<c_d\leq 1-c_\alpha$. Our proofs use both graph container arguments and constructive techniques. We further refine our results by giving the asymptotic behavior of the maximum number of independent sets of a fixed size scaling with $n$ of an $n$-vertex $d$-regular graph with independence number at most $\alpha$. Finally, we consider some exact results on maximizing the number of graph homomorphisms from an $n$-vertex graph $G$ with independence number $\alpha$ to certain target graphs (including the target graph to which homomorphisms are equivalent to independent sets). We conclude by considering some open questions about proper $q$-colorings.
Date: 06-19-2025
Time: 2:00 PM
Location: 125 Hayes Healy