most citedMonotone Maps, Sphericity and Bounded Second Eigenvalue

3 citations · 5 across the 3 of their papers we have counts for

collaborators

3 papers

math.CO2004

Tales of Hoffman

Yonatan Bilu

Hofmman's bound on the chromatic number of a graph states that . Here we show that the same bound, or slight modifications of it, hold for several grap…

math.CO2004★ 3 cited

Monotone Maps, Sphericity and Bounded Second Eigenvalue

Yonatan Bilu, Nati Linial

We consider {\em monotone} embeddings of a finite metric space into low dimensional normed space. That is, embeddings that respect the order among the distances in the original spa…

math.CO2003★ 2 cited

Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap

Yonatan Bilu, Nathan Linial

We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let be a graph on v…