{"entities":{"Q304187":{"pageid":305954,"ns":120,"title":"Item:Q304187","lastrevid":60838533,"modified":"2026-04-10T19:27:03Z","type":"item","id":"Q304187","labels":{"en":{"language":"en","value":"Pattern avoidance in poset permutations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6619139"}},"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":"Q304187$0CD79286-721A-4FBF-8C1A-4DE116F3159C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8c3823181098e9f086895f1426dafe01ea54d7ce","datavalue":{"value":{"text":"Pattern avoidance in poset permutations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q304187$F99D8ECD-8B95-411C-B2B9-0F1FBE6D183E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c4f10fac6a283a573a513bec9f9b6e855dd671e6","datavalue":{"value":"1356.06002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q304187$BF84832D-41F7-4352-BCCB-C8AF04E1A388","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"12fbff80e3e06475a5c40e70f7a4e3f827059b59","datavalue":{"value":{"entity-type":"item","numeric-id":304185,"id":"Q304185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$41B31A08-82B5-4491-AE4F-88792389FE2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0bb0e30f8a7550a7a220e5e9e5499707ad59c57","datavalue":{"value":{"entity-type":"item","numeric-id":304186,"id":"Q304186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$CE7B664E-0776-4B95-BD22-06649D6C468C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e2599ed8061d57585b4363072a1afceea2452436","datavalue":{"value":{"entity-type":"item","numeric-id":172073,"id":"Q172073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$29E181D6-0097-44C5-9771-F35518CE23D7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dfdc4d4cc36ab9323cabe15e9f40864a71d2da75","datavalue":{"value":{"time":"+2016-08-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q304187$4416131E-66EA-4C6F-B540-3C83297EC88C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"673c72d69c1f97216dcb15e28889262708c99e78","datavalue":{"value":"https://arxiv.org/abs/1208.5718","type":"string"},"datatype":"url"},"type":"statement","id":"Q304187$60DA5216-4DC1-42BB-B79D-335E4C62BBF3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"18f77f3a5953d2afff61c0588322e203c7da0f23","datavalue":{"value":"A permutation on an \\(n\\)-element partially ordered set \\((P,<)\\) is a bijection \\(\\sigma: \\, \\{1,2,\\ldots n\\} \\rightarrow P\\) and \\(S_{P}\\) is the set of all permutations of \\(P\\). For another \\(k\\)-element poset \\(Q\\), \\(\\sigma\\in S_{P}\\) is said to contain \\(\\pi\\in S_{Q}\\) if it has entries \\(\\sigma_{i_{1}}, \\sigma_{i_{2}}, \\dots, \\sigma_{i_{k}}\\) with \\(i_{1}<i_{2}<\\dots < i_{k}\\) and, for any \\(1\\leq a,b\\leq k\\) the order relation between \\(\\sigma_{i_{a}}\\) and \\(\\sigma_{i_{b}}\\) is the same as that between \\(\\pi_{a}\\) and \\(\\pi_{b}\\). (The order relation between two distinct elements is either `less than', `greater than' or `incomparable'). It will be seen that this generalises the definition of a pattern in a standard permutation. We let \\(\\text{Av}_{P}(\\pi)\\) be the number of permutations on \\(P\\) which avoid the pattern \\(\\pi\\). In the classical situation where \\(P\\) is totally ordered, we omit the subscript from the notation: in this case, counting permutations which do not contain a given pattern is a long-standing active topic, see e.g. [\\textit{E. Steingrimsson}, ``Some open problems on permutation patterns'', Preprint, \\url{arXiv:1210.7320}] for a recent survey.  In the classical situation, the number of permutations avoiding each of the six possible three letter patterns, namely 123, 132, 321, 213, 231, 312 is the same -- namely the Catalan number \\(C_{n}={2n\\choose n}/(n+1)\\). The article under review aims to render precise the intuition that, in the poset situation, there should be at least as many structures which avoid ``small-medium-large'' substructures of length 3 than others of length 3, because ``small-medium-large'' substructures are easier to fit together. The main rigorous result is that \\(\\text{Av}_{P}(132)\\leq \\text{Av}_{P}(123)\\) for any poset \\(P\\). Interestingly, the authors can also show that there is strict inequality if and only if \\(P\\) contains one of three particular 5-vertex posets \\(Q_{1}\\), \\(Q_{2}\\) and \\(Q_{3}\\) as an induced subposet. The proof is in some sense a development of the proof by \\textit{R. Simion} and \\textit{F. W. Schmidt} [Eur. J. Comb. 6, 383--406 (1985; Zbl 0615.05002)] of the fact that in the classical case \\(\\text{Av}(132)=\\text{Av}(123)\\). Various applications and open problems are also noted.","type":"string"},"datatype":"string"},"type":"statement","id":"Q304187$2D9447E3-3C1B-4E72-8964-74369374A851","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b0b0cea8603b4de1ffd54cda6d37d129691a25c2","datavalue":{"value":{"entity-type":"item","numeric-id":590772,"id":"Q590772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$37479C70-EBB9-469E-AF48-172C53C39CFE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f3d0b1de78ad0e32d646815f9dc7561538cada7","datavalue":{"value":"06A07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q304187$7A282124-4443-49AC-8191-2B6F569F0AD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q304187$C926F7CD-FDCD-463B-A96F-09F615C78EA5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ec87fcf0bc4bf0fc250ec67b47054c8285f6f589","datavalue":{"value":"6619139","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q304187$2D499581-7D07-4142-AD98-BA2F02419779","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"31a14a8a9bc219eadb222ba5d6598c4eb6bf13b4","datavalue":{"value":"permutation pattern","type":"string"},"datatype":"string"},"type":"statement","id":"Q304187$CA1436F9-2370-4621-87DE-18F1AFA21935","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d589d1418bb454d0d57abd8c2020b4fc06552aa","datavalue":{"value":"pattern avoidance","type":"string"},"datatype":"string"},"type":"statement","id":"Q304187$A3532B87-9BA0-47A5-8314-67905FE5DE18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"311b860a0597dd249b584149fd2ab2e7e5bfa5ec","datavalue":{"value":"linear extension","type":"string"},"datatype":"string"},"type":"statement","id":"Q304187$E03B10B9-61B0-4A0B-BDC1-4A485E9BC940","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0da0f5147540e5ff9abe1a7fedfdb0d575bb38f3","datavalue":{"value":"partially ordered set","type":"string"},"datatype":"string"},"type":"statement","id":"Q304187$E0B7F80A-BA19-4D2D-B175-CB764A9027DC","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"8ec1b2bc07750eafa24f811b04e7aeb8bf5e1509","datavalue":{"value":{"entity-type":"item","numeric-id":28318,"id":"Q28318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$BB88A139-7C64-4A7C-8AD5-838304BEB290","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":"Q304187$A952AA45-14D5-4CD2-9EB0-1D4B42AC9B47","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3735c7daf0a945e122ec349a2e9846d10530f4b2","datavalue":{"value":"W1593740639","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q304187$4A4D1327-DD2A-450F-9411-19625D4DD479","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"efd70d9baf0294c8aaadc8d6c24054da8d3c3406","datavalue":{"value":{"entity-type":"item","numeric-id":5952148,"id":"Q5952148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$2E9C2559-30BE-4B73-A1A6-AA79AB72C633","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc50af783799c0025eba117e89fafdbfdf88199f","datavalue":{"value":{"entity-type":"item","numeric-id":1971017,"id":"Q1971017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$26CB33A4-DE22-4581-BAA1-51E26B72A99E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68074387d8f6d5907d69eea7edc26581d4cddbc7","datavalue":{"value":{"entity-type":"item","numeric-id":1909965,"id":"Q1909965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$CA29EBD1-F636-42E1-A03A-E22658FAB1E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5bc6748cdb2e024049a5bd24fc85fa165a11fc3","datavalue":{"value":{"entity-type":"item","numeric-id":1953480,"id":"Q1953480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$63C9E5DA-19C9-4345-A124-AC3B7F191F3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fbc06056ab860c3fe5529345ab39aeea542dcf3","datavalue":{"value":{"entity-type":"item","numeric-id":4821520,"id":"Q4821520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$0438910A-FA5B-44F6-9DA9-5FBC3F32826A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc81470cae845dc6a1117f21b3e8bc304e84a220","datavalue":{"value":{"entity-type":"item","numeric-id":1775550,"id":"Q1775550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$11F50392-270B-42EF-9B03-E1F614586F83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9355b925fac9356724689c0bda75683a9d07f9f","datavalue":{"value":{"entity-type":"item","numeric-id":1771251,"id":"Q1771251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$DF7F751B-7C15-401D-8481-4C1A67C07DA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c94522aa6e561b81b28768429d84eb27f6c4b95","datavalue":{"value":{"entity-type":"item","numeric-id":1398289,"id":"Q1398289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$ADABD355-2372-4972-A0B9-089502B90CA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f4f4e1b94229ae4bd3d106a0af382219bfa4128","datavalue":{"value":{"entity-type":"item","numeric-id":404537,"id":"Q404537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$12A15A5F-2AF4-47BA-BE37-AD9F5CD7EDC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d99b77991f00589d2d06c4687cc07f6b0a7c3c14","datavalue":{"value":{"entity-type":"item","numeric-id":2490026,"id":"Q2490026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$99F49942-5E14-4A7A-B3F7-9A48B5B4B614","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed14b1b52181258518a3c775b41e5e33171f75a5","datavalue":{"value":{"entity-type":"item","numeric-id":2566285,"id":"Q2566285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$6AE52E40-3BBB-4287-A8D1-69BAC125C76A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e303d2e86948a75a2212052b01bb05a420e5219d","datavalue":{"value":{"entity-type":"item","numeric-id":1908273,"id":"Q1908273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$551B9B66-B70E-4F4C-AB93-DD08FA3A25AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$32DBDFF4-971F-4308-8B7E-EE7CFDC208D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"602dc95b4f81c50d4967fd33143a3dd26bace100","datavalue":{"value":{"entity-type":"item","numeric-id":5956779,"id":"Q5956779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$AA7C5696-8E39-47EB-9F4F-EC8F8A1A740D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e73c6f16c7317f2c5db4af33a45ca57e3869ab2e","datavalue":{"value":{"entity-type":"item","numeric-id":3495358,"id":"Q3495358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$E1C4094D-889A-4F3D-9AB1-297C07B835BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af8d47d847385476606b98cfa868c24cd58270d8","datavalue":{"value":{"entity-type":"item","numeric-id":3094527,"id":"Q3094527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$160B79E7-B537-47B5-8E44-9DCAD154EA78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdf079ed452f18f7e741be6953ed81e062a14d52","datavalue":{"value":{"entity-type":"item","numeric-id":2490028,"id":"Q2490028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$C9ECB5FF-8550-49A2-9610-82FE9621C40B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b449c1fa7cfb7efa1bf3e42ea7c8a97fdaca20b","datavalue":{"value":{"entity-type":"item","numeric-id":5916426,"id":"Q5916426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304187$956C2C99-E4C3-4599-AD56-4FD0F55239BA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"90ba4c3dbd63a4bd41a70a02fca9e55d54c519f3","datavalue":{"value":"10.1007/S11083-015-9367-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q304187$15C50C73-A49B-46F2-A144-3200B825AA03","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b839c646c6c3ce9ca24f38dd6fdef797e83a0bf8","datavalue":{"value":{"entity-type":"item","numeric-id":2345778,"id":"Q2345778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bb4c8d39cb0017e7f0a9fef26e687188ce2bfbc","datavalue":{"value":{"amount":"+0.8422631621360779","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":"Q304187$661E240C-0122-4027-9A4B-F42D31496042","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0e5ed4338228706615028536494a11d312341ba","datavalue":{"value":{"entity-type":"item","numeric-id":1960281,"id":"Q1960281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5adeeb6242c586a1050c3498168dea68ae31a6b0","datavalue":{"value":{"amount":"+0.8176068067550659","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":"Q304187$DA19828C-7204-4284-8273-BCFE5D1D433A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49a1d1a2de8f88c9686c340488b6370b611c9028","datavalue":{"value":{"entity-type":"item","numeric-id":2048546,"id":"Q2048546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"290ba1c6e764f8285b6798e28ceb1e542ea9158f","datavalue":{"value":{"amount":"+0.8161965608596802","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":"Q304187$23DDFDBE-1F3A-42CC-945B-F119A8DB2F8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a81743fe1918cde1b3a74c4237ebc15a20281715","datavalue":{"value":{"entity-type":"item","numeric-id":649006,"id":"Q649006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83fb484fa2e257bbaa19acf5a099b85c8162f38f","datavalue":{"value":{"amount":"+0.81446373462677","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":"Q304187$664741F5-D7EA-4A7F-A030-16984BBA49FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f9a766cd7fa24203cb37b774547a24fa5997fad","datavalue":{"value":{"entity-type":"item","numeric-id":404537,"id":"Q404537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f73f581242d0fb465ade9e7bffa4aa9946e8df24","datavalue":{"value":{"amount":"+0.8090811371803284","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":"Q304187$DD424970-2D64-459D-90C3-4311BD5788B6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Pattern avoidance in poset permutations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Pattern_avoidance_in_poset_permutations"}}}}}