66 citations · 70 across the 4 of their papers we have counts for
4 papers
How neighborly can a centrally symmetric polytope be?
Nathan Linial, Isabella Novik
We show that there exist k-neighborly centrally symmetric d-dimensional polytopes with 2(n+d) vertices, where k(d,n)=Theta(d/(1+log ((d+n)/d))). We also show that this bound is tig…
On some low distortion metric Ramsey problems
Yair Bartal, Nathan Linial. Manor Mendel, Assaf Naor
In this note, we consider the metric Ramsey problem for the normed spaces l_p. Namely, given some 1<=p<=infinity and alpha>=1, and an integer n, we ask for the largest m such that…
A counterexample to a conjecture of Björner and Lovász on the -coloring complex
Shlomo Hoory, Nathan Linial
Associated with every graph of chromatic number is another graph . The vertex set of consists of all -colorings of , and two -colorings are adjacent when…
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…