{"entities":{"Q2226628":{"pageid":2237371,"ns":120,"title":"Item:Q2226628","lastrevid":82669094,"modified":"2026-05-06T21:27:27Z","type":"item","id":"Q2226628","labels":{"en":{"language":"en","value":"Expander graphs -- both local and global"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7307767"}},"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":"Q2226628$1069AE59-096F-4207-90A4-F437B302608F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"29b9897c663cb5e9ff31ee0b93f39012bbe0a4c9","datavalue":{"value":{"text":"Expander graphs -- both local and global","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2226628$899C0170-43BA-4566-AE1D-F60720C2C1B7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8d07c3095248bc2284960fa0ff602cd618d216a1","datavalue":{"value":"1474.05237","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2226628$4A7AC363-585C-47C2-B3D8-29F414FC0481","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$91617BB9-8CD5-4568-B834-B0791DA5D459","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":"Q2226628$43049C4F-3BCE-4F6F-BE8D-BA1C51CCC72B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3972cc89c33d20406d53dd6cfa3d6bd85b48f15b","datavalue":{"value":{"time":"+2021-02-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2226628$31437E25-D30B-4CAF-8479-3DD0B0669EA6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5498cb9ab939c177baaf18a0c7c2b6d3992e36d6","datavalue":{"value":"https://arxiv.org/abs/1812.11558","type":"string"},"datatype":"url"},"type":"statement","id":"Q2226628$6F5BF320-6E90-418D-B1CE-CEBFE6ADEBF3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"be265cd691667469542a02273e32ceda52c6e871","datavalue":{"value":"For positive integers \\(a>b\\), an \\((a,b)\\)-graph \\(G=(V,E)\\) is an \\(a\\)-regular graph in which for every \\(v\\in V\\) the link \\(G_{v}\\), i.e. the subgraph induced by the set of neighbours of \\(v\\), is \\(b\\)-regular. We are interested in the expansion properties of \\((a,b)\\)-graphs, noting that for a number of the many applications of expander graphs (e.g. in PCP theory on computer science) we want not only the basic graph \\(G\\) to have good expansion properties but also the link graphs \\(G_{v}\\). (A random regular graph is, with probability tending to 1 a good expander in a suitable sense: but \\(G_{v}\\) is typically an anticlique so not an expander.)  \\par The paper under review constructs two families of \\((a,b)\\)-graphs where both \\(G\\) and the links \\(G_{v}\\) have good expansion properties. The authors consider the second eigenvalue \\(\\lambda_{2}\\) of the graph \\(G\\), where it is well known that comparatively small values of \\(\\lambda_{2}\\) correspond to good expansion properties. An initial result, based on a result of \\textit{N. Alon} and \\textit{R. B. Boppana} [Combinatorica 7, 1--22 (1987; Zbl 0631.68041)], is that the second eigenvalue of an \\((a,b)\\)-graph is at least \\(b+2\\sqrt{a-b-1} +o(1)\\). This bound is tight. However there is a degree of \\lq trade-off\\rq\\, between good expansion of \\(G_{v}\\) and \\(G\\). in that as the quality of the expansion in \\(G_{v}\\) increases the gap between the second eigenvalue of \\(G\\) and the lower bound just mentioned increases. A key role in constructing the graphs is played by the so-called polygraph construction, which (crudely speaking) transforms high-girth expanders into \\((a,b)\\)-graphs. \\par This work fits into the active research topic of high-dimensional expansion, and there is discussion of links with this area in Section 5 of the paper. Work is still proceeding in this area: see, for example, the recent preprint of \\textit{E. Friedgut} and \\textit{Y. Iluz} [``Hyper-regular graphs and high dimensional expanders'', Preprint, \\url{arxiv:2010.03829}] in which related results are given and relevant literature surveyed. Some other classes of \\((a,b)\\)-regular graphs, based on regular triangulations of surfaces and tensor products of graphs. A number of open problems are also listed. Including quantifying more precisely the trade-off mentioned above.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2226628$467D4B01-EC6D-4C06-ABEC-D92131A103C4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"03c2e51ee9604fca084601a3da51bac330d9f1f7","datavalue":{"value":"05C48","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2226628$CBFD4FC0-9598-45D1-BC0B-68C63836EABD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5b5126101ab4505674efcb5789319f63910d08f","datavalue":{"value":"05C81","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2226628$F8B84482-9898-4415-88B4-6CF62F86C767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e669b60521e14398c1f2263792cea32c3a9da254","datavalue":{"value":"05E45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2226628$3F55D4CF-5995-4FF0-AF9F-B8BE109C5432","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2226628$C6FC4051-6D70-4031-A5E0-1AB03E0E8598","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4d54ff0a43810f1e4d642ebe4c4b17134bf37047","datavalue":{"value":"7307767","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2226628$276F3397-8BF5-4394-BED1-FC80AEECF5A7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7eb7ce57864bad79eb8b1130037c18cbe7109e9b","datavalue":{"value":"expander graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2226628$699870BC-A94D-4356-91EF-4F39365F36EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4afa0f1b580453e6753762a982c5cf61b70cf45e","datavalue":{"value":"\\((a,b)\\)-graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2226628$22DAD5C4-2198-4180-995C-8CB3638D2E8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61168a25899535da93fc9f78ca35ae287b6f2ac4","datavalue":{"value":"higher dimensional expander","type":"string"},"datatype":"string"},"type":"statement","id":"Q2226628$5E3967F9-B1EB-498E-8B57-A8768B92E1A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58c34cfe223316591f56cdf41b66e4b6aa918f66","datavalue":{"value":"polygraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2226628$F32DD0F4-28B5-4CBE-9870-9BC1DF83F78A","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":"Q2226628$965D4192-FFE4-47F0-96DD-E0F96F141F41","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":"Q2226628$64B1AEE8-5BC9-4323-8BC8-162EA15E65BB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8c851204184e0554724fccd2b9ee6794bbfb659c","datavalue":{"value":"W3040128980","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2226628$C2963110-87AB-4844-B7A5-329938F364D8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f41391d8e0f4679232fc8f2740b70dfb3bf0d1c","datavalue":{"value":{"entity-type":"item","numeric-id":3502774,"id":"Q3502774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$D7AB679C-0364-4C16-B204-2B6D930DB0AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7103e47bed67b00b43bcb8b24168e6f361a149c","datavalue":{"value":{"entity-type":"item","numeric-id":2500999,"id":"Q2500999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$983FB426-9B69-4625-949C-584E04C6295A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65a20ee4f69bc8d382f3351260f31c5783a75a23","datavalue":{"value":{"entity-type":"item","numeric-id":2327965,"id":"Q2327965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$E0181D4C-0EE4-40D3-A4EF-CDC96BCF5E50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"056e73845d3a0efb6188a6f2d729eda24b078f22","datavalue":{"value":{"entity-type":"item","numeric-id":4787524,"id":"Q4787524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$ABD3E10E-0394-4B9D-9C26-D446C581BB5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a3b271bab4a2024771ce8a55ce6efe0db39ea46","datavalue":{"value":{"entity-type":"item","numeric-id":4284105,"id":"Q4284105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$A0AE3851-400E-4E5B-98FE-FB32296E6211","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"004d94771912c06249a49820e2f302198b4b4656","datavalue":{"value":{"entity-type":"item","numeric-id":2560907,"id":"Q2560907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$EF451D2D-9331-490D-902B-5FADFA30EBDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfb34749ef4f918ec7bbe2f310a9919a523aa3e2","datavalue":{"value":{"entity-type":"item","numeric-id":2414518,"id":"Q2414518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$F20562DF-5953-46EE-8C9B-EEBB75944B39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca4be033dc1e037b43c1538205386964bc6ef38a","datavalue":{"value":{"entity-type":"item","numeric-id":3514498,"id":"Q3514498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$6C22F37F-16A7-4377-8457-FF34EC8220C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b94bda823b6d43ecf5a74b2c47397fd871eba1d2","datavalue":{"value":{"entity-type":"item","numeric-id":4638053,"id":"Q4638053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$FC29485A-5256-4043-B784-8A7EF92CB8B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23a433de57d1e656b82b5a7b3277b8d3b77d7d53","datavalue":{"value":{"entity-type":"item","numeric-id":1606019,"id":"Q1606019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$7FA7A59B-A627-498F-92AE-4383AC654A74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"596d2535e492e057f8d8d69368bde8f71526006b","datavalue":{"value":{"entity-type":"item","numeric-id":2216740,"id":"Q2216740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$49F36C87-37DD-415D-A61F-87DAFE8BFFEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c40e18b1c972d5ca889339bb2a9731c4159a5fd","datavalue":{"value":{"entity-type":"item","numeric-id":814142,"id":"Q814142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$775E8AC8-95B8-46DF-87BC-D71EBD848077","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d85b8332694a05123db301464a4170edcfaf7984","datavalue":{"value":{"entity-type":"item","numeric-id":2352911,"id":"Q2352911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$BABD0149-C92C-4945-B513-C6C03F2F6582","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a94f544906c4f817e549bc036cac60ab529df26","datavalue":{"value":{"entity-type":"item","numeric-id":1170776,"id":"Q1170776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$63DE76BC-6D10-400A-895E-466B37F93B8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"807f1eca3babd69e4aa6877349d621d77338ff27","datavalue":{"value":{"entity-type":"item","numeric-id":585527,"id":"Q585527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$1B644E36-CC47-4BAC-BCCA-AB705449283B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cf47bd968b2f09216201fd5a5fb92ec17877967","datavalue":{"value":{"entity-type":"item","numeric-id":2361120,"id":"Q2361120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$AC8B367D-8E0B-4056-9D8E-4FC81CD2FD94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fc5dfeba65ab9db53e5db6c263b61ba030674f5","datavalue":{"value":{"entity-type":"item","numeric-id":503204,"id":"Q503204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$6ECA1109-67A8-4606-9177-2FAEE60285A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea2d83019b38794c8170ffc76d712fab2bc9e99c","datavalue":{"value":{"entity-type":"item","numeric-id":3430210,"id":"Q3430210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$5F29C4CE-2030-4127-8EF1-A1ED737F0A11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fecf589eb8bd2af857fa862c75da3f28d6956757","datavalue":{"value":{"entity-type":"item","numeric-id":757426,"id":"Q757426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$3A917D7C-7B5B-48AA-AB2F-512F6D589D70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"931a424c7c82eb929f664f0a0d1ddb723900b67d","datavalue":{"value":{"entity-type":"item","numeric-id":3286073,"id":"Q3286073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2226628$A9F43B8F-B260-4781-A721-58AEE5CC3DD9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"189c7931395550f2c04410a1660bd05910febb68","datavalue":{"value":"10.1007/S00493-019-4127-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2226628$1D4234EE-A0FF-47F9-96D3-38F3AD0D7D5B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6be927d18b29eb729feb5876932ff9f541a7824b","datavalue":{"value":{"entity-type":"item","numeric-id":4230352,"id":"Q4230352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3280d7cfa888be5ba9415013cd4dcbf37e55a15","datavalue":{"value":{"amount":"+0.7786835432052612","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":"Q2226628$722FDCFD-5CEA-4172-B197-27C7837E4310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9349a8b493f4c7a1f38e051963923f2edb304524","datavalue":{"value":{"entity-type":"item","numeric-id":4273623,"id":"Q4273623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e353092771f70e48b300e6869f0687e6271ab71b","datavalue":{"value":{"amount":"+0.7737601399421692","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":"Q2226628$4EB7056F-AC60-4E4D-93A3-2B7D75F0E430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07e24da77f153f393f14138f8a1d2662e4cb0ca1","datavalue":{"value":{"entity-type":"item","numeric-id":4676810,"id":"Q4676810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0fda43e95985569d27351dbc00c18918fc363cf","datavalue":{"value":{"amount":"+0.7692342400550842","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":"Q2226628$26D31C19-46C3-46E3-B08A-FA63CEC44DAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e1a8078f92d25c775d8203b709f1ec5ab17480d","datavalue":{"value":{"entity-type":"item","numeric-id":2236654,"id":"Q2236654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c46263d48a3ead8bb998bae99e9e18ef3e359ad","datavalue":{"value":{"amount":"+0.7638522386550903","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":"Q2226628$8FB96D00-5913-40D5-A9F2-1A799DDB3446","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e3b5239bb462f5f1da3ef4a1ca21acf95d3c57a","datavalue":{"value":{"entity-type":"item","numeric-id":3728028,"id":"Q3728028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a64dfb6fb72396af974539b947789b8a8458875f","datavalue":{"value":{"amount":"+0.7627996206283569","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":"Q2226628$7138B221-9E11-4D31-AC8F-2A10A854CDED","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Expander graphs -- both local and global (scientific article; zbMATH DE number 7307767)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Expander_graphs_--_both_local_and_global_(scientific_article;_zbMATH_DE_number_7307767)"}}}}}