{"entities":{"Q1380790":{"pageid":1391530,"ns":120,"title":"Item:Q1380790","lastrevid":46978041,"modified":"2025-12-25T23:50:44Z","type":"item","id":"Q1380790","labels":{"en":{"language":"en","value":"Lower bounds on the distortion of embedding finite metric spaces in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1127616"}},"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":"Q1380790$DF242102-F448-4691-BCEB-AA9DE04477C6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8854ad7cdf87648d67b8eaa311d7ce818be1f543","datavalue":{"value":{"text":"Lower bounds on the distortion of embedding finite metric spaces in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1380790$4310C43F-85CC-486C-A0CF-27E5C3C572EB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6b676cc971bcaaa6ca9e1b781ad24e7cf202b9f9","datavalue":{"value":"0890.05021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1380790$B6F8FC90-1780-444A-9EE8-A7648D442F13","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5b8f91e5e6818b1d88b0ed048d92082979f451b6","datavalue":{"value":"10.1007/PL00009336","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1380790$EE953121-7BBA-49FA-98A6-5A78F021848D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1380790$F387BCEE-9338-4574-B472-BA3C05BC9187","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7a4aa9887492d0c8972f96f0b793034d2ed1a547","datavalue":{"value":{"time":"+1998-06-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1380790$01781402-7BA0-4E92-B421-9607D88E397F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"40f8458df412a9b54c0e0788dda6ca2c72258b50","datavalue":{"value":"Given two finite metric spaces \\((X,d)\\) and \\((Y,\\delta)\\) with \\(|X|=|Y|\\), and a \\(1-1\\) map \\(f:X \\to Y\\), the Lipschitz norm \\(||f||\\) of \\(f\\) is \\text{\\(\\displaystyle\\max_{s\\neq t \\in X}{\\delta(f(s),f(t))\\over d(s,t)}\\)} and the Lipschitz distance between \\(X\\) and \\(Y\\) is \\(\\text{dist}(X,Y)=\\inf_{f:X\\to Y} ||f||\\cdot ||f^{-1}||\\), where the infimum is taken over all \\(1-1\\) maps. The authors investigate the question of how well a finite metric space can be represented by a subspace of a graph, subject to certain restrictions. Specifically, they prove (1) if \\(H\\) is a simple, unweighted connected graph with \\(n\\) vertices, and if \\(G\\) is any (weighted) graph with the same number of vertices but strictly fewer edges than \\(H\\), then \\(\\text{dist}(H,G)\\geq g/3 - 1\\), where \\(g\\) is the girth of \\(H\\), and (2) with \\(H\\) as above, if \\(G\\) is any weighted graph with at least \\(n\\) vertices, and with \\(\\chi(G)<\\chi(H)\\), then for any \\(n\\)-point subspace \\(S\\) of the vertices of \\(G\\), \\(\\text{dist}(H,S)\\geq g/4 - {3\\over 2}\\). They also investigate how well \\(H\\) can be approximated by a subspace of a graph \\(G\\) with \\(\\chi(G)<\\chi(H)-1\\) (in this case, the minimum distance is a function of the length of a second shortest cycle of \\(H\\)) and of how well an \\(n\\)-circuit can be approximated by a subspace of a tree (the distance is bounded below by \\(n/3 -1\\)). The latter result is then generalized to the following question: how well can the \\(n\\)-sphere be approximated by a subspace of a simplicial complex \\(K\\) of dimension \\(\\leq n\\) with \\(H_n(K)\\) trivial?","type":"string"},"datatype":"string"},"type":"statement","id":"Q1380790$C7314FEC-6AD3-4A38-B5A5-5226BCF7C623","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1380790$DFA5A1B1-2D95-47BF-8EEC-C413E62A718D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"690e1c5cf191f92608f1519d2615db3fab50726d","datavalue":{"value":"1127616","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1380790$DFE5EFFD-C201-4F02-B527-3BBFE8CE06CE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b40e3609d3934d90b4d8e478b07fab3ffed9b1f9","datavalue":{"value":"finite metric space","type":"string"},"datatype":"string"},"type":"statement","id":"Q1380790$561A59CF-5C64-4281-BD9C-8719DBE0BEAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba9992e11c5a892ccd97460fbc31ceefeeb8b95d","datavalue":{"value":"graph embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1380790$1401887A-CDD4-420F-B6B5-4803E803C81C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e34835133853cddd54ff1d64aa57b1decbcc6ed1","datavalue":{"value":{"entity-type":"item","numeric-id":193720,"id":"Q193720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1380790$FB4C7AA9-58D2-4034-9611-86DACE40F4D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b481d9d1e1fd6339de38d10a65dabc0f21090cc0","datavalue":{"value":{"entity-type":"item","numeric-id":168589,"id":"Q168589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1380790$19E150C6-56CF-4D5E-AE43-37C0FC68CE76","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"dd63a294e6572609e555f008f990edc4325ef5e0","datavalue":{"value":{"entity-type":"item","numeric-id":579411,"id":"Q579411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1380790$A2A7322E-7A28-4EFB-AF65-19B84CBC3EB4","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":"Q1380790$05D6415D-B91B-44D7-85B1-A6329BF60CDC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce3af2449e4c3687d0a1100ddd2d68f37dfdf7e7","datavalue":{"value":{"entity-type":"item","numeric-id":3496912,"id":"Q3496912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0289a7484cb040ed29ca5706c3744d36297b3971","datavalue":{"value":{"amount":"+0.8158462047576904","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1380790$4DAEB0D3-37E6-40DF-9074-DD1881027466","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89322a3307e15827c341a1cf85966ce80ef15183","datavalue":{"value":{"entity-type":"item","numeric-id":4415265,"id":"Q4415265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a8b694a65ef8196d6e67bd3bd086268e2da4517","datavalue":{"value":{"amount":"+0.807765543460846","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1380790$B4F3C4D1-29A9-48A7-858D-63C22EAACA6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39b55ca4e17d288fab69b79f3f127f1887cba05a","datavalue":{"value":{"entity-type":"item","numeric-id":413201,"id":"Q413201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33b77ce43535dae86ac13d7044686c65504ea97a","datavalue":{"value":{"amount":"+0.8028947114944458","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1380790$E0D3E369-CB89-4550-9AD3-3F682702588F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e8c87d81f8caaf2ec8411f0a340cafbed2d9ab1","datavalue":{"value":{"entity-type":"item","numeric-id":2408035,"id":"Q2408035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f0353467d543ae53a5d36c1117992eebf91e3bb","datavalue":{"value":{"amount":"+0.8013868927955627","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1380790$2CA84111-608D-44EF-8B7A-2A8D7DCD170C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1380790","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1380790"}}}}}