Ph.D Thesis | |

Ph.D Student | Gorelik Irina |
---|---|

Subject | Weighted Parameters of Matchings |

Department | Department of Mathematics |

Supervisor | PROFESSOR EMERITUS Ron Aharoni |

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.