{"entities":{"Q1204473":{"pageid":1215222,"ns":120,"title":"Item:Q1204473","lastrevid":66348060,"modified":"2026-04-12T09:30:12Z","type":"item","id":"Q1204473","labels":{"en":{"language":"en","value":"On embedding of graphs into Euclidean spaces of small dimension"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 130568"}},"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":"Q1204473$6FED9F22-5E4B-4704-87A3-3304778B7286","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0cd1bc974ede3e12d85b37ff71d7f9ee90ad5457","datavalue":{"value":{"text":"On embedding of graphs into Euclidean spaces of small dimension","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1204473$4473A39D-ABD0-479E-990B-A06DAE1E6FFE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"649dd97936c3382605f025c5743fb54bd15f6822","datavalue":{"value":"0773.05043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1204473$D71A5FA9-44F7-4124-A5F3-83CC98EA9601","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9b97d7f6775e32e066675bba3e4047fc0b156cba","datavalue":{"value":"10.1016/0095-8956(92)90002-F","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1204473$8E31227C-5EB7-4CDD-AF17-6C35718FBF31","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"df3dd90bf8150cc86ec6cf068d061afde632f05e","datavalue":{"value":{"entity-type":"item","numeric-id":913813,"id":"Q913813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1204473$AB191300-DAEB-449C-B607-65F1BF44E01D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c36b77bffff6f43e669d0380d3493f37a56849f","datavalue":{"value":{"entity-type":"item","numeric-id":168591,"id":"Q168591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1204473$7235FF70-1057-490D-B551-417DA5987ED4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2a50a6a2f24b63f866bfb7505a663f8ec06b4a60","datavalue":{"value":{"entity-type":"item","numeric-id":1057877,"id":"Q1057877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1204473$3FF57C24-889A-4B8A-8230-C551EF08CA77","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1204473$EB0D721C-E075-47B1-98EA-A9DFAD62BEF3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fd1a91bacb3b86e97f56b6757c45d39c4521bbf1","datavalue":{"value":{"time":"+1993-03-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1204473$15D69DEB-91A5-40CE-94BB-331AE0790994","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"92df50c55bfa94815464d7e53f0c338a597820a6","datavalue":{"value":"Suppose \\(G=(V,E)\\) is a finite graph with an embedding \\(f:V\\to R^ d\\). If there is a number \\(t\\) so that \\((x,y)\\in E\\) if and only if the scalar product \\(f(x)\\cdot f(y)\\geq t\\), we say \\(G\\) has a scalar product embedding. The least \\(d\\) for which \\(G\\) has such an embedding is called the scalar product dimension and is denoted \\(d(G)\\). If \\(G\\) has \\(n\\) vertices, then clearly \\(d(G)\\leq n\\). The best known general upper bound is \\(d(G)\\leq n- \\sqrt n\\). The paper under review gives another upper bound based on the edge density of \\(G\\), \\(\\rho(G)\\). The edge density is defined to be the maximum over all subgraphs \\((V',E')\\) of \\(G\\) of the quantities \\(2| E'|/| V'|\\). The main result is that there is an absolute constant \\(c\\) with \\(d(G)\\leq c\\rho^ 2\\log n\\), where \\(\\rho(G)\\leq \\rho\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1204473$193685A6-98A5-44AB-965E-76CA5DF41E9B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"61cf9dfec5b66ba829a3bd08d983df202add1f13","datavalue":{"value":{"entity-type":"item","numeric-id":801083,"id":"Q801083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1204473$A492B953-89F7-4F0E-B3EE-29DB311C2603","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1204473$CDC88A6C-1E3C-47EA-B8BC-9950EDB55CBC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9a054bbefead1b718ef649ec8f61bba033dabd13","datavalue":{"value":"130568","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1204473$62BC2363-1D49-4CB4-A01E-A858ED7334A7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"533a8f12e6cf404910488b40362a93374bb65d6a","datavalue":{"value":"finite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1204473$62CC4115-91CC-4C93-AE05-A5269E68F784","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e86d9b4ad5a06064fd9c9bcbc50f8026b1c776dc","datavalue":{"value":"embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1204473$07741DFA-2126-4FEE-B121-32755DFEB6F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f53966d775fcc2db3b5094119d029273a2c52df0","datavalue":{"value":"scalar product embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1204473$D80E4352-B221-4492-8805-C799F81EDE8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cde49dc3ee041eb929220aa415c77f056dec7b7c","datavalue":{"value":"scalar product dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q1204473$597645EB-A5B0-46A3-86F1-26F64415C9EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"817f91d754a6618dd027e0d851a1fc8b7cbc7134","datavalue":{"value":"upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1204473$4E8D1797-C7D2-46EF-9C38-D1C327E96DEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52f104390803a7569ae3f576b172d639d0061261","datavalue":{"value":"edge density","type":"string"},"datatype":"string"},"type":"statement","id":"Q1204473$2391411F-96F1-440E-87E4-183753B4FDF6","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":"Q1204473$B7CBADC9-E068-4E32-B69F-EEEA58EA63AB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5899e3e12a743d53573a910fcbfa636f0f6c8e3","datavalue":{"value":{"entity-type":"item","numeric-id":3852212,"id":"Q3852212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1204473$71016691-6AA6-40F6-A292-AAB3D60E899D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d81d022f27d459c65117397e298a3e45690fb65b","datavalue":{"value":{"entity-type":"item","numeric-id":1844243,"id":"Q1844243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1204473$494883F6-4F8A-4EB0-B299-DA45413CAFE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b747a6d3e881fdb58c7226181f2f1561623d6330","datavalue":{"value":{"entity-type":"item","numeric-id":1121912,"id":"Q1121912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1204473$CE64CB54-C0D8-4848-9682-0D6666C10A1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63ada53980e8d3e7e8a0a401742a431780860804","datavalue":{"value":{"entity-type":"item","numeric-id":5825672,"id":"Q5825672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1204473$D5D8BCD6-1E4B-46F8-8AFE-B17C30DA18DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2f6458a0ae65ee4cd296a67efb900d1043fe003","datavalue":{"value":{"entity-type":"item","numeric-id":1812683,"id":"Q1812683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1204473$803B9141-F945-44C4-95E0-C43E8DC431B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a80b17ce7f6a96d63b0c70b0e03d9559d90df7ec","datavalue":{"value":{"entity-type":"item","numeric-id":1825202,"id":"Q1825202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1204473$01D788EC-F80F-46A2-98AF-335A1B100732","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0ca48ffd9d632455dd7b7205f58f5db400e42750","datavalue":{"value":"https://doi.org/10.1016/0095-8956(92)90002-f","type":"string"},"datatype":"url"},"type":"statement","id":"Q1204473$AE55A580-0342-4731-B833-2E4E670546E5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c76d298d1fa3be170e786c19a8bee99ae1719465","datavalue":{"value":"W2001505356","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1204473$FABF7595-1151-450F-BDB5-648A0DBF3D17","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"180ba645d88ffd59ba1edf33245c08e3ad96ae47","datavalue":{"value":{"entity-type":"item","numeric-id":5915814,"id":"Q5915814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42c42298b65916300cac399ba1601d6fee0b6e23","datavalue":{"value":{"amount":"+0.8406306505203247","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":"Q1204473$C25423E1-582F-4C10-9430-4DA54A639BD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"611eb6dbce6ff0fbbd2acedc009d825cbe86fb75","datavalue":{"value":{"entity-type":"item","numeric-id":5919437,"id":"Q5919437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6448bd4b728b9f29f2fc731d63e7c174ddfc660b","datavalue":{"value":{"amount":"+0.827114462852478","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":"Q1204473$90DD359B-4C20-4BDC-9CFC-ADB6191331F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10beb68d623396596c1c69a96e7d1c3eaa01d931","datavalue":{"value":{"entity-type":"item","numeric-id":1812683,"id":"Q1812683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0df09df7b7b832cf93ce4ada20f3596a70d0b9c","datavalue":{"value":{"amount":"+0.8262755870819092","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":"Q1204473$51A79205-CF7B-4035-A504-2A4E1E8F55FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"509b5ed96088b4c56a4a26fa6055ea85bf71fb57","datavalue":{"value":{"entity-type":"item","numeric-id":4907598,"id":"Q4907598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66f53646155c875a21063605c5ba9d21328cf6fe","datavalue":{"value":{"amount":"+0.8258786201477051","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":"Q1204473$1F5D3A4D-658C-4126-9882-336D45D9304E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61df3577b5fb3a382b59a7a762eaf3647fbd94b0","datavalue":{"value":{"entity-type":"item","numeric-id":1825202,"id":"Q1825202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a6f25960a40121915e9b2967576c938627b968c","datavalue":{"value":{"amount":"+0.7946357727050781","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":"Q1204473$B9F114ED-6069-4E8E-BF41-DA5D14D46738","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On embedding of graphs into Euclidean spaces of small dimension","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_embedding_of_graphs_into_Euclidean_spaces_of_small_dimension"}}}}}