Department of
Applied
Mathematics

Graph Theory meets Extremal Set Theory

Carl Feghali

IUUK

Abstract

In extremal set theory, one is given a set S on n elements and collections A_1, A_2, ..., of subsets of S with some restrictions on those collections (for example, each member of one collection must have a common element with every other member of every other collection). One then typically seeks to bound the size of each A_i. A natural analogue of this setting for graphs, introduced by Holroyd and Talbot in 2002, is to take our graph G to be G = (S, E) and each A_i to be a collection of independent subsets of G. In this talk, I will discuss some old and new problems and results in the area, and make a connection to Chvátal's conjecture. If time permits, I will sketch a proof of a recent result I obtained in joint work with Glenn Hurlbert and Vikram Kamat.