Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

Random k-out subgraphs 

Or Zamir (Princeton/IAS)

Location:  Hill Center Room 705
Date & time: Monday, 20 February 2023 at 2:00PM - 3:00PM

Abstract: 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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.