{"entities":{"Q1063611":{"pageid":1074363,"ns":120,"title":"Item:Q1063611","lastrevid":66182073,"modified":"2026-04-12T08:05:29Z","type":"item","id":"Q1063611","labels":{"en":{"language":"en","value":"Boolean techniques for matroidal decomposition of independence systems and applications to graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3918384"}},"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":"Q1063611$90356FCB-140D-4A00-B6D5-E071AB7CB19C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"df66b2037c3f540991315c88b1530f7c1e3c8acf","datavalue":{"value":{"text":"Boolean techniques for matroidal decomposition of independence systems and applications to graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1063611$5C622C42-0ADE-4FF6-8BBB-B6C53832FF7B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"14068bddef2322b26608eb0d156d98385222a4b6","datavalue":{"value":"0575.05019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063611$3E0568C0-93FA-4B3B-8E14-0DA3D0966A82","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cab528216148767d9f941168b7303cfda6569e1b","datavalue":{"value":"10.1016/0012-365X(85)90189-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063611$6A68A543-299E-479D-A6BC-E708E055701E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5a0bea0ff649e06bff66844d20058efc6765689f","datavalue":{"value":{"entity-type":"item","numeric-id":1063045,"id":"Q1063045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063611$7D55FDB3-2C10-470C-8B0E-9C999F5D24F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"54ae8a1f67117b1c40e7224a6ee62353a2cf60cb","datavalue":{"value":{"entity-type":"item","numeric-id":188437,"id":"Q188437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063611$7316A8CF-5CB7-4151-8E15-7F3F6C0C21B8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063611$7263BA04-4C3D-47BD-8380-8BFBB9F9D05D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1063611$FAA205CF-65DD-4AD5-B8A6-CBFCD646A2D4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"76eb67c9e9335c5b49eb4070e3536e9ae58f0626","datavalue":{"value":"The sets of an independence system \\(\\Sigma\\) on a finite set S can be characterized as the solutions of \\(f(X)=0\\) for a nondecreasing Boolean function f of \\(| S|\\) variables. Representing f as a product \\(f_ 1f_ 2...f_ k\\) corresponds to a kind of decomposition (union of independence systems) of \\(\\Sigma\\) where those cases are most interesting for which each \\(f_ i\\) corresponds to a matroid on S: matroidal decomposition. Making extensive use of the algebraic techniques of Boolean calculations the paper studies these matroidal decompositions of independence systems.    The functions f whose independence system is a matroid are characterized and it is shown that every nondecreasing f is the product of a finite number of such functions. Therefore, every independence system \\(\\Sigma\\) has a matroidal decomposition and the minimal number of matroids in any of them is the matroidal number of \\(\\Sigma\\). Finding matroidal decompositions via the associated Boolean functions is discussed.    Specific results are then obtained for the case \\(\\Sigma =system\\) of stable sets of a graph. For any positive integer k a class of graphs (complete k-partite graphs and k-polar graphs) with matroidal number k is constructed and the graphs with matroidal number 2 are characterized.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063611$75B58978-5FA0-4DE0-8525-D3EC1B01B4DE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063611$C0D7D61E-268F-4552-9567-F759D76E5443","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063611$3FF95177-DCF8-442E-99A0-1AE62750D576","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063611$5F1C5263-3BD5-407F-A13D-915AE9AD4633","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d6da1972d5d2bd1b2a2897361ed39f39a4153d4d","datavalue":{"value":"3918384","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063611$B68AFB87-6028-4072-A47A-E337AC2FEB5F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0062bff246f10874c360cb4d691bf5c2195f236c","datavalue":{"value":"Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063611$E8333AAF-5DC0-4045-886C-F57E61DC06FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f9e34bac160cd36162cca08b0c214ff82c5141b1","datavalue":{"value":"matroidal decompositions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063611$2036DC89-F409-418C-82EF-31B5BCDA3AB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5df066372b43ee0a234844149e91ea9cdd335344","datavalue":{"value":"independence systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063611$D5517E13-4263-40DC-821D-E7CE08583759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd271b779b62c7cd432d9f98fc97aaf6a61067e8","datavalue":{"value":"stable sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063611$CB653236-C45A-4716-A3A4-7F16FE359942","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddc14051a93e8c78a1da682d6f4184d91e9c6088","datavalue":{"value":"graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063611$D367C7C4-E7B9-489B-AE3D-8DFF3DAE27F0","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":"Q1063611$98EA85BF-D37C-4033-8A13-C88A222AB6E4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7f3be34444b87e94060eeddaad78e0c69a90fd2","datavalue":{"value":{"entity-type":"item","numeric-id":4165164,"id":"Q4165164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063611$60A8E3C7-1D7A-41FF-9F2B-6F6544CF6941","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063611$A610F7D1-5685-453E-B1BB-7A3FCD0FB05E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5395d0bcd819be45c30e27db1452a43996bbd557","datavalue":{"value":{"entity-type":"item","numeric-id":4060733,"id":"Q4060733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063611$9DB99D8A-4A97-4FA6-A82F-8B70E6C44AD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063611$F5D82AEE-A809-4566-AA77-63E3DE69ACAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1ba68befc4adee7a1322ff2178224ebed5c620b","datavalue":{"value":{"entity-type":"item","numeric-id":1218433,"id":"Q1218433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063611$14132276-9A33-477F-A18D-D0C971739EC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16ee6ba21410efd14ddd2a024a73c0ed4e5a2745","datavalue":{"value":{"entity-type":"item","numeric-id":4111952,"id":"Q4111952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063611$985454B8-6453-4361-ACB2-C69B89679222","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d981b374034469fd797cb908e1d561707da3750b","datavalue":{"value":{"entity-type":"item","numeric-id":2661525,"id":"Q2661525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f92060a270ab038c3dbfcd1846905435573d1cb3","datavalue":{"value":{"amount":"+0.9182217","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":"Q1063611$150355DD-3670-46C5-823D-6FFA65E555EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"163f46bda6720da201a39836bd3321c17c2d8e2e","datavalue":{"value":{"entity-type":"item","numeric-id":3328285,"id":"Q3328285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1284df8f0c3632104c8c294dadfe8ef03e76bd44","datavalue":{"value":{"amount":"+0.9112251","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":"Q1063611$4F27C78F-4E64-41B0-AECC-8A82298F96A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af6a3d87e7935036037bceb09e25a9038ea09b9f","datavalue":{"value":{"entity-type":"item","numeric-id":1775378,"id":"Q1775378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"478569a6892a718a02bb710007e5e7c022384e84","datavalue":{"value":{"amount":"+0.90082985","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":"Q1063611$063A8F37-8C97-47F3-A28A-ABCC4B368381","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa9163e24935b68a404840eb9bb4e40b3d235da2","datavalue":{"value":{"entity-type":"item","numeric-id":5752609,"id":"Q5752609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9db0c22630d0d8db4ab951670a29f1cbd089a231","datavalue":{"value":{"amount":"+0.88772535","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":"Q1063611$42FFE3BA-5B0D-44DF-87FD-7395C03D71F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12b526cb14defe4332c7bc248fa02dc1d2201d04","datavalue":{"value":{"entity-type":"item","numeric-id":1093645,"id":"Q1093645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0e0f72547a107257d86b4209c445c2d59cab393","datavalue":{"value":{"amount":"+0.8827776","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":"Q1063611$407BD127-D9B0-4BB2-B579-E04300F4C3E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4d1627e79fae36f8e9a23c1612d30e0ea02f1a8","datavalue":{"value":{"entity-type":"item","numeric-id":3682498,"id":"Q3682498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca8f6a2b04e6471e5f55dcd59b8e2723369e8bdb","datavalue":{"value":{"amount":"+0.8818468","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":"Q1063611$061BD4DF-9241-4418-A329-4572A5412085","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f7c6a853c0406a88c4d8ee1b26a9416967d18bc","datavalue":{"value":{"entity-type":"item","numeric-id":3797188,"id":"Q3797188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49b12dc2f94b7d008689a39a899567a4e60452ef","datavalue":{"value":{"amount":"+0.87950575","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":"Q1063611$496F560D-968A-418B-BB93-ACE1992F03E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c173d8fa3e94f07bbc0a5c689d8f0a13dc993a8","datavalue":{"value":{"entity-type":"item","numeric-id":4201561,"id":"Q4201561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef1db9daa1eed33499d0016131589c3269f602dd","datavalue":{"value":{"amount":"+0.8784559","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":"Q1063611$CE063BFF-B4C5-498A-9550-33F1207CDA48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34a1febd9b2d98c50f47b04aa2f622ce5a08bf9e","datavalue":{"value":{"entity-type":"item","numeric-id":2639863,"id":"Q2639863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2348f0e59222e1d4af9c9bee8f74a323a7bb2e38","datavalue":{"value":{"amount":"+0.87573636","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":"Q1063611$14ABB57A-F79A-4A0A-9EB6-61C5ACD274B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b39c2017d24d0a17431ad9d79b1fe06bc20bb288","datavalue":{"value":{"entity-type":"item","numeric-id":4296633,"id":"Q4296633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78ce33ab83d1fbb1ad86fad62548bff223bde7d1","datavalue":{"value":{"amount":"+0.8730172","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":"Q1063611$EEBAB89F-FD97-4060-91A9-E4DE0AA17FBD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Boolean techniques for matroidal decomposition of independence systems and applications to graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Boolean_techniques_for_matroidal_decomposition_of_independence_systems_and_applications_to_graphs"}}}}}