{"entities":{"Q405128":{"pageid":406895,"ns":120,"title":"Item:Q405128","lastrevid":61599690,"modified":"2026-04-11T00:23:20Z","type":"item","id":"Q405128","labels":{"en":{"language":"en","value":"A set and collection lemma"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6340138"}},"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":"Q405128$8D95E0E8-DD10-4F3E-B2C3-89042B8FFFBC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2729c69e848254a84011671f69cbfc3c432de9d0","datavalue":{"value":{"text":"A set and collection lemma","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q405128$169E12E7-2110-4D8B-AF89-3EDA90E49C5E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"901d311d01b30a0ca0c0d1a48550cbc85b786209","datavalue":{"value":"1300.05230","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405128$8E8E97CC-7E35-4967-8D71-5999A119FE7A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3379cff8d5e4805c5ff4f664fcb13704c759d836","datavalue":{"value":{"entity-type":"item","numeric-id":328718,"id":"Q328718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405128$DF9E95C8-85E9-45CB-97A4-C410060B29EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6f8a20409ab1b7a302e9e39ef4598e89538b5cf5","datavalue":{"value":{"entity-type":"item","numeric-id":328719,"id":"Q328719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405128$265612FB-4027-4854-8E57-F5E1554E2CF7","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":"Q405128$044D64A2-1ED9-4C4D-8880-84D2FA4FB819","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f9d8fea32a46af1bd8128cc5dcfc32073a3817d0","datavalue":{"value":{"time":"+2014-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q405128$007CDF9A-521D-4BC5-B407-5EB6DEBC637A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"442140a095a8e421b072a4178d0307263426cc1f","datavalue":{"value":"https://arxiv.org/abs/1101.4564","type":"string"},"datatype":"url"},"type":"statement","id":"Q405128$039CD2E7-CB5B-45DD-A277-EE65016C8BF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"186125333645f157f9e60fd74aa054d5b9e8768d","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p40","type":"string"},"datatype":"url"},"type":"statement","id":"Q405128$1E6E6236-F216-4A20-8BF9-E4382E2EA194","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"00f23f78fb2eaa0b10ae8fbb898b834ec65fa27e","datavalue":{"value":"Summary: A set \\(S\\subseteq V(G)\\) is independent if no two vertices from \\(S\\)~are adjacent. Let \\(\\alpha\\left( G\\right) \\) stand for the cardinality of a largest independent set.{  }In this paper we prove that if \\(\\Lambda\\) is a nonempty collection of maximum independent sets of a graph \\(G\\), and \\(S\\) is an independent set, then there is a matching from \\(S-\\bigcap\\Lambda\\) into \\(\\bigcup\\Lambda-S\\), and \\(\\left| S\\right| +\\alpha(G)\\leq\\left| \\bigcap\\Lambda\\cap S\\right| +\\left| \\bigcup\\Lambda\\cup S\\right| \\). Based on these findings we provide alternative proofs for a number of~well-known lemmata, such as the maximum stable set lemma due to \\textit{C. Berge} [Graphs. Amsterdam-New York-Oxford: North-Holland (1985; Zbl 0566.05001)] and the clique collection lemma due to \\textit{A. Hajnal} [Can. J. Math. 17, 720--724 (1965; Zbl 0129.39901)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q405128$0BFF40A5-B0BD-4439-A819-4327589CA230","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405128$C7C76571-07F4-4D7B-B787-2BE036A1C8AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405128$6B4E4E39-2EC9-442C-BAD9-296B57D988A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ff9d350acea12ffd75e7ed8da6f45c48ff041eef","datavalue":{"value":"05A20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405128$3E133A84-3B3C-4B62-BB46-CDFD179AE0EC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7201a704ac2458a15d725d6f397ac3edc6b05326","datavalue":{"value":"6340138","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405128$F4A6EDED-D9AA-4050-8A10-52E1C25D7881","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcc771f9c4cbb132a4fb9368403bb895cba44b70","datavalue":{"value":"matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q405128$34A126F6-7288-43D3-857A-B0E5E170C439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q405128$43279501-375E-4645-80EB-ECC1F9D67B55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6dd0d7043066fc18c97c64cc2373bc266c0fadc1","datavalue":{"value":"stable set","type":"string"},"datatype":"string"},"type":"statement","id":"Q405128$24976C81-C0AC-4EBB-94CB-DB3EC03E8415","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"274d092672a414a51cbf1f9c6392a720be1e7927","datavalue":{"value":"core","type":"string"},"datatype":"string"},"type":"statement","id":"Q405128$BC11C230-5824-478E-864B-AA8557CB0D1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"896249c4f18ada97dec0bfe62d80c0c653fabf8a","datavalue":{"value":"corona","type":"string"},"datatype":"string"},"type":"statement","id":"Q405128$2CCFF9AE-856E-49FF-93FF-44096EFAEA04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5928c9dcfb061445431e40c46be3050e6d5dbf83","datavalue":{"value":"clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q405128$3C160404-B682-4852-8A23-B8CF107E301E","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":"Q405128$24A20484-C122-437B-8C67-94FBEC076DB9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c17d101cac3e9e0db90d510b1df787cceb9c3f6","datavalue":{"value":{"entity-type":"item","numeric-id":3919752,"id":"Q3919752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405128$232D94EC-BD31-4F74-B6D2-23F939100ABF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7a5d00276ddbce7c8d0d869bc0f6e7a5f88cbd6","datavalue":{"value":{"entity-type":"item","numeric-id":3679215,"id":"Q3679215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405128$460704EE-2E6E-4131-9161-5AD0B0279D4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"466fc7e2455d565b2cfac57f80eb0daf54fdba00","datavalue":{"value":{"entity-type":"item","numeric-id":1850112,"id":"Q1850112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405128$D80983FE-72AF-4021-BDA9-AAFFFA215A17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88f829e6ab86ca48f00d0c31c03093060a9ae6a5","datavalue":{"value":{"entity-type":"item","numeric-id":5325947,"id":"Q5325947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405128$F051B1BF-EBC8-4CA3-A96B-61F7BA7E0638","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29a7656463249e5e8996e4dcda7fb5e8f7370cb0","datavalue":{"value":{"entity-type":"item","numeric-id":1256490,"id":"Q1256490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405128$17297069-E375-41F1-9500-E37F8EE695ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69fdc183f0f3712a7ac87827810eae642731e746","datavalue":{"value":{"entity-type":"item","numeric-id":1837211,"id":"Q1837211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405128$256D2F0F-1B41-4CFC-ACDE-D976BEE9DFEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"153a5da6d0601bbeab907fb1cb0bf3e3c25c3c82","datavalue":{"value":{"entity-type":"item","numeric-id":5338787,"id":"Q5338787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405128$071FD27D-9689-4F85-88CD-FDFD2A82452C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d00d210160acf4fc809a6ade236ff4059780d98","datavalue":{"value":{"entity-type":"item","numeric-id":5199419,"id":"Q5199419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405128$43CF60C4-FD71-4998-B6CD-9126064CEB76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ca21e1df836c5ebfed78ea974f2a2843326692","datavalue":{"value":{"entity-type":"item","numeric-id":4489216,"id":"Q4489216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405128$A656C777-B40D-46E3-AAF1-3C8932429A83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a324ef4a743b24f4c23b3e62553c7e877ee6415c","datavalue":{"value":{"entity-type":"item","numeric-id":1348387,"id":"Q1348387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405128$F982E334-8653-45C1-8E16-548D4D1E50C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08b87980f4084585587741634ab7ba0ec60a4a45","datavalue":{"value":{"entity-type":"item","numeric-id":2502896,"id":"Q2502896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405128$4E4BFDB1-F284-45EE-B948-386A7AEB4D23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"453dd36ef21866edcaa0fd25720c2a3a60772f8c","datavalue":{"value":{"entity-type":"item","numeric-id":3067059,"id":"Q3067059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405128$4E1D3E72-B485-4F8A-959A-62106A8DEB03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ed656a8323c754d35cde16128b4f6b00cce06e3","datavalue":{"value":{"entity-type":"item","numeric-id":599828,"id":"Q599828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405128$FD69A380-8330-41C3-805F-5C8797A9C2C3","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"408c8a594d761bc3a778144d481c51ec3ea8b28f","datavalue":{"value":"bafkreigffvsc5dnxmtaifluz4iitmdokliw67kaessufttkjd25m3bd6le","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405128$3A624B93-BAD8-4FCB-A0E4-1522DA9E6666","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d687d2b1c8c08bba39fd954bbe6014278a99fea3","datavalue":{"value":{"entity-type":"item","numeric-id":5135778,"id":"Q5135778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e78d0087c845070cf103d8a675da9a71e075df7b","datavalue":{"value":{"amount":"+0.7565453052520752","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":"Q405128$1A5168DC-EB0F-493B-A4B2-E26AB0C725C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a4008f01ecfd7c65cb5724e8673446dc61cec80","datavalue":{"value":{"entity-type":"item","numeric-id":2314418,"id":"Q2314418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dfab031f3814248696bd28f82f6ca9049eaa1b5","datavalue":{"value":{"amount":"+0.7508146166801453","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":"Q405128$DEE5E9FB-C3D2-477C-840B-4A8AB21D54D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6576e39a87a11e3acc0b4efd0803266109908dcb","datavalue":{"value":{"entity-type":"item","numeric-id":5198028,"id":"Q5198028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba440f8b5f56da2be80015c473c4b854c0105c48","datavalue":{"value":{"amount":"+0.7421404719352722","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":"Q405128$BB3077D2-20A0-4832-AA90-3000594DD3B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37d115ac439c7685766ec14a26a89a85286c861f","datavalue":{"value":{"entity-type":"item","numeric-id":3346368,"id":"Q3346368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69d18abd7d42d171072da03bb1f67ef34374ab3c","datavalue":{"value":{"amount":"+0.7386598587036133","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":"Q405128$3779ACD5-984F-471C-9871-2EF38EABDC42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"488ad754a85eb4d8708919d8ce2034d77e036325","datavalue":{"value":{"entity-type":"item","numeric-id":3979619,"id":"Q3979619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdeed9663d46d50782251a02cfb498ccd59e55b7","datavalue":{"value":{"amount":"+0.7356129288673401","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":"Q405128$8E089AE9-48BA-4140-92F3-6F1B733CF7AA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A set and collection lemma","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_set_and_collection_lemma"}}}}}