Campus Event Calendar
Event Entry
New for: D3
What and Who
Cutoff Phenomenon for Random Walk on Kneser Graphs
Ali Pourmiri
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 4 October 2011
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
In this talk, we show the cutoff phenomenon for simple random walks on Kneser graphs. Given two integers n and k, the Kneser graph K(2n+k,n) is defined as the graph with vertex set being all subsets of {1,...,2n+k} of size n and two vertices A and B being connected by an edge if A∩B = ∅. We show that if k = O(n), then the random walk on K(2n+k,n) exhibits a cutoff at 1/2log_{1+k/n}(2n+k) with a window of size O(n/k).
Contact
Ali Pourmiri
--email hidden
passcode not visible
logged in users only
Ali Pourmiri, 09/30/2011 19:10
Ali Pourmiri, 09/09/2011 17:44 -- Created document.
Ali Pourmiri, 09/09/2011 17:44 -- Created document.