{"entities":{"Q2309229":{"pageid":2319972,"ns":120,"title":"Item:Q2309229","lastrevid":57843594,"modified":"2026-04-02T18:45:12Z","type":"item","id":"Q2309229","labels":{"en":{"language":"en","value":"Stability for maximal independent sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7183929"}},"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":"Q2309229$710B67BF-384B-4D55-8D76-C93883EDBF2C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"afb90619458218bfe74b9eaded6f6eeead1df346","datavalue":{"value":{"text":"Stability for maximal independent sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2309229$A2A1FFD2-5292-4687-9512-EB62B6BF5293","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"28695b0efb355dcf6fa8806f565f2b56255f67c7","datavalue":{"value":"1435.05156","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2309229$48B254A2-8FBE-4274-AAAC-AB4471D46A4A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"69507b8a8033c857592c8d02027c7f96ff96aa0b","datavalue":{"value":"10.37236/8530","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2309229$BF0000F5-F796-4379-98D2-A2B2C3D00C56","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ba2b188a98caab98b1bb36c16909b98dfb8f1e9e","datavalue":{"value":{"entity-type":"item","numeric-id":1983095,"id":"Q1983095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309229$554E2CE8-E001-48C4-B347-1AD1259F7783","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d1a8b239d5a7f549910817e61d8809ac746dac16","datavalue":{"value":{"entity-type":"item","numeric-id":762169,"id":"Q762169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309229$E861716D-ECFC-482B-B80B-9B6CC49D72F9","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":"Q2309229$208AF983-6D54-4B15-B557-E05BC3F046E6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a956fc7bdaab6286c0ff311db45ecfd4aff84f08","datavalue":{"value":{"time":"+2020-03-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2309229$ABE6614F-0CCC-47F3-A42D-8251AB7C4AE1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"92110de2a7b6929b7583d8abeeafb6dcde7e5a7a","datavalue":{"value":"https://arxiv.org/abs/1808.06666","type":"string"},"datatype":"url"},"type":"statement","id":"Q2309229$3AF3B3B6-0F2B-4748-ACBA-3DF83ED2A612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"8632470aa06274aea08916969f0acbbdb473d64c","datavalue":{"value":"https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i1p59","type":"string"},"datatype":"url"},"type":"statement","id":"Q2309229$2F69D782-F8B5-444E-92E6-54AA3CC87E4C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1b85a7800a8aa7580afbd8947da9d665991bd447","datavalue":{"value":"Summary: Answering questions of Y. Rabinovich, we prove ``stability'' versions of upper bounds on maximal independent set counts in graphs under various restrictions. Roughly these say that being close to the maximum implies existence of a large induced matching or triangle matching (depending on assumptions).  A mild strengthening of one of these results is a key ingredient in a proof (to appear elsewhere) of a conjecture of \\textit{L. Ilinca} and \\textit{J. Kahn} [Order 30, No. 2, 427--435 (2013; Zbl 1297.06005)] giving asymptotics for the number of maximal independent sets in the graph of the Hamming cube.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2309229$772EA8EB-19E2-4706-93B3-0BAD8308F582","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2309229$AF110325-A248-4094-B818-936D949EA79C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2309229$15419919-47C6-4E34-900D-345E7367A83A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"82d4d4ac752a4714fe47002019865667fd2dc0e7","datavalue":{"value":"7183929","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2309229$E3D7063D-6BDE-4135-BEE2-05ECB3A9ED5A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"063a87a9648ad2ae3033a7819ab19f7dd12e622c","datavalue":{"value":"large induced matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2309229$8D4EB6EA-7C35-4D7C-849E-4A6639EA420C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"65b3fdbc3f1dedd50319a5175b9d97823541c903","datavalue":{"value":"triangle matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2309229$36FEAC80-AA1C-4230-A674-E1B5212E7AD5","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":"Q2309229$C90CF031-F321-49D0-AE55-6145F89EF800","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6e8e89eef11f964ef9ad5c48e7f6e24979e6a89e","datavalue":{"value":"W3011646037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2309229$7F3C8F40-869F-4860-83F9-EF6F7B62920C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"435363cd3f775038825f8575dc2a17f196b35bec","datavalue":{"value":{"entity-type":"item","numeric-id":1109031,"id":"Q1109031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309229$9B193AAD-2584-4CB6-A76C-175433CDB416","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a0256be6705108130fb01910564c5773692d3e3","datavalue":{"value":{"entity-type":"item","numeric-id":385145,"id":"Q385145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309229$10046F29-3A19-4D9E-A596-C7596D6007AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae35b42269b65df7a1c59338bf97c0ea301c5c81","datavalue":{"value":{"entity-type":"item","numeric-id":2488567,"id":"Q2488567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309229$63C4A009-4EAA-43AB-8D45-26CC1D324C4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60e71fd0d2221371d782e4046b4425200846def0","datavalue":{"value":{"entity-type":"item","numeric-id":3791174,"id":"Q3791174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309229$5969E2F2-C01F-4428-82E7-D1A9283E7E66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"497feb4ec6a6f2e68369db992d2252b4cd0ad376","datavalue":{"value":{"entity-type":"item","numeric-id":4695389,"id":"Q4695389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309229$4E2BD8E5-91C7-4CD5-9307-DDF2AB9F4F82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"730cd4d73fda1764ae5e4d2aa12894bb52b2e060","datavalue":{"value":{"entity-type":"item","numeric-id":2376906,"id":"Q2376906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309229$ECE75905-EE41-4FD2-A63A-50CA58F48CD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"958ca878e5b62556f835007572d5016da5391314","datavalue":{"value":{"entity-type":"item","numeric-id":5117318,"id":"Q5117318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309229$27CF87AC-0372-4219-91AC-A7E686169EB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3127634cf7f26d7344ac1d4042e384295e928c20","datavalue":{"value":{"entity-type":"item","numeric-id":2678457,"id":"Q2678457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309229$459311B6-7AE5-4DC4-957E-F2B90577A15B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d0b2fce2b242cc432634970b75f6a32544e3aaa","datavalue":{"value":{"entity-type":"item","numeric-id":4156696,"id":"Q4156696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309229$6CB92F66-817B-4225-86D4-033954932678","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65c334f24f0ea0f5930a0f10f3816e5cbac17eea","datavalue":{"value":{"entity-type":"item","numeric-id":5920767,"id":"Q5920767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309229$0A02F4F9-C8B5-4CA3-8B00-D77DAEE0C02D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a120159771a880a64db24710bf8bd97336b6ac99","datavalue":{"value":{"entity-type":"item","numeric-id":2867092,"id":"Q2867092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309229$51E06704-D71C-49CF-918C-334833E59CFD","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"6573217e2807f021141cd33a6f5f1519bf5907ac","datavalue":{"value":"bafkreicfzoqm3eg2b5pietkhwakzowu63rjoscb2nr2bdh2nx4ebgxfswy","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2309229$D46AEC56-7F1A-4308-93E3-71BCD1282098","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"761e4c01a37a5a070512847bf48b179e8dfb8529","datavalue":{"value":{"entity-type":"item","numeric-id":5931790,"id":"Q5931790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4243f7513184c8464225267270609e8cce82661","datavalue":{"value":{"amount":"+0.89385027","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2309229$A0DCCF2C-CD9F-4A6F-BF92-E72D331BD7DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64ce6a768c3c0ab7454ad7e8d91e9e0aeab4c1a5","datavalue":{"value":{"entity-type":"item","numeric-id":4021172,"id":"Q4021172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afa226e10b34bd9c074831b57e1f41eaf021d20b","datavalue":{"value":{"amount":"+0.8904499","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2309229$A8207FF3-29CB-4F4E-8961-0129C43AA771","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97de43371356ce58d85fb39c84cfe240b900504e","datavalue":{"value":{"entity-type":"item","numeric-id":1753011,"id":"Q1753011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4601e30e63e53faed58685e1df4e04804ea80bcb","datavalue":{"value":{"amount":"+0.8817863","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2309229$E437928D-E682-482D-A92F-94953A695253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d850cc6932cffc9f7dd934b1a4d41852daf4109","datavalue":{"value":{"entity-type":"item","numeric-id":2181736,"id":"Q2181736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c57748ef422e0cbb5a5426083e181c2b9ab161e3","datavalue":{"value":{"amount":"+0.881518","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2309229$D543F29C-5EE9-4070-A363-42A31E8978D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f443a0adc0b0467c59585a6db0fde9ebb396b5d","datavalue":{"value":{"entity-type":"item","numeric-id":893441,"id":"Q893441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41c1de49bc38de897982bd8286eed15ff0db6089","datavalue":{"value":{"amount":"+0.87622637","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2309229$DE312CD9-85D5-4FD9-8484-D7BACA7A93DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3ba1d01bd8fdf4cba40cee5ae5b87074cab56b0","datavalue":{"value":{"entity-type":"item","numeric-id":1382236,"id":"Q1382236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb21268ab53903996cecd9dcd547843787c25994","datavalue":{"value":{"amount":"+0.8760057","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2309229$9EDBC50D-CE59-45FD-9D9A-4E7250266BDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10038cc7571e1b57b4d776d1b68c98d79e3a62cd","datavalue":{"value":{"entity-type":"item","numeric-id":5214116,"id":"Q5214116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb1962e79bbe5c26966c58023e3dba78ddd176c4","datavalue":{"value":{"amount":"+0.8750015","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2309229$AE645E78-CC18-4450-AE2A-D8202E5950F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bef35c74f050ad8b529dbc0c836a9113882bf9b7","datavalue":{"value":{"entity-type":"item","numeric-id":2738747,"id":"Q2738747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95fb589c7dc938525710bf973c893e310bc5375b","datavalue":{"value":{"amount":"+0.87270445","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2309229$0911133A-5B41-4C4E-94B9-4A8F7A411274","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":"Q2309229$028F08EC-5A59-4EAD-8F2B-9EF7536E6603","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2309229","badges":[]}}}}}