Ph.D Thesis
Ph.D Student Irina Gorelik Weighted Parameters of Matchings Department of Mathematics Full Professor Aharoni Ron

Abstract

Combinatorial results and problems often have weighted versions. Sometimes the latter do not demand new methods, as compared with the non-weighted versions, but often they do.

The aim of this thesis is to explore such weighted versions, as well as the geometry of the polytopes associated with them.

The first section of the thesis deals with the relationship between the polytopes of integral and fractional covers in hypergraphs. The first of these two polytopes is contained in the second, and there are two ways of comparing the distance of the polytopes from the origin. One is the ratio between the distances travelled to enter the polytopes when you start from the origin and go in a certain direction (vector of weights).  We pose some conjectures regarding this parameter, and prove some of them, mainly for graphs. In addition, we prove a weighted version of a theorem of Lovasz, that states that the minimum size of a cover in an r-partite hypergraph is at most r/2 times the minimum size of a fractional cover.

The second question we study is the weighted version of a theorem of Aharoni, Berger and Ziv, that in chordal graphs the domination number and the independent domination number are the same. We show that the weighted version is not true for general chordal graphs, but we prove equality in some special cases, in particular interval graphs.

Another result whose weighted version we study is due to Aharoni, Berger, Holzman and Kfir - that the fractional joint independence number of two graphs on the same set of vertices is at least the collective domination number of the graphs. While the weighted version of the theorem remains open, we prove a weighted version of a special case, in which one of the graphs is the disjoint union of cliques. This is the setting of ``independent systems of representatives'' (ISRs), a central notion in matching theory (defined in the introduction).

In the last two parts of the thesis, we prove some results on the existence of ISRs. The first one deals with two geometric versions of ISRs, namely when the sets are convex sets in ℝn. The second concerns a generalization to hypergraphs of a sufficient condition for the existence of ISRs, proved by Aharoni, Alon and Berger. The proof uses spectral methods.