***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Michael Krivelevich (Tel Aviv U)

Thursday 19th February, 3:00 in Fine Hall 224.

Title: Combinatorial conditions for graph rigidity,
          with applications to random graphs

Graph rigidity is one of the most classical subjects in graph theory,
studying geometric properties of graphs. Formally, a graph G=(V,E) is
d-rigid if a generic embedding of its vertex set V into R^d is rigid,
namely, every continuous motion of its vertices preserving the lengths
of the edges of G necessarily preserves all pairwise distances between
the vertices of G.

We develop a new sufficient condition for d-rigidity, formulated in
graph-theoretic terms. This condition allows us to obtain several new
results about rigidity of random graphs. In particular, we argue that
for edge probability p>2ln n/n, a random graph G(n,p) is with high
probability (whp) cnp-rigid, for c>0 being an absolute constant. We
also show that a random r-regular graph G_{n,r}, r>=3, is whp cr-rigid.
Another consequence is a sufficient condition for d-rigidity based on
the minimum co-degree of the graph.    

The talk should be accessible to a general graph-theoretic audience.
No previous experience (whether positive or negative) with graph
rigidity will be assumed.

Joint work with Alan Lew and Peleg Michaeli.

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)