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>