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.