{"entities":{"Q1691099":{"pageid":1701840,"ns":120,"title":"Item:Q1691099","lastrevid":72523122,"modified":"2026-04-14T05:29:41Z","type":"item","id":"Q1691099","labels":{"en":{"language":"en","value":"Bounds on parameters of minimally nonlinear patterns"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6826151"}},"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":"Q1691099$5E706853-21DD-44A1-A179-79C93584BCE5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dad5d3a0183decda8a04009d6421bca24539b19a","datavalue":{"value":{"text":"Bounds on parameters of minimally nonlinear patterns","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1691099$4E6043F4-AEFB-44E1-BFD1-A246CBEA10DD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7fb6c6456ed8e68d6a38e2271c290986f02f5050","datavalue":{"value":"1386.05191","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1691099$EAE109E1-ED4C-4962-AD00-F7123F38AA16","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"09a5790ba99c138522bb1bd4536c1a06c8d7baea","datavalue":{"value":{"entity-type":"item","numeric-id":1691098,"id":"Q1691098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1691099$81F9B690-6996-47F4-8768-AB13AE6AADC5","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":"Q1691099$6A980AB6-5535-4D5B-ADF8-D6D5F721F3AB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9250d461f553bf174209fd981535ffea5fd639ab","datavalue":{"value":{"time":"+2018-01-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1691099$DD163876-52DF-4DC6-A421-802FEF8776C2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"baac465198e18396032ea2c4b5684561dff89e01","datavalue":{"value":"https://arxiv.org/abs/1701.00706","type":"string"},"datatype":"url"},"type":"statement","id":"Q1691099$A9162FA7-1A00-4933-87F7-C8DB4FDD2E76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"f80706348dd8c7f390241e281fc383c42684c2b8","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1691099$AEF4EE49-A6E5-4392-8288-F3F27D3C03BE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a2cb882116bdb8e6837bf187fccf8adbe053876b","datavalue":{"value":"Summary: Let \\(\\mathrm{ex}(n, P)\\) be the maximum possible number of ones in any 0-1 matrix of dimensions \\(n \\times n\\) that avoids \\(P\\). Matrix \\(P\\) is called minimally non-linear if \\(\\mathrm{ex}(n, P) \\neq O(n)\\) but \\(\\mathrm{ex}(n, P') = O(n)\\) for every proper subpattern \\(P'\\) of \\(P\\). We prove that the ratio between the length and width of any minimally non-linear 0-1 matrix is at most \\(4\\), and that a minimally non-linear 0-1 matrix with \\(k\\) rows has at most \\(5k-3\\) ones. We also obtain an upper bound on the number of minimally non-linear 0-1 matrices with \\(k\\) rows.  In addition, we prove corresponding bounds for minimally non-linear ordered graphs. The minimal non-linearity that we investigate for ordered graphs is for the extremal function \\(\\operatorname{ex}_{<}(n, G)\\), which is the maximum possible number of edges in any ordered graph on \\(n\\) vertices with no ordered subgraph isomorphic to \\(G\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1691099$C7B07AC8-2C43-4917-9309-D1C2D5227A95","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b02a47bb3e6ffda6ae8940845178eca3854c8d36","datavalue":{"value":"05D99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1691099$4878CE80-3A4E-4C74-8990-AC9B178C2633","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d8a802d217f978f938b0d6b6187d60ec1473adca","datavalue":{"value":"6826151","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1691099$3B607088-BDAF-4623-A826-426CA7FDD5F7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"801410884c8a790949fbcbcd0cfe9e3f9ad134f4","datavalue":{"value":"extremal functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1691099$0A378111-EFD7-4841-9983-A601A03C22C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"92c1fa317f2d56dc1218643741ac7adce1e68b9f","datavalue":{"value":"ordered graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1691099$157202CD-40FB-4D54-88CA-560F303FD3C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3b00ea9af44f1f30b8e446c359c46c86090fd12","datavalue":{"value":"0-1 matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1691099$EF44658F-B743-4A13-BE0E-4C0516B63F01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d010a72834d7552d13dccab07ba9617ef7760f61","datavalue":{"value":"minimally non-linear","type":"string"},"datatype":"string"},"type":"statement","id":"Q1691099$4F99A621-22FF-42DA-A9D8-F8A2CACDC135","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d589d1418bb454d0d57abd8c2020b4fc06552aa","datavalue":{"value":"pattern avoidance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1691099$0C2D3179-6B43-46F1-B449-EB1D6954C92E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1e866a56049d4a9e216c228366aba6f6513d5b0","datavalue":{"value":"generalized Davenport-Schinzel sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1691099$E62376C7-6FFD-4144-8696-09C649C4E070","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":"Q1691099$6C6678E0-F9DE-45D5-936B-1F0F79D34039","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf78f24dc9967d0a6148cbfe129076e5e338f2c7","datavalue":{"value":{"entity-type":"item","numeric-id":4325546,"id":"Q4325546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1691099$813F7B8F-40BC-416B-B99D-18664B73D413","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a242496d908b6d1e30e137bd48db323e9a6e17e","datavalue":{"value":{"entity-type":"item","numeric-id":5340927,"id":"Q5340927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1691099$CFBB1864-0AA5-447B-B97C-436B5905BC4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6b95d315981609a84ebfa01f95f8f1666479596","datavalue":{"value":{"entity-type":"item","numeric-id":5300510,"id":"Q5300510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1691099$E0824AA4-312B-4144-9DDF-67F0EEB7C65C","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":"Q1691099$9F53A8E5-C988-4CFA-A499-CE74E189420E","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":"Q1691099$69388EEB-76E6-4336-8CC6-55D7C9303411","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":"Q1691099$06FC6794-B385-466A-B2DB-86A7A3138A38","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":"Q1691099$95E160C3-669D-4881-810A-81FA26B54B51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c73a7c5807ec65edc3a4e99d90c6487b978833b5","datavalue":{"value":{"entity-type":"item","numeric-id":4263474,"id":"Q4263474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1691099$0AF6084D-0ACC-4CEB-967C-AA8E3683F9F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b4233d398f92b7310c2fba72ff7772b5a60457a","datavalue":{"value":{"entity-type":"item","numeric-id":2643869,"id":"Q2643869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1691099$2146F016-B017-49AA-B6E3-8052877B5BBC","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":"Q1691099$5529E470-C57F-400D-ADE8-AD752B8B3CBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"743c8062e07d18cd64ec304f9ff8ddbc241d0b7d","datavalue":{"value":{"entity-type":"item","numeric-id":3578194,"id":"Q3578194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1691099$D88D6C72-3435-4455-AB43-F36A6F071900","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8ac4341f417c59bf3cfe287f789f79581e16470","datavalue":{"value":{"entity-type":"item","numeric-id":2472738,"id":"Q2472738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1691099$621BD036-441F-4395-BEDB-A6F1EB03CFC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0e78b1f00892cec946b04d0283b98cce7038878","datavalue":{"value":{"entity-type":"item","numeric-id":409347,"id":"Q409347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1691099$C34DD0EC-B506-49C6-AA16-673C00E93CDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d8af891eae59b11b799161426f1c3e5421093bf","datavalue":{"value":{"entity-type":"item","numeric-id":543917,"id":"Q543917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1691099$3EED87F7-DA0F-48DF-91C3-89283353458F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d3e960ec1452beacc7616b77b957c8e1b9024a5","datavalue":{"value":{"entity-type":"item","numeric-id":2566807,"id":"Q2566807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1691099$84F692FC-D149-4B84-8A33-BEB17FD911EC","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"472e0f370b47a25d2d2b49bc681b9d8d335515a4","datavalue":{"value":"bafkreiaw3dgkwt7u4mt655ahle5yiwsn2g5x6qs7rxwgb6qhl2jokgarp4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1691099$64854168-949F-44E9-A577-BA6E61F71F60","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ea6c7c6ba2e85e6c579c92ad622b3083f95060f","datavalue":{"value":{"entity-type":"item","numeric-id":2209895,"id":"Q2209895"},"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":"Q1691099$4F2E3196-2EF6-4DBD-9221-C4F2F648A5B3","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":"0453227c7424604762b14ea2276a1aec555cfe7d","datavalue":{"value":{"amount":"+0.8283240795135498","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":"Q1691099$E24898F9-DCB9-42FA-982B-BCFA27810E61","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":"0f3b3c8553587972afef2d3c4980b0805f84c6f7","datavalue":{"value":{"amount":"+0.8020780682563782","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":"Q1691099$3960EAF2-1867-447E-BCD4-3D37F7A3DFD2","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":"88b700cb4a87dbf9a327d1d3d524faad5f145512","datavalue":{"value":{"amount":"+0.7999556064605713","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":"Q1691099$EC5D9A6D-35C4-4932-8520-4659B03816ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fdab993098218c7c1dd9483c636ea3231dd97a7","datavalue":{"value":{"entity-type":"item","numeric-id":2566807,"id":"Q2566807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c044dad5d7156f88e1d4f22a2140d7ea06e6559","datavalue":{"value":{"amount":"+0.7929711937904358","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":"Q1691099$6BA96741-78D9-4CCA-9175-CECDBAFB700D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounds on parameters of minimally nonlinear patterns","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounds_on_parameters_of_minimally_nonlinear_patterns"}}}}}