{"entities":{"Q663092":{"pageid":664941,"ns":120,"title":"Item:Q663092","lastrevid":63406440,"modified":"2026-04-11T12:44:21Z","type":"item","id":"Q663092","labels":{"en":{"language":"en","value":"On the chromatic number of random geometric graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6006219"}},"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":"Q663092$BC226807-1280-4A2D-BA8F-ACFFDA0F7E0D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6c1b3d1ba6acb1957ad02536f7b25a5a816b79ff","datavalue":{"value":{"text":"On the chromatic number of random geometric graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q663092$A809B479-964B-4600-9D94-60F91AB5CADB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"64bff966490620a1d8e127eb0c2242a3226cfdeb","datavalue":{"value":"1263.05097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q663092$1BE6FF2D-75AF-4E88-A81D-56568B959431","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b28167d2cbd3c8a14389400da8d34571438d12b2","datavalue":{"value":{"entity-type":"item","numeric-id":394281,"id":"Q394281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q663092$B2491E92-000A-42DE-8915-F3EE7CE7BE07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"03f08a3cbc69e48052a97dab7b19fd1cbcee9fe9","datavalue":{"value":{"entity-type":"item","numeric-id":1227010,"id":"Q1227010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q663092$F6A38CE8-451C-41E0-839F-32FA39706963","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q663092$A88D76E5-F700-4AA4-B699-D298C92728DB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6eb3272d0161057811dc00bb0e9bfbb7171fee74","datavalue":{"value":{"time":"+2012-02-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q663092$02993E1D-6AA5-4B78-B26F-6B948994F6F5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"995adb016a94067124d54eb11247a75344bec841","datavalue":{"value":"https://arxiv.org/abs/1101.6065","type":"string"},"datatype":"url"},"type":"statement","id":"Q663092$51B691CC-E4BC-4412-AEED-9956969C89C4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4b3df7ea2a1d11f44cacc7d329f360f95b8d872b","datavalue":{"value":"This paper studies the chromatic number \\(\\chi(G)\\) and clique numbers \\(\\omega(G)\\) of random geometric graphs,  especially in a `threshold' case where earlier results had not given insight. In detail, let \\(\\|.\\|\\) be a norm on \\({\\mathbb{R}}^{d}\\), with packing density \\(\\delta \\in (0,1]\\). (The packing density is, informally, the greatest proportion of \\({\\mathbb{R}}^{d}\\) which can be filled with disjoint translates of the unit open ball \\(B\\).) Let \\(\\nu\\) be a probability distribution on \\({\\mathbb{R}}^{d}\\) with probability density function \\(f\\). Given a sequence \\(X_{1},X_{2},\\dots\\) of independent random variables distributed as \\(\\nu\\), we say that the random geometric graph \\(G_{n}\\) has vertices \\(X_{1},\\dots, X_{n}\\) with two vertices \\(X_{i}, X_{j}\\) being adjacent if and only if \\(\\| X_{i}-X_{j}\\| \\leq r=r(n)\\) for some function \\(r(n)\\), with \\(\\lim_{n\\rightarrow \\infty} r(n)=0\\).     The main result has four parts, depending on the value of \\(nr^{d}\\). Firstly, if \\(nr^{d} \\ll n^{-\\alpha}\\) for some fixed \\(\\alpha>0\\), then with probability 1, for all but finitely many \\(n\\)   \\[ \\chi(G_{n}) = \\omega(G_{n}) \\in  \\left\\{\\left\\lfloor \\frac{\\ln(n)}{\\ln(nr^{d})} + \\frac{1}{2}\\right\\rfloor, \\left\\lfloor \\frac{\\ln(n)}{\\ln(nr^{d})} + \\frac{1}{2} \\right\\rfloor+1\\right\\}. \\]     Secondly, if \\(n^{-\\varepsilon} \\ll nr^{d} \\ll \\ln(n)\\) for all \\(\\varepsilon>0\\), then \\(\\chi(G_{n})\\) and \\(\\omega(G_{n})\\) are both almost surely \\(\\sim \\ln(n)/\\ln (\\ln(n)/(nr^{d}))\\). This is a technical improvement of an earlier result in [\\textit{M.~D.~Penrose}, Random Geometric Graphs, Oxford University Press (2003; Zbl 1029.60007)].     Thirdly (this `threshold' case is the main novelty) is the case where \\(nr^{d}\\) is roughly a constant times \\(\\ln(n)\\). In detail, let \\(\\sigma = \\sup\\{t : \\operatorname{vol}(\\{x: f(x)>t\\}) >0\\}\\) be the essential supremum of \\(f\\) (\\(\\operatorname{vol}\\) denotes Lebesgue measure). The result is then that, if \\(\\sigma nr^{d}/\\ln(n) \\rightarrow t\\) as \\(n \\rightarrow \\infty\\), then \\(\\chi(G_{n}) \\sim f_{\\chi}(t)\\sigma nr^{d}\\) almost surely, for a (complicated!) continuous non-increasing function \\(f_{\\chi}\\), which depends on \\(d\\) and \\(\\|.\\|\\) only. Further \\(\\lim_{t\\rightarrow \\infty} f_{\\chi}(t) = \\operatorname{vol} (B)/(2^{d}\\delta)\\) and \\(\\lim_{t\\rightarrow 0} f_{\\chi}(t) = \\infty\\). Here the clique number behaves differently from chromatic number: again assuming \\(\\sigma nr^{d}/\\ln(n)\\rightarrow t\\), we have \\(\\omega(G_{n}) \\sim f_{\\omega}(t)\\sigma nr^{d}\\) almost surely, where \\(f_{\\omega}\\) is a (complicated!) continuous, strictly decreasing function with \\(\\lim_{t\\rightarrow\\infty} f_{\\omega} (t) = \\operatorname{vol}(B)/2^{d}\\): in particular, it is a factor (about) \\(1/\\delta\\) away from \\(f_{\\chi}\\) for large \\(t\\) (provided \\(\\delta<1\\)).     Finally, for \\(nr^{d} \\gg \\ln(n)\\) (but \\(r(n)\\rightarrow 0\\) still) we have (again sharpening a result of Penrose) that, almost surely,   \\[ \\chi(G_{n}) \\sim \\frac{\\operatorname{vol}(B)\\sigma nr^{d}}{2^{d}\\delta}, \\quad \\omega(G_{n}) \\sim \\frac{\\operatorname{vol}(B)\\sigma nr^{d}}{2^{d}} \\]   so again \\(\\chi\\) and \\(\\omega\\) differ provided \\(\\delta<1\\). Proof techniques include showing that the chromatic number of the random geometric graph is approximated by the fractional chromatic number, and a large amount of detailed analysis of so-called generalised scan statistics.","type":"string"},"datatype":"string"},"type":"statement","id":"Q663092$076CB2D5-3A23-42A9-A397-5B6FD3EDA9A3","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":"Q663092$6B045000-FABD-41CC-9CA8-A5A59125296B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q663092$6C73DA6A-78C7-4186-BE0B-4B8234400E2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"671a9141f7533e3d7d525a297ffd04f047259a12","datavalue":{"value":"60D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q663092$F81B266A-CA22-4DF5-9B29-22480F15ECC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q663092$6D15FE38-A32B-4B6A-BAA0-FFAB43C678D6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"631e4d3f6efac9cbf08d9c689ba83f811c97320c","datavalue":{"value":"6006219","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q663092$CE462CE8-45C2-4302-929D-54C210268FD8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"23ed096b8fec3cdc67dc96d2c7a5937d3cb572a5","datavalue":{"value":"random geometric graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q663092$BE6A2B94-BD42-4A89-BD98-B2CA6C93265B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q663092$A37F3B1C-0499-4097-8CCB-818F05E4C5EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb2169375ebb26ec0067c3fe2ae2119dcb9b464e","datavalue":{"value":"clique number","type":"string"},"datatype":"string"},"type":"statement","id":"Q663092$6F7CF612-E33C-476D-99E8-36F35AD462DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"637872e1bd0dd812655871ae455bcab7bf55fd2b","datavalue":{"value":"fractional chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q663092$EC12FB63-6244-46D9-8C64-7DD9B4F34BAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5a214eca03411a6b537cc2d4ec2ec99509baa8b","datavalue":{"value":"generalized scan statistic","type":"string"},"datatype":"string"},"type":"statement","id":"Q663092$177380A7-5A84-40DC-9375-97530426A3D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2a6e7a6df478bcaef8cc07998b2a800920e36ed","datavalue":{"value":"packing density","type":"string"},"datatype":"string"},"type":"statement","id":"Q663092$2E723FBF-C363-4D39-B91C-3B5B52F42172","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":"Q663092$775E0017-8236-485C-BE32-B6A98FFDC4C2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ac6d269be076ec1c72a5284702e4360e27c278e3","datavalue":{"value":"W3101994521","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q663092$5E453317-5D4F-42C2-8163-37CAF62D1699","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f380170dd9de5e69fb40eb46470ac085e19dc87a","datavalue":{"value":{"entity-type":"item","numeric-id":1174134,"id":"Q1174134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q663092$BB90A294-E324-4985-A88F-6863C34EC37E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"810e5186e041cdc2693cc7d82ba8b5c663991d61","datavalue":{"value":{"entity-type":"item","numeric-id":5951048,"id":"Q5951048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q663092$C042A9E7-2F92-41DE-A8AF-8ABB811B28B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0a876e959b6e1cf5ba72cd222f33874a5f0081e","datavalue":{"value":{"entity-type":"item","numeric-id":1386337,"id":"Q1386337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q663092$649F1ACD-FF7F-4F42-B2EA-21455CD4039E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdd51985f8df50c8dac6708d27413a9259a40295","datavalue":{"value":{"entity-type":"item","numeric-id":5905438,"id":"Q5905438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q663092$5A5D39E1-A64D-409C-ADD5-47B80BD878E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6dabe225485800a1b19fe30399f1d0682b5274d4","datavalue":{"value":{"entity-type":"item","numeric-id":5546445,"id":"Q5546445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q663092$A9F3EB42-09B9-4189-AB36-34B4EF14A8DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56ae6174626dffb0e5bb36dbe6b6047d7e02d8d8","datavalue":{"value":{"entity-type":"item","numeric-id":4800395,"id":"Q4800395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q663092$42F21F58-1DB5-4998-8B38-06D55B47339D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"078cd904684e44e3d180b6de5ee4153ee98494d6","datavalue":{"value":{"entity-type":"item","numeric-id":2390151,"id":"Q2390151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q663092$ECD7763A-4F74-42AD-B873-50153341EAE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a53b69cbc4a2d6fc8411a0ffa863e46323ab96fd","datavalue":{"value":{"entity-type":"item","numeric-id":4458875,"id":"Q4458875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q663092$224B284D-40CF-4373-AEA7-6BAB6015B7A7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f0b6158825186abd394b48b455b356f17330c186","datavalue":{"value":"10.1007/S00493-011-2403-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q663092$9E4EB86B-EB6E-43FF-B7FF-996BD7A1A45E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"103a9d4f2768184ca5a6c6d9bcc91526e94babbe","datavalue":{"value":{"entity-type":"item","numeric-id":3576649,"id":"Q3576649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"646bc8b1a4e1ebd1d3e69ce06ff48443bf34f9ae","datavalue":{"value":{"amount":"+0.9402036070823668","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":"Q663092$6E74864F-62E7-42FB-B962-A6C1D6E24C33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1e3c14324ae9957df7e7a98300f837b5f0dcdb0","datavalue":{"value":{"entity-type":"item","numeric-id":5420381,"id":"Q5420381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3653977acda6e3210a007fd013c8680ba8bf452d","datavalue":{"value":{"amount":"+0.8467622995376587","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":"Q663092$CCED0A81-C0D5-4152-A7C9-EBCE93116C08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c689d399ab4379ad17914255162626ee0de32be","datavalue":{"value":{"entity-type":"item","numeric-id":5396740,"id":"Q5396740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9c5fb4c96a896e0ecb28451e1a9af39d420aae2","datavalue":{"value":{"amount":"+0.8349629640579224","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":"Q663092$253A34C8-7A2D-492B-BB4C-995447B7F11C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f62dd2a23652d753d49a374ccb7bc8b33cd22af","datavalue":{"value":{"entity-type":"item","numeric-id":5194659,"id":"Q5194659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f408eb23a1522ab45854486fca64d5c133533a30","datavalue":{"value":{"amount":"+0.8348209857940674","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":"Q663092$009B29E3-E763-43F3-A9A5-C5E6535BEA36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da84c43d606655562b289564dc2afb1a1802f4a3","datavalue":{"value":{"entity-type":"item","numeric-id":2390151,"id":"Q2390151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8e4f398dd1a54ec68c6ad29031199db06ef69f5","datavalue":{"value":{"amount":"+0.8267586827278137","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":"Q663092$91263616-ECEC-42BC-B694-831042EFE444","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the chromatic number of random geometric graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_chromatic_number_of_random_geometric_graphs"}}}}}