{"entities":{"Q1010616":{"pageid":1012464,"ns":120,"title":"Item:Q1010616","lastrevid":50626037,"modified":"2026-01-14T14:55:02Z","type":"item","id":"Q1010616","labels":{"en":{"language":"en","value":"Matrix partitions with finitely many obstructions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5540836"}},"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":"Q1010616$CC3765E1-2F69-4959-B583-1770DFA68EA9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8e9cbb210c0f8be60a4c915e221adf591c9c7b36","datavalue":{"value":{"text":"Matrix partitions with finitely many obstructions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010616$B3A66505-650D-4020-AB3C-913C0C025A9E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2cb9185be580ff2a6718fcb024b4b36a22319adf","datavalue":{"value":"1158.05326","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010616$C6BCDFEB-79BF-4494-98C1-4BAC0F6474DB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"52e1360a5020703d86a91e069accafd47f3fe515","datavalue":{"value":{"entity-type":"item","numeric-id":293381,"id":"Q293381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010616$4498A1DC-1025-42B4-8D17-D2D7C97FBC43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3b5375d01a59455d415f2afee9796bf93e2b3c4","datavalue":{"value":{"entity-type":"item","numeric-id":338573,"id":"Q338573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010616$AB816F5E-B5F5-4A33-8FFE-AA6620D45DF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"757ca2592a848327f99ad71a132ea82ba3a9f667","datavalue":{"value":{"entity-type":"item","numeric-id":1010615,"id":"Q1010615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010616$D02E24B4-FA25-44BC-AC31-1549B63BC0B0","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":"Q1010616$BCF7CF42-1778-4FE1-B987-4F322A2DA869","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f584a175cfc2fafdfc362244f176e06010bbf381","datavalue":{"value":{"time":"+2009-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1010616$24F17EE2-5A47-4FC4-A2B8-0D4A63D2CBF9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c21b6e2362f75444108b380241bcb7effad6cb25","datavalue":{"value":"https://eudml.org/doc/129715","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010616$21290988-252D-444E-B05B-75C7BC16EA9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"844dc6b155befdb40a1fc2c12fe0e869627e669c","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_14/Abstracts/v14i1r58.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010616$70465818-29E3-4806-9BAA-191E9BDF3EB0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"948d4d7c0536ff7525b17dffbf15aee8e0c50380","datavalue":{"value":"Summary: Each \\(m\\) by \\(m\\) symmetric matrix \\(M\\) over \\(0, 1, *\\), defines a partition problem, in which an input graph \\(G\\) is to be partitioned into \\(m\\) parts with adjacencies governed by \\(M\\), in the sense that two distinct vertices in (possibly equal) parts \\(i\\) and \\(j\\) are adjacent if \\(M(i,j)=1\\), and nonadjacent if \\(M(i,j)=0\\). (The entry \\(*\\) implies no restriction.) We ask which matrix partition problems admit a characterization by a finite set of forbidden induced subgraphs. We prove that matrices containing a certain two by two diagonal submatrix \\(S\\) never have such characterizations. We then develop a recursive technique that allows us (with some extra effort) to verify that matrices without \\(S\\) of size five or less always have a finite forbidden induced subgraph characterization. However, we exhibit a six by six matrix without \\(S\\) which cannot be characterized by finitely many induced subgraphs. We also explore the connection between finite forbidden subgraph characterizations and related questions on the descriptive and computational complexity of matrix partition problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010616$0A321EDB-3F0F-4382-9B2D-C5693BBD6329","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010616$DBD4C804-F196-4D17-A211-A1D2A63DB9DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"822dbc4c091d9d354470bf66dcd7d659b1bcc45b","datavalue":{"value":"15A99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010616$0B29E4AB-75AB-4357-8897-E8A7E08CB35F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010616$B43056A8-F41B-4331-92DE-7DDA864A20E8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8b5213463ec96bbbd3dc1c137e35a689cfa367dc","datavalue":{"value":"5540836","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010616$362E3CD4-21D2-41EA-B271-93090FB3F7D4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10766b111e21ecbd937d361fbfb402a673d22930","datavalue":{"value":"matrix partitions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010616$E2AC43A6-3EAC-46DA-8A78-0335588F5AB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"453a43e7e93d9a367957c940a4dbc5498dddc3ee","datavalue":{"value":"forbidden subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010616$421EBB12-1C58-4246-B121-5609E78A0D9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"446f315f6b0cc4e9075b49dd109dcad60447d7c5","datavalue":{"value":"generalized colourings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010616$813D53AF-EFC3-4302-BFAF-C57BFECEED81","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":"Q1010616$37D88F12-82FF-4ADE-842B-11DCC4CC22DC","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"ef8ac7c8badc96255ef46ec220febb64f24ee174","datavalue":{"value":"bafkreiacngvghqksxx3bjl63wfxicwmsbxr7747tb5ukjlzatroq33ktlq","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010616$421C5BC5-99CE-4C97-84CD-EBD8D884A070","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d822ee158e23f548c18f082c3be8a78fb454575","datavalue":{"value":{"entity-type":"item","numeric-id":3439607,"id":"Q3439607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cafed14b3a5da7b197b0278db14890b1120c132","datavalue":{"value":{"amount":"+0.9546990990638732","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":"Q1010616$DE512648-03DE-4D1F-A819-8804E63C568A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4f01523afeae956b22d8ba6b3c971808fcc800c","datavalue":{"value":{"entity-type":"item","numeric-id":2433706,"id":"Q2433706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c91f6fb161bbf00fb3c4f276257241fc9b40d96","datavalue":{"value":{"amount":"+0.8622455596923828","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":"Q1010616$A657BC72-4DA2-4D9D-A898-69A39B22DE67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38083bafb48793d931f5d74f0f6b25f7c4c379db","datavalue":{"value":{"entity-type":"item","numeric-id":2636832,"id":"Q2636832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d800afe667a83615de69da59f494c6c5f3450f7","datavalue":{"value":{"amount":"+0.8464797139167786","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":"Q1010616$DC07AE6E-4E2C-4A18-B2B7-B560AF2FBB9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf6815d25bf9ae35f9391a6022294b7cf3619164","datavalue":{"value":{"entity-type":"item","numeric-id":383740,"id":"Q383740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35ac4401efd84cd56bff0877bfb4b9cef6afa6ed","datavalue":{"value":{"amount":"+0.8412180542945862","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":"Q1010616$2A4579D4-DAA0-4658-9DD3-625EB2C5B5E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f7f37e5842bbc9327810539c5ec6b906e362a5b","datavalue":{"value":{"entity-type":"item","numeric-id":5251620,"id":"Q5251620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eaa98f8d1bb42b1610e7058c8248ba05c44d0ce1","datavalue":{"value":{"amount":"+0.8367524147033691","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":"Q1010616$A94B4B23-DDBE-456F-B12B-267E22FEAD82","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1010616","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1010616"}}}}}