{"entities":{"Q1856066":{"pageid":1866808,"ns":120,"title":"Item:Q1856066","lastrevid":73673094,"modified":"2026-04-14T16:52:16Z","type":"item","id":"Q1856066","labels":{"en":{"language":"en","value":"The minimum number of monotone subsequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1861456"}},"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":"Q1856066$E5568B57-5505-4658-8861-183EEF6F827D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"18968cc20bb181ba34f080afbcae7c211dd5b8df","datavalue":{"value":{"text":"The minimum number of monotone subsequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1856066$0914B565-E963-4AB9-91C3-055024789A7E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"29300259bf216a6e9b340beb2da35927261717d0","datavalue":{"value":"1017.05002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1856066$A289634E-EDD5-4201-A2E6-BAD783A50691","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b2df2d65586a1d50198cbd24e7d1c6db53e1ca5d","datavalue":{"value":{"entity-type":"item","numeric-id":1408876,"id":"Q1408876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1856066$2D8B2187-4197-461F-BC7A-BA5675415B34","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":"Q1856066$3D8B4455-210A-4112-B63F-EB0564832695","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"111dc11587271f29bffc5b4de8ed3b84d4c073f3","datavalue":{"value":{"time":"+2003-05-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1856066$55D18B7B-C14B-4705-8F7B-07FEEE2D2935","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"38833680f56d74eff578a0b307e4bb40a20f0cc9","datavalue":{"value":"https://eudml.org/doc/122777","type":"string"},"datatype":"url"},"type":"statement","id":"Q1856066$1C4640A9-6D27-4B0E-A90B-7070A4144FD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"672eb8391f54fc01913d17a01048ebcff3db8b29","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_9/Abstracts/v9i2r4.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1856066$B24CA23F-32F8-40E5-87D2-10A040FFC0C4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0a2fa19d4770a42a4baca6a0c40d6aabe63b74e0","datavalue":{"value":"\\textit{P. Erd\u0151s} and \\textit{G. Szekeres} [Compositio Math. 2, 463-470 (1935; Zbl 0012.27010)] showed that any permutation of length \\(n \\geq k^2 + 1\\) contains a monotone subsequence of length \\(k+1\\). As a variation of this problem the following question is raised: If \\(n \\geq k^2 + 1\\), then there is at least one monotone subsequence of length \\(k+1\\); how many such sequences must there be? An upper bound on the minimum number of \\((k+1)\\)-subsequences is obtained by a simple example. It is conjectured that this bound is tight which is proven for \\(k=2\\), with a complete characterisation of the extremal permutations. Different from the case \\(k=2\\), computational experiments indicate that for \\(k>2\\) the extremal permutations have all \\((k+1)\\)-subsequences in the same direction (i.e., all ascending or all descending, respectively) if \\(n \\geq k(2k-1)\\), except for the case \\(k=3\\) and \\(n=16\\). Under this condition it can be shown that the above bound is still tight, and the extremal permutations containing the minimum number of monotone \\((k+1)\\)-subsequences are characterised. It is conjectured that extremal permutations indeed have all \\((k+1)\\)-subsequences in the same direction if \\(n \\geq k(2k-1)\\), except for \\(k=3\\) and \\(n=16\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1856066$463D1306-5481-468D-A3EC-5CCADD2C8848","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cd82a38b4fa9f2b7fd7dde601f94fd2c96d5a6ee","datavalue":{"value":{"entity-type":"item","numeric-id":227996,"id":"Q227996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1856066$8279A9D2-E269-4D0B-AE3B-F44F96E43934","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1856066$53CE1855-4C98-4AED-9686-D9DF2B4F5DCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b4b251e34f965e85a4a30c5d646e0bae1192967","datavalue":{"value":"05D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1856066$3C02FFA4-2210-4C9B-B8A9-A1EA241547A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1856066$FAE0DFE2-8FAD-4D2C-B2AD-2F3818D9311F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b006a483c4a064ec3048d77a9a24b874bd080534","datavalue":{"value":"1861456","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1856066$5E40A7A1-C56C-4B1A-87BA-4CAC61E71F7A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2298204374653d20fda8fe5f6687bd7bdc0afa6f","datavalue":{"value":"monotone subsequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1856066$5B125A8D-40D4-41CA-BD75-CB15619E9716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cdcc858e642c37f46f6fa377f2e2634fe466a35","datavalue":{"value":"permutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1856066$A31E9244-6B5C-4D2C-A58F-F6F143512464","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":"Q1856066$2CBEE694-E09A-4B26-A64C-2F87903C6183","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"217df4ac3c9cb3e9fdb046896d9fa6f8b4c8cb34","datavalue":{"value":{"entity-type":"item","numeric-id":1239159,"id":"Q1239159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e185fc5b73547dc2e9d7af6d04e708f59f7361a","datavalue":{"value":{"amount":"+0.8018121","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1856066$F8CC1AA1-3B5C-432B-BD80-12D0D4CE1F21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7381cdc2ade8abd1bf27fe3d7c4b3235e5c7c84","datavalue":{"value":{"entity-type":"item","numeric-id":294635,"id":"Q294635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ab6005afdee2f9db4a29846ed1d98efeeed8e5b","datavalue":{"value":{"amount":"+0.78715533","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1856066$FAB7A961-40D2-474A-9827-40447AEDEA36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43191e4ecd373f92f5a2069f566c65ae0b5645ff","datavalue":{"value":{"entity-type":"item","numeric-id":2831890,"id":"Q2831890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc5a492a70070490629ae7cfcc9c8b689f6c9642","datavalue":{"value":{"amount":"+0.7860998","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1856066$3ED92DD2-B0F0-41DF-A60F-D8AA228E19B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16f7205bf64d35a2bd76aae4c863c371f2a42af4","datavalue":{"value":{"entity-type":"item","numeric-id":293263,"id":"Q293263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8642b7e8f10707cbeb00d0c8cb7dad67f63a43c3","datavalue":{"value":{"amount":"+0.77667904","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1856066$9D9759C7-7C37-43BC-9502-C9551EDBF62C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d197b60e9038805ff98fb353886a6652519d813","datavalue":{"value":{"entity-type":"item","numeric-id":4601054,"id":"Q4601054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85a2243070d634b508dea1e1e58873fb4471a0ba","datavalue":{"value":{"amount":"+0.7730737","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1856066$3BFB90AF-DFC9-4706-BA5A-E2ABFF7BCF2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca309c61720e815935a400f2111053c87e9aaa27","datavalue":{"value":{"entity-type":"item","numeric-id":5060113,"id":"Q5060113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85737a534f19d0a3218ed873cdedeb307728f4f7","datavalue":{"value":{"amount":"+0.77045995","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1856066$384A9966-5AFE-48DE-AE5F-689169B2C5CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"265b412535c5cb27eb5e2d484ffd2e1e81cd2a94","datavalue":{"value":{"entity-type":"item","numeric-id":5364246,"id":"Q5364246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f77df23bac9967a291e543cb4a01ac067155790","datavalue":{"value":{"amount":"+0.7625411","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1856066$CFBAE517-D34A-404E-AE04-BB5BB6C98020","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4f51f297bb0be1d9d6a9a80435e822dadf4b1b2","datavalue":{"value":{"entity-type":"item","numeric-id":490988,"id":"Q490988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b4388e5dd91a332ce8be46936eec60282c7db37","datavalue":{"value":{"amount":"+0.7576001","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1856066$A2E6926E-192C-4384-B4D9-95FC1D78C79C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f157d773a113fb97966060e5efb221d029be1297","datavalue":{"value":{"entity-type":"item","numeric-id":5421713,"id":"Q5421713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99a5bf05fc2707eec1dc646a9ae09b6e457ab780","datavalue":{"value":{"amount":"+0.7537571","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1856066$695612C3-AF98-4326-AAC2-1E89499FAC91","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"91776e51b928c689a7cc2d986da44c16808c9878","datavalue":{"value":"bafkreicmvm2y4tsivso64w3m6whn5apsbg24jagbcx3wamurll7n3z6yoe","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1856066$B64362E0-7C7E-41DC-8759-71D43165A803","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The minimum number of monotone subsequences","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_minimum_number_of_monotone_subsequences"}}}}}