טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentGorelik Irina
SubjectWeighted Kernels in Digraphs
DepartmentDepartment of Mathematics
Supervisor Professor Ron Aharoni
Full Thesis textFull thesis text - English Version


Abstract


A kernel in a digraph is an independent and dominating set of vertices. By a result of Boros and Gurvich, a digraph whose underlying graph is perfect and that does not contain a cyclic triangle has a kernel.  A special case of the

Boros-Gurvich theorem is the famous theorem of Gale and Shapley, that states that in a graph that is the union of two sets of disjoint chains (transitive tournaments) there must exist a kernel. Sands, Sauer, and Woodrow generalized this theorem, and proved that in fact any digraph G whose edge set is the union of two posets has a kernel. The Boros-Gurvich theorem has an integral weighted version that can be proved using a well known theorem of Scarf, together with polyhedral considerations. The main aim of this thesis is to prove a weighted version of the SSW theorem. In this case, the polyhedral proof does not apply, and a direct approach is needed.

Another theme of the thesis follows the footsteps of a result of Conway, stating that in the Gale-Shapley case, the set of kernels forms a lattice with respect to each of two natural partial orders defined on this set. This was generalized by Blair and Fleiner to the setting of the SSW theorem. I will describe the Fleiner approach, using what he calls ``comonotne functions'', and also provide a direct proof.