{"entities":{"Q2121745":{"pageid":2132488,"ns":120,"title":"Item:Q2121745","lastrevid":73451586,"modified":"2026-04-14T16:02:48Z","type":"item","id":"Q2121745","labels":{"en":{"language":"en","value":"Pattern avoidance over a hypergraph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7503023"}},"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":"Q2121745$14F2B3F7-DEB1-42E0-AECB-6DE8C3C78932","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"432afde6c258a4ee53c0f03e3d931bc532fafe68","datavalue":{"value":{"text":"Pattern avoidance over a hypergraph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2121745$101295A9-D88A-4362-A91D-9E0ABB7EA8BE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"73d9782f9eb54176e470fb01f08a495ad020f9a2","datavalue":{"value":"1486.05006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121745$9DD2193D-A68D-491B-BD02-88BFB839E0B3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3caff2fa97d4fd3fcab92b3fcb34a7a2b531ab7f","datavalue":{"value":"10.37236/9014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121745$FF759E31-3274-4159-A040-578524EDE6F9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ecce77652121ebdf658513f4e07fef9e8fa1d04","datavalue":{"value":{"entity-type":"item","numeric-id":394535,"id":"Q394535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121745$86A9855E-74CD-430F-B235-5346078C83F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8830922e1a4b2146e6b8300d7696efaaba6e7073","datavalue":{"value":{"entity-type":"item","numeric-id":2121744,"id":"Q2121744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121745$6CBDAC74-1D39-4ADF-A92A-D1FDC2D3407D","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":"Q2121745$F4234EC4-F684-4302-921E-7A5643C61DDB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d249924fb2575f70cd1998ce670af4e4c548d4a2","datavalue":{"value":{"time":"+2022-04-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2121745$65B68D0C-7BE1-4F48-BBF7-9963FFFCE829","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f026e3e6d4f8be28f57b1d12663a24b0bfaa7efd","datavalue":{"value":"https://arxiv.org/abs/1906.09659","type":"string"},"datatype":"url"},"type":"statement","id":"Q2121745$79E84CDA-68DD-4F37-9611-5E30A47DCAB0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"70853864fdf3ea7f6333b2d1e16c3d61524864ac","datavalue":{"value":"Summary: A classic result of \\textit{A. Marcus} and \\textit{G. Tardos} [J. Comb. Theory, Ser. A 107, No. 1, 153--160 (2004; Zbl 1051.05004)] (previously known as the Stanley-Wilf conjecture) bounds from above the number of \\(n\\)-permutations \\((\\sigma \\in S_n)\\) that do not contain a specific sub-permutation. In particular, it states that for any fixed permutation \\(\\pi\\), the number of \\(n\\)-permutations that avoid \\(\\pi\\) is at most exponential in \\(n\\). In this paper, we generalize this result. We bound the number of avoidant \\(n\\)-permutations even if they only have to avoid \\(\\pi\\) at specific indices. We consider a \\(k\\)-uniform hypergraph \\(\\Lambda\\) on \\(n\\) vertices and count the \\(n\\)-permutations that avoid \\(\\pi\\) at the indices corresponding to the edges of \\(\\Lambda\\). We analyze both the random and deterministic hypergraph cases. This problem was originally proposed by Asaf Ferber.  When \\(\\Lambda\\) is a random hypergraph with edge density \\(\\alpha \\), we show that the expected number of \\(\\Lambda \\)-avoiding \\(n\\)-permutations is bounded (both upper and lower) as \\(\\exp(O(n))\\alpha^{-\\frac{n}{k-1}} \\), using a supersaturation version of \\textit{Z. F\u00fcredi} and \\textit{P. Hajnal} [Discrete Math. 103, No. 3, 233--251 (1992; Zbl 0776.05024)].  In the deterministic case we show that, for \\(\\Lambda\\) containing many size \\(L\\) cliques, the number of \\(\\Lambda\\)-avoiding \\(n\\)-permutations is \\(O\\left(\\frac{n\\log^{2+\\epsilon}n}{L}\\right)^n\\), giving a nontrivial bound with \\(L\\) polynomial in \\(n\\). Our main tool in the analysis of this deterministic case is the new and revolutionary hypergraph containers method, developed in papers of \\textit{J. Balogh} et al. [J. Am. Math. Soc. 28, No. 3, 669--709 (2015; Zbl 1310.05154)] and \\textit{D. Saxton} and \\textit{A. Thomason} [Invent. Math. 201, No. 3, 925--992 (2015; Zbl 1320.05085)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2121745$C94ACF1D-D66B-41C8-B1B8-B43BBEC27426","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121745$F75BFE5D-4E65-4977-9E87-6271D76B9A92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b85c221f9847adc30512692a640a50dd4e3d1cb","datavalue":{"value":"05A16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121745$57B20BBD-7E24-46A5-A946-E3E1E9D2E7F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121745$7195C124-BDC1-469D-B841-E3716B0FE953","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"17eaa2bf787a4a89c7934eb4ac3853a4c7b70eee","datavalue":{"value":"7503023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121745$365B4FF8-0576-4774-8C98-D1F9DF468E68","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c21e36790e451ae11a7a8e36f33f82d43b990ec6","datavalue":{"value":"Stanley-Wilf conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q2121745$90BFC9F0-8247-40B3-B587-BCFAFBA87638","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9cbb23edd1d0a7bb03c71b05e0e8bf64ef2c29ef","datavalue":{"value":"\\(k\\)-uniform hypergraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2121745$F26AF20F-2922-4A7C-8A31-2B37559F267A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f0117ccc745457a5a1e1340e9657ffdcd7855e6","datavalue":{"value":"hypergraph containers method","type":"string"},"datatype":"string"},"type":"statement","id":"Q2121745$D266DF76-C2EA-4D83-B48D-5B9608125AE1","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":"Q2121745$2B002537-698A-4874-B1FF-CC20ACAB3F09","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"21f187859a414436c994566326f99c7439d45d9e","datavalue":{"value":"W4205461450","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121745$B2C87C6C-6939-4D76-B5B0-40A4B96BF48D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"16cb1947d5a73bb8d297f236151608d68b53e0e3","datavalue":{"value":{"entity-type":"item","numeric-id":5247664,"id":"Q5247664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121745$6531377A-E385-411C-91D7-14B991F15513","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4278a5a3fe9b02d05ecd9e67066c5b29c407b981","datavalue":{"value":{"entity-type":"item","numeric-id":5216319,"id":"Q5216319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121745$00A9E343-0D70-45D6-8BE7-6E9D24D2018D","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":"Q2121745$2A2B1421-2AB5-4AE7-98CA-699CDA140A85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7924cf00e176dc312ada3dd6e4066621b333e218","datavalue":{"value":{"entity-type":"item","numeric-id":4502539,"id":"Q4502539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121745$BA3CFA66-7D4D-4A32-AA84-EDC2038EF0AA","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":"Q2121745$BF74BF03-CC9D-4A2E-A2D9-322D4F017900","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d72afc55a9d8cfc781fd2fcb3a0be4dd8f00e7dd","datavalue":{"value":{"entity-type":"item","numeric-id":291780,"id":"Q291780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121745$E57A50AA-D556-4452-8021-AA2DE4EFF32C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b579af14f32e0ff0bb89075e11e8b6724a2a6dea","datavalue":{"value":{"entity-type":"item","numeric-id":496210,"id":"Q496210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121745$DA5365D9-7195-40ED-A0A7-4698E7996E50","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"0dc6a6f090052a41a0dc039cdd835ed28702c819","datavalue":{"value":"bafkreievtqa5rdl3o2balsnknmm3cbghu2hnkdavtnhjcxtebug6l6v3gi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121745$A4E02E94-B618-4708-AD99-74A2481027FA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11f255c779da2c9abc491787629d642ecb87d43e","datavalue":{"value":{"entity-type":"item","numeric-id":1572761,"id":"Q1572761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db27e9dfb31de47b412992b44e24ab0517ff98b1","datavalue":{"value":{"amount":"+0.8128549456596375","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":"Q2121745$818C28DE-3AFD-4647-9A4D-69E423B40F4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ca4dfb399ff786265e9ce97ba03b43ae3650235","datavalue":{"value":{"entity-type":"item","numeric-id":5194608,"id":"Q5194608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db27e9dfb31de47b412992b44e24ab0517ff98b1","datavalue":{"value":{"amount":"+0.8128549456596375","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":"Q2121745$20F532FF-3186-4B6A-BF2C-269EFE9E0814","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c84f0a09cb28fb840b9c681242bfc8f0d9f6150","datavalue":{"value":{"entity-type":"item","numeric-id":598446,"id":"Q598446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fc2e2aae466e57011f0833663f9aec57b814593","datavalue":{"value":{"amount":"+0.7943928837776184","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":"Q2121745$B547E287-8889-4B25-A95E-3283B304A258","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b81d8d39533cce54992f52338a151d1ccc163cc6","datavalue":{"value":{"entity-type":"item","numeric-id":1305174,"id":"Q1305174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06d998f98a4088b8c875259247edffbe3f63ce0a","datavalue":{"value":{"amount":"+0.7887041568756104","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":"Q2121745$7DBCCDFB-8FDF-4948-9D0B-E72BD25C953C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52608567094097828b47e0cc96c31ae318b070ed","datavalue":{"value":{"entity-type":"item","numeric-id":1971017,"id":"Q1971017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fa2214145e6b97580d1e4b29756c9fa65d6129a","datavalue":{"value":{"amount":"+0.7880381345748901","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":"Q2121745$65B8311C-D458-4256-8F5C-87646F975E89","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":"Q2121745$DCE09986-8547-43FD-A464-8821553C8456","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Pattern avoidance over a hypergraph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Pattern_avoidance_over_a_hypergraph"}}}}}