{"entities":{"Q691598":{"pageid":693447,"ns":120,"title":"Item:Q691598","lastrevid":63758994,"modified":"2026-04-11T15:21:23Z","type":"item","id":"Q691598","labels":{"en":{"language":"en","value":"On First-Fit coloring of ladder-free posets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6111995"}},"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":"Q691598$67C902FB-FC78-41DA-9DA1-DB4E85E014C7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"56173a56293ffe431f614b85567af94b68dea13a","datavalue":{"value":{"text":"On First-Fit coloring of ladder-free posets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q691598$51220442-1711-4CD2-BE7B-007E1AC61DBE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a8483549cb1a7603da47f672303a4692a70f082d","datavalue":{"value":"1288.06004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q691598$99DC8132-73E7-484F-91BE-61B4896D6D27","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c1a1b1249037fd5c62e7e3ca86183b63bb7d8ea2","datavalue":{"value":{"entity-type":"item","numeric-id":691597,"id":"Q691597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q691598$F5701733-6C46-4EFC-A732-603D39F9582E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e8e4763e432b6ffd9ef1ff20256862696bdf24ca","datavalue":{"value":{"entity-type":"item","numeric-id":555495,"id":"Q555495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q691598$A7CDBA0B-C618-4570-B73F-2137B42943A2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q691598$1886B671-58C4-43FF-8AED-5971E884E8E6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0fd3ad4961dd3b754cee18b6f99fcca42b4edd99","datavalue":{"value":{"time":"+2012-12-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":"Q691598$820214D8-BED8-40C8-AB50-4049CB36C6FD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"59ee7544972254a728c46aaccf2aed42ff37f796","datavalue":{"value":"A classical theorem by \\textit{R. P. Dilworth} [Ann. Math. (2) 51, 161--166 (1950; Zbl 0038.02003)] states that every finite partially ordered set (henceforth \\textit{poset}) of width at most \\(w\\) can be partitioned into \\(w\\) chains. This bound of \\(w\\) chains is tight. However, this bound of \\(w\\) cannot be achieved by an on-line partitioning, and the quest for such an on-line upper bound of the number of chains is ongoing. More precisely, an \\textit{on-line poset \\(P^{\\prec}\\)} is a poset \\(P = (V,\\leq_P)\\) together with a linear (or total) ordering \\((V,\\prec)\\) (representing the order of which a partitioning algorithm receives the elements of the poset.) Let \\({\\mathcal{P}}_w\\) denote the class of posets that have width at most \\(w\\), and let \\(\\mathrm{val}({\\mathcal{P}}_w)\\) denote the smallest upper bound on the number of chains that an on-line algorithm partitions a poset from \\({\\mathcal{P}}_w\\) into. The first sub-exponential bound for \\(\\mathrm{val}({\\mathcal{P}}_w)\\) was proved by \\textit{B. Bosek} and \\textit{T. Krawczyk} [``The sub-exponential upper bound for on-line chain partitioning'', in: Proceedings of the 51st annual IEEE symposium on foundations of computer science, FOCS 2010. Los Alamitos: IEEE Computer Society. 347--354 (2010; \\url{doi:10.1109/FOCS.2010.40})], who showed that \\(\\mathrm{val}({\\mathcal{P}}_w) \\leq w^{14\\lg w}\\). One of the simplest on-line chain partitioning algorithms is First-Fit (FF), which greedily assigns each new vertex \\(v_i\\) to the chain \\(C_j\\) with the least index \\(j\\) such that for all \\(h<i\\) if \\(v_h\\in C_j\\), then \\(v_h\\) is comparable to \\(v_i\\). For a poset \\(Q\\) let \\(\\mathrm{val}_{\\mathrm{FF}}(Q,w)\\) denote the smallest upper bound on the number of chains that a First-Fit on-line algorithm partitions a \\(Q\\)-free poset of width at most \\(w\\) into. A poset \\(L_m\\) is called an \\textit{\\(m\\)-ladder} if its vertices are two disjoint chains, \\(x_1 < \\cdots < x_m\\) and \\(y_1 < \\cdots < y_m\\), such that \\(x_i < y_i\\) for all \\(i\\in\\{1,\\ldots,m\\}\\) and \\(y_i\\) and \\(x_j\\) are incomparable for \\(i\\leq j\\leq m\\) (so the Hasse diagram of \\(L_m\\) looks like a ``skewed'' ladder, where for each \\(i\\in\\{i,\\ldots,m\\}\\) the step/bar between \\(x_i\\) and \\(y_i\\) goes down from \\(y_i\\) to \\(x_i\\) at a 45 degree angle.) The main theorems of the paper are then the following (in)equalities: (i) \\(\\mathrm{val}_{\\mathrm{FF}}(L_2,w) = w^2\\), (ii) \\(\\mathrm{val}_{\\mathrm{FF}}(L_m,2) \\leq 2m\\), and (iii) \\(\\mathrm{val}_{\\mathrm{FF}}(L_m,w) \\leq w^{2.5\\lg w + 2\\lg m}\\). The last inequality yields a basis for a simpler proof of the mentioned result of Bosek and Krawczyk, that \\(\\mathrm{val}({\\mathcal{P}}_w) \\leq w^{14\\lg w}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q691598$2DA7964B-121E-4717-8679-762B327B860D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"40a8c8304e09a825de719366905817f3f4c840d6","datavalue":{"value":{"entity-type":"item","numeric-id":368450,"id":"Q368450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q691598$6AC83452-70AA-4893-82EA-A16EF6107F73","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q691598$FB0FE075-DBFD-46D9-ACE3-53D0AD88C4C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2d5a866d412ef8af951814448fda0a03016cd3a5","datavalue":{"value":"68W27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q691598$5D045DC8-8D6A-4647-A907-0E681528CD8E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1bad11e31fee248d64e129533a4c807dcb7fd85c","datavalue":{"value":"6111995","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q691598$DA2E3E49-FB7D-46C6-9644-95ADA916F503","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":"Q691598$44D4C67A-379F-4A5E-AF45-2323DD6F9438","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2883e87dfcf37b058a535adf89847dc11f6c03b5","datavalue":{"value":"https://doi.org/10.1016/j.ejc.2012.07.007","type":"string"},"datatype":"url"},"type":"statement","id":"Q691598$4F61C608-B5B4-48DA-882A-C665C681A79B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"51933cdee7ea03145d537945177c2a01a5f0089d","datavalue":{"value":"W1971238463","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q691598$632F9D5C-CBF7-48D4-8496-FCC3051933F2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"348481ea4a61e1ffc914100057f0d5b724d0e65b","datavalue":{"value":"10.1016/J.EJC.2012.07.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q691598$257B925D-6D89-48E1-B0FF-72D245D0503A","rank":"normal"}],"P1643":[{"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":"5e754acad68ede142662794ee09a6633e8bc5d5e","datavalue":{"value":{"amount":"+0.8842207789421082","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":"Q691598$C4DD1FE7-B399-4519-AD8C-2C9C05501963","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":"c43497bd1490a9cf141a15dccfcc16b7ace4a219","datavalue":{"value":{"amount":"+0.8737157583236694","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":"Q691598$6B0B02FC-5C43-4049-9446-5DDF2ECA1018","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e08913b909afbbf0f94de89b497cc84cd9c419d5","datavalue":{"value":{"entity-type":"item","numeric-id":1943697,"id":"Q1943697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a32f0bc19196374c5f0717ecf83d72d564dc21e","datavalue":{"value":{"amount":"+0.8495878577232361","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":"Q691598$55D15525-D857-4CB0-8AE2-28B131C7D9E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c98e0faffe960d0892b5128979d3a27215e09a0f","datavalue":{"value":{"entity-type":"item","numeric-id":651432,"id":"Q651432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56d57532302ce74468fcd61a69022dd9f1736044","datavalue":{"value":{"amount":"+0.8349364399909973","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":"Q691598$4F25681D-0D6C-4D5C-8CDF-4EF796D1C9C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c18d476c9d2b90a9c3799bc806ad68a6b98338ad","datavalue":{"value":{"entity-type":"item","numeric-id":4899045,"id":"Q4899045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acaee789f173a5ed6246d65bb6ee67a85848ccd2","datavalue":{"value":{"amount":"+0.83187335729599","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":"Q691598$CD712F89-6C15-4FF6-99B4-2BACE3FBB8B7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On First-Fit coloring of ladder-free posets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_First-Fit_coloring_of_ladder-free_posets"}}}}}