A tight threshold for metric Ramsey phenomena

Moses Charikar, Adriana Karagiozova

Type: Article

Publication Date: 2005-01-23

Citations: 4

DOI: https://doi.org/10.5555/1070432.1070450

View Publication

Locations

Symposium on Discrete Algorithms - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Some Low Distortion Metric Ramsey Problems	2004	Yair Bartal Nathan Linial Manor Mendel Assaf Naor
+ PDF Chat	On metric ramsey-type phenomena	2003	Yair Bartal Nathan Linial Manor Mendel Assaf Naor
+ PDF Chat	On metric ramsey-type phenomena	2003	Yair Bartal Nathan Linial Manor Mendel Assaf Naor
+ PDF Chat	On metric Ramsey-type phenomena	2005	Yair Bartal Nathan Linial Manor Mendel Assaf Naor
+	Metric spaces are Ramsey	2005	Jaroslav Nešetřil
+	A Ramsey theorem for metric spaces	2018	Péter Komjáth
+	Inapproximability for metric embeddings into R^d	2008	Jiřı́ Matoušek Anastasios Sidiropoulos
+ PDF Chat	Inapproximability for Metric Embeddings into R^d	2008	Jiřı́ Matoušek Anastasios Sidiropoulos
+ PDF Chat	Ramsey partitions of metric spaces	2023	Saharon Shelah Jonathan L. Verner
+	ON METRIC RAMSEY-TYPE DICHOTOMIES	2005	Yair Bartal Nathan Linial Manor Mendel Assaf Naor
+	Ramsey-type results for metric spaces	1987	Péter Komjáth
+	Advances in Metric Ramsey Theory and its Applications	2021	Yair Bartal
+	Metric Dichotomies	2007	Manor Mendel
+	On the nonexistence of dimension reduction for $\ell2_2$ metrics.	2008	Mohammad Moharrami Avner Magen
+	Metric Dichotomies	2007	Manor Mendel
+	Metric structures in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" display="inline" overflow="scroll"><mml:msub><mml:mrow><mml:mi>L</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:math>: dimension, snowflakes, and average distortion	2004	James R. Lee Manor Mendel Assaf Naor
+	Reifenberg flat metric spaces, snowballs, and embeddings	1999	Guy C. David Tatiana Toro
+	Low-distortion embeddings of infinite metric spaces into the real line	2008	Stefan Geschke
+ PDF Chat	Local versus global properties of metric spaces	2006	Sanjeev Arora László Lovász Ilan Newman Yuval Rabani Yuri Rabinovich Santosh Vempala
+	Local versus global properties of metric spaces	2006	Sanjeev Arora László Lovász Ilan Newman Yuval Rabani Yuri Rabinovich Santosh Vempala

Works That Cite This (4)

Action	Title	Year	Authors
+	Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem	2010	Assaf Naor Terence Tao
+	Embedding proper ultrametric spaces into $\ell_p$ and its application to nonlinear Dvoretzky's theorem	2012	Kei Funano
+ PDF Chat	An introduction to the Ribe program	2012	Assaf Naor
+ PDF Chat	Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem	2012	Assaf Naor Terence Tao

Works Cited by This (5)

Action	Title	Year	Authors
+	On hilbertian subsets of finite metric spaces	1986	Jean Bourgain T. Figiel Vitali Milman
+ PDF Chat	Some Low Distortion Metric Ramsey Problems	2004	Yair Bartal Nathan Linial Manor Mendel Assaf Naor
+	Finite metric spaces	2002	Nathan Linial
+ PDF Chat	On metric ramsey-type phenomena	2003	Yair Bartal Nathan Linial Manor Mendel Assaf Naor
+	Ramsey-type theorems for metric spaces with applications to online problems	2006	Yair Bartal Béla Bollobás Manor Mendel