{"entities":{"Q1090686":{"pageid":1101438,"ns":120,"title":"Item:Q1090686","lastrevid":66431070,"modified":"2026-04-12T10:02:16Z","type":"item","id":"Q1090686","labels":{"en":{"language":"en","value":"Regressions and monotone chains. II: the poset of integer intervals"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4008440"}},"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":"Q1090686$5055FB20-FCA0-4EDA-9CC5-46EE3F732F1D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6a1f0abac5008be884b32f73a24ee2d35e91df35","datavalue":{"value":{"text":"Regressions and monotone chains. II: the poset of integer intervals","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1090686$32E9E2CC-109F-4938-B62C-F3DF85A75B3D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ed04b4d4b81cc7cae2ec6b584fe8c5eabd8a41c8","datavalue":{"value":"0622.05047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090686$8834A79B-02AF-4869-A859-4BCD8797ED44","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c77de10d2377a41ae194330e6954834be2f3e666","datavalue":{"value":"10.1007/BF00337694","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090686$5D46FFD8-3F4E-4F38-8C1C-47EA7AD9951C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7a539e6b59a5781e06906f6b0f6a357a21edb017","datavalue":{"value":{"entity-type":"item","numeric-id":792346,"id":"Q792346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090686$8D4DB44C-5420-4B59-B0C8-158223512AC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4d4c73f0a1fcfa77f8c56f84fd9c0566fb0d581","datavalue":{"value":{"entity-type":"item","numeric-id":185079,"id":"Q185079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090686$7401F677-7BDF-4200-A63F-3EB3728953F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c61d0b4df374523ec5b59f8a7d6c81266878fe30","datavalue":{"value":{"entity-type":"item","numeric-id":178698,"id":"Q178698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090686$D1D3D140-2029-436A-B03F-45A9CEB4EFF4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e2599ed8061d57585b4363072a1afceea2452436","datavalue":{"value":{"entity-type":"item","numeric-id":172073,"id":"Q172073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090686$38B8AEF9-9DD2-4837-A137-B85D1E44441D","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":"Q1090686$FE8A32F7-614A-4AA6-8D8A-10F03E612CF7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"81011cfe0976b30cd8aa7fc8a327da1aca9d9c12","datavalue":{"value":"[For part I see \\textit{D. B. West, W. T. Trotter} jun., \\textit{G. W. Peck} and \\textit{P. Shor}, Combinatorica 4, 117-119 (1984; Zbl 0541.05045).]    A regressive function (also called a regression or contractive mapping) on a partial order P is a function \\(\\sigma\\) mapping P to itself such that \\(\\sigma\\) (x)\\(\\leq x\\). A monotone k-chain for \\(\\sigma\\) is a k-chain on which \\(\\sigma\\) is order-preserving, i.e., a chain \\(x_ 1<...<x_ k\\) such that \\(\\sigma (x_ 1)\\leq...\\leq \\sigma (x_ k)\\). Let \\(P_ n\\) be the poset of integer intervals \\(\\{i,i+1,...,m\\}\\) contained in \\(\\{\\) 1,2,...,n\\(\\}\\), ordered by inclusion. Let f(k) be the least value of n such that every regression on \\(P_ n\\) has a monotone \\(k+1\\)-chain, let t(x,j) be defined by \\(t(x,0)=1\\) and \\(t(x,j)=x^{t(x,j-1)}\\). Then f(k) exists for all k (originally proved by D. White), and \\(t(2,k)<f(k)<t(e+\\epsilon_ k,k)\\), where \\(\\epsilon_ k\\to 0\\) as \\(k\\to \\infty\\). Alternatively, the largest k such that every regression on \\(P_ n\\) is guaranteed to have a monotone k-chain lies between \\(lg^*(n)\\) and \\(lg^*(n)-2\\), inclusive, where \\(lg^*(n)\\) is the number of applications of logarithm base 2 required to reduce n to a negative number. Analogous results hold for choice functions, which are regressions in which every element is mapped to a minimal element.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090686$F62C6B37-C4DE-4D5A-9AEE-6F390BF3F2C7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090686$04FCDF05-50F6-4F3E-BFCB-DE25068F79BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090686$92F20294-CCEE-4FC2-85DF-83D75CC0040A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d2bd3c66467c5356dcbc319257202f980ff6dcc","datavalue":{"value":"62J02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090686$F7DE652C-736A-49C6-A895-B8793BFEB03C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0bd7c01a852883692c5d771741ea2c007ae6d986","datavalue":{"value":"4008440","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090686$8F545FF3-2456-417E-81DB-93DB81ACE7FA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88f9e038ce90ce67b356cbe14c3c3f15dfb789be","datavalue":{"value":"Ramsey theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090686$BE00EFBA-2B7B-4DDA-82F9-ED2D92919D2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b44d3fde5ad4527d741a93773ec397ddf0efc3d8","datavalue":{"value":"regression","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090686$24D020B5-8770-4017-88AD-2D620075C4DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bea519f64ea7a1327827697949d75a20a83ef6ec","datavalue":{"value":"contractive mapping","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090686$8BFE85B9-B3B4-4AEF-A183-8522AAAB916E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad974574d2590d1233c0e161dd5582619a00ae12","datavalue":{"value":"choice functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090686$0D24AE3C-6CDF-4FD6-94D8-43940CF2D4DA","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":"Q1090686$DB9E5B0E-5635-47FE-A7EF-EB0BAC911C41","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"09c3046a8a2e3350396a0b97510cc6958bb659c8","datavalue":{"value":{"entity-type":"item","numeric-id":5966942,"id":"Q5966942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090686$81B35AB9-CC52-4A31-8001-78154A2FEBD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"529efdc1de11e511269b48c0db37e613f7622770","datavalue":{"value":{"entity-type":"item","numeric-id":5573406,"id":"Q5573406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090686$1E368CB3-39B1-41EC-91D4-4E0991C6490F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb04ee143a1e603fa0096cd64938e27e91d9490","datavalue":{"value":{"entity-type":"item","numeric-id":1164629,"id":"Q1164629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090686$4E3654A1-D599-45F1-9F4E-3F0209C42F9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67585c4cd5d4241c9bf7bb768b9576770c774303","datavalue":{"value":{"entity-type":"item","numeric-id":1838478,"id":"Q1838478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090686$F8DD21D9-C72B-4852-B1A1-609CAE3509B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1435873963d167384cbb0bd216bfc3f359f542ae","datavalue":{"value":{"entity-type":"item","numeric-id":5635449,"id":"Q5635449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090686$F1C7F5CF-1EF0-477E-B3D1-20368CD52728","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090686$5C3FA311-9CFA-4467-8733-319F7ADEDC2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aaf515d8a713abdb193da2f9bd34658fa84e67ef","datavalue":{"value":{"entity-type":"item","numeric-id":5532564,"id":"Q5532564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090686$6A2EA835-6222-4228-9F63-D7717F6EE01E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84bf8881d124841f5bf0ab699044dd95fdce70c6","datavalue":{"value":{"entity-type":"item","numeric-id":5634002,"id":"Q5634002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090686$B85CC572-2452-44B6-AA2E-19FC60850F3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e3a6567a47aa4fd048e36733ade20dd59ac706d","datavalue":{"value":{"entity-type":"item","numeric-id":791524,"id":"Q791524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090686$FD3B3DDC-106D-4E9F-AEEA-D8179BCBB289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19325a5bed0c5e36634c76c5bc44805d78459419","datavalue":{"value":{"entity-type":"item","numeric-id":5525396,"id":"Q5525396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090686$40786A81-AB25-48EA-8419-C5CB3EBD7A20","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1489ea74446dac70988aa29a875e4055b5797559","datavalue":{"value":"https://doi.org/10.1007/bf00337694","type":"string"},"datatype":"url"},"type":"statement","id":"Q1090686$ECD1A647-BD4F-4321-9B06-6F22C6DF93C9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d12b5e9f2dd14bd23073c262a3ecde46d5c9a847","datavalue":{"value":"W2125391905","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090686$82D1531F-39E1-4C9C-BD45-28CD4BA1CB00","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e17997d39d214e71e68d1a677d8e802a9787768","datavalue":{"value":{"entity-type":"item","numeric-id":794668,"id":"Q794668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a97f2dacc17484f5cd0dd87e201bb1dcafd5092f","datavalue":{"value":{"amount":"+0.8376798629760742","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":"Q1090686$9B3765E5-003D-4FB9-9B22-6BF3E61310F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84124dd95e349e12ff671616475c8e89f8085e73","datavalue":{"value":{"entity-type":"item","numeric-id":966137,"id":"Q966137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"759b05a80e6800dab646cbe81ebf7edf11cea2b3","datavalue":{"value":{"amount":"+0.7332825660705566","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":"Q1090686$C47982B5-8944-4124-BE91-E8BEE8B1EFF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8aba2f6a70105ba87cfb0827e9094a6512a2d39b","datavalue":{"value":{"entity-type":"item","numeric-id":1057290,"id":"Q1057290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"030563b0a26c0864c830d38e7b560b518105e667","datavalue":{"value":{"amount":"+0.7268797159194946","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":"Q1090686$A0F10750-2454-43FE-A511-986EDE27A799","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8165616d9391b8cf3f0ae1b864e459ecaf24964f","datavalue":{"value":{"entity-type":"item","numeric-id":4669393,"id":"Q4669393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95f1ebd5042cd3fc523366c48daa459e1d4432ce","datavalue":{"value":{"amount":"+0.7080569267272949","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":"Q1090686$C573B8A3-1DC8-4FDC-95DC-3A06B0EE4520","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37370f26cdb322a7c3d475ff689939807478703d","datavalue":{"value":{"entity-type":"item","numeric-id":791524,"id":"Q791524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1219f41358d711f5f4e4d4007a3d0f7d8037bfee","datavalue":{"value":{"amount":"+0.7080026268959045","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":"Q1090686$AF4D4CF5-D5A0-4116-BED1-ACB4006BBCA7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Regressions and monotone chains. II: the poset of integer intervals","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Regressions_and_monotone_chains._II:_the_poset_of_integer_intervals"}}}}}