{"entities":{"Q2381125":{"pageid":2391868,"ns":120,"title":"Item:Q2381125","lastrevid":57881976,"modified":"2026-04-02T22:39:02Z","type":"item","id":"Q2381125","labels":{"en":{"language":"en","value":"Expanding graphs, Ramanujan graphs, and 1-factor perturbations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5195199"}},"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":"Q2381125$BF41A6DF-394A-4C90-A80B-B44EB354F872","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9e5d8ba46b3776555f34af7622f62b3d05eae546","datavalue":{"value":{"text":"Expanding graphs, Ramanujan graphs, and 1-factor perturbations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2381125$A116944B-22C8-46C3-8B4E-2CF47F0F83E2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c07d7b4da260eaf1f0d38f5c5ce5006885596bef","datavalue":{"value":"1130.05038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2381125$3FCF6239-BC40-4BD7-99B4-E0F5FF6D86BE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8e1b9b74408e8f75be17d218f4fd787c89d61840","datavalue":{"value":{"entity-type":"item","numeric-id":633541,"id":"Q633541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381125$E93AC88C-B62F-4AD6-8E16-1C6D87B01524","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8e7e4ea382cc5c316584ec3e6287a52ed7a9f3a7","datavalue":{"value":{"entity-type":"item","numeric-id":1063208,"id":"Q1063208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381125$49425F8B-05AB-47A4-A8EA-017F56A29BF8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c4f16ddc5cdb18d4f4fb3ee6d704d6609c3404ba","datavalue":{"value":{"entity-type":"item","numeric-id":223802,"id":"Q223802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381125$8936A101-712B-406D-8A62-D2BD490D7F64","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6e1fa8a744de31aab5e0066db3d2fb556fbdf6da","datavalue":{"value":{"time":"+2007-09-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2381125$3F6EC0B3-0966-42E1-B1B2-181DE6993BC5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8f15ace262ce41dd14831203507f2a7ba1de8e52","datavalue":{"value":"https://arxiv.org/abs/math/0503330","type":"string"},"datatype":"url"},"type":"statement","id":"Q2381125$8F1C9841-6D15-4CAD-B9BE-997977DA1CBF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0bb8dd58cfa872531e6be8b55f7972886d9cf8e2","datavalue":{"value":"This note gives a procedure for constructing infinite sequences \\((X_i)_{i \\in I}\\) of \\(k\\)-regular connected simple finite graphs with increasing vertex sizes such that inf\\(_{i \\in I}(k - \\lambda _1(X_i))\\) is strictly positive, that is, expanders of degree \\(k\\). Here \\(\\lambda _0(X_i) \\geq \\lambda _1(X_i) \\geq \\cdots \\geq \\lambda _{n-1}(X_i)\\) are the eigenvalues of the adjacency matrix of \\(X_i\\). For \\(p\\) and \\(q\\) distinct odd primes, the subgroup \\(S_{p,q}\\) of PGL\\(_2(q)\\) is defined and the graph \\(X^{p,q}\\) is specified as the Cayley graph of PGL\\(_2(q)\\) with respect to \\(S_{p,q}\\) when \\(p\\) is not a square modulo \\(q\\). \\(X_{p,q}\\) turns out to be a \\((p+1)\\)-regular bipartite connected Ramanujan graph. The desired expanders are obtained by considering \\(X^{p,q}-F\\) for bipartite \\(X^{p,q}\\), where \\(F\\) is a perfect matching in the graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2381125$09ED011A-4DF3-49E3-AD38-B509A2E5E27E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf8837edd6f8e1022b15c3d0748921656854f53e","datavalue":{"value":{"entity-type":"item","numeric-id":1811077,"id":"Q1811077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381125$CD04C6F5-1456-43B1-A689-9C5F69EB50C1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2381125$2CAC3EDF-2723-4C0A-A29D-EB7D9EDF2B50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2381125$0B698F12-447E-4C5B-A8A9-DAEB544C9A9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2381125$A55D03B1-ACC4-4072-9976-DF1728FDB971","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3090d503d2b0af7e2a95c58c1736e8196d89c4ef","datavalue":{"value":"5195199","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2381125$F3385F44-B270-4EB6-A8D0-05E8199B4E11","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2381125$A228992E-8E16-442D-BF57-CAF1EC8FE917","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"527fd9bb73202f3ccbc2e98a6043eb9ea7b5dd2e","datavalue":{"value":"expander","type":"string"},"datatype":"string"},"type":"statement","id":"Q2381125$6E84C8C1-23A4-4A9B-BA6F-214CB5B6FEFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c44271d1bcae7fcfcfaabee16b248e4b8116d1f","datavalue":{"value":"graph eigenvalue","type":"string"},"datatype":"string"},"type":"statement","id":"Q2381125$91BE94F9-3025-47A2-9ECC-8658B29A99E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2381125$EB5CCA37-270F-4CE4-A741-A1049E974E4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"789cbdbf063f2e698cf3f08d0ca8ca7bcf372197","datavalue":{"value":"Ramanujan graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2381125$B56E47B6-74D7-41D7-B826-9ADA77C59B45","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":"Q2381125$7CEB616C-6F75-4025-863C-2591F7CDA24B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5002dd115604ab58e1172d4628f929e7c0324fa","datavalue":{"value":{"entity-type":"item","numeric-id":2887618,"id":"Q2887618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c462786e3c685e208b7f7714be477ba6f0f6e3fb","datavalue":{"value":{"amount":"+0.90013117","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2381125$902C9305-2BAC-4BC6-A05E-EFCAEFB4932C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"007e524c0091f16791ea80acc5b655f948beb990","datavalue":{"value":{"entity-type":"item","numeric-id":2291671,"id":"Q2291671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca0b80afca5cb2438b333068ba62510b887c12cf","datavalue":{"value":{"amount":"+0.89591837","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2381125$699DD42B-98FB-41C2-8EE9-74A24C2A017E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41c6b126a8c42ff86d54bef99b592d0e66442605","datavalue":{"value":{"entity-type":"item","numeric-id":4486236,"id":"Q4486236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e292d9cc885670fd92a055929c8548583be0508","datavalue":{"value":{"amount":"+0.8948665","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2381125$C173192F-1F98-46E1-9023-E5CDFF1C09DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e3ec9d89e892528c6338d788800b73cf549c477","datavalue":{"value":{"entity-type":"item","numeric-id":1003586,"id":"Q1003586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6a8aea3080c6f8d3f8f964fcbb4bf698bf74bc9","datavalue":{"value":{"amount":"+0.8941148","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2381125$3C205375-BCB8-4311-92FF-5F6B345185BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f3188598b261b6ec54d55e7803dc38efa3e0783","datavalue":{"value":{"entity-type":"item","numeric-id":1906672,"id":"Q1906672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ea3b1077df6a78aa0754bc9f927e2564b2704e6","datavalue":{"value":{"amount":"+0.8899744","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2381125$FA5AB9C0-46DF-4EBB-93ED-6DDBA6AF1399","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":"16ef7326b3ffe1c98a0fa40d73ad528f6e09a9b5","datavalue":{"value":{"amount":"+0.8894209","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2381125$AD2B69EB-B23C-48AB-BDC3-7D9A1F86ECBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a551a85d8c8b3037ce30e8efa85a94dab1851b07","datavalue":{"value":{"entity-type":"item","numeric-id":5900217,"id":"Q5900217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a938f017a3b32c90313b50756357b2663f3009b7","datavalue":{"value":{"amount":"+0.88932556","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2381125$06F22E69-939F-4244-A6B5-1634A6B82982","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"582cf5a3f0ab7562ab3ca330097bdda6579d9dc8","datavalue":{"value":{"entity-type":"item","numeric-id":5892544,"id":"Q5892544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a938f017a3b32c90313b50756357b2663f3009b7","datavalue":{"value":{"amount":"+0.88932556","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2381125$6E81A488-3123-40F9-8982-0E1E125384FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10d1566f19ec942f24ea8f619b996775de5ed7aa","datavalue":{"value":{"entity-type":"item","numeric-id":5894137,"id":"Q5894137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a938f017a3b32c90313b50756357b2663f3009b7","datavalue":{"value":{"amount":"+0.88932556","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2381125$C7ADE56B-804F-4028-B2A8-858558ABD5C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"460f75339c89fc070506b07d90e54681db2f415e","datavalue":{"value":{"entity-type":"item","numeric-id":5156337,"id":"Q5156337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cc4663bb4b64ee4b0e725cedfcde038aed9dcb0","datavalue":{"value":{"amount":"+0.88867664","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2381125$3DE7897A-A5D3-4CFD-82EE-B594F8C3DB15","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2381125","badges":[]}}}}}