The Taub Faculty of Computer Science Events and Talks

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.