66 citations · 108 across the 7 of their papers we have counts for
7 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 Metric Ramsey-type Dichotomies
Yair Bartal, Nathan Linial, Manor Mendel +1
The classical Ramsey theorem, states that every graph contains either a large clique or a large independent set. Here we investigate similar dichotomic phenomena in the context of…
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…
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…
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…