{"entities":{"Q1112844":{"pageid":1123593,"ns":120,"title":"Item:Q1112844","lastrevid":49230232,"modified":"2026-01-06T19:42:19Z","type":"item","id":"Q1112844","labels":{"en":{"language":"en","value":"Eigenvalues and expanders"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4079476"}},"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":"Q1112844$813DF7F1-D31B-45F0-8726-1B41D3030128","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8ae566b453ce596fde79e66c82aa4a1d37b6d914","datavalue":{"value":{"text":"Eigenvalues and expanders","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1112844$3AA39335-E30C-4E19-814F-B709563D1FCC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f6bf27dd5d4eb3e5a3310f28c4d1254ba880d83e","datavalue":{"value":"0661.05053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112844$753F2DF3-51ED-4418-94E1-25368BFCC132","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1dc774666ab0adbe7ca1498b6c60766cee648e69","datavalue":{"value":"10.1007/BF02579166","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112844$517E1707-D51E-4DEE-927C-D0E9412C0428","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":"Q1112844$BC7C0A2D-C167-49C0-AA75-97F745396448","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1112844$4F56B13B-6B23-4908-A400-63445D346598","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b2f02d78e662ae89f83bbaadeb27b92d2ab83b1e","datavalue":{"value":"Let \\(G=(V,E)\\) be a graph. An \\((n,d,c)\\)-expander is any bipartite graph on the sets of vertices \\(I\\) (inputs) and \\(O\\) (outputs), where \\(| I| =| O| =n\\), the maximal degree of vertices is \\(\\underline{d}\\), and   \\[ \\operatorname{card} \\{v\\in V\\mid vx\\in E\\text{ for some }x\\in X\\}\\geq [1+c(1- \\alpha /n)]\\cdot \\alpha, \\]   whenever \\(X\\subseteq I\\) and \\(| X| =\\alpha \\leq n/2\\).    In this paper it is shown that a regular bipartite graph is an expander if and only if the second largest eigenvalue of its adjacency matrix is well separated from the first. This enables one to generate expanders randomly and check efficiently their expanding properties. It also supplies an efficient algorithm for approximating the expanding properties of a graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112844$94033181-C183-4752-A974-A1A25127232C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5dd3db219aece07c365780bbac832e2c8e40fcde","datavalue":{"value":{"entity-type":"item","numeric-id":182235,"id":"Q182235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$8E21190F-D3E0-4945-AF42-A5E12EE560B7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"03c2e51ee9604fca084601a3da51bac330d9f1f7","datavalue":{"value":"05C48","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112844$A536B5E8-B5F9-4064-8E12-DC110F8A9A8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112844$05CB5EBE-BCE5-43A5-9177-F7039297FE02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112844$70E8C3AC-73D4-4B6D-8A19-F9A62F6715B4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"92d7e635021c53d46ce04560c876313ab3f8d0c0","datavalue":{"value":"4079476","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112844$A4D9A8CA-BB03-4C34-9435-90AED60DFDC9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4859cbf6c06a8763cec19c16c30583d96e46f1cd","datavalue":{"value":"eigenvalues of graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112844$DFAEC0C3-5CE9-444B-844B-B5E5E98B009E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8dc199a8f6d08f52ea1ca3384bdfe904a0e05ab8","datavalue":{"value":"regular bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112844$BF51D0F5-9418-421F-8FE5-08A6255148A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"527fd9bb73202f3ccbc2e98a6043eb9ea7b5dd2e","datavalue":{"value":"expander","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112844$F9446E82-CB43-4F06-BB77-5A428493E6BC","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"970c5293e1a4b8e72d3422381a447e0e8815fee4","datavalue":{"value":"Q97007656","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112844$ADD2AA6C-ECF4-4A60-B9C7-749A5B083674","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c61d0b4df374523ec5b59f8a7d6c81266878fe30","datavalue":{"value":{"entity-type":"item","numeric-id":178698,"id":"Q178698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$ECA94B30-DD9D-46E7-B7B3-DF9244DA134F","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":"Q1112844$DA004445-3DB9-4FC8-B0A5-7110A65D2F15","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"404ac0ea8a68165856263ebfce29e658b5c4631d","datavalue":{"value":{"entity-type":"item","numeric-id":1259903,"id":"Q1259903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$834F29B0-AB2A-424F-B0C6-AAC9038725C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b44ed555aed1fbc544de1802074fd0df13fb2c0","datavalue":{"value":{"entity-type":"item","numeric-id":1056541,"id":"Q1056541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$823DAC40-A9ED-4361-8DA7-11EACABCA744","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0df8c16fb6d4d3c861f57e0569695f268c7efadd","datavalue":{"value":{"entity-type":"item","numeric-id":800384,"id":"Q800384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$4F92B491-7CDA-4A41-87CE-40449292BD03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ab44c38234842ff7992ba00e47b9713793ea09","datavalue":{"value":{"entity-type":"item","numeric-id":3782808,"id":"Q3782808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$4B6DA9FD-CF06-490A-AE66-D4376A7503F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"126b782009523459e46f18be26a6feddeff272d9","datavalue":{"value":{"entity-type":"item","numeric-id":1165218,"id":"Q1165218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$BB76565F-012D-44AC-9121-F3AF5E850669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73065e1f99acfea60791aaa874a6b317e685fafe","datavalue":{"value":{"entity-type":"item","numeric-id":4770409,"id":"Q4770409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$13201696-2F02-4656-A4C5-EAEB64863B84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d62d37656d0227b756f89809dd6d6715edcdc07","datavalue":{"value":{"entity-type":"item","numeric-id":1162529,"id":"Q1162529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$1D92D0EC-84F6-4694-AEAA-27CB7C6D5D52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f34fb167d6b58149e4c07bc6f477f173f3d07b81","datavalue":{"value":{"entity-type":"item","numeric-id":1150630,"id":"Q1150630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$E4FF5E74-877D-47FE-A906-D67D6FF6C9D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8c370940f88e260ea9c75b2735c4be0912a6727","datavalue":{"value":{"entity-type":"item","numeric-id":3205169,"id":"Q3205169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$E06FBD94-E7B0-4AE4-94C8-BC6B6B749007","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b978709a654c254a17ab7ff5ba398a44d607d3c4","datavalue":{"value":{"entity-type":"item","numeric-id":5682350,"id":"Q5682350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$3BE79CC8-B534-4FC3-B7F1-CECA9D1CF254","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3009684eb7945556c56793ee792b9b228bab1d6","datavalue":{"value":{"entity-type":"item","numeric-id":1169017,"id":"Q1169017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$6A1BC74B-9844-4B64-930A-E6931FC39951","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8c3fb0ef3c7cbeb1b19e8a3632e3bd5fcfcda10","datavalue":{"value":{"entity-type":"item","numeric-id":1165257,"id":"Q1165257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$25DEA933-D19C-42B7-9208-A580512DBF9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60af8adb317254ad3ddefa749dfd41beebecb0eb","datavalue":{"value":{"entity-type":"item","numeric-id":3672658,"id":"Q3672658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$057C0EA5-8D4B-41D4-96FA-BEA3842FE3F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3868dbf56bd7e8d60550e371f494d2e9172a76b","datavalue":{"value":{"entity-type":"item","numeric-id":3959426,"id":"Q3959426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$74129B54-FAA4-46C6-A880-D9A25E3963AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbebee9b3fc070c9b73e7dd9a4fe191a6564e2bd","datavalue":{"value":{"entity-type":"item","numeric-id":4071451,"id":"Q4071451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$F5072D10-88CF-4224-A866-093297570D76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"269635745073557f0f4110dda846345f065df27b","datavalue":{"value":{"entity-type":"item","numeric-id":1156146,"id":"Q1156146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$F5A7C8B5-291C-4184-AD63-D69D59312ABC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4889dc56c7217c646e3175bcede965add157ef74","datavalue":{"value":{"entity-type":"item","numeric-id":4134003,"id":"Q4134003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$CB9AA014-6A11-4F24-BB19-1C68B1132612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a9a1e50831b9a5cd08a6a33132a8100644040a3","datavalue":{"value":{"entity-type":"item","numeric-id":3947137,"id":"Q3947137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$4D70F558-3A6F-44FF-A57C-99F6525661C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f99fc0604c1edf1b44f83c3b9538e477322458c","datavalue":{"value":{"entity-type":"item","numeric-id":4143082,"id":"Q4143082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$1E61E927-6FF0-4AF4-8A5C-98545883A7F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef981ceebc4057a833e8dba3d778d83171b14096","datavalue":{"value":{"entity-type":"item","numeric-id":5514782,"id":"Q5514782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$DE1B9770-F98F-4980-887E-145679BEF2A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9875551a1c7ec022c1eb43c87471680f90729f1","datavalue":{"value":{"entity-type":"item","numeric-id":3313788,"id":"Q3313788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$447E89A5-25CF-448D-B488-FB82B34626EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4448e7594c82f4f5731fc716996a6f3b13396420","datavalue":{"value":{"entity-type":"item","numeric-id":3216690,"id":"Q3216690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$AC7B0AE0-1785-4865-9D73-600D39F8137B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88400135b49f4397bf174ec3e94f5ee990b34d20","datavalue":{"value":{"entity-type":"item","numeric-id":1140426,"id":"Q1140426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$58E1AB35-4478-4AFB-8EDE-81D7B60DC6F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f580bff201ef3d7430922e0f1d5f7c995f4d70b0","datavalue":{"value":{"entity-type":"item","numeric-id":1236886,"id":"Q1236886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$9B6315FE-2F67-442D-B3BF-A3128B49A3F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d23aff6f5296b9a097ffb9b4764dc7e6eabd65bb","datavalue":{"value":{"entity-type":"item","numeric-id":770453,"id":"Q770453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112844$AE0FF753-6F67-45DA-91AD-C9BAF35E6B53","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8838c7ad52f4aa0c65991be6923c248e77b99704","datavalue":{"value":{"entity-type":"item","numeric-id":690667,"id":"Q690667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5d253b4608b99f13d5cd16f11390f7c5f12bbb3","datavalue":{"value":{"amount":"+0.8417675495147705","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":"Q1112844$6176302D-A973-47E8-8CFA-A8D606489487","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8785204c4b83a432667c1ec9ac4c884f441252b","datavalue":{"value":{"entity-type":"item","numeric-id":1098859,"id":"Q1098859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2a1803bf25d14553cb1f6506894a74386254cd9","datavalue":{"value":{"amount":"+0.8412944674491882","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":"Q1112844$66701F66-17C4-45D5-A392-01DDCDF63A62","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":"c3b79e2db8262a04fe68276cf6edc0d93d95faf8","datavalue":{"value":{"amount":"+0.8356066942214966","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":"Q1112844$0A5B82F1-494A-4B3C-9F56-0C210776A33E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70056fa6b8d707c7f2cb9832c8993163004f91cc","datavalue":{"value":{"entity-type":"item","numeric-id":4369891,"id":"Q4369891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"638817eff967f9c92687e6c15bbcee2d3fc0dbb6","datavalue":{"value":{"amount":"+0.8349457383155823","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":"Q1112844$B83EAB8C-09F6-45A5-AA34-9A9C6D5932C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54380656dc8e56fa14464a061513683236ee4347","datavalue":{"value":{"entity-type":"item","numeric-id":4273619,"id":"Q4273619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2a380e7bff5a51727b9250e3d4c39d52b4c3216","datavalue":{"value":{"amount":"+0.8340093493461609","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":"Q1112844$583ADBD0-81FA-4CF6-AC89-F2B624905B91","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1112844","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1112844"}}}}}