{"entities":{"Q2517665":{"pageid":2528408,"ns":120,"title":"Item:Q2517665","lastrevid":55880752,"modified":"2026-02-20T19:05:36Z","type":"item","id":"Q2517665","labels":{"en":{"language":"en","value":"A relationship between generalized Davenport-Schinzel sequences and interval chains"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6476273"}},"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":"Q2517665$E23EAF2C-589A-40FA-B79F-A6FB11D6F4D2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4281e66a423095c45aab62d8b3b64426b0fee2d3","datavalue":{"value":{"text":"A relationship between generalized Davenport-Schinzel sequences and interval chains","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2517665$E61DB2ED-B7B7-449D-9E0E-060D806718BA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e4e3275c10a37f3b981f0038872a7ba22efb2975","datavalue":{"value":"1319.05008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2517665$69D29750-4E71-4966-B649-85560CC8BB8B","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":"Q2517665$89D544E8-260D-4A7F-9CBC-8DD25206B212","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f5d7e575ce06abec1e01331d693d8d1b08ceff3b","datavalue":{"value":{"time":"+2015-08-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2517665$056E8340-F164-4CA6-A9AA-BF99E183DE88","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"82a0afe09c27a811ca41cb110d11fc55fbaaa968","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p19","type":"string"},"datatype":"url"},"type":"statement","id":"Q2517665$D47BADDF-5AFC-49B1-A686-A049D727322F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7d6029c9e0ff3fdcadecb293a7ba8bf387aabfc0","datavalue":{"value":"Summary: Let an \\((r, s)\\)-formation be a concatenation of \\(s\\) permutations of \\(r\\) distinct letters, and let a block of a sequence be a subsequence of consecutive distinct letters. A \\(k\\)-chain on \\([1, m]\\) is a sequence of \\(k\\) consecutive, disjoint, nonempty intervals of the form \\([a_{0}, a_{1}] [a_{1}+1, a_{2}]\\dots[a_{k-1}+1, a_{k}]\\) for integers \\(1 \\leq a_{0} \\leq a_{1} <\\dots< a_{k} \\leq m\\), and an \\(s\\)-tuple is a set of \\(s\\) distinct integers. An \\(s\\)-tuple stabs an interval chain if each element of the \\(s\\)-tuple is in a different interval of the chain. \\textit{N. Alon} et al. [in: Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, January 20--22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 1194--1203 (2008; Zbl 1192.68812)] observed similarities between bounds for interval chains and Davenport-Schinzel sequences, but did not identify the cause. We show for all \\(r \\geq 1\\) and \\(1 \\leq s \\leq k \\leq m\\) that the maximum number of distinct letters in any sequence \\(S\\) on \\(m+1\\) blocks avoiding every \\((r, s+1)\\)-formation such that every letter in \\(S\\) occurs at least \\(k+1\\) times is the same as the maximum size of a collection \\(X\\) of (not necessarily distinct) \\(k\\)-chains on \\([1, m]\\) so that there do not exist \\(r\\) elements of \\(X\\) all stabbed by the same \\(s\\)-tuple. Let \\(D_{s,k}(m)\\) be the maximum number of distinct letters in any sequence which can be partitioned into \\(m\\) blocks, has at least \\(k\\) occurrences of every letter, and has no subsequence forming an alternation of length \\(s\\). \\textit{G. Nivasch} [J. ACM 57, No. 3, Article No. 17, 44 p. (2014)] proved that \\(D_{5, 2d+1}(m) = \\Theta( m \\alpha_{d}(m))\\) for all fixed \\(d \\geq 2\\). We show that \\(D_{s+1, s}(m) = \\binom{m- \\lceil \\frac{s}{2} \\rceil}{\\lfloor \\frac{s}{2} \\rfloor}\\) for all \\(s \\geq 2\\). We also prove new lower bounds which imply that \\(D_{5, 6}(m) = \\Theta(m \\log \\log m)\\) and \\(D_{5, 2d+2}(m) = \\Theta(m \\alpha_{d}(m))\\) for all fixed \\(d \\geq 3\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517665$D776F160-BBFB-41EC-9AB6-D8326E9535D9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2517665$1CCB38B1-220A-44AE-AF18-AF312E120B6D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6b3d01f68f1e9d80e86817b935b49b90e83652ff","datavalue":{"value":"6476273","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2517665$6CD3240D-D4D3-4662-8700-451955A9E4BF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a27cd7b4224d8a8b50cfca6a9aaac10e3dd6c0e7","datavalue":{"value":"alternations","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517665$084E8F8B-EE7A-4872-BD39-4FE78377AE6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"933771fc3803877d94fc9a3700c9c1cb05fc298f","datavalue":{"value":"formations","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517665$2C16BB6D-511A-4F46-9A2F-8D37C9FAE697","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1e866a56049d4a9e216c228366aba6f6513d5b0","datavalue":{"value":"generalized Davenport-Schinzel sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517665$FD8EB5AC-1F02-4662-B2DE-4D09FAA0AE05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"30f3f97b46df4a2e74c13107c07603a49d31b517","datavalue":{"value":"interval chains","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517665$9B5B12B6-21BF-44DB-9A11-B558AC8F6A05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849cc51825e89b579c4613d5e01150c80e2a9275","datavalue":{"value":"inverse Ackermann functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517665$18EFD926-7B6D-47AD-A8CD-C701F67FCD06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d4ce0d50ef2d3fddc856fbf9944536f0e151c35f","datavalue":{"value":"permutations","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517665$0A02A516-4CBC-4B2C-8752-56F430AA9246","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"48689c3e021df08de04162a27b34e006b36dd085","datavalue":{"value":{"entity-type":"item","numeric-id":1040838,"id":"Q1040838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517665$87DA756A-AA6E-471E-A306-B6E90EDE3F13","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":"Q2517665$6A552E8C-6DB1-43A3-A666-EE744463C0C4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf78f24dc9967d0a6148cbfe129076e5e338f2c7","datavalue":{"value":{"entity-type":"item","numeric-id":4325546,"id":"Q4325546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517665$192C0939-C37C-4E12-A797-A5AF1E7EADC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ad6a447ed415489e99550ada5d106e44638f0b1","datavalue":{"value":{"entity-type":"item","numeric-id":911595,"id":"Q911595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517665$F230696E-2D4A-4FE2-9561-0FD6987CE6C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a0939623878f6b81e057dc2445e3611b4dea2d1","datavalue":{"value":{"entity-type":"item","numeric-id":3579389,"id":"Q3579389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517665$C615BC88-F6CB-42FE-8C97-CB72AACB5B90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36533bb00a296428bd93114194d22b7089e94634","datavalue":{"value":{"entity-type":"item","numeric-id":439058,"id":"Q439058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517665$FB267863-CF2E-42D6-BA80-99F62D873987","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":"Q2517665$3698B17B-DAA7-4BC8-B375-407FCA7A67E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6b95d315981609a84ebfa01f95f8f1666479596","datavalue":{"value":{"entity-type":"item","numeric-id":5300510,"id":"Q5300510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517665$C25584DD-EF66-4ECD-BBF2-5B2FCBDC6FA0","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":"Q2517665$62685393-EFF9-423A-B36F-BC1F595C9FD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"201f81637d81b2a961cfae9f81bf87bee08d6a66","datavalue":{"value":{"entity-type":"item","numeric-id":3137399,"id":"Q3137399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517665$DF510884-779C-4365-9953-F32653596AAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c73a7c5807ec65edc3a4e99d90c6487b978833b5","datavalue":{"value":{"entity-type":"item","numeric-id":4263474,"id":"Q4263474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517665$A80916B7-0AF1-4C27-A8D7-81B9413AD1B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"743c8062e07d18cd64ec304f9ff8ddbc241d0b7d","datavalue":{"value":{"entity-type":"item","numeric-id":3578194,"id":"Q3578194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517665$7187B468-9AE9-43E2-923E-8D703CBD48F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0e78b1f00892cec946b04d0283b98cce7038878","datavalue":{"value":{"entity-type":"item","numeric-id":409347,"id":"Q409347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517665$D7939AD0-7AF1-49F9-9CCA-43E31C25B902","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6dd6b3be73adf34e20356eb2431b3ddc29386f1f","datavalue":{"value":{"entity-type":"item","numeric-id":5174492,"id":"Q5174492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517665$1663A297-E565-4CD5-BE6C-DD22B7E0DE47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1368d1b906d8e2960e7fc869129f76b5828ec2a8","datavalue":{"value":{"entity-type":"item","numeric-id":5363086,"id":"Q5363086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517665$9D78F859-8A33-47F0-9921-69A3219C156F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92f6b5a3ffd3132ceebbbaa75410a299d1fe362c","datavalue":{"value":{"entity-type":"item","numeric-id":1193537,"id":"Q1193537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517665$E08630EB-813E-484B-8620-3E07B9B8193B","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"22b9740137a47ef82dd33fe9955a14309ab69eb9","datavalue":{"value":"bafkreibowcyjpsr3x6iztbkdahq3judm54bbky5f3xxnmfjdn66wm7viky","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2517665$39B198FD-F07E-431F-9B3F-C84A347A6E2E","rank":"normal"}],"P1643":[{"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":"c1bcaff0cce3187d32427616f11a8bc549b14d3a","datavalue":{"value":{"amount":"+0.7959107160568237","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":"Q2517665$6C9E7D33-2BC7-4D11-8521-B9993ED47407","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":"7c5c220adbda790b6b5db9ba4be36837d51eef50","datavalue":{"value":{"amount":"+0.7948302030563354","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":"Q2517665$9F269D30-9A05-4DC8-A135-E148111BB966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d8a1f8eac8248b7a2ed8d31c3019338ea7b90a8","datavalue":{"value":{"entity-type":"item","numeric-id":3452162,"id":"Q3452162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdf63843da8f399f53b30dfca3099d42a0ac993c","datavalue":{"value":{"amount":"+0.7926080226898193","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":"Q2517665$8CE8B96D-ABA5-4377-AB60-CBA4B8816597","rank":"normal"},{"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":"75ae58451f1f2643e4da1f9e08139addf9c3c9d0","datavalue":{"value":{"amount":"+0.787602961063385","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":"Q2517665$72F200DC-84AF-4F03-B009-9F400868B32D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"908ee1fc4c5902b8143886a0897c38047aa92696","datavalue":{"value":{"entity-type":"item","numeric-id":5363086,"id":"Q5363086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93c960cbf01fc2611cae21531aa2d0411ebc09af","datavalue":{"value":{"amount":"+0.7838537096977234","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":"Q2517665$29AE96AF-0E10-4999-A601-54D356239110","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2517665","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2517665"}}}}}