{"entities":{"Q1789056":{"pageid":1799798,"ns":120,"title":"Item:Q1789056","lastrevid":57558408,"modified":"2026-03-31T09:52:43Z","type":"item","id":"Q1789056","labels":{"en":{"language":"en","value":"On an extremal problem for poset dimension"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6949477"}},"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":"Q1789056$3B54CADF-E9A0-4689-BF47-33D6250CD9FD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8ea0b957b9058b64c690c683a5a42c4549d0dfcb","datavalue":{"value":{"text":"On an extremal problem for poset dimension","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1789056$924EF3AE-0435-4C73-8481-84DA3EA16EDD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"23367efee0ef402af20aad3bcb1db4009b1302d0","datavalue":{"value":"1406.06004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1789056$7635CBB6-D826-4179-BE20-EEDD1080C6E5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1789056$8D88500F-7802-4B2D-8DB7-56ED7EFB8FE4","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":"Q1789056$4871DE77-997F-43FB-8072-474425531F36","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d6fb386ba4436b2fd380b04497cf42193d92b54c","datavalue":{"value":{"time":"+2018-10-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1789056$DDD10320-19F2-4AF6-AA5E-B05B268A2BE0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2fffba015b7c85c78982f0a0fbccb7018004a421","datavalue":{"value":"https://arxiv.org/abs/1705.00176","type":"string"},"datatype":"url"},"type":"statement","id":"Q1789056$BCAC2516-7261-4738-8FE2-17A01E56C3F3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"65129afb58e7dfc8cc3854b950dfd063c0113577","datavalue":{"value":"Every partially ordered set (poset) with \\(n\\) elements has either a chain or an antichain of size \\(\\sqrt{n}\\) by Dilworth's theorem, so has a subposet of dimension 2 of that size (recalling that the dimension of a poset is the smallest number of total orders on the ground set whose intersection is the poset in question). In the paper under review, the authors study \\(f(n)\\), the largest number such that every poset on \\(n\\) elements has a subposet on \\(f(n)\\) vertices with dimension 2 and concentrate on upper bounds on \\(f(n)\\).  The main result of the paper is that \\(f(n)\\leq 4n^{2/3}+o(n^{2/3})\\). The analogous question can also be asked for the largest \\(d\\)-dimensional subposet, call this \\(f_{d}(n)\\) (so that \\(f(n)\\) above is \\(f_{2}(n)\\)). The main result here is that \\(f_{d}(n)=O(n^{d/(d+1)})\\). The proof for \\(d=2\\) with the precise constant is short: the multiplicative 4 can be improved to 3, it seems unknown whether the exponent \\(2/3\\) can be improved. The proof for general \\(d\\) uses a multivariate generalisation of a result by \\textit{A. Marcus} and \\textit{G. Tardos} [J. Comb. Theory, Ser. A 107, No. 1, 153--160 (2004; Zbl 1051.05004)] which controls the number of 1 entries in a \\(\\{0,1\\}\\)-matrix that avoids a given permutation matrix.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1789056$201C9195-691F-48E0-A0FC-D347A4D99BAD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f3d0b1de78ad0e32d646815f9dc7561538cada7","datavalue":{"value":"06A07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1789056$B57258F8-C20B-4344-8AD8-F7370166240D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9bd9af688c0b97c53a0660570659cd00420d9c9b","datavalue":{"value":"05D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1789056$F1D3B1C1-454C-4B94-A47E-74EEFA18AC1F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"32ef9df0a8bdc13591bbc898f5bd96bc69a91855","datavalue":{"value":"6949477","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1789056$E98567B4-FAC0-4C6F-BF43-8A7456DB7B5B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bedf903784eeba0fa13d8545c010927ac8abaf15","datavalue":{"value":"partially ordered sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1789056$2891A5A8-19A2-4B88-8E64-DA2598E2F5AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"23cd9004e97bde5e05c0ec9563af2cfd60f80089","datavalue":{"value":"poset dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q1789056$6F61FB67-0FCF-4C56-B8B5-BC98793EB78F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39911c6eb3357797f71228694114dda795773934","datavalue":{"value":"extremal combinatorics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1789056$3D992365-B573-4F1D-A9B9-BDE42A0EAAB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18ee3a80cd5ac96e9cd588561d71f3861b4eedae","datavalue":{"value":"permutation matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1789056$1FAEBADD-486C-44F6-B801-5B9E64A39407","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b0b0cea8603b4de1ffd54cda6d37d129691a25c2","datavalue":{"value":{"entity-type":"item","numeric-id":590772,"id":"Q590772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1789056$BFFAAF68-ED95-4188-BDA8-2A384C95DF21","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"eecff7672d98ddd92e9f59bf72dece031571efe6","datavalue":{"value":{"entity-type":"item","numeric-id":35496,"id":"Q35496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1789056$0213B644-5421-4DEE-8D4A-1AF26DEDCE48","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":"Q1789056$8942EBBB-973E-46F4-B6ED-E8722D1D363E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"861c868f09252917d495af889d46bec568c0f256","datavalue":{"value":"W2611872613","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1789056$832B704B-F91F-4B45-8260-95D5C5ED8716","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"bdf9863adbf62362a50371745c97420128b8d799","datavalue":{"value":"Q59610173","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1789056$C1634D52-830A-463C-914E-4EFCC172D5C5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b4233d398f92b7310c2fba72ff7772b5a60457a","datavalue":{"value":{"entity-type":"item","numeric-id":2643869,"id":"Q2643869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1789056$9C9FE0E5-62C6-4CF2-BAC6-E9E2251DA793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50240b068b2f4e66fb8cd75d033da96637e75bdc","datavalue":{"value":{"entity-type":"item","numeric-id":598446,"id":"Q598446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1789056$86D75B2D-887B-46A5-B160-19FE777ACB6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1649f9016b10118dab8447742feb7ec483484f16","datavalue":{"value":{"entity-type":"item","numeric-id":5366963,"id":"Q5366963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1789056$764A2219-6A87-4EE3-BBC3-DABBD9FFE406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db782e9e5e41c106fe01470f053eaa3f07fa9c76","datavalue":{"value":{"entity-type":"item","numeric-id":5965144,"id":"Q5965144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1789056$4884A434-3A61-433E-8394-2C767433A3C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fcfd47c3fe9e0f097b76c7c78a15869fd96ffd9","datavalue":{"value":{"entity-type":"item","numeric-id":4004146,"id":"Q4004146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1789056$F831E680-58A8-47C8-8214-114A836251C6","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"6b9040db0f01651e997f4a0d07f37527b974b23d","datavalue":{"value":"journals/order/GuspielMP18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1789056$1159C2FB-D8FA-4BC1-A653-847A5A5FF9ED","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4c183644bf16245be33a8cf15541821276c5f0e5","datavalue":{"value":"10.1007/S11083-017-9444-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1789056$4D2363E5-D12B-4CF4-9685-5FB24C1D34A5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c84f0a09cb28fb840b9c681242bfc8f0d9f6150","datavalue":{"value":{"entity-type":"item","numeric-id":598446,"id":"Q598446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4793c4b71932225dabefa8e56a7947914a5ee30","datavalue":{"value":{"amount":"+0.8197718","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1789056$70CE7298-EEEB-48D9-819F-5011EA2768CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d227fef3c2a919e7de4547a5d68aa33c815d5e47","datavalue":{"value":{"entity-type":"item","numeric-id":2643869,"id":"Q2643869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d96b7e36ddd56f5bd2aff90d3520558fb047f2f8","datavalue":{"value":{"amount":"+0.80554646","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1789056$BA202941-B571-4428-A403-5295EA4544B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b8945c46e45dc8419b03905c9c2fdd6f8244fca","datavalue":{"value":{"entity-type":"item","numeric-id":1003642,"id":"Q1003642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"323fa6687538a4754c8105f962b309900cf214e2","datavalue":{"value":{"amount":"+0.7633942","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1789056$29C594AB-280A-4BB0-9B1B-FB40A32C8FEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb9bf75057924c741a1291b9dcc9ccf632057f30","datavalue":{"value":{"entity-type":"item","numeric-id":439058,"id":"Q439058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2be435125cd4d6f3b46d7f738bbacb9ee62f5612","datavalue":{"value":{"amount":"+0.7633028","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1789056$E7685DA4-1A7A-4109-8536-620A79AE4B62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aefa7145f11287c3b77d634c91fb31c106191ad9","datavalue":{"value":{"entity-type":"item","numeric-id":485003,"id":"Q485003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"546df77e6bd43b440e63f28aaca55972398eb9be","datavalue":{"value":{"amount":"+0.7613011","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1789056$0B055F11-B3E7-450E-BDD2-8197D9D19EA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3da119e9b5ff6de6018c1da4ee16b7f1a71c1e47","datavalue":{"value":{"entity-type":"item","numeric-id":5965144,"id":"Q5965144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee840c8b1e40d2054e889c4c18a5ec7b8f3c9433","datavalue":{"value":{"amount":"+0.75920373","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1789056$65A7E6F2-03A1-4019-8EA0-C45CF19FDE22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e04021ad7bf820e08d4ed83dfef7d903762a478b","datavalue":{"value":{"entity-type":"item","numeric-id":4575898,"id":"Q4575898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54304d1bc8c8f20bcc1324a9879ac15a7e6ac7c5","datavalue":{"value":{"amount":"+0.75754374","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1789056$C1EF71B4-EAA4-4E20-9DE5-B649F4DAB790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"deac82b69bfe2eee9487f350e932bc8c458c5f46","datavalue":{"value":{"entity-type":"item","numeric-id":418865,"id":"Q418865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26ce5fc87dbc6e08945f868b06c047f1e7011da9","datavalue":{"value":{"amount":"+0.75466657","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1789056$2F22B06E-6B9F-4BE5-8A37-4B5228EEEE59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"550013e1035ef96e80333c73f9e0ac4e03844c89","datavalue":{"value":{"entity-type":"item","numeric-id":5743461,"id":"Q5743461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21fe21f359de07b8da3ef907405217861d71c258","datavalue":{"value":{"amount":"+0.75460464","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1789056$273E8B2D-3EF8-4D6A-8246-1080A931A2D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40f35e536954b0b6bb61b8bd57f0c482356f7245","datavalue":{"value":{"entity-type":"item","numeric-id":409347,"id":"Q409347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76870f20d615cb8c378fffe3b8dcaf6c80f4ed7f","datavalue":{"value":{"amount":"+0.7498403","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1789056$01195851-2AD9-4583-9B56-280A85FF0FF7","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1789056$7962C793-7E8C-4756-AE3E-5CFD279A0C56","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1789056","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1789056"}}}}}