66 citations · 108 across the 7 of their papers we have counts for
4 papers · 1 filter
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…