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

Speaker: Or Zamir (Princeton and IAS)

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

Title: Random k-out subgraphs


Each vertex of an arbitrary simple graph on n vertices chooses k random
incident edges. What is the expected number of edges in the original graph
that connect different connected components of the sampled subgraph? We
prove that the answer is O(n/k), when k ≥ c log n, for some large enough c.
We conjecture that the same holds for smaller values of k, possibly for any
k ≥ 2. Such a result is best possible for any k ≥ 2. 
We give applications of this sampling lemma for models of distributed
algorithms.

Based on joint work with Jacob Holm, Valeria King, Mikkel Thorup and Uri
Zwick.

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


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