Searching for Erdös-Ko-Rado GraphsAlgebra & Discrete Mathematics
|Speaker:||Jessica De Silva, California State University, Stanislaus|
|Start time:||Mon, Nov 1 2021, 11:00AM|
The Erdös-Ko-Rado (EKR) theorem states that the maximum size of an intersecting family of $r$-element subsets of $[n]$ can be attained by taking all subsets containing some fixed element. This classical result in extremal combinatorics has been rephrased in the language of graph theory as an extremal property regarding independent sets of a graph. A family of independent $r$-sets of a graph $G$ is an $r$-star if every set in the family contains some fixed vertex $v$. A graph is $r$-EKR if the maximum size of an intersecting family of independent $r$-sets can be attained by an $r$-star. In this context, the classical EKR theorem determines the values of $r$ for which the empty graph satisfies the $r$-EKR property. This talk will highlight that there is much to be discovered in the search for EKR graphs, along with motivation and early findings for classes of very well-covered graphs.