{"entities":{"Q276436":{"pageid":278203,"ns":120,"title":"Item:Q276436","lastrevid":60579066,"modified":"2026-04-10T17:50:36Z","type":"item","id":"Q276436","labels":{"en":{"language":"en","value":"A subexponential upper bound for the on-line chain partitioning problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6576805"}},"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":"Q276436$2AFF8543-55C5-4544-B044-C7120953A7B7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"02b4a160c4f4168c0b82628538fca3d9a480c254","datavalue":{"value":{"text":"A subexponential upper bound for the on-line chain partitioning problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q276436$380C08F9-ACBC-46FB-B188-6778F4B5ED86","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"919cb1db44cc82439d9556a42e6b72c0f15474fc","datavalue":{"value":"1349.68324","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q276436$05A45E98-8B63-4405-848C-F0A0D70C1D63","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"01ff5be92d121f7423ad3cd6c581778876c098c4","datavalue":{"value":{"entity-type":"item","numeric-id":251889,"id":"Q251889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$871303CF-21BF-4BBF-9CF5-9B478F93833C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"01d3f52cde17e115913ecc9ad5790fd561ea9dce","datavalue":{"value":{"entity-type":"item","numeric-id":276435,"id":"Q276435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$A03A2C10-045B-4617-B2D1-283B2024A95C","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":"Q276436$69717A9E-1149-4CA2-B53F-D2AE7C2B9B0C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e14340917da0b560f1aa784255616bd78a4a4ba6","datavalue":{"value":{"time":"+2016-05-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q276436$D50EEE05-0FB7-46A5-A8D0-CD474AE235D6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"819c7d3495d5ced417de604e0e99b23a3a682fe8","datavalue":{"value":"The online chain partitioning problem is a game between two players: Spoiler and Algorithm. In each round Spoiler introduces a new point to the poset and gives its relation to all existing points. Algorithm's task is to maintain a chain partition of the growing poset by incorporating the new point into one of the already existing chains or creating a new chain for the new point. Spoiler tries to build a poset to force Algorithm to use as many chains as possible, while Algorithm's task is to keep the number of chains as small as possible.  Let \\(\\text{val}(w)\\) denote the smallest number \\(n\\) for which Algorithm has a strategy that can partition any poset of width \\(w\\) into at most \\(n\\) chains. By Dilworth's theorem \\(\\text{val}(w)\\) would be \\(w\\) if the game were played off-line. For the on-line game the best upper bound so far is \\(\\text{val}(w) \\leq (5^w-1)/4\\) by \\textit{H. A. Kierstead} [Trans. Am. Math. Soc. 268, 63--77 (1981; Zbl 0485.03019)], the highest lower bound is \\(\\text{val}(w) \\geq (2-o(1))\\binom{w+1}{2}\\) from the survey paper by \\textit{B. Bosek} et al. [Order 29, No. 1, 49--73 (2012; Zbl 1259.06002)] which slightly improves E. Szemer\u00e9di's earlier lower bound of \\(\\binom{w+1}{2}\\).  The main result of the paper is that \\(\\text{val}(w) \\leq w^{13 \\log w}\\). The proof is by first reducing the chain partition problem to a so-called regular game, where Spoiler introduces certain antichains rather than points. In Lemma~3.1 it is proved that if Algorithm has a strategy for using at most \\(\\text{reg}(w)\\) colors for the on-line regular game of width \\(w\\), then  \\[ \\text{val}(w) \\leq \\text{reg}(1)+ \\dots + \\text{reg}(w). \\]  Second, the authors give a recursive algorithm for the on-line regular game and prove the recursion  \\[ \\text{reg}(w) \\leq 32\\left(1+\\binom{w^3+1}{2} \\right)(2w-1)w^5 \\text{val}(w/2) \\]  in Lemma~3.2. Putting the two lemmas together yields the desired upper bound for \\(\\text{val}(w)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q276436$9BED5899-619B-4354-83D5-A041249B2942","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2d5a866d412ef8af951814448fda0a03016cd3a5","datavalue":{"value":"68W27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q276436$93631ECD-637D-4732-A404-723B9B1DD83B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q276436$FE022C76-ACDD-45D6-A835-9FA56520006B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f3d0b1de78ad0e32d646815f9dc7561538cada7","datavalue":{"value":"06A07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q276436$4F686E47-3313-4606-B85F-BECC1AFF401A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"12aa5a8e48c202bfd950b287f0cdc8905a2a3388","datavalue":{"value":"6576805","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q276436$60AAD3AD-EACB-459C-9567-3FC891587061","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80b6ab4c1cd966e2c3c7723d9876f1cbe5352dfe","datavalue":{"value":"online algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q276436$1E6F35FE-4958-4F05-A3BD-F23BCDB191B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f6c3b663d924662e9382bc82c1bfd03ba68387a","datavalue":{"value":"chain partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q276436$02B065A4-A023-4ADA-BB3A-A1D0F5CAD462","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0da0f5147540e5ff9abe1a7fedfdb0d575bb38f3","datavalue":{"value":"partially ordered set","type":"string"},"datatype":"string"},"type":"statement","id":"Q276436$ED8F2EDC-BB1B-4A6F-A18A-2E7785DF7031","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":"Q276436$2DE438FE-7DC2-4029-942D-2B48CF17B5A5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d7031ac0e6d1939f2cc1bfb577af09f4b8b4c9b4","datavalue":{"value":"https://doi.org/10.1007/s00493-014-2908-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q276436$FE74216B-2FE5-41DD-B554-E49CF8E78D4F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ed4d7fe2687deed3fff0fe98c21c1e9e2a1b1b07","datavalue":{"value":"W2083080918","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q276436$96916E1C-39CE-44A0-A8DC-595DAD77B547","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fb9cdffaf992252163881e3e7160c54586bd51e","datavalue":{"value":{"entity-type":"item","numeric-id":2385526,"id":"Q2385526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$E3A41CCC-53B6-4A9F-9D2A-7693B7C410E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53ba7b88ff93079370405361d72352426c295644","datavalue":{"value":{"entity-type":"item","numeric-id":766153,"id":"Q766153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$82A9D8DC-6C6D-4175-9A5D-E9B65582F0E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a49c8a9cc267b848441d1d4a844f0384750952e","datavalue":{"value":{"entity-type":"item","numeric-id":5300485,"id":"Q5300485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$BD22F9E8-1CA0-4F0C-9412-E061895F481E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bb3cc4ba71acfd6e88195c2ac1a97ec1b7d47ea","datavalue":{"value":{"entity-type":"item","numeric-id":3058541,"id":"Q3058541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$00848D47-8A42-45B6-8DD7-3EC418923DDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b99910b69f934d3f01929d755ff012867327467","datavalue":{"value":{"entity-type":"item","numeric-id":2851690,"id":"Q2851690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$A07ADC4B-32CA-4BC7-ADC7-22FE0A06E96C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2765dda96b2fcb688aadcef0e89443df2020f9d9","datavalue":{"value":{"entity-type":"item","numeric-id":3830539,"id":"Q3830539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$8656417C-8308-4E07-B952-C5EDC0244EDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4cdcc4bfdabe8e7212fab98a736d6256e13c07b3","datavalue":{"value":{"entity-type":"item","numeric-id":4899045,"id":"Q4899045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$47DFD085-E289-4FF3-9E75-E5DA12FD600A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e6b9487c97fa26caa80f523e7121a1932537eb2","datavalue":{"value":{"entity-type":"item","numeric-id":1392205,"id":"Q1392205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$F6E14736-FC90-437E-AD80-09BE85F01AE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"337e5d5e3a3e208b83ed4c6fc26f77505f094e93","datavalue":{"value":{"entity-type":"item","numeric-id":1943698,"id":"Q1943698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$AFA7D969-5476-4072-8A6B-F35A71C1E3D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bf9cf6e9b9847b2f86a53ca6242f6d1280d5b09","datavalue":{"value":{"entity-type":"item","numeric-id":651432,"id":"Q651432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$09401BD1-A3F6-41CC-8A5C-9E39912DB4BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de43f3e978a9ce24db65e773f8fff3d02c7dc139","datavalue":{"value":{"entity-type":"item","numeric-id":3944587,"id":"Q3944587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$F7CC932E-4F49-49E7-AEA4-260E3EACA9FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"372721357012bc2636bb821681f4581980872fbc","datavalue":{"value":{"entity-type":"item","numeric-id":4722060,"id":"Q4722060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$D8C36381-AD03-4B0E-B258-B52E69A9CF06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"053ffe8d65e0994d475a368e3c3296b25479e09b","datavalue":{"value":{"entity-type":"item","numeric-id":2266723,"id":"Q2266723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$4563C479-0FFA-43FB-A3A2-3A6CD95BCDAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2774d605306950b14f1a4f728bb4dd0c7a5d9678","datavalue":{"value":{"entity-type":"item","numeric-id":691598,"id":"Q691598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$E94C60FC-E5E6-48C0-8FDE-668FBB3652EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b686b6561b404abd99050b38d4f468b71b973a86","datavalue":{"value":{"entity-type":"item","numeric-id":3950561,"id":"Q3950561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$609B1DDD-B027-4CC6-87BF-5D6C44399E54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"615931ac7b57fd43ffa56406b73f933d03a80da5","datavalue":{"value":{"entity-type":"item","numeric-id":4871756,"id":"Q4871756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276436$18432E3C-65DF-4EFA-96C4-C64F07EA73A5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ab092e3ef84443d175e319d402b512afde9d8f7b","datavalue":{"value":"10.1007/S00493-014-2908-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q276436$A144B16E-F5FC-493B-AF0B-0FF958CABEB7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f44742cb727033a9cce80ba7111f274de36343ed","datavalue":{"value":{"entity-type":"item","numeric-id":766153,"id":"Q766153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e85dd705853bcdf84c7771c5410ae4f36641054f","datavalue":{"value":{"amount":"+0.9234804511070251","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":"Q276436$6DA39289-327C-4827-8259-ABD07A3F63AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4e9bbe8d3a316b3fa82e99a034e24d7bedd75cb","datavalue":{"value":{"entity-type":"item","numeric-id":3058541,"id":"Q3058541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67a428ea0fcb7e2bebdb776c1824cca116c16bcd","datavalue":{"value":{"amount":"+0.9207459688186646","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":"Q276436$8059B23F-A2EE-46A8-9A37-28A7292A6520","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"979e99c235df3d6a656cfe09a231c2913c55715f","datavalue":{"value":{"entity-type":"item","numeric-id":1392205,"id":"Q1392205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05b2ee97bc93f038e3cb646f89cf1c752d5ac79d","datavalue":{"value":{"amount":"+0.8931615352630615","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":"Q276436$D7E01247-6EEF-4B6E-91E8-9DC4627B6233","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fddc858b0e915ccb0c3fd821ab8793000a0e89a1","datavalue":{"value":{"entity-type":"item","numeric-id":1753118,"id":"Q1753118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78a8fd0a126dd989aca0609a9cfdc2a18f2adb33","datavalue":{"value":{"amount":"+0.8856107592582703","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":"Q276436$73AAB747-886C-4807-B640-26829280454C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcf60c1c699016cbf83b18311d54033a9e4b14e0","datavalue":{"value":{"entity-type":"item","numeric-id":1943698,"id":"Q1943698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e6b774b9ec4469056a1b69cafb139231d614d87","datavalue":{"value":{"amount":"+0.8768723011016846","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":"Q276436$D1B2BCE5-4610-4E8A-AF28-50E740EA362A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A subexponential upper bound for the on-line chain partitioning problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_subexponential_upper_bound_for_the_on-line_chain_partitioning_problem"}}}}}