The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science


                            Computer Science Seminar

                                  Nati Linial
                               Hebrew University


                                 will speak on


                             Random lifts of graphs

Abstract:
Let $G$ and $H$ be two graphs.  A map $f:V(H) ---> V(G)$ is a {\it covering
map}, if the neighbors of every $x$ are mapped 1:1 onto the neighbors of
$f(x)$. If $G$ is connected (as we assume), the preimage of every vertex or
edge in $G$ has the same cardinality $n$ (`the order of the covering map
$f$').  The class of graphs $H$ that have an order $n$ covering map onto $G$ is
studied.  It turns out that this class of graphs has a natural structure of a
probability space. We consider how typical properties of graphs in this class
are related to properties of $G$. Among the topics we study are: Connectivity,
girth, expansion, chromatic number and matchings.

This talk is based on joint works with:  Alon Amit, J. Matousek and E.
Rozenman.





                      The lecture will take place in the 
                     Lecture Hall, Room 1, Ziskind Building
                            on Monday, June 19, 2000
                                    at 14:30