{"entities":{"Q2925523":{"pageid":2936243,"ns":120,"title":"Item:Q2925523","lastrevid":58052550,"modified":"2026-04-03T15:03:38Z","type":"item","id":"Q2925523","labels":{"en":{"language":"en","value":"The thresholds for diameter 2 in random Cayley graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6356976"}},"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":"Q2925523$22464772-5504-49B5-8DEB-2305ED536854","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"df6b75bffee6eed3e1d0273f1af4c3a0189a3780","datavalue":{"value":{"text":"The thresholds for diameter 2 in random Cayley graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2925523$47888365-225D-4AE7-8AF9-C9FE3028FA87","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6bc053b6e1f42258a1c5f95d5b281ed215856451","datavalue":{"value":"1304.05069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2925523$1F728365-B88E-459F-B387-BFE8B35E1BC1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"92669db398e78c9ce52a9409c48d81912ef4fb8d","datavalue":{"value":{"entity-type":"item","numeric-id":396928,"id":"Q396928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925523$32529453-915A-4B21-A8FA-80B480F8FE87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4f8e99f011862c9ce37529ebab7b80e600f59b85","datavalue":{"value":{"entity-type":"item","numeric-id":311573,"id":"Q311573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925523$2816988D-D7F1-4F80-A7CC-4B38C78C68B2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8bf8bd8f9bc724703ae7642bd9fc1fa56d190149","datavalue":{"value":{"time":"+2014-10-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2925523$F6B54042-0D67-4D60-8B74-93987CFCC46E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a3053ea9c2a09f54f013efcf580f3cfa9d3739a8","datavalue":{"value":"https://arxiv.org/abs/1108.3547","type":"string"},"datatype":"url"},"type":"statement","id":"Q2925523$617E202E-CA91-40B8-970A-476FBDF65971","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2925523$F558C047-BCCF-4B0A-971C-4EE9BD002D37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2925523$CD4910F4-778F-40E4-8420-8047959BD5DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2925523$1FC925D7-BBE7-434A-B349-4F4924887518","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0fb5c2b5135b23a64eead86c75bb584d8442d720","datavalue":{"value":"05B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2925523$88EDD596-1B9F-4FFC-93FD-A52046F1A038","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a7960574d15707dc5636975b655534e09a79a7a5","datavalue":{"value":"6356976","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2925523$84DAA1C3-6FE9-4D09-8A92-EC9F85337DEC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2925523$87C170BD-B362-4DFF-8D13-77C0EEF56038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64e1ee688b6f898d32c9c2776a1d825855a56d60","datavalue":{"value":"Cayley graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2925523$516328CE-C95C-441B-8EBF-80339FEE267A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd227adb1378edbe90691dff18511cebed6b0036","datavalue":{"value":"diameter","type":"string"},"datatype":"string"},"type":"statement","id":"Q2925523$17E0BE1C-759B-4A78-B87B-6E743BCB8AB6","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":"Q2925523$1AE71376-9D58-4DF9-93B9-376886AC7865","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8ae83b2635281751fcc19aeb85c6a1b3d106d4c7","datavalue":{"value":"W1987163348","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2925523$3C8F4813-E11D-4CA9-97A5-7968DB122CC0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"51c39846915c652e3e7fc569ac3707c3746576fa","datavalue":{"value":{"entity-type":"item","numeric-id":2909242,"id":"Q2909242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925523$8BDA0F38-5709-4E64-9FF3-2CF2A6D6C1E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2798c91b2f0ab87981686d14899b98e5f6c96f49","datavalue":{"value":{"entity-type":"item","numeric-id":2509744,"id":"Q2509744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925523$D48A818F-1621-49A8-81DF-76EB943BFBCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"938b5a8d010102108fc756bfbe7e54aa03cc7861","datavalue":{"value":{"entity-type":"item","numeric-id":4798165,"id":"Q4798165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925523$D7F8E2D0-2E3D-4F71-BCBE-5B036B563989","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"035da4b6dc57a992e6aae8e3ad8ab6bef6974d3a","datavalue":{"value":{"entity-type":"item","numeric-id":1886582,"id":"Q1886582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925523$B9A95F04-BF89-4862-9CC9-BA93537880AB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2fc858b4780299049ac4b4c50c5483c193f49009","datavalue":{"value":"10.1002/RSA.20486","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2925523$53CB9518-953F-48D6-9B78-C76841E8755E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"607ae7f7d11ced7a8909533172911c64cec6dcc4","datavalue":{"value":{"entity-type":"item","numeric-id":6486797,"id":"Q6486797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925523$BCF7A8D1-0579-4FC6-96F2-01E58B06BC6F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ac5eca973c4239ca6d8104d0f45f270ce666e5a8","datavalue":{"value":"Given a group \\(G\\), the model \\(\\mathcal{G}(G,p)\\) denotes the probability space of all Cayley graphs of \\(G\\) with each generator chosen independently with probability \\(p\\) from \\(G\\). The authors investigate the properties of graphs \\(\\Gamma\\in \\mathcal{G}(G,p)\\) for an arbitrary group \\(G\\), \\(|G|=n\\rightarrow \\infty\\). In particular they prove that with high probability the diameter of \\(\\Gamma\\) is at most 2 when \\(p\\geq \\sqrt{(2+\\epsilon)\\frac{\\log{n}}{n}}\\) and this result is best possible as with high probability the diameter of \\(\\Gamma\\) is greater than 2 when \\(\\Gamma\\in \\mathcal{G}(\\mathbb{Z}_2^n,p)\\) and \\(p\\leq \\sqrt{(2-\\epsilon)\\frac{\\log{2^n}}{2^n}}\\).NEWLINENEWLINENEWLINE They also prove that with high probability the diameter of \\(\\Gamma\\) is greater than 2 when \\(p\\leq \\sqrt{(\\frac{1}{4}-\\epsilon)\\frac{\\log{n}}{n}}\\) in the case of a general group \\(G\\) and when \\(p\\leq \\sqrt{(\\frac{1}{2}-\\epsilon)\\frac{\\log{n}}{n}}\\) in the case of an abelian group \\(G\\). Also, these results are best possible. Namely, if \\(G\\) is a cyclic group and \\(p\\geq \\sqrt{(\\frac{1}{2}+\\epsilon)\\frac{\\log{n}}{n}}\\), then with high probability the diameter of \\(\\Gamma\\) is at most 2. Similarly, if \\(0<\\epsilon<1/4\\), \\(G\\) has at most \\(O(n^{(1+\\epsilon)/2})\\) involutions, at most \\(O(n^{(1+\\epsilon)/2})\\) elements \\(x\\) with \\(\\mathrm{cl}(x)\\leq 1/\\epsilon\\), at most \\(O(n^{(1+\\epsilon)/4})\\) involutions \\(x\\) with \\(\\mathrm{cl}(x)\\leq 1/\\epsilon\\) and at most \\(\\epsilon^2 n/49\\) conjugacy classes, then with high probability the diameter of \\(\\Gamma\\) is at most 2, when \\(p\\geq \\sqrt{(\\frac{1}{4}+\\epsilon)\\frac{\\log{n}}{n}}\\).NEWLINENEWLINENEWLINE The authors consider also the model \\(\\mathcal{G}(L,p)\\), where \\(L\\) is a Latin square. In this model the set of vertices is \\([n]\\) and two vertices are adjacent if and only if \\(L_{ij}\\in S\\) or \\(L_{ji}\\in S\\), where the elements of \\(S\\) are chosen from \\([n]\\) independently with probability \\(p\\). The authors prove that in this case with high probability the diameter of \\(\\Gamma\\in \\mathcal{G}(L,p)\\) is at most 2 when \\(p\\geq \\sqrt{(26+\\epsilon)\\frac{\\log{n}}{n}}\\) and with high probability is greater than 2 when \\(p\\leq \\sqrt{(\\frac{1}{4}-\\epsilon)\\frac{\\log{n}}{n}}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2925523$7502D98A-0622-4A23-AF9A-3652296B2FFE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"598097f4cb6c0412db7ca87f6dfd9e995f9684a1","datavalue":{"value":{"entity-type":"item","numeric-id":268263,"id":"Q268263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2925523$540A003E-B53C-47BD-B80A-903D278ED1C4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60de46812671b172680647e7c3b949fc57024907","datavalue":{"value":{"entity-type":"item","numeric-id":2509744,"id":"Q2509744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d557b8818da916ad9ad14f58d1efc2c7b2dbb5e6","datavalue":{"value":{"amount":"+0.9256406426429749","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":"Q2925523$A8DCB1DB-BC08-41D3-96CF-772B960C68F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2c32a08fe0f1478c7044b9672b78dd00e5704b1","datavalue":{"value":{"entity-type":"item","numeric-id":5403029,"id":"Q5403029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94b4cafbdd4008204e4b0951779e9ecb97e5ba6b","datavalue":{"value":{"amount":"+0.877383828163147","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":"Q2925523$398BDEBD-2BE6-4A41-B730-67065189FA94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42f0a3bafab4bddfde73c03357ae5797d65e259e","datavalue":{"value":{"entity-type":"item","numeric-id":3585197,"id":"Q3585197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c864047f647e4069658b5e1cbc9bc0af0f07797a","datavalue":{"value":{"amount":"+0.8643641471862793","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":"Q2925523$1D31378D-F171-4F3E-9E67-14C8409A964D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29f3fdf131150ad2492c63e9c8a9144911760bc8","datavalue":{"value":{"entity-type":"item","numeric-id":1375344,"id":"Q1375344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c423fb7731345e6bdf919653d89d068b5c297dcb","datavalue":{"value":{"amount":"+0.8640658259391785","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":"Q2925523$AF506876-06D4-455E-A936-8EC0991F92E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad4a8ac725278ead3db532c2c843636b47d55668","datavalue":{"value":{"entity-type":"item","numeric-id":4291197,"id":"Q4291197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7c53a9a36d6a7a652afb0ad1c783432e3246004","datavalue":{"value":{"amount":"+0.8543969988822937","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":"Q2925523$0434176F-D705-40E0-A53B-6D98EEFA69D7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2925523","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2925523"}}}}}