{"entities":{"Q2209895":{"pageid":2220638,"ns":120,"title":"Item:Q2209895","lastrevid":57771234,"modified":"2026-04-02T11:23:11Z","type":"item","id":"Q2209895","labels":{"en":{"language":"en","value":"Sharper bounds and structural results for minimally nonlinear 0-1 matrices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7270350"}},"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":"Q2209895$43F9E248-5D38-4F45-BDCF-35CEEA9512E5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4fde4ee49f9c441fce5710a95c569cdb4915da6f","datavalue":{"value":{"text":"Sharper bounds and structural results for minimally nonlinear 0-1 matrices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2209895$39ACBA8E-E2A8-4F72-90E3-74F0ABE44F7F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0f83431be86ab291394bd492241f891bd5080ff4","datavalue":{"value":"1451.15021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2209895$D202BB1E-5BD3-42AD-8F6B-9C5F6E875351","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0761c74c71a78f14e003ca6cd5079b1be2fd381a","datavalue":{"value":"10.37236/7801","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2209895$E38180FF-4E62-43C6-9C95-FCB6179E44C3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eaf8ba6cb45936f13800ef66a298946e4f28d85e","datavalue":{"value":{"entity-type":"item","numeric-id":2141368,"id":"Q2141368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209895$5BE8CF02-2E19-42B5-BCAC-51896226C749","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"48689c3e021df08de04162a27b34e006b36dd085","datavalue":{"value":{"entity-type":"item","numeric-id":1040838,"id":"Q1040838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209895$D170136A-EE56-44E0-AE2C-4831D1BFC569","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":"Q2209895$F2CDDD31-377C-4E5C-9B5D-763F42925999","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0aa71f2549cafe88468a911374ac89171b141e84","datavalue":{"value":{"time":"+2020-11-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2209895$F37B90E8-2EB8-48C7-B447-72AA2BBDAA22","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fab2580162b339b6832bd4fdf2b40fc9c4749bdf","datavalue":{"value":"https://arxiv.org/abs/1804.05999","type":"string"},"datatype":"url"},"type":"statement","id":"Q2209895$2C382A01-21D8-4FF6-A955-F56EF4609077","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a8a3f19456bdefd80dee9b6db9d44ba388b0df28","datavalue":{"value":"Summary: The extremal function \\(\\operatorname{ex}(n, P)\\) is the maximum possible number of ones in any 0-1 matrix with \\(n\\) rows and \\(n\\) columns that avoids \\(P\\). A 0-1 matrix \\(P\\) is called minimally nonlinear if \\(\\operatorname{ex}(n, P) = \\omega(n)\\) but \\(ex(n, P') = O(n)\\) for every \\(P'\\) that is contained in \\(P\\) but not equal to \\(P\\).  Bounds on the number of ones and the number of columns in a minimally nonlinear 0-1 matrix with \\(k\\) rows were found in [\\textit{P. A. CrowdMath}, Electron. J. Comb. 25, No. 1, Research Paper P1.5, 11 p. (2018; Zbl 1386.05191)]. In this paper, we improve the upper bound on the number of ones in a minimally nonlinear 0-1 matrix with \\(k\\) rows from \\(5k-3\\) to \\(4k-4\\). As a corollary, this improves the upper bound on the number of columns in a minimally nonlinear 0-1 matrix with \\(k\\) rows from \\(4k-2\\) to \\(4k-4\\).  We also prove that there are not more than four ones in the top and bottom rows of a minimally nonlinear matrix and that there are not more than six ones in any other row of a minimally nonlinear matrix. Furthermore, we prove that if a minimally nonlinear 0-1 matrix has ones in the same row with exactly \\(d\\) columns between them, then within these columns there are at most \\(2d-1\\) rows above and \\(2d-1\\) rows below with ones.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2209895$ECFEC35A-7906-4358-9F57-459996D30C17","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2a3b3e6e451112ae88a925a4babad921e127a616","datavalue":{"value":"15B34","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2209895$3ADF7B3B-AAAD-4489-AF4F-679E2B6582F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a6c6840ed6ccc38a95b421c87c1ec55f8094382","datavalue":{"value":"15A45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2209895$1CED5AE7-5828-4A5F-AE89-94035740E44F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4815a2ec2d373a57207ea65c70aacb1cb7fd5aea","datavalue":{"value":"7270350","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2209895$F61A40FC-AF51-44B8-A3B7-4556D3453A18","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"07b02cf04a9e1df266c07d42c39d93eb90bcdc9b","datavalue":{"value":"0-1 matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q2209895$3AF5586D-0B72-4428-ABE0-FF3339866B23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7cc5c27a033cc92069352b1609430b366a6c2aed","datavalue":{"value":"minimally nonlinear matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q2209895$3D615A55-B5FF-4824-B84D-638798F955AB","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":"Q2209895$88D70347-4E98-42EA-B1D6-33596F5E842D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7bd6731027536505d3e30ed75b4c6f89f9c12e1a","datavalue":{"value":"W2797580864","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2209895$2799F8F4-42ED-455A-9230-D6B04ED56D1C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef6a4c7fc6f67341fbbf0539c7e3ffd5e4754b59","datavalue":{"value":{"entity-type":"item","numeric-id":1691099,"id":"Q1691099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209895$921BB6FF-266F-45B0-B89B-EE181A4723B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66797c22f6271f13ce2cad427668f7aea451e947","datavalue":{"value":{"entity-type":"item","numeric-id":1813293,"id":"Q1813293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209895$28D933E9-FD2B-4163-9C75-3AD3EA1E11BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3293570593bb7b7ad11f990abbe0418a1c6ee3aa","datavalue":{"value":{"entity-type":"item","numeric-id":1195475,"id":"Q1195475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209895$8DCD9E72-B5CE-41A5-A0C6-EF92B2F22747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6a7da44af0b05ee487b5fdc95232faf6faae2f","datavalue":{"value":{"entity-type":"item","numeric-id":1040839,"id":"Q1040839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209895$22142638-D292-43D2-A077-FF5FC28291D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d985e7a71c72abe0626b999b32d405d498f35a3","datavalue":{"value":{"entity-type":"item","numeric-id":1003638,"id":"Q1003638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209895$028DFE22-F54D-475A-8F9A-FEBEF2C80865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50240b068b2f4e66fb8cd75d033da96637e75bdc","datavalue":{"value":{"entity-type":"item","numeric-id":598446,"id":"Q598446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209895$52F8EE73-9FF4-4C78-BB6C-F04CBBC6BEE2","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"3d35a374bccae6530ba644de06be2f89e74d088b","datavalue":{"value":"bafkreifrknjewuka4mm4w6xh2ub6hx2rhzbi46nb3tglywkjf3yuylav6e","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2209895$E665DF51-D2C6-4BC8-886C-618E744AE1C3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ca3fd73973f5f5a8df637381fa8be2799c9f1e5","datavalue":{"value":{"entity-type":"item","numeric-id":1691099,"id":"Q1691099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa1e6a3181661965cf6e43a18f77f7de85f8f6a9","datavalue":{"value":{"amount":"+0.9132963418960572","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":"Q2209895$5D2ACEAF-7F45-48A9-82A8-C1F47EF04054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"514407bb2483847620c5dcf4ca1bd4d04c13cc9b","datavalue":{"value":{"entity-type":"item","numeric-id":1003638,"id":"Q1003638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1317bd22253f25cfde2e175667a0337cfbaba066","datavalue":{"value":{"amount":"+0.8063119649887085","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":"Q2209895$FD6FD938-A9B6-4033-8CE1-5D1D6F59CAFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82e09d4d57230e74afac0a2d6925da49528b3357","datavalue":{"value":{"entity-type":"item","numeric-id":2515587,"id":"Q2515587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76a43b95969211b329b0a231844cd0ded39e771f","datavalue":{"value":{"amount":"+0.804517388343811","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":"Q2209895$3096D358-76A7-4E9B-8F11-15CCA8214FE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70b15f68b0b3e3e155c578e9dd745e1ae4e7092e","datavalue":{"value":{"entity-type":"item","numeric-id":1024495,"id":"Q1024495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d4d63cfacfbbff57e6abb40be16955e6d0fa67f","datavalue":{"value":{"amount":"+0.7949573397636414","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":"Q2209895$4E51F39C-AA07-47F5-989A-D82411C5C8F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65e98c075172c6ddd453ef183c7bd1caae868d32","datavalue":{"value":{"entity-type":"item","numeric-id":5417674,"id":"Q5417674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27142999a5bb3cb19336a27e54e9e4db19e3b375","datavalue":{"value":{"amount":"+0.7864429950714111","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":"Q2209895$8B5168D2-5C94-4E5C-B7A8-9C91A439156C","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209895$7AA2A446-77DF-4E42-9C88-9E9E46CEAA75","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2209895","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2209895"}}}}}