{"entities":{"Q1108295":{"pageid":1119044,"ns":120,"title":"Item:Q1108295","lastrevid":69661455,"modified":"2026-04-13T08:32:23Z","type":"item","id":"Q1108295","labels":{"en":{"language":"en","value":"Edge subdivision and dimension"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4066961"}},"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":"Q1108295$4E2892FA-81E2-434B-BF21-2DD4D691EA62","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0e9c7bd8b5179421a19c48f99cdac36e88aed4c2","datavalue":{"value":{"text":"Edge subdivision and dimension","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108295$92139B7A-57E5-44FD-A57E-63339F6FCE33","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0423ffa3b1d1b6dba2709c1c1d1fbf6db4c9b579","datavalue":{"value":"0654.06002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108295$8A6340C1-FC6F-4F3B-8FB4-AA065D601757","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"927c74a3c9ef76d22c5ad671ee4d6192021a9040","datavalue":{"value":"10.1007/BF00337619","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108295$3C7F86F9-7F7B-4CF0-9D80-1526D0DEE6EC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ef8392e01c11e85b032ddf62d87088b822bd19a","datavalue":{"value":{"entity-type":"item","numeric-id":344852,"id":"Q344852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108295$C52C29C3-A16C-4DBE-9D73-0068C938786E","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":"Q1108295$FB0A83AD-5CBE-4423-A85B-09227671D559","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1108295$C3673866-10FD-4AF8-97F0-56AC5CCDC6B9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e7854d4bca8e49ca7d23cc134251a0f5a6ca7a70","datavalue":{"value":"M. Habib conjectured that the dimension problem for the so-called \\(N\\)-free partial orders could be solved in polynomial time. Kierstead asked whether the conversion of a partial order by edge subdivision can multiply the dimension by more than a constant; if not, then a polynomial time algorithm for determining the dimension of an \\(N\\)-free partial order would yield a polynomial time algorithm for this problem for an arbitrary partial order. It is proved that the dimension can be multiplied by an arbitrary large factor. However, there is a remark that R. Kimble gives a polynomial transformation from a partial order \\(P\\) of arbitrary height to a partial order \\(P'\\) of height 1 such that \\(\\dim P\\leq \\dim P'\\leq 1+\\dim P\\). Hence, a polynomial algorithm for the dimension of \\(N\\)-free partial orders does imply a polynomial time constant ratio approximation algorithm for the general dimension problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108295$52561B1B-5B16-4C89-BDCA-518C91B5DF2E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"967efbf7e9159f2448c17bb8438ae3fe0ce8fb52","datavalue":{"value":{"entity-type":"item","numeric-id":334969,"id":"Q334969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108295$C7B079FE-554D-47C2-AD96-D6BA166CDE52","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108295$285677B2-5D59-4B01-9D6A-1D971551B7FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108295$B09F832F-6568-4903-AA23-7CA974890CCC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b9038044e6913052eda32a265bd278a9deea631f","datavalue":{"value":"4066961","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108295$C9BCF709-E897-4528-A68A-9EA4DA4700B9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4768181659397122937393c61764e2f954409467","datavalue":{"value":"dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108295$7A9B7EA5-5A13-4624-AC20-B16C6DF7D070","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c91ac54d2d48135591270c6999e86f492f3758c","datavalue":{"value":"N-free partial orders","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108295$998AB91F-D4E4-49AE-9642-204DEA72F5CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108295$994B4251-8812-4D83-BFEB-21EBA208ACB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0378c51c2c332d2e3dbcf4869c0305deb0fb14c","datavalue":{"value":"height","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108295$7E0F6818-A875-4678-BC43-D21D56FEDCBE","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":"Q1108295$B5B3E453-2A34-43E7-922E-F9431249993B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"09905fc8b39ddbd68ae04612d3fac1a46f3a18cc","datavalue":{"value":{"entity-type":"item","numeric-id":4918389,"id":"Q4918389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108295$8A90A919-C9D4-40AD-896E-4D8C36576EBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"729e33ee3dcf4427d583c252818241bb00291311","datavalue":{"value":{"entity-type":"item","numeric-id":1235194,"id":"Q1235194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108295$FF9C0D01-95F5-459D-9A6B-68EB0FB32CC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04655507cfa3b8351f7f0657e6f8472d4b8b19a3","datavalue":{"value":{"entity-type":"item","numeric-id":5780132,"id":"Q5780132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108295$A782974E-6C48-404B-BC47-5E2B441F28B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74ca2ba6f9556babb6c5a4ff7f644e956e998ae2","datavalue":{"value":{"entity-type":"item","numeric-id":1246441,"id":"Q1246441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108295$0185BB29-F6FC-46FF-8445-7FAC43D946D8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"068cab5749b489a65f5dbed185f738d01319fa50","datavalue":{"value":{"entity-type":"item","numeric-id":2716970,"id":"Q2716970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf9a0926da471617d4e341e9c2491a3a060f8508","datavalue":{"value":{"amount":"+0.7856191396713257","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":"Q1108295$C89E293C-0D34-4D16-965D-2AAA78635E16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70be5013f41d0721f395f09375b73eb2bc2b4bb8","datavalue":{"value":{"entity-type":"item","numeric-id":2957691,"id":"Q2957691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24a284ddc0b8e8bccf5c3f2f7feccabd0a8f20a9","datavalue":{"value":{"amount":"+0.7744331955909729","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":"Q1108295$D541FADE-B1A0-45DA-AFCD-B6DA14FF5748","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c31f998d3d683962984fd037d848f64fffa1a33","datavalue":{"value":{"entity-type":"item","numeric-id":4525259,"id":"Q4525259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96264d8704f67fc2b4a4b1a25c50b9af9a646f2d","datavalue":{"value":{"amount":"+0.7535446286201477","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":"Q1108295$9A07EB28-5D03-4D79-B217-19F4DF5885E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1e45728dd8802b6534f923845f58c3f125b3aa7","datavalue":{"value":{"entity-type":"item","numeric-id":3503501,"id":"Q3503501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63450a44f1b4a01b34ee71e28ed672f9398ecd6f","datavalue":{"value":{"amount":"+0.7502638697624207","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":"Q1108295$99D5125E-AE75-4137-9A8F-1437C5516AEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7f007cc23d7a0c72733e29a9235f292c0426183","datavalue":{"value":{"entity-type":"item","numeric-id":2221914,"id":"Q2221914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0502afdab2dc5a4ba40d643a3bcdd1ed1cf6fd84","datavalue":{"value":{"amount":"+0.7478266954421997","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":"Q1108295$89798BF3-3415-4249-9C3F-809BAF77F4A6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Edge subdivision and dimension","badges":[]}}}}}