{"entities":{"Q6133144":{"pageid":13267451,"ns":120,"title":"Item:Q6133144","lastrevid":58696755,"modified":"2026-04-06T09:07:08Z","type":"item","id":"Q6133144","labels":{"en":{"language":"en","value":"Extremal independent set reconfiguration"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7729679"}},"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":"Q6133144$2942E5F9-420B-4AF4-B8F7-164935D041B9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"20f1b34b1f7251e30bcfd4022965145b31f5645a","datavalue":{"value":{"text":"Extremal independent set reconfiguration","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6133144$8AB72F7B-9DC7-48AB-809C-0DD8B82CF066","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f0b5ce31cc3d64cf9d230bb70fb22eb29972375c","datavalue":{"value":"1519.05188","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6133144$34639059-F07E-49CC-A95C-3BBA44D1CA00","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0f288e572c93a56fdcc0314ae59e528eb5804ee0","datavalue":{"value":"10.37236/11771","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6133144$88E76938-E3D6-4CB8-B8F9-CD207BA8B22D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebc3e32045f9761c31fcd6202016ff847b18bae9","datavalue":{"value":{"entity-type":"item","numeric-id":512580,"id":"Q512580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$5516FB5D-A5CF-4A03-A2B3-7C7AAC10D5AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0acc8102aa7609c7481992aee3f963b66dc4038a","datavalue":{"value":{"entity-type":"item","numeric-id":2305898,"id":"Q2305898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$F3A50718-CFC0-4094-84EF-ACA18CEDD0C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8acddea1a39e0f346d74120dae0af6aa23637a22","datavalue":{"value":{"entity-type":"item","numeric-id":777376,"id":"Q777376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$49041F81-2D77-48FC-97B2-F9A81CBA1F0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"422d41f94f8a39580a8eaa67cd40c776a7c16584","datavalue":{"value":{"entity-type":"item","numeric-id":858107,"id":"Q858107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$ECDD0CEF-4EFC-4619-907B-83AB20DE308E","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":"Q6133144$82CDA3E8-5B31-4BFB-8B2F-D51E366A80D7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a8fbdc973831ed82b98450c41c7d5e06c8adadc9","datavalue":{"value":{"time":"+2023-08-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6133144$BF635EAB-1F1A-4817-AD2C-2A7BE8AD3728","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"db0ab29c387e83783c3b1dab00311afd780a4991","datavalue":{"value":"https://arxiv.org/abs/2301.02020","type":"string"},"datatype":"url"},"type":"statement","id":"Q6133144$720267E0-ED2C-4DAF-859B-571998D7EB47","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0f54c0c0743b824ffc181077f2aae5d624626aa7","datavalue":{"value":"Summary: The independent set reconfiguration problem asks whether one can transform one given independent set of a graph into another, by changing vertices one by one in such a way the intermediate sets remain independent. Extremal problems on independent sets are widely studied: for example, it is well known that an \\(n\\)-vertex graph has at most \\(3^{n/3}\\) maximum independent sets (and this is tight). This paper investigates the asymptotic behavior of maximum possible length of a shortest reconfiguration sequence for independent sets of size \\(k\\) among all \\(n\\)-vertex graphs.  We give a tight bound for \\(k=2\\). We also provide a subquadratic upper bound (using the hypergraph removal lemma) as well as an almost tight construction for \\(k=3\\). We generalize our results for larger values of \\(k\\) by proving an \\(n^{2\\lfloor k/3 \\rfloor}\\) lower bound.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6133144$6D8EA6AF-C2C7-466E-A0F6-C338C8EE1EEE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6133144$47A79AD4-A8E1-4BAF-8645-79BF483FB6D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6133144$A40CC49D-172E-419C-B551-D46351D37E57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6133144$EE1CBB2B-9793-4977-A1A2-269FA695F6FF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"feb34af5409c2dcadb9c2c3289db2d6f408834e2","datavalue":{"value":"7729679","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6133144$1090629E-0B3B-4DB3-991A-F5306AA6A30B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"652eee1abb0b4092b3e174172e3a130bee92c3ae","datavalue":{"value":"combinatorial reconfiguration framework","type":"string"},"datatype":"string"},"type":"statement","id":"Q6133144$4F519DEE-B25D-425A-A57F-64C602F9BA10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9aba1c8e1659faef0c860f3acd0a6a5c50308ce2","datavalue":{"value":"configuration graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6133144$BE12E520-1FEA-4B96-9F2E-0073E216C68B","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":"Q6133144$811C2D1A-4D7F-4F12-9C37-B3F75A9526EE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d184614190f5d7d84106cc149a3d1eb441d61dd8","datavalue":{"value":"W4385358738","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6133144$48821480-DF76-49EF-B10F-CF0367996E24","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"27e54002794ce6f4658b7210c8581544b860f3e8","datavalue":{"value":{"entity-type":"item","numeric-id":6115427,"id":"Q6115427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$7EF0A4ED-EB9D-440E-B31C-441C318D7B06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"248c3ba53672e3b1c031bd917c407c9bc91bba06","datavalue":{"value":{"entity-type":"item","numeric-id":5834919,"id":"Q5834919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$ADDEC366-8BDE-4D15-B25A-D7663C17AF90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9641eac6c877a00dfe790d713c5d781f338fa11d","datavalue":{"value":{"entity-type":"item","numeric-id":1687909,"id":"Q1687909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$DBD5E847-A469-4DFD-8A34-7B84AAD89C6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98322fc6aba611537ddffa93fa92a17e21da0cdc","datavalue":{"value":{"entity-type":"item","numeric-id":496016,"id":"Q496016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$1847A902-4903-4A5A-A18F-9084C4FA539A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86a7c7030b13980ad390e490cc44270b8b1343a4","datavalue":{"value":{"entity-type":"item","numeric-id":5886100,"id":"Q5886100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$A8844599-9393-4629-ADE1-B1ABCBD0883C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cab85a43c3a2c622940dade0ce475e90ad2f2b75","datavalue":{"value":{"entity-type":"item","numeric-id":2482877,"id":"Q2482877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$1446CB64-81CA-483B-9F43-F6440AE66A08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e184195c5a8284dcbf17831e106578831ea79773","datavalue":{"value":{"entity-type":"item","numeric-id":2570127,"id":"Q2570127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$58FC7930-B7DC-43EE-87F4-5D73F1039C6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74efae8620bed35c19b6f3116177d4b2e98936d2","datavalue":{"value":{"entity-type":"item","numeric-id":719258,"id":"Q719258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$4606994A-CEAC-4E40-AE5E-92541A50E134","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aee199819198f52249bbfa0aa9cdb4f0fc68dc46","datavalue":{"value":{"entity-type":"item","numeric-id":441866,"id":"Q441866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$4E4EEB32-5F0A-4A7D-BA43-23F4360763DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"155a5be71ec85581934887e7f138dea14e3c39e6","datavalue":{"value":{"entity-type":"item","numeric-id":5809257,"id":"Q5809257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$E94CDD92-0DA7-423D-9C43-1B242EAEC941","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efedccfcba75b2e5af002fe70ba92de53e072faa","datavalue":{"value":{"entity-type":"item","numeric-id":4629977,"id":"Q4629977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$C6BBEAFA-FA69-498F-94A5-F633719F6DD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fc00f68d01a683da71ebdbf42254dc69e2487a1","datavalue":{"value":{"entity-type":"item","numeric-id":2331456,"id":"Q2331456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$163DEEB7-EDCB-4CFE-82AD-6CCE75E9AE84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd968cefc028d9aa5a3adad211ca18d315086825","datavalue":{"value":{"entity-type":"item","numeric-id":5385859,"id":"Q5385859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$F5D748D5-4167-43EB-BB1E-6BEC3DA04D65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28d4ed8388f5bc6b9907b07191ce55da1c665437","datavalue":{"value":{"entity-type":"item","numeric-id":4175585,"id":"Q4175585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$DD50C946-1A01-42FD-A37C-5AC9E734019D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f80e72c60e965ff74053ca242a8f8bc9d31aec4","datavalue":{"value":{"entity-type":"item","numeric-id":2875857,"id":"Q2875857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$ADF6A0CE-711F-4135-97EE-F1301925F9F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fed39d42ca2b2dd840b667cc91f78a1d8b8fb44","datavalue":{"value":{"entity-type":"item","numeric-id":1686224,"id":"Q1686224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$B46B7A92-B57E-4972-B297-628594C61114","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b34a246508428ac62689a0f6e17e01f841a8d923","datavalue":{"value":{"entity-type":"item","numeric-id":3002782,"id":"Q3002782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6133144$93106962-60D8-45E4-99CF-CB4BCFBAE589","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"872b623214212a6374a94d6e376b1b299904c13c","datavalue":{"value":{"entity-type":"item","numeric-id":2192091,"id":"Q2192091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50e443b69d16652d7a2f56a89d4e1408c3e0577a","datavalue":{"value":{"amount":"+0.8212437033653259","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":"Q6133144$7B2F0380-8B71-47C1-863C-69EAC9DA24A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2efcc0e3177595e2657dd192c7d30a1006e8074","datavalue":{"value":{"entity-type":"item","numeric-id":4636582,"id":"Q4636582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a0470e0b00fadd94b609312fde1410ea391e065","datavalue":{"value":{"amount":"+0.8139939904212952","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":"Q6133144$64EAEB9D-2DEE-491B-8103-665EAC1EA179","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"514313049f3d07d0a9f12df3f8136f0171b156ff","datavalue":{"value":{"entity-type":"item","numeric-id":1801058,"id":"Q1801058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea6d70d129c2e4d8a087c34072bdd51b558ba171","datavalue":{"value":{"amount":"+0.8139934539794922","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":"Q6133144$83516AB1-0635-4125-B3F9-BC6F0D3CA90A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41c7ad2df9f71abe4fea81fa7be069881c364e8d","datavalue":{"value":{"entity-type":"item","numeric-id":2945182,"id":"Q2945182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dcb77f5d1c51810e478ad149b1677f977d6c0b4d","datavalue":{"value":{"amount":"+0.8136891722679138","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":"Q6133144$8E9FEFA7-F944-465D-B9C1-123682BEC3D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a73bde6c13195d54b7246829f9c87fd1647fd5d4","datavalue":{"value":{"entity-type":"item","numeric-id":441866,"id":"Q441866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81c2a652344c0a8a8f29387da35fc52af95a8008","datavalue":{"value":{"amount":"+0.8127214908599854","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":"Q6133144$5E15D95F-8825-4D0A-8A7A-E8B73E34DC13","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":"Q6133144$C09569F0-E67D-41FE-BE79-CE70DB2FDDDD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6133144","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6133144"}}}}}