{"entities":{"Q1103620":{"pageid":1114372,"ns":120,"title":"Item:Q1103620","lastrevid":67000674,"modified":"2026-04-12T14:15:13Z","type":"item","id":"Q1103620","labels":{"en":{"language":"en","value":"Forbidden submatrices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4053629"}},"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":"Q1103620$2B5423B8-BF56-48F3-89CC-50B52BC06EA3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9c2340baf9a3844b149e726474b98af55ee03e3f","datavalue":{"value":{"text":"Forbidden submatrices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1103620$8C48CFD8-8A97-48A6-BDEC-20938C9EE5E4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fe98194f53ee74dda09ad1e351f3e8da0f85a7e9","datavalue":{"value":"0646.05009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103620$E1925222-EE0C-4504-9C08-F900405B3A04","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8b8503d6622fb9b767e9d095c47e367c22437d30","datavalue":{"value":"10.1016/0012-365X(86)90211-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103620$948F64C9-00E4-4337-B5F0-799A83AF0286","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":"Q1103620$814812DB-026B-4D35-8CED-867E7829C89F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1103620$84075E56-BCFA-4833-9819-5605E4D52ACD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e643523c50306822a187ab501bf4456568d22d21","datavalue":{"value":"We consider an \\(m\\times n\\) (0,1)-matrix A, no repeated columns, which has no \\(k\\times \\ell\\) submatrix F. We may deduce bounds on n, polynomial in m, depending on F. The best general bound is \\(O(m^{2k-1})\\). We improve this and provide best possible bounds for \\(k\\times 1\\) F's and certain \\(k\\times 2\\) F's. In the case that all columns of F are the same, good bounds are obtained which are best possible for \\(\\ell =2\\) and some other cases. Good bounds for \\(1\\ell \\ell\\) F's are provided, namely \\(n\\leq (\\ell -1)m+1\\), which are shown to be best possible for \\(F=[1010...10]\\). The paper finishes with a study of the 14 different \\(3\\times 2\\) possibilities for F, solving all but 3.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103620$21944B89-D46E-476C-B706-524F9A054219","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"772466e23f65811e4792a58a12ff09d79c338e5f","datavalue":{"value":"05B20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103620$7C70B831-466E-44FE-8B79-EAB5A9EDF639","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f21e2eebbbf4645a0e25fc3b26221aa46b8c572f","datavalue":{"value":"4053629","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103620$B31B9E44-1560-4ED3-862B-C7C20529FA62","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9fcb559c3d785e55d39389ae0f2205a170a4dc45","datavalue":{"value":"(0,1)-matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103620$EDD7B325-BA20-4CBD-B756-69B913AE3A40","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3c7a09266880b9246b87f74318f3fac418e3fcad","datavalue":{"value":{"entity-type":"item","numeric-id":489296,"id":"Q489296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103620$F1F7A1F9-3BD5-4843-BFA9-DD0507255C91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"947071be942dac18e853a747b6abc41c36475503","datavalue":{"value":{"entity-type":"item","numeric-id":787137,"id":"Q787137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103620$09BB23A0-D03E-44C5-ABA9-AFBDAF4A897E","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":"Q1103620$FCCF996E-5BF1-46D9-9E80-158D6A201EE8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1023bc48ef891e77bfb6a9538b0b93dfc2ed7bde","datavalue":{"value":{"entity-type":"item","numeric-id":1089344,"id":"Q1089344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103620$80B78FB6-6101-47CF-AC12-1FD463B27479","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d20d43981ea8728a5c02a1bf60e0f2b91181b43","datavalue":{"value":{"entity-type":"item","numeric-id":788002,"id":"Q788002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103620$77161B3A-CDEE-4B0F-9FE3-66167DD34A0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"859f3b322135cca80dc0e7e759fdae62bf94cc94","datavalue":{"value":{"entity-type":"item","numeric-id":3222197,"id":"Q3222197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103620$10502F5C-EE60-4C44-B5ED-4077B4A0B356","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4931ab7df2ae059e9321582bbb6e0be5553d3815","datavalue":{"value":{"entity-type":"item","numeric-id":1145706,"id":"Q1145706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103620$52221A93-8515-49C3-BF3A-81685FB39F39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b87f240b74f3f9df9c2b55fdb1be42ca8217e47","datavalue":{"value":{"entity-type":"item","numeric-id":3691772,"id":"Q3691772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103620$85126E48-D3C3-4398-843A-80CA1BC75D0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fdaaa82266c25ca119e16dca818943849305a6f","datavalue":{"value":{"entity-type":"item","numeric-id":1058516,"id":"Q1058516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103620$4E826CFF-8FF2-4225-81EA-8D30B8D90203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed28daf112121dc08adf4ce72a073bd046e54847","datavalue":{"value":{"entity-type":"item","numeric-id":2556406,"id":"Q2556406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103620$396FA534-CDA5-4483-A515-E1340BB470F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b910f3bdbfee2ff3a0d24df8459e194840d200d1","datavalue":{"value":{"entity-type":"item","numeric-id":2553434,"id":"Q2553434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103620$CAF455C5-C283-4E0B-92B9-5E2CC51B3963","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"62882edfca6a6d999ed1f0eb4d8d57bfa62bc5ae","datavalue":{"value":"https://doi.org/10.1016/0012-365x(86)90211-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1103620$366ED0E2-049D-4EC5-B9E1-914DBC0B48A0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"575135c712a43b4e5110ed3c9e9658f87f3882cc","datavalue":{"value":"W2913796054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103620$5291DC71-E699-4632-BDFF-6674561B932B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ba797ebd5e15a5a9f9bf5516a6a21490252153b","datavalue":{"value":{"entity-type":"item","numeric-id":2258896,"id":"Q2258896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef1089f86bb65aa8ea497c667753ef95b676b2fb","datavalue":{"value":{"amount":"+0.9112812876701356","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":"Q1103620$F738FB89-0336-4B45-82AA-34038612E261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d00d16951095acff6e592021ebc5e569d656914","datavalue":{"value":{"entity-type":"item","numeric-id":1359370,"id":"Q1359370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"748b9b3eea96dcd6738d9dc443e053b2dedbd7cb","datavalue":{"value":{"amount":"+0.8713023066520691","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":"Q1103620$18580C7F-E807-4BA4-A9DE-2E56966FC2E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f18c39b5e44c9556eed0fc7c9cefc25647f9d33e","datavalue":{"value":{"entity-type":"item","numeric-id":1953376,"id":"Q1953376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4837d23e29ef4ca5e6cd55183c83482f6bf40404","datavalue":{"value":{"amount":"+0.8709529042243958","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":"Q1103620$C7A34BEB-B506-4968-A8FF-B15822182F67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61d6a631ae3b65eecaf5b7cbef094aa68aca72f8","datavalue":{"value":{"entity-type":"item","numeric-id":1089344,"id":"Q1089344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a706bab2f23f5e24c732b3ccda013f8eff7ab095","datavalue":{"value":{"amount":"+0.8638498783111572","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":"Q1103620$7591F1E5-C046-4B53-B0C7-450391913E43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9609b64e98d6ffe63913f75684a0abf6297fe895","datavalue":{"value":{"entity-type":"item","numeric-id":1059636,"id":"Q1059636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ee965212b9705624b86189376b535254858ad24","datavalue":{"value":{"amount":"+0.8423964381217957","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":"Q1103620$191B46E8-2567-4174-8063-89903997E2C6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Forbidden submatrices","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Forbidden_submatrices"}}}}}