66 citations · 108 across the 7 of their papers we have counts for
6 papers · 1 filter
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…
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…
Finite metric spaces--combinatorics, geometry and algorithms
Nathan Linial
Finite metric spaces arise in many different contexts. Enormous bodies of data, scientific, commercial and others can often be viewed as large metric spaces. It turns out that the…