{"entities":{"Q304175":{"pageid":305942,"ns":120,"title":"Item:Q304175","lastrevid":60838434,"modified":"2026-04-10T19:27:02Z","type":"item","id":"Q304175","labels":{"en":{"language":"en","value":"Posets with cover graph of pathwidth two have bounded dimension"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6619132"}},"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":"Q304175$A4BF62FA-830C-4457-9FE0-5867928EEAF9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"19c24758682050bda788e539d5669ea9c104bf5e","datavalue":{"value":{"text":"Posets with cover graph of pathwidth two have bounded dimension","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q304175$6B12326F-DE00-484C-AC71-C75274EEC56D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ebe76974d42b088279097254fe51ac2ce704e853","datavalue":{"value":"1364.06002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q304175$C1184546-65D9-48B9-91B5-B2E24ED390FA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cdc7ee790d13d99f502699149c00c5e450baccbb","datavalue":{"value":{"entity-type":"item","numeric-id":293601,"id":"Q293601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$9083A8EF-676F-4D02-AE10-7FCDA9B97E25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e34c32339ce649498ea14352aa16765fd53d8e44","datavalue":{"value":{"entity-type":"item","numeric-id":304173,"id":"Q304173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$39B13BB9-56F6-494A-82F7-583587C59AB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"91f2eeab060c62a930318e4dd024e4953f139d53","datavalue":{"value":{"entity-type":"item","numeric-id":304174,"id":"Q304174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$2ABE7EB9-237F-4DA1-9499-C3A1172B4F3F","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":"Q304175$74B2340E-B87B-466F-A54C-976D933BDBBE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dfdc4d4cc36ab9323cabe15e9f40864a71d2da75","datavalue":{"value":{"time":"+2016-08-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q304175$47AB47F4-D0BD-4AC7-86E5-3051641E7A3D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d0c22a6b271ab4e1ed56144b3b88a858a6a07aaa","datavalue":{"value":"https://arxiv.org/abs/1308.4877","type":"string"},"datatype":"url"},"type":"statement","id":"Q304175$0224399F-7366-46D1-BBDF-13674CC4FB15","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"821f577106e6fa49a06e2fdc7e3e70a639655a97","datavalue":{"value":"The dimension of an ordered set \\(P\\) with order relation \\(\\leq \\) is the smallest number of total orders whose intersection is the order \\(\\leq \\). Let \\(G=(V,E)\\) be a graph, let \\(T\\) be a tree and let \\({\\mathcal V} =(V_t )_{t\\in T}\\) be a family of subsets \\(V_t \\subseteq V\\) indexed by the tree \\(T\\). Then \\((T,{\\mathcal V}) \\) is called a tree-decomposition of \\(G\\) iff \\(V=\\bigcup _{t\\in T} V_t \\), every edge of \\(G\\) is a subset of a set \\(V_t \\), and, if \\(t_1\\), \\(t_2\\), \\(t_3 \\) are vertices of \\(T\\) such that \\(t_2 \\) lies on the unique path from \\(t_1 \\) to \\(t_3 \\) in \\(T\\), then \\(V_{t_1 } \\cap V_{t_3} \\subseteq V_{t_2} \\). The width of a tree decomposition is \\(\\max _{t\\in T} |V_t |-1\\). The treewidth \\(\\mathrm{tw}(G)\\) is the smallest width of a tree-decomposition of \\(G\\). A path-decomposition is a tree-decomposition in which \\(T\\) is a path and the pathwidth of a graph is the smallest width of a path-decomposition of \\(G\\).  It has been long known that, if \\(P\\) is a connected ordered set whose cover graph has treewidth \\(1\\) (that is, it is a tree), then its dimension is at most \\(3\\). Moreover, there are ordered sets of arbitrarily high dimension whose cover graph has pathwidth \\(3\\), which leaves path- and treewidth \\(2\\) as the last cases to consider. The authors show that the dimension of an ordered set whose cover graph has pathwidth at most \\(2\\) is at most \\(17\\). They also note that the cover graph of any ordered set that contains the standard example \\(S_5 \\) has treewidth at least \\(3\\) and that it has been proved in [\\textit{G. Joret} et al., ``On the dimension of posets with cover graphs of treewidth 2'', Order (to appear), \\url{doi:10.1007/s11083-016-9395-y}] that the dimension of an ordered set whose cover graph has treewidth at most \\(2\\) is at most \\(1276\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q304175$EE68411F-B0F8-41BA-93EB-4205FE7F4F91","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f3d0b1de78ad0e32d646815f9dc7561538cada7","datavalue":{"value":"06A07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q304175$339C80CC-C0FA-445F-BA44-8F2E7FA4EE5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q304175$86897FEC-CBEF-4BAE-BB75-2E4BF2B55999","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6b316c649596e6d47abeeffd1eba45135a2d9ef9","datavalue":{"value":"6619132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q304175$040EDC5A-4E7F-49E4-8B83-2A5D58AE1487","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"762a112ef0429a3655234c3e246a242461dca9bf","datavalue":{"value":"poset","type":"string"},"datatype":"string"},"type":"statement","id":"Q304175$5FD36EED-B99A-4484-A011-272E9C91E5CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67f458d393b772a7cf36a53976d2b5be911e683d","datavalue":{"value":"pathwidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q304175$2BF34801-F108-4B9D-B0AF-6CFF2A50C18A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df6c9c3c01b5b996760d1ae0bf9e2cef46282302","datavalue":{"value":"cover graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q304175$B2355E1C-1884-4D5A-91EF-AAFA8A570449","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4768181659397122937393c61764e2f954409467","datavalue":{"value":"dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q304175$C8C3CF4D-0827-4F4F-9024-3BAB5F43D137","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d57d68ed777850433efcc3de197edd817953ef26","datavalue":{"value":"treewidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q304175$271AEB54-4D73-4F20-827A-D7FFE13A15B4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"293134ea196be1b852c58b1816aedda2786a855a","datavalue":{"value":{"entity-type":"item","numeric-id":172078,"id":"Q172078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$470BB000-92AF-41D7-B1EF-3882493E054A","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":"Q304175$AFAF2EBA-FBF4-49E3-9EDC-229389ED27E7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ab87b88d7cc21783690ba15da0a541a226560fed","datavalue":{"value":"W3098298570","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q304175$D670401F-B6B3-4535-BE31-D7F93D072EA3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c89d2d985aacffc4ab2f62604454fbca80c041b8","datavalue":{"value":{"entity-type":"item","numeric-id":2915439,"id":"Q2915439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$F73006FD-E1BB-4374-8ECE-252EEEE6E35F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d62e967816953cecad41268e715794a55d56323d","datavalue":{"value":{"entity-type":"item","numeric-id":3577833,"id":"Q3577833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$6704704F-6CC7-4A65-ABB1-05BEFB5D7743","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a68b3d49f7fb11b5bd23d4e006443493317bc09f","datavalue":{"value":{"entity-type":"item","numeric-id":966048,"id":"Q966048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$E190FFD5-BF12-4C98-BA4D-E3F9BDF004B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fb549524f195b043ec146ce3fed6dbed73ac5c6","datavalue":{"value":{"entity-type":"item","numeric-id":2354607,"id":"Q2354607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$B661C9BA-D35B-4B36-A973-2B2AFF91D6D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5cd64e41383e58b27038dda2995ea96c06c46af4","datavalue":{"value":{"entity-type":"item","numeric-id":1230790,"id":"Q1230790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$B85D6E46-1B88-4BE7-BA58-4AEDE723C0CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43177551f0974b81151e809aeb3df9fe7cbc518c","datavalue":{"value":{"entity-type":"item","numeric-id":2400108,"id":"Q2400108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$380B8FA3-328C-4A98-813E-B538DC1A9B0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5caa95ff885f04ceaee50a6b44f5aa4a65b46179","datavalue":{"value":{"entity-type":"item","numeric-id":2407679,"id":"Q2407679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$96EBE584-84CB-46B1-9C3F-508DA9658BF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4dd4d57512f38a10ac805d833978b7983a24ebc6","datavalue":{"value":{"entity-type":"item","numeric-id":5904865,"id":"Q5904865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$D89D1D2A-D72B-4C2D-9810-0C2783BE6BF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e83aa35aca0c6d2baa71c54cef665fda1314390","datavalue":{"value":{"entity-type":"item","numeric-id":1336625,"id":"Q1336625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$ECA6B051-F96B-44CC-A22C-94C2B5B76071","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ef0f89b3d4848285d16b9f024f89d4a5e76a218","datavalue":{"value":{"entity-type":"item","numeric-id":799684,"id":"Q799684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$5B377D3F-D401-4469-8E5D-B89C85C47D89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"248729ebc4d6876ccf402d4746249e334c3f8ead","datavalue":{"value":{"entity-type":"item","numeric-id":705888,"id":"Q705888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$BCB00202-30B6-43A4-AA1D-FB51CC2FCF63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8c7c2d2468d5838f59038882cc6dad38144a5e0","datavalue":{"value":{"entity-type":"item","numeric-id":1108295,"id":"Q1108295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$D435AF8B-3D76-46A5-AE7F-51D7A0788682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4d3a7e80edce55ce2fbb113a72c85e6d4712b50","datavalue":{"value":{"entity-type":"item","numeric-id":2509772,"id":"Q2509772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$796DFE01-7AB0-4A6D-88E1-8E06C534E29E","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":"Q304175$96EDCE61-464E-42E6-9C9F-4A694A8A5A63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1924e5ca4ad8d9abc4eff9a398910a5e0103f106","datavalue":{"value":{"entity-type":"item","numeric-id":1217722,"id":"Q1217722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q304175$8031FF21-B7A7-4CCC-82BB-3DF53AC26BF1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6ca8e119f806f6d226075c99b2466aad11a38e9f","datavalue":{"value":"10.1007/S11083-015-9359-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q304175$E99BBACD-A966-4CB3-8044-5BB8C617B5F5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7c99db10b2bb5b3a13925cb1938ccb8b4b3b39c","datavalue":{"value":{"entity-type":"item","numeric-id":2407679,"id":"Q2407679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dff5440baffc6fb186608d8aecd096d850ba27b6","datavalue":{"value":{"amount":"+0.8907784223556519","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":"Q304175$CDA70720-EEF5-464E-A197-0C03CFC685C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f526bcf81e3833b7916270b5ffe523298fb2f96c","datavalue":{"value":{"entity-type":"item","numeric-id":2400108,"id":"Q2400108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d70ccea533ae111211ebc0d024f99eb834b111d","datavalue":{"value":{"amount":"+0.8874683976173401","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":"Q304175$8B21251E-DA99-43FE-8614-1089702E88F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bb4fef70331308019ce515691e128c3216c9467","datavalue":{"value":{"entity-type":"item","numeric-id":781526,"id":"Q781526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6253e844f47a95ede848d591fbca3e65fab1f4a8","datavalue":{"value":{"amount":"+0.8757714033126831","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":"Q304175$DD1CBBB5-45B2-4341-A066-5BC289EFEA44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c776ad73f1ed84071ad01047816960e63ed2809b","datavalue":{"value":{"entity-type":"item","numeric-id":2658384,"id":"Q2658384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39be711c10e4271a8be1b05de7f3d10da4a6dda9","datavalue":{"value":{"amount":"+0.8556069731712341","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":"Q304175$B7F4555C-1BE9-47FF-A56C-852FA9B5CD14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0a1225c62a64ab383af66e0023b5dd18936291c","datavalue":{"value":{"entity-type":"item","numeric-id":2279268,"id":"Q2279268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10c175a6d7bea8a7768d9724a1f33fec9e514c9b","datavalue":{"value":{"amount":"+0.8332183957099915","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":"Q304175$D3EDB834-4FA7-471D-A050-F52CBA5722C2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Posets with cover graph of pathwidth two have bounded dimension","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Posets_with_cover_graph_of_pathwidth_two_have_bounded_dimension"}}}}}