From radin@math.biu.ac.il Sun Nov 26 01:06:14 2006
Date: Sun, 26 Nov 2006 01:06:14 +0200 (IST)
From: Adin Ron <radin@math.biu.ac.il>
To: Combinatorics Seminar:  ;
Bcc: berger@cri.haifa.ac.il, Ori Gurel-Gurevich <origurel@gmail.com>, Anna Melnikov <melnikov@math.haifa.ac.il>
Subject: Bar-Ilan Combinatorics Seminar

                       ==============================
                       Bar-Ilan Combinatorics Seminar
                       ==============================

The next meeting of the seminar will take place, IYH, on

(when)  Tuesday, 7 Kislev 5767 (Nov. 28)
          refreshments at 11:45 am, talk at 12 noon

(where) Room 331 (Math Dept Seminar Room),
          Math and CS Building, Bar-Ilan University

(who)   Eli Berger (University of Haifa)

          will talk about

(what)  "On the duality between independence and domination"

Abstract:
---------
In this talk we introduce several results relating the dominating sets in 
a graph to the independent sets.

A {\em jointly independent set} for graphs $G_1, G_2, \ldots,G_r$ is an 
independent set in the union of the graphs $G_i$, namely a set independent 
in all of the graphs. This notion has a fractional counterpart. For a 
graph $G$ we denote by $\Omega(G)$ the polytope in $\mathbb{R}^V$ whose 
vertices are the incidence vectors of the independent sets of $G$. Let 
$\Omega(G_1,...,G_r)= \bigcap_{i \le m} \Omega(G_i)$.  Write 
$\alpha^*(G_1,...,G_r)= \max \{\vec{1} \cdot \vec{x}: ~ \vec{x} \in 
\Omega(G1,...,G_r)\}$. Also write: $\gamma(G_1,...,G_r)$ for the minimal 
number of non-punctured neighborhoods in the graphs, whose union is $V$. 
One of the results that will be shown is that For any pair $\{G_1,G_2\}$ 
of graphs $\alpha^*(\{G_1, G_2\}) \ge \gamma(\{G_1, G_2\})$. For $r$ 
graphs $G_1,G_2,\ldots,G_r$ we have $\alpha^*(\{G_1, G_2,\ldots,G_r\}) \ge 
\frac{2}{r}\gamma(\{G_1, G_2,\ldots,G_r\})$. This generalizes a result of 
Lovasz.

This is joint work with Ron Aharoni, Ron Holzman and Ori Kfir.


Forthcoming Events
==================
* 14 Kislev (Dec. 5)
    Ori Gurel-Gurevich (Weizmann Institute):
    "K-wise independent events and percolation"
* 21 Kislev (Dec. 12)
    Anna Melnikov (University of Haifa):
    TBA 
*************************************************************************
You are all invited ! (Graduate students especially welcome)
If you want to give a talk at the seminar, or know a prospective speaker,
please contact  Ron Adin <radin@math.biu.ac.il>.
Seminar's homepage: <http://www.math.biu.ac.il/~radin/comsem/comsem.html>
*************************************************************************