{"entities":{"Q2322509":{"pageid":2333252,"ns":120,"title":"Item:Q2322509","lastrevid":57851928,"modified":"2026-04-02T19:34:36Z","type":"item","id":"Q2322509","labels":{"en":{"language":"en","value":"Diameter of Ramanujan graphs and random Cayley graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7101336"}},"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":"Q2322509$D4AB42AD-535B-4F5B-B908-FD3EE91519BB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dec5136bb6b2a511ce79b2369975a891f7cc695f","datavalue":{"value":{"text":"Diameter of Ramanujan graphs and random Cayley graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2322509$975ABF4A-BCB8-4DC9-817D-6E55375491E0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c4c184652c829104e1331d57a17c5931cc079aae","datavalue":{"value":"1438.05128","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2322509$5DA05F1B-584E-4B24-B185-AA344894FB53","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bc8e13ed36826d29bd7c5d600477c0485b6e5c0f","datavalue":{"value":{"entity-type":"item","numeric-id":2197502,"id":"Q2197502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2322509$B818DF19-8C9D-4615-8635-793B4854B9FE","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":"Q2322509$36FEF68E-A02A-4B9C-83E0-2D9F71E1F36B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"761866c458b823deb2476ea286c91321ef138424","datavalue":{"value":{"time":"+2019-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2322509$C6770729-AB0A-40D0-90A1-B5FC132BDD88","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6e720c8b586b21599f4fb4d11ba3b187b9d0357d","datavalue":{"value":"https://arxiv.org/abs/1511.09340","type":"string"},"datatype":"url"},"type":"statement","id":"Q2322509$F91B8F92-4F0E-48EF-8EE2-CFC23283B1CB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f000810c84572d8b5065d254896aad027e100023","datavalue":{"value":"Let \\(X_{p,q}\\) denote a \\((p+1)\\)-regular bipartite or non-bipartite graph depending on \\(p\\) being a non-quadratic or quadratic residue modulo \\(q\\), respectively. \\textit{A. Lubotzky} et al. [Combinatorica 8, No. 3, 261--277 (1988; Zbl 0661.05035)] constructed an explicit family of \\((p+1)\\)-regular Ramanujan graphs \\(X_{p,q}\\), where \\(p\\) and \\(q\\) are prime numbers and \\(q \\equiv 1 \\pmod4\\). The author shows that the diameter of LPS Ramanujan graphs \\(X_{p,q}\\) is greater than \\((4/3) \\log_{p}(n)+O(1)\\), where \\(n\\) is the number of vertices of \\(X_{p,q}\\). He also constructs an infinite family of \\((p+1)\\)-regular LPS Ramanujan graphs \\(X_{p,m}\\) with diameter greater than or equal to \\(\\lfloor(4/3) \\log_{p}(n)\\rfloor\\), and he shows that for any \\(k\\)-regular Ramanujan graph only a tiny fraction of all pairs of vertices have distance greater than \\((1+\\varepsilon)\\log_{k-1}(n)\\). Numerical results indicate that for LPS Ramanujan graphs and random Cayley graphs the diameters are asymptotically \\((4/3) \\log_{k-1}(n)\\) and \\(\\log_{k-1}(n)\\), respectively.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2322509$F64607B7-B31B-4B8A-B00F-66416512B7FE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2322509$B7640EC2-5A63-4276-A8D8-0D644AA0FF66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2322509$A9F5E96E-F51C-41C5-988C-0DE4ED20F6D1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"493ade80165fee401af0d3d7afffb3b816cacc0c","datavalue":{"value":"7101336","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2322509$432F62E9-4F1D-4446-8DF5-B18E1610EAD7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"789cbdbf063f2e698cf3f08d0ca8ca7bcf372197","datavalue":{"value":"Ramanujan graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2322509$E61F3596-75C5-4BEB-942A-8D3B03D65A03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"157da90b3e36e1d11ade3292cb5de76a538a9b21","datavalue":{"value":"\\(k\\)-regular graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2322509$AF893F8B-0D48-43F0-B202-CEED35048C69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd227adb1378edbe90691dff18511cebed6b0036","datavalue":{"value":"diameter","type":"string"},"datatype":"string"},"type":"statement","id":"Q2322509$95F862FB-A48F-475F-B728-E854F91E5DF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9f046045effe4d96bd7d28b79a6e3ca55890681","datavalue":{"value":"Cayley graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2322509$D2E1E02D-553A-4A57-944A-5D02678D75CF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a45b400d22190ce8d9d8376830240adc5a55cd78","datavalue":{"value":{"entity-type":"item","numeric-id":367043,"id":"Q367043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2322509$E27DB8FD-3B6B-40D2-B3C6-415E22A269CF","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":"Q2322509$E50E6F99-AA24-4E42-93CB-6A71EA7D454E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3875a4dab80d0ef49fbc8c3062f39d3f18215d63","datavalue":{"value":"W2963298745","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2322509$F6FD5128-70BA-4870-B9B1-4690B6874170","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f67100ec38618c08d42fab382278824e8751f851","datavalue":{"value":"10.1007/S00493-017-3605-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2322509$4E01A5BA-DE84-4A53-8B2A-44AF7A7D6CCB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11ed444a55b40d8c8990b9a5993dfa350fe33672","datavalue":{"value":{"entity-type":"item","numeric-id":2197504,"id":"Q2197504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e144c5c0a883d5f4172fdd4b40e05e3177641fa","datavalue":{"value":{"amount":"+0.8294003009796143","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":"Q2322509$CC095D3C-1274-4332-A644-8E240C25812E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80afb2116658d98a82fd862731d2d581b65de218","datavalue":{"value":{"entity-type":"item","numeric-id":920107,"id":"Q920107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d34935c2da1db8742b110c5d7bc5245982b77a91","datavalue":{"value":{"amount":"+0.8247419595718384","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":"Q2322509$4CFF1FD6-A8A1-467E-86CA-0020A199CEE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3c384276a9a64c461f307c2ab50128f05ee6d15","datavalue":{"value":{"entity-type":"item","numeric-id":4390680,"id":"Q4390680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9121f45389882772530a1072474b079d452b729a","datavalue":{"value":{"amount":"+0.8092876672744751","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":"Q2322509$6F488528-E1A0-4F63-B27F-3762C375D0D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40a2f5dcd4e363805590e9955440dbfd02b1c406","datavalue":{"value":{"entity-type":"item","numeric-id":4400627,"id":"Q4400627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9121f45389882772530a1072474b079d452b729a","datavalue":{"value":{"amount":"+0.8092876672744751","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":"Q2322509$2AE4F92F-D83E-46F7-8D2B-AA2894BEAD75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3e52dcb490f1da90e9173c1c1d4c79cfe5bca02","datavalue":{"value":{"entity-type":"item","numeric-id":1333324,"id":"Q1333324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f3c8e873deaa3d15e197b0a7b193c079f60e7a7","datavalue":{"value":{"amount":"+0.8078768849372864","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":"Q2322509$89BF67ED-6985-4E99-A5FD-EB30E8615835","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2322509","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2322509"}}}}}