Discrete Mathematics and Optimization Seminar

JACQUES VERSTRAETE
University of Waterloo
Monday January 23rd at 4.30pm
Burnside 1205

Title. Polynomials and Factors.

Abstract. Let S be a family of subsets of a set X, and let d(x) denote the degree of x in X. Let f be a function
assigning to each x in X a set of integers in {0,1,2,...,d(x)}. Lovasz defined an f-factor of S to be a
subfamily of S in which d(x) in f(x)for all x in X. Using Alon's combinatorial nullstellensatz, we prove that
if |f(x)| > \lceil d(x)/2 \rceil for all x in X, then S has an f-factor. This result is best possible and, in
the particular case of graphs, verifies a conjecture of Addario-Berry. Further applications of the algebraic
techniques will be discussed, as well as some open problems.