{"entities":{"Q2568494":{"pageid":2579237,"ns":120,"title":"Item:Q2568494","lastrevid":48566554,"modified":"2026-01-05T05:57:33Z","type":"item","id":"Q2568494","labels":{"en":{"language":"en","value":"Explicit bounded-degree unique-neighbor concentrators"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2213255"}},"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":"Q2568494$385B7EAB-AA05-4E56-AD80-1EAE40DD450B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4f58a7d5299ba5ed1098b8edb963a659b9f0dbe7","datavalue":{"value":{"text":"Explicit bounded-degree unique-neighbor concentrators","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2568494$5B24FE19-C2D4-412E-B84F-E69BDB78C519","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"71bd2ec949157093034097e0830ca25db78173b7","datavalue":{"value":"1089.05034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2568494$A161A0A7-EDBB-4259-AC95-55215F121901","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"71da963f870a561d621046b2c1303bd2c34f0294","datavalue":{"value":{"entity-type":"item","numeric-id":1872890,"id":"Q1872890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2568494$4FFF17F1-FC5D-458B-B4A7-EA2260ADC20D","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":"Q2568494$2E056CE5-C387-492E-B299-27D3397E83B4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e2100ced5bb0fc7a2f2d75de03e2412195897a08","datavalue":{"value":{"time":"+2006-06-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2568494$6D5B207B-6883-409B-BF48-B75945416C11","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"734f96472ecc5dbaaafa92887a3a8aaa04711871","datavalue":{"value":"A bipartite graph \\((I, O, E)\\), where \\(|O| \\leq (1-c)|I|\\) and \\(c >0\\) is an \\((\\alpha, \\epsilon)\\)-unique-neighbor concentrator, if for each subset \\(S\\) of \\(I\\) such that \\(|S| \\leq \\alpha |I|\\), there are at least \\(\\epsilon |S|\\) vertices of \\(O\\) that are adjacent to exactly one vertex of \\(S\\). Unique-neighbor concentrators were used in the construction of self-routing networks, see \\textit{S. Arora, F. T. Leighton and B. M. Maggs} [SIAM J. Comput. 25, No. 3, 600--625 (1996; Zbl 0852.68004)] (note it is referred incorrectly in the paper), and \\textit{N. Pippenger} [J. Comput. Syst. Sci. 52, No. 1, 53--60 (1996; Zbl 0846.68006)]. The author shows that there is an infinite family of bounded-degree \\((\\alpha, \\epsilon)\\)-unique-neighbor concentrators for some \\(\\alpha > 0\\) and \\(\\epsilon > 0\\). The usual method of using the second largest eigenvalue breaks down, so the author comes up with a clever product of a fixed graph \\(H\\) on 44 vertices by a 44-regular Ramanujan graph \\(\\Lambda\\). Indeed, \\(\\Lambda\\) is any element of an infinite family constructed by \\textit{A. Lubotzky, R. Phillips and P. Sarnak} [Combinatorica 8, No. 3, 261--277 (1988; Zbl 0661.05035)]. In order to show that the product is a unique-neighbor concentrator, some properties of the graph \\(\\Lambda\\) are recalled, these were established by the second eigenvalue method, see \\textit{N. Kahale} [J. Assoc. Comput. Mach. 42, No. 5, 1091--1106 (1995; Zbl 0885.68117)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2568494$E8CB1B23-6681-45B3-AD62-4B182421D13A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"73456c3353ea197c90c73d5f0daaf3b9d502d311","datavalue":{"value":{"entity-type":"item","numeric-id":235726,"id":"Q235726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2568494$08520312-BDE9-49AA-A29A-59E268C56C21","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2568494$E173ED69-E9F0-4123-B446-0F1BB6267DD0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c42d977531a74ca3862a5b0e7f9f018f5298b252","datavalue":{"value":"2213255","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2568494$35972872-87F9-40CE-84C9-DCA7936CB34B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89b097773537f6be57565fe94a10dc3fe9a9882f","datavalue":{"value":"expanders","type":"string"},"datatype":"string"},"type":"statement","id":"Q2568494$1650753E-F8A5-42F2-B32A-1FC5987A823F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c7548a91644a0edc61c6f22ea505e9b44f6e124","datavalue":{"value":"Ramanujan graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2568494$4B24FC6B-6520-4E67-A22F-84AC0D2A2339","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":"Q2568494$9EDD49C5-8C20-421A-A4E2-BFA9CD9F448F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cf156d05f391afa073ca2c149e190ecf8321ef39","datavalue":{"value":"https://doi.org/10.1007/s00493-005-0022-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q2568494$4B2FEC9B-8EFC-4CC7-AE2C-5BCCC8024F20","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4a79bab0745f55e8dea959f7ea09cdf02cf749bb","datavalue":{"value":"W2063638759","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2568494$13B7E37E-82F1-46BE-956A-E214C8F81CD4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"50cf52cf1ce4ed7b7c49a01fb90483e9aae67dbc","datavalue":{"value":"10.1007/S00493-005-0022-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2568494$088A7A7F-339F-4E0F-B263-6E8EE2958871","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a66aac2737961812a616d63d94270588d4a2d646","datavalue":{"value":{"entity-type":"item","numeric-id":1842573,"id":"Q1842573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b8860f3c797762e62bc579b3458df2c62acc2be","datavalue":{"value":{"amount":"+0.784553050994873","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":"Q2568494$C642AF31-C70A-4E5E-9158-DB6665D36717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8184be22d8f89548e1228e9704133b501b91702","datavalue":{"value":{"entity-type":"item","numeric-id":3216690,"id":"Q3216690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3333193d06cf39ddcb605fed61ba402d1b479dd","datavalue":{"value":{"amount":"+0.7678526639938354","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":"Q2568494$5D361545-444B-4623-880C-A294FE0582DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6242c444746e674ed1323e0885e0b693cfec203","datavalue":{"value":{"entity-type":"item","numeric-id":920104,"id":"Q920104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d6c67fc568cda952c29eb73ed2a9591daf9738d","datavalue":{"value":{"amount":"+0.7480635643005371","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":"Q2568494$1F96FBEC-88ED-4004-A963-FE53091E59A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa2b79c03d864e3be94afa14637373acb15a2269","datavalue":{"value":{"entity-type":"item","numeric-id":3782808,"id":"Q3782808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06c82013871688fee50b444cdcbc8bdc383e7c9e","datavalue":{"value":{"amount":"+0.7375115752220154","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":"Q2568494$A481CADA-4E3B-4D8D-9B14-D543C3A5A85B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d433bd08c6caf59dbbef2cf286e4391e0fd155d","datavalue":{"value":{"entity-type":"item","numeric-id":2115273,"id":"Q2115273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d605f4ad9bda8fd97deb4b1327e32b18e05c850f","datavalue":{"value":{"amount":"+0.7261451482772827","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":"Q2568494$2CB85A50-E01D-4D04-B564-ADACBB006B2B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2568494","badges":[]}}}}}