***********************************
* 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)