{"entities":{"Q471395":{"pageid":473162,"ns":120,"title":"Item:Q471395","lastrevid":62131695,"modified":"2026-04-11T03:59:05Z","type":"item","id":"Q471395","labels":{"en":{"language":"en","value":"Realization of subgraphs of random graphs by graphs of diameters in Euclidean spaces"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6369725"}},"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":"Q471395$03257ACD-3F4D-4D04-9DEA-5A164E20896B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bbcfcc66a29cf84189ae6470079e6d9cdb8c6f09","datavalue":{"value":{"text":"Realization of subgraphs of random graphs by graphs of diameters in Euclidean spaces","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q471395$FDA0CABD-0CFC-4197-A0B8-54BF4592D74B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a5edf4867458e4c5d2c04aac7e4666718b7c13b1","datavalue":{"value":"1305.05210","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q471395$35A03B47-C54E-44FF-BFBC-AE78F4F1A634","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c25d7ff2fefc88302b3fc90459e770f130b0efb2","datavalue":{"value":"10.1134/S1064562414030296","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q471395$77264FE8-2718-4D7F-B95E-137519586FEF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b770fd3859b7f245c50251118cf915424b0b5ac","datavalue":{"value":{"entity-type":"item","numeric-id":471394,"id":"Q471394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q471395$36405382-E7EE-42A0-9287-C24FEF61ABBD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2bbc31fcaa3dcf49d82403ba391044fdfb104e43","datavalue":{"value":{"entity-type":"item","numeric-id":161529,"id":"Q161529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q471395$FD894960-0AA2-4775-B5C9-BF9FE9BDAE7A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7716cb22ca1a0f2aae16b7f525027a88bc263ef8","datavalue":{"value":{"time":"+2014-11-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q471395$BB25C640-5987-4388-82BC-A0D4185E629E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7af180ab84471c607fce7991e3a55e41d2473597","datavalue":{"value":"A graph of diameters in \\(\\mathbb{R}^{d}\\) is a graph whose vertex set \\(V\\) is a set of points in \\(\\mathbb{R}^{d}\\) and whose edge set consists of those pairs of points for which \\(d(x,y)=\\max_{x,y \\in V}d(x,y)\\). In other words, two vertices are adjacent if and only if the distance between them is the largest distance in the set of distances. Clearly the smallest number of sets of smaller diameter into which \\(V\\) can be partitioned is equal to the chromatic number of \\(G\\). The former quantity is the so-called Borsuk number of the set, related to the (now known to be false) Borsuk conjecture on the minimum number of sets of diameter strictly less than one into which a set of diameter one can be partitioned.   The paper under review studies the quantity \\(u_{d}(n,p)\\) which is   \\[ \\begin{multlined}\\max\\{k: \\mathbb{P}_{n,p}\\big( \\exists H=(W,F)\\subset G: | W|=k,\\,H=G\\mid_W,\\\\ H {\\text{ is a graph of distances in }}\\mathbb{R}^{d}, \\chi(H)\\geq d+1\\big)>1/2\\}.\\end{multlined} \\]   In words, this is, for \\(d\\leq 3\\), the maximum \\(k\\) such that, in an Erd\u0151s-R\u00e9nyi random graph \\(G(n,p)\\), there is an induced subgraph on \\(k\\) vertices which is a graph of diameters in \\(\\mathbb{R}^{d}\\) with the maximum possible chromatic number. We use here the truth of the Borsuk conjecture in dimensions \\(\\leq 3\\).   The paper states (but does not prove) various results on values on the typical (i.e. the \\textbf{whp} values) of \\(u_{d}(n,p)\\) as \\(p=p(n)\\) varies, for various values of \\(d\\) -- especially 2 and 3. For example, \\(u_{2}(n,p)\\) is typically about \\(2\\log_{b}(np)\\) where \\(b=1/(1-p)\\). Some less sharp \\textbf{whp} bounds on \\(U_{d}(n,p)\\) for more general \\(d\\) are also stated. Proofs are in another paper by \\textit{A. A. Kokotkin} and \\textit{A. M. Raigorodskii} [Mosk. Fiz.-Tekh. Inst., Trudy Inst. 4, 19--28 (2012)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q471395$B2047A3A-AE64-48C0-A22E-A943445015BA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b0b0cea8603b4de1ffd54cda6d37d129691a25c2","datavalue":{"value":{"entity-type":"item","numeric-id":590772,"id":"Q590772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q471395$7EFF9AFF-49A1-4F8F-B295-2C9C3D438582","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q471395$40F885D9-BDC2-4B37-A4CA-6D25635278EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q471395$9E7F71E2-A097-4FB3-9854-C2652F11AAC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q471395$2EB0F250-D23A-46FD-8A47-9D9CCB84CC42","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cb00e9cf4996cd7e65ec35f78fb30094f0b88a90","datavalue":{"value":"6369725","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q471395$6D6DF19E-D065-4B4B-8B24-FB3880B2919D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q471395$F4530FF9-518C-4E95-BE9C-C404E7F36A71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e9e17ed8a7eb748fb9def4dc1d5d0ab4036bcb8","datavalue":{"value":"graph of diameters: Borsuk conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q471395$33DBF602-3F42-4B36-9916-ABF37A664186","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":"Q471395$B4DA9C4D-3BA2-4309-97A3-A5A6DBA1E208","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"48e8567933e8042fcc7158f93a4b203812c046cd","datavalue":{"value":{"entity-type":"item","numeric-id":4752779,"id":"Q4752779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q471395$F957A9E0-81B0-48A4-98EB-893ED81F73E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a748cc73a535dd5df6ea8573adf889565fe2a12a","datavalue":{"value":{"entity-type":"item","numeric-id":4719727,"id":"Q4719727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q471395$6DE4D876-45A8-49DB-AEBC-2321EA92FCF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1af1d343f0556aef88cc74062c59f678d139b4ae","datavalue":{"value":{"entity-type":"item","numeric-id":630237,"id":"Q630237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q471395$BE3ACB2E-2B9A-481D-A1BB-729BCEBC48D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a41ad67a719cd1a05f711afeb8d12711030e196","datavalue":{"value":{"entity-type":"item","numeric-id":2847920,"id":"Q2847920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q471395$DD56312B-5EE2-4F10-89C9-8818E84AC96A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d84a0aea8c3e088188f2bd6bc42b948f26a03d8e","datavalue":{"value":{"entity-type":"item","numeric-id":452856,"id":"Q452856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q471395$9B6D5814-6634-4779-B2D6-300EA700D159","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"839a2142e6de05a3cf1aad0da3c86e04df240647","datavalue":{"value":{"entity-type":"item","numeric-id":2564763,"id":"Q2564763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q471395$B7F54BED-1D20-4750-849C-56AC4B4FB17F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8b656de080ff5b24898858b58fde36475098a8a","datavalue":{"value":{"entity-type":"item","numeric-id":5917516,"id":"Q5917516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q471395$E6179AEB-97FA-42AF-9FA0-D3460993C986","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b07d6ae8072ec0b52d1a52248f558d67752e38c","datavalue":{"value":{"entity-type":"item","numeric-id":2743189,"id":"Q2743189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q471395$71B4476F-F544-4E81-949E-D250BEED7A3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2531f30ec1705a99476fbb63907e750f141d8c4","datavalue":{"value":{"entity-type":"item","numeric-id":1760937,"id":"Q1760937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q471395$393DEC46-5A84-4CC5-BAFF-B777388B1845","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9ef3f899f423ce1034571bfc4c940c69196bba3","datavalue":{"value":{"entity-type":"item","numeric-id":393923,"id":"Q393923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q471395$B34CE588-49FA-4264-A5C3-26CB3B52ED78","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"451c5f2bab8499d855eb606ab0a3cc115f07858b","datavalue":{"value":"https://doi.org/10.1134/s1064562414030296","type":"string"},"datatype":"url"},"type":"statement","id":"Q471395$71F2DA42-34E5-49B9-B0AE-72475DBD9192","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e08ec335c8b4821301ac5d39b1b12b633270b180","datavalue":{"value":"W2067577095","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q471395$E3D5133E-154C-4632-B7C5-F9E518710F08","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac91463fcb14fddf7bb7128f2177bb2b4c81af2a","datavalue":{"value":{"entity-type":"item","numeric-id":745606,"id":"Q745606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ff85acc7fc4a0430fb8059c11efe334e95db18c","datavalue":{"value":{"amount":"+0.8798940181732178","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":"Q471395$9AB440B9-25EF-46D4-87FD-D4CFDE478EC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2565aacaa7b2e6da40a25425e4976477ce09975","datavalue":{"value":{"entity-type":"item","numeric-id":3593723,"id":"Q3593723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b800a6ca3f48f5c628f0413c3b38f3bb62492e42","datavalue":{"value":{"amount":"+0.813940703868866","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":"Q471395$F5765B55-F319-44AB-AA62-971A9F7A4D84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cff7bc7875a62f7e12912b656b1ec1080288ee2","datavalue":{"value":{"entity-type":"item","numeric-id":5113958,"id":"Q5113958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f306cf6547d949f15723f2577442b29cf4391b4b","datavalue":{"value":{"amount":"+0.811674952507019","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":"Q471395$B091B914-BBF1-404C-9743-FEFCE0E9B315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c489954241b82bae9798dd18337e297d343a6667","datavalue":{"value":{"entity-type":"item","numeric-id":1760937,"id":"Q1760937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1d55b4252034a3eee38cc40378f3fac9ccd2a7a","datavalue":{"value":{"amount":"+0.8065986633300781","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":"Q471395$30B7F23E-7A93-4726-BA62-E3947E0EFD5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d489cdffa4d9756ab5d5099b80fa381972fbc9c6","datavalue":{"value":{"entity-type":"item","numeric-id":2455210,"id":"Q2455210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66cd69018b02998070d7ea46e203ef14275e4f3d","datavalue":{"value":{"amount":"+0.791374146938324","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":"Q471395$4328CD58-FB72-4432-931A-5518BB5C7672","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Realization of subgraphs of random graphs by graphs of diameters in Euclidean spaces","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Realization_of_subgraphs_of_random_graphs_by_graphs_of_diameters_in_Euclidean_spaces"}}}}}