-
Rényi, Nagyterem + Zoom
-
-
-
-
-
-

Description

Abstract:

In 2005 Holroyd and Talbot made a conjecture that generalizes the Erdős-Ko-Rado Theorem to graphs in the following way.
Consider the family $\cal I^r(G)$ of independent sets of size $r$ in a graph $G$ on $n$ vertices, and let $\cal F$ be an intersecting subfamily.
Say that a subfamily ${\cal H} \subseteq {\cal I}^r(G)$ is a star if some vertex $x$ is in every set of $\cal H$, and define $\mu(G)$ to be the
minimum size of a maximal independent set in $G$.  They conjectured that if $r \le \mu(G)/2$ then the size of $\cal F$ is at most the size
of the largest star.  This can be viewed as a special instance of a uniform version of Chvátal's 1974 conjecture on hereditary families.

I will give an overview of the history of this topic before presenting more recent results and open problems with various collaborators
including Eva Czabarka, Emiliano Estrugo, Carl Feghali, Susanna Fishel, Péter Frankl, Vikram Kamat, Karen Meagher, Adrián Pastine,
and others.  Among the results are injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems, certification of the Holroyd-Talbot
conjecture for smaller $r$ on sparse graphs, and partial results and conjectures on trees regarding what vertices a largest star can be centered on.

 

The lecture can be followed by zoom if necessary: