{"entities":{"Q1953538":{"pageid":1964280,"ns":120,"title":"Item:Q1953538","lastrevid":78039317,"modified":"2026-05-06T10:38:32Z","type":"item","id":"Q1953538","labels":{"en":{"language":"en","value":"A survey of forbidden configuration results"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6171961"}},"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":"Q1953538$ECAA6E0A-CB25-48BA-A6E6-8CBC7D17D103","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cc6dcfe484d08315986de4d6cee0756ac58824af","datavalue":{"value":{"text":"A survey of forbidden configuration results","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1953538$92C80D71-EEE0-4647-A15A-DAE713CC4D0C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"eeeffa5783379044c415ae9ebb20f2df45bf8234","datavalue":{"value":"1267.05278","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953538$6FB8FE1C-72A5-485E-ACE2-A66ADF086CA3","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":"Q1953538$3333D3DA-64EA-4FF4-9778-1F233364F430","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4a8303ee696998ba030c9b1c3b6bc07c6038c334","datavalue":{"value":{"time":"+2013-06-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":"Q1953538$593F68B3-75D7-40C8-BE47-AFEA051CDCBC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"891600717b9d30409eb4ebf422d2a9eb97cac67b","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS20","type":"string"},"datatype":"url"},"type":"statement","id":"Q1953538$AD1DC6C8-D1A1-474D-822D-7429860D4F10","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f27bc36ee557758c51aa011e5f5f73d32c8f302a","datavalue":{"value":"Summary: Let \\(F\\) be a \\(k\\times l\\) \\((0,1)\\)-matrix. We say a \\((0,1)\\)-matrix \\(A\\) has \\(F\\) as a configuration if there is a submatrix of \\(A\\) which is a row and column permutation of \\(F\\). In the language of sets, a configuration is a trace and in the language of hypergraphs a configuration is a subhypergraph.    Let \\(F\\) be a given \\(k\\times l\\) \\((0,1)\\)-matrix. We define a matrix to be simple if it is a \\((0,1)\\)-matrix with no repeated columns. The matrix \\(F\\) need not be simple. We define \\(\\operatorname{forb}(m,F)\\) as the maximum number of columns of any simple \\(m\\)-rowed matrix \\(A\\) which do not contain \\(F\\) as a configuration. Thus if \\(A\\) is an \\(m \\times n\\) simple matrix which has no submatrix which is a row and column permutation of \\(F\\) then \\(n \\leq \\operatorname{forb}(m,F)\\). Or alternatively if \\(A\\) is an \\(m \\times (\\operatorname{forb}(m,F)+1)\\) simple matrix then \\(A\\) has a submatrix which is a row and column permutation of \\(F\\). We call \\(F\\) a forbidden configuration.     The fundamental result is due to Sauer, Perles and Shelah, Vapnik and Chervonenkis. For \\(Kk\\) denoting the \\(k \\times 2k\\) submatrix of all \\((0,1)\\)-columns on \\(k\\) rows, then \\(\\operatorname{forb}(m,Kk) = (mk-1)+(mk-2)+ \\dots (m0)\\). We seek asymptotic results for \\(\\operatorname{forb}(m,F)\\) for a fixed \\(F\\) and as m tends to infinity .A conjecture of \\textit{R. P. Anstee} and \\textit{A. Sali} [Combinatorica 25, No. 5, 503--518 (2005; Zbl 1107.05090)] predicts the asymptotically best constructions from which to derive the asymptotics of \\(\\operatorname{forb}(m,F)\\). The conjecture has helped guide the research and has been verified for \\(k \\times l F\\) with \\(k=1,2,3\\) and for simple \\(F\\) with \\(k=4\\) as well as other cases including \\(l=1,2\\). We also seek exact values for \\(\\operatorname{forb}(m,F)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953538$F563A81E-B6EC-4831-838C-37DBC91C1DC2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9bd9af688c0b97c53a0660570659cd00420d9c9b","datavalue":{"value":"05D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953538$89D985CE-C7CA-4D20-AF6F-8020C4AC65A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953538$649F5721-BCDD-4CD6-9855-5A81762BB483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"772466e23f65811e4792a58a12ff09d79c338e5f","datavalue":{"value":"05B20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953538$32981D91-9030-45BF-925D-A23D997ED590","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3fecd2dd2f19198c1e9857f675120a2d15c60d2a","datavalue":{"value":"6171961","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953538$FA2FC897-0216-4713-B614-B4E64955CAF5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99ea09330f3842295918e5ea89988ff65d8415ca","datavalue":{"value":"extremal set theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953538$1EAD83EE-A7C6-4065-A027-C574F9190B2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"002cc1ba3816f862bb523925d4b44534398a82ef","datavalue":{"value":"extremal hypergraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953538$F66A9ED5-829A-4A3C-83B7-DAFE448AC73C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"314cf51b4035a1d323705bef111e3b42b3a4f95b","datavalue":{"value":"(0,1)-matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953538$3D659AB9-F446-45A6-B5AF-3349F6F7BA6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c9b8892fbe18b1921b609db96440dc9340d1a2b1","datavalue":{"value":"forbidden configurations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953538$4565BD12-C013-41F2-9039-5AC11138FA09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c49916021edccb418deb9b5c9398917147892e7c","datavalue":{"value":"trace","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953538$14F42FEF-06F8-49DF-BAD1-2425AF22D5DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"40dfb25b9dc7aa9fd8093db5d6b661320a1cf8af","datavalue":{"value":"VC-dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953538$D85E1FEE-BCA3-4A2A-A683-6EC374E4CDF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc586c1df0eef4aef9ea2351a31e68c964e44bc4","datavalue":{"value":"subhypergraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953538$B9427EA7-1DAE-4221-B6F5-C6A3E9F4EC72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0b9821176513016a0586ed724a4c4fb2b39becb","datavalue":{"value":"shattered set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953538$98721522-BE64-48F8-869E-DE17BBCF24C3","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":"Q1953538$0A3AB236-E0E6-4CE6-B1F4-21D3F6C0441D","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":"Q1953538$5C04C47B-3725-4310-81DC-DFAC298D7EF0","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"44386b051c5e96b6c629371cddfc54cae73f5bf9","datavalue":{"value":"bafkreid6uy5ekea5a2x45bdxm7iakdfjhzfk37okr6q2bp4ehgloncstje","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953538$84D0DE78-2700-4B4C-9195-0E3076ED8879","rank":"normal"}],"P1643":[{"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":"e003617c3d283c77a8f8de0064e628f3873c113c","datavalue":{"value":{"amount":"+0.9199172258377076","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":"Q1953538$17A0ED4A-D5EC-4DB9-8A71-D18015744B00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25d1de2b2f12e1b1e3d672089a2e6f0aaed436f8","datavalue":{"value":{"entity-type":"item","numeric-id":2857317,"id":"Q2857317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5974856180b53361af9d350d1bcb1c35ab6ffc44","datavalue":{"value":{"amount":"+0.9198085069656372","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":"Q1953538$9327BECA-918C-4AFC-9682-F16932FD1526","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2dc034e4fd5406a4bbd5cebd2876dde69663c38","datavalue":{"value":{"entity-type":"item","numeric-id":641192,"id":"Q641192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82cb25f19ea8bc9d95eadef8558d9b98a461b4d4","datavalue":{"value":{"amount":"+0.9183583855628968","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":"Q1953538$F716851B-5BF9-401F-B458-8E227169ECC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4c3e80681001f32e81b2ae1095421e422543d82","datavalue":{"value":{"entity-type":"item","numeric-id":2509735,"id":"Q2509735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be5393dc823408f5b6b8259090a9d2440a722f0f","datavalue":{"value":{"amount":"+0.9150574207305908","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":"Q1953538$847A79D5-1C5A-4782-94B2-696DA50302F2","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":"ac3c784083c2376b2b86145b4c38bc47be216eaf","datavalue":{"value":{"amount":"+0.9100042581558228","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":"Q1953538$52C1567E-9136-4993-9693-B5B2408B18D2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A survey of forbidden configuration results","badges":[]}}}}}