Technion 
 
Combinatorics Seminar
 
Speaker: Irena Gorelik
 
Date: Jan. 18
Time: 1:30pm
Place:  AMADO 619 
 
Title: Kernels in Weighted Digraphs
 
Abstract:
A kernel in a digraph is an independent and dominating set of vertices.
Generalizing the famous Gale-Shapley theorem, Sands, Sauer, and Woodrow
proved that a digraph G whose edge set is the union of two posets has a
kernel.  Another well-known result about kernels is the Boros-Gurvich
theorem, stating that in digraph whose underlying undirected graph is
perfect, and in which there is no induced cyclic triangle, has a kernel. The
latter theorem has a weighted integral version that follows from polyhedral
considerations. In this talk I will survey these results, and show an
integral weighted version of the Sands-Sauer-Woodrow theorem.
Joint work with Eli Berger and Ron Aharoni.
 
---------------------------------------------------------
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: David Howard   <howard@techunix.technion.ac.il>