Theory Seminar: Vector Representation
of Graph Domination

Noga Zewi (CS Technion)

Monday, 07.12.2009, 14:30

Amado 509

The famous Hall's marriage theorem from 1935 states that in a bipartite
graph with sides M and W, there is a matching of M into W if and only if
every subset A of M has at least |A| neighbors in W. A generalization of
this theorem for r-partite hypergraphs was proved by Aharoni and Haxell in
2000, using topological methods. In 2005 Aharoni, Berger and Meshulam proved
a stronger version of this theorem, using a new function on graphs, called
the Gamma function. This function represents vectorially the domination
number of a graph, in a way similar to that in which the Lov�sz Theta
function represents the independence number of a graph.

For most graphs, the calculation of the Gamma function is very difficult. In fact, it is not even known whether there is at all an algorithm for calculating it. We prove lower and upper bound on Gamma, formulated in terms of known domination and algebraic parameters of the graph, and we then use these bounds to calculate the value of Gamma for cycles and for trees. We also make use of the Gamma function in order to generalize a fractional version of the famous Ryser's conjecture.

In the talk I will describe the topological methods, and some of the methods used to obtain the new results on Gamma.

The research was done under the supervision of Ron Aharoni.

For most graphs, the calculation of the Gamma function is very difficult. In fact, it is not even known whether there is at all an algorithm for calculating it. We prove lower and upper bound on Gamma, formulated in terms of known domination and algebraic parameters of the graph, and we then use these bounds to calculate the value of Gamma for cycles and for trees. We also make use of the Gamma function in order to generalize a fractional version of the famous Ryser's conjecture.

In the talk I will describe the topological methods, and some of the methods used to obtain the new results on Gamma.

The research was done under the supervision of Ron Aharoni.