Combinatorics Seminar
Speaker: Irena Gorelik
Date: Jan. 18
Time: 1:30pm
Place:  AMADO 619 
Title: Kernels in Weighted Digraphs
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   <> 
Announcement from: David Howard   <>