{"entities":{"Q2382346":{"pageid":2393089,"ns":120,"title":"Item:Q2382346","lastrevid":78615446,"modified":"2026-05-06T12:01:27Z","type":"item","id":"Q2382346","labels":{"en":{"language":"en","value":"Limitations to Fr\u00e9chet's metric embedding method"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5198519"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$4E8BCB08-B588-4E6B-81DF-B1E412335E66","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c84e1e30f2a92d1d28d06261a722f12d9bbaf172","datavalue":{"value":{"text":"Limitations to Fr\u00e9chet's metric embedding method","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2382346$6103BAD8-05F8-4C06-A3A0-676CAA792333","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4108dd8625d1c3fea7225bfb7199b5d91a52b9f4","datavalue":{"value":"1132.46045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382346$CB7DE3A2-16EC-48FF-ABC9-7E6E69E08560","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ef5b90d8c0baf091c1aa0e2adf22efc074b26121","datavalue":{"value":"10.1007/BF02777357","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382346$F0EBB3F9-B2AF-45EE-B5DD-32556F3BBBA8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c81ab3c92f44f395b025a7c9836ac25b0a0d1756","datavalue":{"value":{"entity-type":"item","numeric-id":178480,"id":"Q178480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$83783FE1-BF60-4110-A09C-F942C291F186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e15064a955e2b0fc1477893d6cd3b38b1f1b89dc","datavalue":{"value":{"entity-type":"item","numeric-id":185634,"id":"Q185634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$E9EFC4DA-1072-4521-B6E6-34193C90EE04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6441b04c78f0db4705bdccbf7117dee8afcd822d","datavalue":{"value":{"entity-type":"item","numeric-id":388454,"id":"Q388454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$BF69B986-52A5-4FBB-B334-D67BC32F935C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c2129463e4fb202d617a918e802d846c3730ad87","datavalue":{"value":{"entity-type":"item","numeric-id":610753,"id":"Q610753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$8497037B-B545-44DE-A72D-798D1E7D78AF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1d50f9b953eac0b2404563f86ad398ee3823cb48","datavalue":{"value":{"entity-type":"item","numeric-id":173732,"id":"Q173732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$29ADC712-9DD9-4471-97EA-60E2A021ABDE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a1c6d1eb5a1881a1c15c479f8c9d6be5d5505633","datavalue":{"value":{"time":"+2007-10-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2382346$D3F08C45-B40E-4475-8826-15BCE7A70811","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9e839d4871b4aab7bc762f0be223a9ef60c4becd","datavalue":{"value":"https://arxiv.org/abs/math/0406404","type":"string"},"datatype":"url"},"type":"statement","id":"Q2382346$58BDF8F7-0658-4258-A3DB-7ECD8A169C9F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"00ad52cfc769726fc64a3aa5b97616683c0890ec","datavalue":{"value":"The paper is devoted to low-distortion embeddings of finite metric spaces into the Banach spaces \\(\\ell_p\\) \\((1\\leq p<\\infty)\\). The distortion of an (injective) embedding \\(f:X\\to\\ell_p\\) is defined as the product of the Lipschitz constants \\(\\text{Lip}(f)\\cdot\\text{Lip}(f^{-1}|_{f(X)})\\).   The authors define a Fr\u00e9chet embedding as an embedding \\(f:X\\to\\ell_p^S\\) (\\(S\\) is the set of all nonempty subsets of \\(X\\)) given by   \\[ f(x)=\\{\\alpha_A\\cdot\\text{distance}(x,A)\\}_{A\\in S}, \\]   where \\(\\alpha_A\\) are some real numbers (usually assumed to be non-negative). Such embeddings play a significant role in the theory [see \\textit{J. Bourgain}, Isr. J. Math. 52, 46--52 (1985; Zbl 0657.46013); \\textit{S. Rao}, ``Small distortion and volume preserving embeddings for planar and Euclidean metrics'', in: Proceedings of the Fifteenth Annual Symposium on Computational Geometry (Miami Beach, FL, 1999), 300--306 (electronic), ACM, New York (1999; Zbl 0993.68504)].   The problem considered in this paper is inspired by the recent studies on Ramsey type problems of the following type: given a finite metric space, a how large subset of it has a small-distortion embedding into \\(\\ell_2\\)? See \\textit{M. Mendel} and \\textit{A. Naor} [J.~Eur. Math. Soc. 9, No. 2, 253--275 (2007; Zbl 1122.68043)] for an important recent Ramsey type result and references. The point is that in the recent achievements on Ramsey type problems Fr\u00e9chet embeddings are not used, instead they use approximations of metrics based on hierarchically well-separated trees introduced by \\textit{Y. Bartal} [``Probabilistic approximation of metric spaces and its algorithmic applications'', in: 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), 184--193, IEEE Comput. Soc. Press, Los Alamitos, CA (1996)].  The main result of the present paper (Theorem 2) shows that it is not coincidental: some of the known Ramsey type results cannot be achieved using Fr\u00e9chet embeddings. The presentation of the main result is self-contained.  The final section of the paper contains comments on relations between ultrametrics and dominated \\(\\ell_1\\) metrics introduced by \\textit{J. Matou\u0161ek} and \\textit{Y. Rabinovich} [Isr. J. Math. 123, 285--301 (2001; Zbl 0987.46022)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382346$33244A55-817A-4A55-A8AB-EDECF94132FF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2bb0a9b5cc34aac48ce30600862f79854c409cf1","datavalue":{"value":"46T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382346$635A5D86-AE0E-4538-879A-24081EBB4ABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382346$1C61A2A0-1DB4-4530-8150-70A852CA43EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9934057d10323980704e6b94db4ebac54a6fd5ff","datavalue":{"value":"54E35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382346$38DBF0B2-8089-46E8-8264-8E890EC2337C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c08710bc121395b0a2f9606e43b200d45cf246b9","datavalue":{"value":"5198519","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382346$C583787F-D1B4-4CBB-8137-8F77C34F4714","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b40e3609d3934d90b4d8e478b07fab3ffed9b1f9","datavalue":{"value":"finite metric space","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382346$8324C7F2-5CB4-4D2D-90EB-85E39B6283CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c673dc2855ba713347a1a98300bf7cd78321396","datavalue":{"value":"Lipschitz mapping","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382346$1D2F40A6-2887-4BBB-B507-D8740F929CE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"373ec0b2c9989db4f2d6a1e53aff0b5ca2c6044e","datavalue":{"value":"low-distortion embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382346$5EBAB287-34CC-44D3-85EA-AE6252ED28D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79868fa7d2ed2a6553b37c589c14ecdcfeb2d4ec","datavalue":{"value":"Banach space","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382346$56A2F794-26A5-4EB3-B98D-C5844C1AD98B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"14ba19fd9284d2cf0d8decec72dc0f5317181977","datavalue":{"value":{"entity-type":"item","numeric-id":394136,"id":"Q394136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$9541F332-CE30-41B5-8577-5954387D6B5B","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$82B01BBF-8027-46DE-BA87-D2CD555A4CA8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe6de0e03b6f04b5fcf8b4fe9f7d754d9a60c923","datavalue":{"value":{"entity-type":"item","numeric-id":4938152,"id":"Q4938152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$FEE657D0-3438-4486-8B2B-716C99F29084","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dad50c537b2c42fe2e4a71ad558c92763d5b0e1d","datavalue":{"value":{"entity-type":"item","numeric-id":1110768,"id":"Q1110768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$064A5085-5B42-4B44-B072-4D45F4007075","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c417311d24cef752f3618763c9ec868ab50774c","datavalue":{"value":{"entity-type":"item","numeric-id":1577009,"id":"Q1577009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$8C0D0A57-5221-404C-B3A2-DF87EDF8A5D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a22dcef4db1745e92e071975735a64db791b855","datavalue":{"value":{"entity-type":"item","numeric-id":3767843,"id":"Q3767843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$890CFB22-1F9C-4DF7-8798-965178366374","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6eee10244a474146b33792fb94385a5fb6982855","datavalue":{"value":{"entity-type":"item","numeric-id":1894703,"id":"Q1894703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$024D4B76-3D18-4653-B09D-49ED6FD53918","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bda0716344d26183535d0b48ba2c329efdfdcef2","datavalue":{"value":{"entity-type":"item","numeric-id":1912794,"id":"Q1912794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$F1083C59-D317-4915-AE56-C000BFC1EB53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11dd61e340645f8c3a92581a64cc09aa179efe21","datavalue":{"value":{"entity-type":"item","numeric-id":1376045,"id":"Q1376045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$7BC966D0-822F-4986-9152-07D556159B8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cae47064c63d30bafe36c9219eab3baab345830","datavalue":{"value":{"entity-type":"item","numeric-id":4530626,"id":"Q4530626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$F0C3D4C5-1626-4E0B-B7DE-DD58021CA30B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0c24a3d05945c77aa419fe7bb5c50eca258ca3e","datavalue":{"value":{"entity-type":"item","numeric-id":5939287,"id":"Q5939287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$845856B0-6C37-427F-A4FD-C5390D57DECA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32e2187ea371ada76056cfa2f23220d87fe44eb7","datavalue":{"value":{"entity-type":"item","numeric-id":5175966,"id":"Q5175966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382346$BC5D3360-9650-45B7-AF0A-668A2B85FE6A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3d93b1591763aa3b5ec322768d7df92ba5646a58","datavalue":{"value":"W2009836834","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382346$851D6870-AD3C-487E-B9DA-FF71703ACB89","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bad5609c5ade52a257a3c32efd56f847c38db66","datavalue":{"value":{"entity-type":"item","numeric-id":1422397,"id":"Q1422397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23bc95ce7bec481430dd61b5054248547ac294e9","datavalue":{"value":{"amount":"+0.8400272","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2382346$7392BC5B-4DEA-4F6B-915B-2362CC1A4B9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4e3d04d4ececbb79adf62e9b09b873471fa1777","datavalue":{"value":{"entity-type":"item","numeric-id":1764172,"id":"Q1764172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c9fe15b4dda3bbb7b0b5f7ed364e5d7ea4d8e38","datavalue":{"value":{"amount":"+0.75948983","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2382346$2DD8703E-8173-4CF3-9E77-C6ED6E9F6BF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b8d51a88e56534554533e7be4396e9d3c705314","datavalue":{"value":{"entity-type":"item","numeric-id":2921662,"id":"Q2921662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f2246329ecc99ecc5795ee9f97425081b25ed6b","datavalue":{"value":{"amount":"+0.73767745","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2382346$984FD3D9-EC0A-425D-A11C-2DAF63F91201","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6e8dc42fda3fe2c3422a2c6cd823f3ff12938c5","datavalue":{"value":{"entity-type":"item","numeric-id":4695658,"id":"Q4695658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5eddd411134d79fcf676f6cd1b89fddbede2b4e","datavalue":{"value":{"amount":"+0.73136294","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2382346$510AF7D8-52D9-4B75-96B1-A492822EC2C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84342891e4b56cb49d35da037a47f24a76bbcdde","datavalue":{"value":{"entity-type":"item","numeric-id":2994685,"id":"Q2994685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85af5480d696824e226376a1731572f535787620","datavalue":{"value":{"amount":"+0.72737306","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2382346$7803052B-5654-49FC-B671-FBC9A80E7A31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"960a79e543551259adc54c8ccb13c1ccaae73843","datavalue":{"value":{"entity-type":"item","numeric-id":2143363,"id":"Q2143363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41bfdab5ed4a7ed2b571cecbcf07c32ca906a60c","datavalue":{"value":{"amount":"+0.7155927","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2382346$E81A38F9-EC15-473A-B56A-E43695B6A5A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b559f82ed5f6acb2691b596f97ace4273e41939","datavalue":{"value":{"entity-type":"item","numeric-id":4328568,"id":"Q4328568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"004214df6ec3a3c0ba982675c79007c820e8ff6b","datavalue":{"value":{"amount":"+0.7044479","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2382346$F9384C67-E668-42C7-89F9-DA745FA09DEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d700d5047f0351e75ee16daf5953d6178c6983a","datavalue":{"value":{"entity-type":"item","numeric-id":1969001,"id":"Q1969001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"569afc08eb05c62baacb78282cc0e994d6cfa44f","datavalue":{"value":{"amount":"+0.7025231","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2382346$DD7FE5F0-82B2-4616-B3E2-BAE62DE50D4C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Limitations to Fr\u00e9chet's metric embedding method","badges":[]}}}}}