Seminar Details
Random k-out Subgraphs
- Start Date: February 20, 2023
- Event Start Time: 2:00 PM
- Event End Time: 3:00 PM
- Seminar Series: Rutgers Discrete Mathematics Seminar
- Presenter(s): Or Zamir - Institute for Advanced Study
- Event Location: Hill Center-Room 705
- Event Additional Info: <p>See: <a href="https://sites.google.com/view/rutgersdmseminar">https://sites.google.com/view/rutgersdmseminar</a></p>
- Presentation Type: Stand Alone Presentation
- 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.