{"entities":{"Q2684887":{"pageid":2695630,"ns":120,"title":"Item:Q2684887","lastrevid":56793615,"modified":"2026-03-23T15:12:04Z","type":"item","id":"Q2684887","labels":{"en":{"language":"en","value":"Finding large expanders in graphs: from topological minors to induced subgraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7655012"}},"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":"Q2684887$5CC9A44B-2CF2-4C44-B2C2-CFCC2E5D2B57","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"daf1246933087ed63cf5ddfae16acd67c4bb6ef6","datavalue":{"value":{"text":"Finding large expanders in graphs: from topological minors to induced subgraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2684887$6DFFE537-2E16-4112-8800-D6FB1D2283E1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c0356f05180fc0418f8235d1e0bb95b0d7618a73","datavalue":{"value":"10.37236/10859","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684887$12A17751-C5E6-47FC-B67B-8B3049ED75C5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eeb97d1c09f6a34a750722200a2da0018e7823ae","datavalue":{"value":{"entity-type":"item","numeric-id":2099810,"id":"Q2099810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684887$DE41E8DC-FD84-4563-BF5C-51CF0D90CD42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"52794ea33618a13587baa1033cd1b0861d6409cf","datavalue":{"value":{"entity-type":"item","numeric-id":247201,"id":"Q247201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684887$67935245-61C1-4F36-A656-897F215F0A6F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684887$BCE4BBAF-C99A-450B-876D-059E46A6FC0E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e2c66fb7aab39afe15eb7d8af0079ba7f34f4d9d","datavalue":{"value":{"time":"+2023-02-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2684887$ED6C4145-A610-4706-A52D-CE6B79A5B2B4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"df62016dad61f75d9cdff286b18d9dd4552c62d8","datavalue":{"value":"https://arxiv.org/abs/2012.15722","type":"string"},"datatype":"url"},"type":"statement","id":"Q2684887$884784CF-EE86-4634-809C-85EDCB0B505D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ef3cc388e372818b1af36434a3ae22a76cd0dfc0","datavalue":{"value":"Summary: In this paper, we consider a structural and geometric property of graphs, namely the presence of large expanders. The problem of finding such structures was first considered by \\textit{M. Krivelevich} [SIAM J. Discrete Math. 32, No. 1, 611--623 (2018; Zbl 1381.05040)]. Here, we show that the problem of finding a large induced subgraph that is an expander can be reduced to the simpler problem of finding a large topological minor that is an expander. Our proof is constructive, which is helpful in an algorithmic setting.  We also show that every large subgraph of an expander graph contains a large subgraph which is itself an expander.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2684887$4CC22B1F-3869-4B3F-B511-86B429E4B49A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"03c2e51ee9604fca084601a3da51bac330d9f1f7","datavalue":{"value":"05C48","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684887$3A04B499-291D-4ADD-A229-EA4E1F2604F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49261cbbd2f3b64e072aca4630c2592536037a47","datavalue":{"value":"05C83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684887$9060DDDD-113E-43A3-B8D5-2545B4D17625","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5b5126101ab4505674efcb5789319f63910d08f","datavalue":{"value":"05C81","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684887$A272BAA7-59EF-4FA6-9816-481E4F940287","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f69528cea35ad35a0f81b1419c5bdc2905d27952","datavalue":{"value":"60F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684887$412000C9-C123-45A4-BB11-654EC2D58FFE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"53a52fc2124a42ade16f9853e4f37a5787408b0a","datavalue":{"value":"7655012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684887$25169248-0BF4-4D78-8CC4-5C474341B37D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29f90cd83dad24fc82d0e60664cc695c283ac5bf","datavalue":{"value":"random walk","type":"string"},"datatype":"string"},"type":"statement","id":"Q2684887$5AC627C2-B66B-4998-90B0-58AFBA2C3A42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"65320f434ec1b814502a6be87b79dc0883cea9df","datavalue":{"value":"linear sized expander subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2684887$94D2793E-F9FC-4C09-9738-55A9A9FB83BD","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":"Q2684887$977C75F9-8CF5-4842-95B8-589B9F5A1A0A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0844abbbb5ba65b51478bde61f56aa9f713d0d67","datavalue":{"value":"W3117223236","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684887$4C272487-751F-4923-915F-A725F2BDC874","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"198bba29d7d66df862afcb4d6a84c2940b4b2072","datavalue":{"value":{"entity-type":"item","numeric-id":1112844,"id":"Q1112844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684887$8FD03EDF-B53C-4754-A484-D88940026404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c69385ba93956fbc98e8023194f1895165a90a52","datavalue":{"value":{"entity-type":"item","numeric-id":5039232,"id":"Q5039232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684887$777B6685-91BF-4E42-BE9E-E542EEB3A72A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e07a86ac8a4147f4de4bb1b8e5c31b34b9184f5","datavalue":{"value":{"entity-type":"item","numeric-id":5614192,"id":"Q5614192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684887$5DBA4382-C35C-42F1-A343-5A61F0C94BE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4add356b145271b9757e772351bd3d4c25cdffd6","datavalue":{"value":{"entity-type":"item","numeric-id":4210091,"id":"Q4210091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684887$1D4BF68E-E736-4A09-A60E-B9BE08A722B6","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":"Q2684887$71CB2EE8-2128-44A8-BD60-E99F53A51D78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8802396d6d653062718814dd3b9ff34b6644ed58","datavalue":{"value":{"entity-type":"item","numeric-id":3583579,"id":"Q3583579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684887$84DF70C6-C661-4252-9A68-B9EADC24DC1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46483d37e0c179fdb9ca58c9dd807ac007a98b32","datavalue":{"value":{"entity-type":"item","numeric-id":4604650,"id":"Q4604650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684887$385601C5-B4F7-4B69-A677-FC979EEDF509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ded816bf6b422b71100e12d1c7a547080649d9fb","datavalue":{"value":{"entity-type":"item","numeric-id":5149169,"id":"Q5149169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684887$87B27140-6417-47F8-95B7-6D39EBA26FAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"890445470b074cf37229cab0ca8ed62a36463c02","datavalue":{"value":{"entity-type":"item","numeric-id":5051457,"id":"Q5051457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684887$ABAE7DF4-AA73-4F60-84E5-E50C2B3B285B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"771bd9858c553f4313a10d72a7a9edfc5d49cd65","datavalue":{"value":{"entity-type":"item","numeric-id":5175038,"id":"Q5175038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684887$25D7A50D-9699-4E01-A5BE-9976AC6CAB12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c74df52623076088cc0e296ef1a793335b3b1a59","datavalue":{"value":{"entity-type":"item","numeric-id":313429,"id":"Q313429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684887$10F73906-AAFE-4B4D-AFBA-4C7B85B79D79","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"65a7e1d1dc72bc6c2a0c7e65d18d09729d9d5a28","datavalue":{"value":"bafkreigch7rjum2dj6apfltrerfy3nzfzu6g7nsxvnlhnazbmm2pntnu34","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684887$F63FA074-0E7F-4451-BC13-A78D7E3B3D7A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f400927364bcd901e9517ec1d929817f76032e66","datavalue":{"value":{"entity-type":"item","numeric-id":5149169,"id":"Q5149169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f042b80f0ebba22f97631bddb6f5b2f44ddb0945","datavalue":{"value":{"amount":"+0.7974060773849487","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":"Q2684887$137872FE-3953-4640-AFFC-900C92B9DF98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d7d6e9fcaccd287e00af48c774a41adfb17065c","datavalue":{"value":{"entity-type":"item","numeric-id":4604650,"id":"Q4604650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f58ec2dc4a92b340e85aec45b9937f776dcd735","datavalue":{"value":{"amount":"+0.7829815149307251","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":"Q2684887$9023360A-39A4-46AA-BB83-4978E0A8C43B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4f3892fdfb09ba1e7e85d3a91e6d422ab1d68ea","datavalue":{"value":{"entity-type":"item","numeric-id":1028516,"id":"Q1028516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5646617c3bf58b306c816d1d1809eff7ed6e1253","datavalue":{"value":{"amount":"+0.7432140707969666","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":"Q2684887$E85A57BA-61E9-4B0E-8838-63CA29E8CB6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cacb6eb5df3c715d62b5ae22aa481a01ef6f3ac2","datavalue":{"value":{"entity-type":"item","numeric-id":4575817,"id":"Q4575817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2a88994ea0bdd73cf57d203462427575594d43a","datavalue":{"value":{"amount":"+0.7277770042419434","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":"Q2684887$03A063ED-AA24-40C8-930C-391F4624E284","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38c2a9829434b61c077cd68099319ad478921812","datavalue":{"value":{"entity-type":"item","numeric-id":2689227,"id":"Q2689227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7028954659af3a817aac301285a5a2ae8e79ed19","datavalue":{"value":{"amount":"+0.7225942015647888","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":"Q2684887$B9C1AE95-5960-4545-B373-E6C57EDD22FD","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684887$A3C16932-D184-4AB9-8FD8-56F0DE5453AA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2684887","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2684887"}}}}}