{"entities":{"Q2411507":{"pageid":2422250,"ns":120,"title":"Item:Q2411507","lastrevid":57901497,"modified":"2026-04-03T00:37:23Z","type":"item","id":"Q2411507","labels":{"en":{"language":"en","value":"Large cuts with local algorithms on triangle-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6797307"}},"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":"Q2411507$A644AAAE-C4A2-4D60-9A50-A7CBC5FD2B76","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eeee58e02bb76053705218ec34a2358af81e38ae","datavalue":{"value":{"text":"Large cuts with local algorithms on triangle-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2411507$B59D05E7-6958-44BB-BDF9-858BDA6E469F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c0a6ed70d9799ffbe82b2512f32edc534b241b38","datavalue":{"value":"1373.05189","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2411507$F7382646-CFFF-4343-A26E-EC45D2094233","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce5cf6a89a3f363f55f56db663e5fe057494c4b7","datavalue":{"value":{"entity-type":"item","numeric-id":896699,"id":"Q896699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$CC4D30BF-9B70-442B-B3FC-92B66B528C05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"85f6c5fe982c1241c12c5470fe4b950b44b04e26","datavalue":{"value":{"entity-type":"item","numeric-id":896022,"id":"Q896022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$6692598E-BF6E-4005-B2C6-0E85DC341A3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ca4daefaa4f60d5ae94ebd7a8af1a88fc5b915b","datavalue":{"value":{"entity-type":"item","numeric-id":324620,"id":"Q324620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$017B8E09-AFBD-4717-9A5A-32AE66B73B96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"72eb7577da4ce2320e365d0abc7a6ec50e002098","datavalue":{"value":{"entity-type":"item","numeric-id":642984,"id":"Q642984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$36AB9EA7-1585-4B07-B263-291451A111E0","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":"Q2411507$7D94AE4A-AE82-4F1B-8031-973C16AF5947","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c5a04010440d7ffd7654f08953b21d31e131a50b","datavalue":{"value":{"time":"+2017-10-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2411507$D118C825-700D-49F2-9BC5-C858FDAC252F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f19d5c18a32dd11571615f8f0425b4e053424f8c","datavalue":{"value":"https://arxiv.org/abs/1402.2543","type":"string"},"datatype":"url"},"type":"statement","id":"Q2411507$A0A7B6F2-92F1-42C0-B9F7-C4FE712FD05A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"c7dce9f5c7a87128401751f5057def08662782de","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i4p21","type":"string"},"datatype":"url"},"type":"statement","id":"Q2411507$7BC1E01A-E020-44AC-8123-462C3EC28D4A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cff646db4345061eaf3e7b1d94e5672827ad8003","datavalue":{"value":"Summary: Let \\(G\\) be a \\(d\\)-regular triangle-free graph with \\(m\\) edges. We present an algorithm which finds a cut in \\(G\\) with at least \\((1/2 + 0.28125/\\sqrt{d})m\\) edges in expectation, improving upon Shearer's classic result. In particular, this implies that any \\(d\\)-regular triangle-free graph has a cut of at least this size, and thus, we obtain a new lower bound for the maximum number of edges in a bipartite subgraph of \\(G\\).  Our algorithm is simpler than Shearer's classic algorithm and it can be interpreted as a very efficient \\textit{randomised distributed (local) algorithm}: each node needs to produce only one random bit, and the algorithm runs in one round. The randomised algorithm itself was discovered using \\textit{computational techniques}. We show that for any fixed \\(d\\), there exists a weighted neighbourhood graph \\(\\mathcal{N}_d\\) such that there is a one-to-one correspondence between heavy cuts of \\(\\mathcal{N}_d\\) and randomised local algorithms that find large cuts in any \\(d\\)-regular input graph. This turns out to be a useful tool for analysing the existence of cuts in \\(d\\)-regular graphs: we can compute the optimal cut of \\(\\mathcal{N}_d\\) to attain a lower bound on the maximum cut size of any \\(d\\)-regular triangle-free graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2411507$611FFFC5-ED2B-4DB5-BB12-DDDBB0738896","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2411507$5FD2EC83-93C4-4245-9999-05FD6492045C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"43aef7ededc7d4eab0d2ca8347df3c6578c2893c","datavalue":{"value":"6797307","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2411507$C8A83477-AE07-48D9-9067-BEAC8EC7062A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf4dc3db86d44e89a36d3ec12340c2571d04f06","datavalue":{"value":"graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q2411507$841702FA-8BE9-4883-BBC6-6BF4999F98CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34012c92c499b6a6beb6c6030b4f33ccbf9f4fcc","datavalue":{"value":"regular graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2411507$5E3343CF-79BE-44CC-BCB3-FBFD7D4E70E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1262d51f50334708902b19dcd78f24e1a994f9ba","datavalue":{"value":"cuts","type":"string"},"datatype":"string"},"type":"statement","id":"Q2411507$FC69B4FB-A8E8-45EA-960D-AEAB933A3EEF","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":"Q2411507$3BE9E61B-9980-4E82-8F97-59D65FC0DB40","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4329ca36ea7b8ebaadb6a856658f81663adced37","datavalue":{"value":{"entity-type":"item","numeric-id":2563506,"id":"Q2563506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$6F1E27CD-E495-48D0-9A59-6332211AC0CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ade52f5b7f0758a5fa2e96dfb0513dfffaf1537","datavalue":{"value":{"entity-type":"item","numeric-id":3905312,"id":"Q3905312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$945CCEFE-9269-4EC1-A95D-8E4FB9F496D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3219170a6c30631af63ece3d6aa7ed54f1f3f4a","datavalue":{"value":{"entity-type":"item","numeric-id":5428812,"id":"Q5428812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$809AF00A-874E-4B9D-AAEE-CF26AE33C2B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$4E3ACD46-92E3-48EF-857D-7456832036F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6469d5aad62ac14b25dfc13b5c4323fe6b28e225","datavalue":{"value":{"entity-type":"item","numeric-id":3866127,"id":"Q3866127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$BCFDF7D8-A393-43C3-AFF9-2423F96BB7AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63223a2b10e799e0a620d9698b0286ebd9668db5","datavalue":{"value":{"entity-type":"item","numeric-id":5441360,"id":"Q5441360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$79A9BD64-A17B-4627-BF30-A3D537B06A83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3770e7465d3ea037ac6e4e207159f97b1942ff20","datavalue":{"value":{"entity-type":"item","numeric-id":5054815,"id":"Q5054815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$5262923C-FEFA-4935-9497-33072EA44F63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"434e3d029b3c74ed7da0e93d488afceb7c5b2fa6","datavalue":{"value":{"entity-type":"item","numeric-id":5454254,"id":"Q5454254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$F764EE29-EE26-4256-A7E3-ADD3411D40FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f52d47ff6966bb988022ac1f493d6ecb90baf435","datavalue":{"value":{"entity-type":"item","numeric-id":5177259,"id":"Q5177259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$D7EF9A48-A57D-4BC9-85A1-B40B05D8F7BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"308b35a6a5b4ac526a39371e07d1ce2848ff196f","datavalue":{"value":{"entity-type":"item","numeric-id":3990110,"id":"Q3990110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$C76606A4-BF92-4040-90B8-64CD0E5E7704","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10ccf4d42c4757827ddea695c7555934bd0854b7","datavalue":{"value":{"entity-type":"item","numeric-id":1112836,"id":"Q1112836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$93C6C810-2BCD-474B-A59D-9F3272CC66B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d208bc7faa2a891430ffc025a2944816c8d37c5a","datavalue":{"value":{"entity-type":"item","numeric-id":5202209,"id":"Q5202209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$B352882F-C03D-4126-9DD5-6496B597B70C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ab1bb3fea25d37273520a93b75d353b55f5193c","datavalue":{"value":{"entity-type":"item","numeric-id":1333324,"id":"Q1333324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$1A90C19E-60BF-411C-8C5C-AB0181442731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"954b4a911776133a1e66e35089de4e4b9ee2cff9","datavalue":{"value":{"entity-type":"item","numeric-id":3977297,"id":"Q3977297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$651981F1-953A-4E7D-BD30-0DE01C1A7274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce6133d293bb8bfa149948ffdc9b0f276ef45523","datavalue":{"value":{"entity-type":"item","numeric-id":1186548,"id":"Q1186548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$4E6B4846-61EE-4F61-9901-C19F120E10FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8baa23286ca49968fb16b65cde47c98002896253","datavalue":{"value":{"entity-type":"item","numeric-id":4840774,"id":"Q4840774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$4EB39FBB-3F7E-4F7A-9F86-AE70A2D59F9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8839d5dd5306b247fca71a539a780d0b789f651a","datavalue":{"value":{"entity-type":"item","numeric-id":3460706,"id":"Q3460706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$21B05C84-486D-47D4-A3B7-C367397D9FA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5d44b0768db07357eda1d235a428f7ec777b530","datavalue":{"value":{"entity-type":"item","numeric-id":3990224,"id":"Q3990224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$125ACB27-00FA-4B85-8956-E6E23701065B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25bad8bd39d29e7c2125ba679be0411610efea5b","datavalue":{"value":{"entity-type":"item","numeric-id":2875112,"id":"Q2875112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$AA849F96-3BF3-463B-8568-6CBBFFE3D39C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a2013da7a36b0c841b6254b17aed91599c6b8ac","datavalue":{"value":{"entity-type":"item","numeric-id":4507337,"id":"Q4507337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411507$750DCA23-B3CF-45E0-8076-2D49082902E9","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"6271dfb0d4b85d214b20cfb55bce1df18481f547","datavalue":{"value":"bafkreigbv44ktfpp6mabkh2paxlon7ot7476qzhsl6tdswjdz3gaiawm3a","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2411507$2CB943FC-4175-4BFD-8A08-DCE5F82B649A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4006e612e06594612b7802bfcdccd990027d4f6","datavalue":{"value":{"entity-type":"item","numeric-id":5918122,"id":"Q5918122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d76e296db7d0cc46a75c9e30abf02f0676f8e0e","datavalue":{"value":{"amount":"+0.8262502551078796","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":"Q2411507$ECEDEA8C-EB6F-4D24-B911-00EB298A76C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48f4c8a3816cb2f4da97830ebd31d9d3acbeb28f","datavalue":{"value":{"entity-type":"item","numeric-id":5937918,"id":"Q5937918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5598ff8144d48310a7d08d01e82cbbf8ab3b62d","datavalue":{"value":{"amount":"+0.7837645411491394","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":"Q2411507$DF781C00-8EB2-4BE6-ABC9-8C02FD4E8B3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f965b2ca46ee8790b7a30fd7248b13b03b84344","datavalue":{"value":{"entity-type":"item","numeric-id":1715061,"id":"Q1715061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a7960bee91fc77e89a49a9ef3e3d23be05856e8","datavalue":{"value":{"amount":"+0.7788101434707642","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":"Q2411507$EB8F0B8F-2CAA-42DB-A35C-162CFADC01C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"045be61c18ecf0edd84465d1f3a22a7357330838","datavalue":{"value":{"entity-type":"item","numeric-id":1297468,"id":"Q1297468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e6501e792f82a4425b0cec6be33691f7b207e8a","datavalue":{"value":{"amount":"+0.7742903232574463","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":"Q2411507$21413940-39CB-4A58-9C5F-217E2BFD6D9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b671fe90e64e5d4fca09abe73317f3294817d039","datavalue":{"value":{"entity-type":"item","numeric-id":4550236,"id":"Q4550236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64a6078b65b76bcd57570f4ea76866329e39c38c","datavalue":{"value":{"amount":"+0.7732985019683838","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":"Q2411507$CB5C53B4-39FA-408F-8E71-04ACD542AAB0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2411507","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2411507"}}}}}