Yonatan Bilu

most citedMonotone Maps, Sphericity and Bounded Second Eigenvalue

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

collaborators

Showing math.COShow all

3 papers · 1 filter

math.CO2004

Tales of Hoffman

Yonatan Bilu

Hofmman's bound on the chromatic number of a graph states that $χ \geq 1 - \frac{λ _{1}}{λ _{n}}$ . 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 $G$ be a graph on $n$ v…