Speaker: Eli Berger (Princeton University)                                      

Title: On Hall Type Theorems and Strong Colorability                            

Abstract:
---------
The area of Hall type theorems gives us many interesting open questions.
The recent introduction of topological techniques to this area puts many
of these questions within reach. 

The talk will discuss many of these questions and will give a few new
results in the field, including the following weighted version of Haxell's
theorem: 

Let G be a graph whose vertices are paritioned into m sets V1...Vm. Let w
be a function on the vertices (weight) with nonnegative integer values.
Let q be the maximal weight of an ISR in G. Then there exists a function f
on the vertices and a function g on {1...m}, with nonnegative integer
values, so that for every v in (say) Vi

$$ g(i) + f(v) \leq w(v) \leq g(i) + sum_{u \in N(v)} f(u) $$

and

$$ sum_{i=1}^m g(i) + sum_{v \in V} f(v)/2 \leq q$$.

This theorem can be used to prove a fractioned version of the strong
colorability conjecture (that every graph with maximal degree Delta is
2Delta strongly colorable). Some more conjectures of that type will be
discussed. 

This talk is a joint work with Ron Aharoni and Ran Ziv