**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.