{"entities":{"Q2314418":{"pageid":2325161,"ns":120,"title":"Item:Q2314418","lastrevid":78862079,"modified":"2026-05-06T12:36:28Z","type":"item","id":"Q2314418","labels":{"en":{"language":"en","value":"Monotonic properties of collections of maximum independent sets of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7083956"}},"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":"Q2314418$BD9B3E83-676E-49E0-8EDC-75DC55FF22A8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"886987c7256f5bc13c83ed3cb5a773927e3fea73","datavalue":{"value":{"text":"Monotonic properties of collections of maximum independent sets of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2314418$CF80E89B-A028-4AE9-9B88-7318B4AF533C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"62edbf0d0c0bafb51b718b01c7e9e745aafed869","datavalue":{"value":"1442.05159","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2314418$F792BA9A-9B41-467D-B8A2-84A47D83EF6B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"163104c51d94cc8db6cc4a695e2eaa6900a79337","datavalue":{"value":{"entity-type":"item","numeric-id":892170,"id":"Q892170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$CC3CAEC8-4846-4FB7-B215-9B9E1FBAD2DF","rank":"normal"},{"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":"Q2314418$EE3579FA-8A1F-4C63-A143-961DCA4A679B","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":"Q2314418$9951686A-91FC-4352-948D-608DA3FCC251","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e2599ed8061d57585b4363072a1afceea2452436","datavalue":{"value":{"entity-type":"item","numeric-id":172073,"id":"Q172073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$8E7BF6F4-310D-43B3-BA9E-6D9BA5E492C4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9188f4fbcb344562138d779febd5aeba85eab48c","datavalue":{"value":{"time":"+2019-07-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2314418$2FD9538B-CF0C-47D8-8C6E-A7C03C8132EA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cb9abf161cdcade9ab0ea6938875e4309d075139","datavalue":{"value":"https://arxiv.org/abs/1506.00249","type":"string"},"datatype":"url"},"type":"statement","id":"Q2314418$1DF06E79-1818-4FAD-936F-7BEE288D442F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"380ee207182ae95cb50b776e67e33fc19cd02ed7","datavalue":{"value":"Let \\(G\\) be a graph. The set \\(S\\subset V(G)\\) is independent if there exists no edges between vertices of \\(S\\) and \\(\\alpha(G)\\) is the maximum cardinality of an independent set. Let \\(\\Omega(G)\\) denote the family of all maximum independent sets of \\(G\\) and let \\(\\Gamma\\) be any subfamily of \\(\\Omega (G)\\). The function \\(f:\\Gamma\\mapsto \\mathbb{N}\\) is defined with  \\[ f(\\Gamma)=\\left|\\bigcup_{S\\in\\Gamma}S\\right|+\\left|\\bigcap_{S\\in\\Gamma}S\\right|. \\] Two subfamilies \\(\\Gamma\\) and \\(\\Gamma^\\prime\\) of \\(\\Omega(G)\\) are in relation \\(\\triangleleft\\), that is \\(\\Gamma^\\prime\\triangleleft \\Gamma\\), if  \\[ \\bigcup_{S^\\prime\\in\\Gamma^\\prime}S^\\prime\\subseteq \\bigcup_{S\\in\\Gamma}S \\text{ and }  \\bigcap_{S\\in\\Gamma}S\\subseteq \\bigcap_{S^\\prime\\in\\Gamma^\\prime}S^\\prime. \\] The authors show that \\(f\\) is \\(\\triangleleft\\)-increasing together with several consequences of that. In particular, they show that the following equation holds for every K\u00f6nig-Egerv\u00e1ry graph \\(G\\): \\[ \\left|\\bigcup_{S\\in\\Gamma}S\\right|+\\left|\\bigcap_{S\\in\\Gamma}S\\right|=2\\alpha(G). \\]","type":"string"},"datatype":"string"},"type":"statement","id":"Q2314418$C0561410-0DC6-42C5-8A9E-C44F30611216","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7fbfd6a9c9db4c04ae1819627a7c5da1a84e5679","datavalue":{"value":{"entity-type":"item","numeric-id":279208,"id":"Q279208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$0E226A87-0A4C-48CD-8262-357156110C65","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2314418$743901C0-F972-4CB6-AA50-69D8D5798196","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2314418$A681661B-948E-4906-BE94-DC1D021A17BE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b41ee219d765f55d46ae72535183966cc581215d","datavalue":{"value":"7083956","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2314418$95C04632-3AB5-4527-9587-FF3513FE1ADB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2314418$E239741B-F13A-4512-92E5-F71185379537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"971de6b4b88e7d82009a84077fbbaca6f807769a","datavalue":{"value":"K\u00f6nig-Egerv\u00e1ry graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2314418$0F8B4953-AFF3-488D-BCA5-C2C3735A2E04","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":"Q2314418$CB854916-9EE6-40D0-8E34-7DEF27014AD3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ff8891d2d0f6132efc8b0437313faadd6f4194d1","datavalue":{"value":"W2963811814","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2314418$A163C389-7578-4D1C-8C16-99DE0DEAACC6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"24041b1c30209c85ea013cbce048392f858752df","datavalue":{"value":{"entity-type":"item","numeric-id":1873814,"id":"Q1873814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$433E7018-D881-49FD-BF20-020630BDCC51","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":"Q2314418$ADDD6C60-E49F-41A2-90C7-9BD40029BBF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a1814f19eb5b739dfe9551fc10281c58def1723","datavalue":{"value":{"entity-type":"item","numeric-id":2457270,"id":"Q2457270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$A8DA6193-D014-4CE6-901E-B5F08303E356","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecbcf170115f6f30d9f7435716b60cb2dbcf2656","datavalue":{"value":{"entity-type":"item","numeric-id":5477956,"id":"Q5477956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$877C07F1-2E34-4524-91CC-1BB4B5E4CC1D","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":"Q2314418$1C114165-E479-4D9B-B585-25B900400559","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9b79bc1779cb60dc5f30b21bb22934d49f81c6d","datavalue":{"value":{"entity-type":"item","numeric-id":3581593,"id":"Q3581593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$BE86EF21-CC43-4AE6-81BF-6F0436C7E020","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf05925c161b50902a475d27429912f455994b38","datavalue":{"value":{"entity-type":"item","numeric-id":5919887,"id":"Q5919887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$511B2AAA-1951-4AFA-8597-998BD38016F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a31bc58ee4bc875a888e717e50eed21220abcf6e","datavalue":{"value":{"entity-type":"item","numeric-id":616388,"id":"Q616388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$513FB465-0626-4656-A5C9-1E3AF62A6BE6","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":"Q2314418$B6CF18E5-7BF7-4C83-B5C8-059ADEC29237","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f0a42664ea63f9be5897badc85bfcc6d06eddc9","datavalue":{"value":{"entity-type":"item","numeric-id":1869204,"id":"Q1869204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$C4E223DB-2A05-40C2-B2C1-95A6F07530AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32fe0ec2f106d9b2ab8b07193bafda07f5c977c6","datavalue":{"value":{"entity-type":"item","numeric-id":2902909,"id":"Q2902909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$04E10EB1-4F42-4035-9FCA-453C3CBBE3F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b44b8efb244efa9d1d80580526bdb328774861bf","datavalue":{"value":{"entity-type":"item","numeric-id":1926061,"id":"Q1926061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$3EF98F50-97E6-43BD-B21F-39CB015F3C1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f127139c6185e0188ae78a5811a3c64be1a7a207","datavalue":{"value":{"entity-type":"item","numeric-id":4906181,"id":"Q4906181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$7D88FCBD-B69B-442F-81F8-EEF99F37B71A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8320b90682a3747b9c732440a03352f9a37820b5","datavalue":{"value":{"entity-type":"item","numeric-id":368442,"id":"Q368442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$852A2A2F-8519-4484-B0EA-9E7470DC4495","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a8ac04684602f5043c8dd59676ace91da63b50f","datavalue":{"value":{"entity-type":"item","numeric-id":1939576,"id":"Q1939576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$09FCB436-7D39-470C-A557-13492F8D3214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ffa64bd3474a2e18ffd260e0b27483bc5d64d85","datavalue":{"value":{"entity-type":"item","numeric-id":2446347,"id":"Q2446347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$BCBA3CE6-AFD6-4E92-B11C-92FD9D1578F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0157d4dee6b8f7b0d3431e922361c4c9c3a0f1e","datavalue":{"value":{"entity-type":"item","numeric-id":405128,"id":"Q405128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$48538E76-AEE4-4A9D-AE08-E1ABC53826E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e58e1a571308da8eca3bafaef66104caf803216b","datavalue":{"value":{"entity-type":"item","numeric-id":741775,"id":"Q741775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$52EA8CE9-57E6-45FF-BECF-CAC371F7358D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"379b4ccdd3df17cafdab54bc614bf3a1ff480037","datavalue":{"value":{"entity-type":"item","numeric-id":2629485,"id":"Q2629485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$B5D6B1D2-6593-4553-8DD4-67FEC7B0698D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b577a5ad520b7e73cb32be324a751e863dbbfbdf","datavalue":{"value":{"entity-type":"item","numeric-id":5522742,"id":"Q5522742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$926628B6-5145-470F-B0BD-31771B458C43","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":"Q2314418$EDDB5A9E-1457-4B8A-9262-ADC93A560293","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0cd675799d3755f6c4297b4f14421d31f77d558","datavalue":{"value":{"entity-type":"item","numeric-id":4713055,"id":"Q4713055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2314418$5A1E0C97-4846-43FE-9AA5-9B550EE03ECA","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"3f8b3502bb091b80b2e29eead2b265c64e7272a3","datavalue":{"value":"Q129575430","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2314418$EA41E590-EAF9-4AD4-90E4-2DFE07B9C308","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5c60e32c02937b8859729a0956ac0fd3ec6978eb","datavalue":{"value":"10.1007/S11083-018-9461-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2314418$EA778F9C-9BE5-46F4-B50A-BBD33CD46FA3","rank":"normal"}],"P1643":[{"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":"dcc7e91f7adf62690a2aab1a5537bcf084dea2a8","datavalue":{"value":{"amount":"+0.8216797113418579","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":"Q2314418$66F3B2A7-684B-4772-AB76-1EB7F615EBBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20db5454e7d21746fbc72a275ba2f6e0ab17a948","datavalue":{"value":{"entity-type":"item","numeric-id":2403804,"id":"Q2403804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"252d44bfbf0286c3180989feb12fccd0f3f9cabe","datavalue":{"value":{"amount":"+0.8101236820220947","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":"Q2314418$6C4D1BE8-4D3B-49BA-A492-43A190AFB970","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ce8e726f419292a220ff06a90580c04631569f7","datavalue":{"value":{"entity-type":"item","numeric-id":1671323,"id":"Q1671323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f0dd9392a91e008e92933d1f689e31beecb48e6","datavalue":{"value":{"amount":"+0.8024110794067383","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":"Q2314418$E3102409-3CD6-487B-A4E2-11D543D6A6A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65d0dc64d7b0e79512b9d463ad15823a6a9797ac","datavalue":{"value":{"entity-type":"item","numeric-id":2857406,"id":"Q2857406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5922b453048a1b8b607ba476650b9804a8f08e7f","datavalue":{"value":{"amount":"+0.783274233341217","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":"Q2314418$79F8D216-8C0F-4D93-9F17-116F81872420","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5d51486e655105c487e50621b1b681cc83d739b","datavalue":{"value":{"entity-type":"item","numeric-id":5377038,"id":"Q5377038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e826eccc832f3fda23b67f8b39f579f908dd3ba7","datavalue":{"value":{"amount":"+0.7708138823509216","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":"Q2314418$0AD70D01-D75F-44C0-8E5E-67FD9971B574","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Monotonic properties of collections of maximum independent sets of a graph","badges":[]}}}}}