Speaker: Xinyu Wu (CMU)
Title: Explicit near-fully X-Ramanujan graphs
Abstract:
In this talk I will introduce constructions of finite graphs which resemble some given infinite graph both in terms of their local neighborhoods, and also their spectrum.
First, I will show how a "recipe" in the form of some matrix-coefficient non-commutative polynomial can be used to specify many infinite graphs, including those arising from various graph products, and also generate finite graphs which are covered by the infinite graph. A recent landmark result of Bordenave and Collins implies that for all such graphs, with high probability the finite graphs generated with this recipe also have their nontrivial spectrum close to that of the infinite graph.
Next, I will talk about an explicit form of this result: we provide a deterministic polynomial-time algorithm which, for any X which can arise from a matrix-coefficient polynomial, produces arbitrarily large graphs G that are covered by X and have (nontrivial) spectrum at Hausdorff distance at most eps from that of X.
Based on joint work with Ryan O'Donnell (CMU).