{"entities":{"Q1097885":{"pageid":1108637,"ns":120,"title":"Item:Q1097885","lastrevid":70305732,"modified":"2026-04-13T13:52:31Z","type":"item","id":"Q1097885","labels":{"en":{"language":"en","value":"Almost linear upper bounds on the length of general Davenport-Schinzel sequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4035840"}},"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":"Q1097885$BDBCEB2C-166E-451D-AE62-9ACEB2AF205D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b162f8d6753f6f36a0e5c2a7511c001373cf90ba","datavalue":{"value":{"text":"Almost linear upper bounds on the length of general Davenport-Schinzel sequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1097885$C4FB4A16-4C9B-402A-9200-4CD16D800557","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"68c8de710887c2d7a2d0482a8166865e817ce83d","datavalue":{"value":"0636.05004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097885$4B22CB04-4A8B-4692-A67A-B3588D83957F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4ed7308d90e36d41e2df4ee7f65a1d814fdb05fc","datavalue":{"value":"10.1007/BF02579209","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097885$A60F3F46-9E27-4CB0-84B4-638232EC3B3D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"05973d4747711a904c4eb354f325fda834906623","datavalue":{"value":{"entity-type":"item","numeric-id":396765,"id":"Q396765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097885$E4DD6A69-61F8-4AE7-814F-C7D304BFDA83","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097885$236D6DB5-B680-4B06-9DDF-7E4067331276","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1097885$3216656E-2F70-4B05-B115-A8897345C5B1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8fdc800f19786abdffcf4853ebf6684f421ff6e8","datavalue":{"value":"(n,s)-Davenport-Schinzel sequences are sequences that are composed of n symbols, and are such that (i) no two adjacent elements are equal, and (ii) there does not exist a (not necessarily contiguous) alternating subsequence of length \\(s+2\\) of the form a...b...a...b... for any two distinct symbols a and b. Davenport-Schinzel sequences arise in the computation and analysis of the lower or upper envelope of a set of functions, and are thus a powerful and versatile tool for a variety of problems in combinatorial and computational geometry. This paper establishes almost linear upper bounds on the maximum length \\(\\lambda_ s(n)\\) of (n,s) Davenport-Schinzel sequences. These bounds are of the form \\(O(n\\alpha (n)^{O(\\alpha (n)^{s-3})})\\), and they generalize and extend the tight bound \\(\\Theta\\) (n\\(\\alpha\\) (n)) obtained by \\textit{S. Hart} and the author [ibid. 6, 151-177 (1986; see above, Zbl 0636.05003)] for the special case \\(s=3\\) (\\(\\alpha\\) (n) is the extremely slowly growing functional inverse of Ackermann's function), and also improve the upper bound O(n log *n) due to E. Szemeredi (1974).    The results of this paper have later been slightly improved by Agarwal, Sharir and Shor (1988), who have shown that  \\[  \\lambda_{2s}(n)=O(n\\cdot 2^{O(\\alpha (n)^{s-1})}),\\quad for\\quad s\\geq 2,\\quad \\lambda_{2s+1}(n)=O(n\\cdot \\alpha (n)^{O(\\alpha (n)^{s-1})}),\\quad for\\quad s\\geq 2.  \\]  Moreover, these bounds are almost tight for even s, because  \\[  \\lambda_{2s}(n)=\\Omega (n\\cdot 2^{\\Omega (\\alpha (n)^{s- 1})}),\\quad for\\quad s\\geq 2. \\]","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097885$2000E534-8FA0-47E8-94E4-4C6AC2A61F14","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"880665e99fe5de07999ef2f74a810b36dd3dabed","datavalue":{"value":"05A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097885$A229ED12-B79E-4F39-AC96-8F10877FD0A5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"83e7e36d1fef90a19e06ccafccfe5039696c6cae","datavalue":{"value":"4035840","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097885$84F0DB54-74D7-4376-8936-F96710218E47","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"900572492ff0b9c514cba808fa7fe3539b0c1cb0","datavalue":{"value":"Davenport-Schinzel sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097885$D8E1D952-B3F0-4038-82BE-7424FAA285CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df30d260a0a8299eca168bbaab05f7b67ba40127","datavalue":{"value":"forbidden subsequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097885$E200DE9D-0261-4E49-9711-C039B5A051B3","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":"Q1097885$CA2C307A-DC2F-44B0-9F3E-B171489AA672","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7f962d4b7bceadb914a43cc05d640fec4e9860f","datavalue":{"value":{"entity-type":"item","numeric-id":5619850,"id":"Q5619850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097885$E1FA8B9B-D64A-453E-A5BE-1E8323350261","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":"Q1097885$B13D8D98-754C-4471-80C9-AF3B0C1354C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c368a550cf5b4e92a6d4f0e58d9ca1eb20b223cd","datavalue":{"value":{"entity-type":"item","numeric-id":1097884,"id":"Q1097884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097885$19A1F85A-A803-41F7-BA4B-216571238C67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d833ab673ebd20a91b14b64621d6d105390ebc3","datavalue":{"value":{"entity-type":"item","numeric-id":5618381,"id":"Q5618381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097885$CEF173A4-0A5E-4A72-AD44-3BB7D9D4B7AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"932383d1ac997ed208ef47dcb574b592efaf75b3","datavalue":{"value":{"entity-type":"item","numeric-id":4065031,"id":"Q4065031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097885$9C646110-27F3-408C-9E8C-B027D65D0095","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9dad7f1692830906fef4c67ac576524086da90fc","datavalue":{"value":"https://doi.org/10.1007/bf02579209","type":"string"},"datatype":"url"},"type":"statement","id":"Q1097885$DC37DBC5-9646-445A-B642-FC0B21DFB07F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c2e79361bb382765004fe742613ddc4bf911a63b","datavalue":{"value":"W2077909149","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097885$0691765A-43E2-426F-A4FD-B48D5F42FEC6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbef73deca305c9a236cbe8af1d0206592f5c3c1","datavalue":{"value":{"entity-type":"item","numeric-id":911595,"id":"Q911595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8414652d46a9f131381aa22ccc5cdf560f57bef7","datavalue":{"value":{"amount":"+0.9332727193832396","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":"Q1097885$AEA95278-4622-433E-9DDE-D83F74737FF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f51da463431e60834a117135a61f94e9ec28121f","datavalue":{"value":{"entity-type":"item","numeric-id":4633804,"id":"Q4633804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b8725c42f9a39795b5c6f9e4c93d1da8e96b98c","datavalue":{"value":{"amount":"+0.923153042793274","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":"Q1097885$754FB4FA-7661-4C7E-8545-4BAA889FB3E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86413ba6be88481277107ac40b784fecca852057","datavalue":{"value":{"entity-type":"item","numeric-id":3578194,"id":"Q3578194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23ff0250392544a37c456bd9913a5c0bd3758238","datavalue":{"value":{"amount":"+0.917169451713562","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":"Q1097885$B06B2115-A879-4FD5-9843-83B4BD34984A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0aa87b16b07d9f20df1c8555f96fa072ac62bc70","datavalue":{"value":{"entity-type":"item","numeric-id":5174492,"id":"Q5174492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4aee79e13199f50625d118eec2d547ca95503d9","datavalue":{"value":{"amount":"+0.911579966545105","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":"Q1097885$C705C031-D752-4D69-862E-A7C318A31A56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9dc6880229342628a1986fb0acd06a192af8c10","datavalue":{"value":{"entity-type":"item","numeric-id":1119587,"id":"Q1119587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1244d748e2b8afa98bf302ef6c0a0dce56be787","datavalue":{"value":{"amount":"+0.9037508368492126","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":"Q1097885$C4EDF97A-0E65-4DB5-95D3-067B8F154D4E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Almost linear upper bounds on the length of general Davenport-Schinzel sequences","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Almost_linear_upper_bounds_on_the_length_of_general_Davenport-Schinzel_sequences"}}}}}