{"entities":{"Q2658384":{"pageid":2669127,"ns":120,"title":"Item:Q2658384","lastrevid":57987063,"modified":"2026-04-03T08:40:52Z","type":"item","id":"Q2658384","labels":{"en":{"language":"en","value":"Boolean dimension and tree-width"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7326546"}},"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":"Q2658384$A0327679-E1BF-46B3-BF99-A20837BA9ADC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a102e5e6e8c2aa32f2f7f839548a9a2781491ea8","datavalue":{"value":{"text":"Boolean dimension and tree-width","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2658384$9827C3A7-78E4-419D-9DF8-6147B8BD363E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"32875a66c74c1fbc98372a6bb8ea877dc6b11bce","datavalue":{"value":"1474.06004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2658384$47306855-D6D2-4C38-ABB8-35226A9365DD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca7b664c187d2c65eff6bdc5f0cc37778962b26b","datavalue":{"value":{"entity-type":"item","numeric-id":470956,"id":"Q470956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2658384$6DCB9BA9-086D-4146-9797-042FDCDFCEA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4cd896cc324ed8d238532cc31bb366d571b9dcae","datavalue":{"value":{"entity-type":"item","numeric-id":377498,"id":"Q377498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2658384$EC845254-DAD7-46A1-B400-A8411C15BCC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eb43e4c4f1b169e3803b8b6726a3b03e15c78164","datavalue":{"value":{"entity-type":"item","numeric-id":170482,"id":"Q170482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2658384$C41948E1-873D-46E1-8D18-8D2EEC4A5D66","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2658384$BBA34F7F-074B-4702-B31B-9A7B62CFAEB1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ce26ebc4089a72e32535d87f895c5f4eab068797","datavalue":{"value":{"time":"+2021-03-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2658384$13A1CE48-7298-4DB6-844F-4642BEE2E716","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"93c53be058232247841a44a04164a7e6cbb0b06f","datavalue":{"value":"https://arxiv.org/abs/1707.06114","type":"string"},"datatype":"url"},"type":"statement","id":"Q2658384$86D50E2F-4520-49C5-8E95-36E02BCD9FDA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4c8fcabe5cf0c2a6c13738fbfbb6a64272b604e2","datavalue":{"value":"The dimension of a partially ordered set (poset) \\((P,\\prec)\\), denoted dim\\((P)\\), is the smallest number of linear extensions (i.e. total orders which agree with the partial order where it is defined) whose intersection is the poset. Posets with small dimension tend to be tractable in various ways as dimension is some kind of measure of the complexity of the poset. \\textit{J. Ne\u0161et\u0159il} and \\textit{P. Pudl\u00e1k} [in: Irregularities of partitions. Papers from the meeting held at Fertod, Hungary, from July 7th through 10th, 1986. Berlin etc.: Springer-Verlag. 137--140 (1989; ZBL 0683.06003)] introduced a variant called Boolean dimension, which is the smallest number of linear orders on the underlying set \\(P\\) whose intersection is the partial order. (The difference is that the orders need not be linear extensions of the underlying poset). Clearly bdim\\((P)\\leq \\) dim\\((P)\\). Whereas the dimension can be linear in the number of vertices \\(n=\\vert P\\vert\\) for a finite \\(P\\) e.g. for the so-called ``standard examples'', it is known that bdim\\((P)=O(\\log(n))\\) from Ne\u0161et\u0159il and Pudl'{a}k's paper [loc. cit.]. \\par The cover graph of a poset \\(P\\) has the same vertices as \\(P\\) and an edge from \\(x\\) to \\(y\\) if \\(x\\prec y\\) or \\(y\\prec x\\) and there is no element \\(z\\) such that \\(x\\prec z\\prec y\\) or \\(y\\prec z\\prec x\\). The main result of the paper under review is that if the cover graph of a poset has bounded tree-width, then the Boolean dimension is bounded. The authors also present some interconnected open problems in the area.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2658384$F1ABDD27-B45F-4AB0-98F4-E2319CE46165","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f3d0b1de78ad0e32d646815f9dc7561538cada7","datavalue":{"value":"06A07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2658384$66640EA6-F727-451D-B525-3A7DAB59FA6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2658384$9EB955AF-E58F-4BDE-8B0E-3D0DAD56A9E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2658384$695C20E5-49E1-4831-9B0F-AC9BF358C557","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"85c0ec3339d40456497da5bab902378909988f7d","datavalue":{"value":"7326546","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2658384$C80C2BDD-C017-4754-BEE9-30A7DFD722DC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bedf903784eeba0fa13d8545c010927ac8abaf15","datavalue":{"value":"partially ordered sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q2658384$4315DFFC-21F8-4DAF-B24D-C64563B60157","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6377904946660c7be072be4f19d18e242e949f04","datavalue":{"value":"Boolean dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q2658384$ADB22BB0-5468-48D0-BBD9-5D4627B3FD82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b81b0e661ffd7a2b0cf4d74a6388abe874250e20","datavalue":{"value":"tree-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q2658384$176968A2-B02F-4FA6-961E-E587F5F285BD","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":"Q2658384$5D65DB5E-F789-45B0-8305-D3486757B054","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":"Q2658384$3F149917-644E-4D57-AE45-D4E2734DD249","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"08e5db22cd2e0dea2bc362db13639b388847cdd8","datavalue":{"value":"W3039203263","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2658384$C86C9025-1240-4C5F-BEBC-32CD0EF3CDBF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a033df8721331fd5b8463ced1618fb41ba87344","datavalue":{"value":{"entity-type":"item","numeric-id":781526,"id":"Q781526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2658384$58C1255D-2876-41F2-B540-0D9222564E5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54980765514b494e4a2b52753ee3ee5ed011ed18","datavalue":{"value":{"entity-type":"item","numeric-id":1354634,"id":"Q1354634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2658384$3DF6171E-1566-4BE3-A4DA-B13C71E185BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"740468b4110a6f73be66b89c2f161cd39cec3098","datavalue":{"value":{"entity-type":"item","numeric-id":3137307,"id":"Q3137307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2658384$63D85BA7-7789-4756-AE3D-F82A0B189419","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42bcb963f62a4cbbca21ce29c88d24d2cccd3004","datavalue":{"value":{"entity-type":"item","numeric-id":3137188,"id":"Q3137188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2658384$6FA560A7-FD80-4048-B6A1-8E7D4D0754F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2fcca63b4b48801ff4f4e096fdcad7e954c1b5d","datavalue":{"value":{"entity-type":"item","numeric-id":3783593,"id":"Q3783593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2658384$35A33C15-D875-487F-AD4F-49764195162A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d139d8be3366d73ed32a948f5c4d10479d515071","datavalue":{"value":{"entity-type":"item","numeric-id":913830,"id":"Q913830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2658384$A7C0C4C4-4EAF-4CEA-BCB5-B08B5E8DCF0C","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":"Q2658384$218B5701-E3C8-4CC9-B50E-0D296D927C03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb0d230a6c18c42f79e8150e3893a52d64bfc63d","datavalue":{"value":{"entity-type":"item","numeric-id":781531,"id":"Q781531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2658384$B25DAF36-D64A-489A-A07D-6932A3CAC385","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05dc0eb84b9d14ca0fc0dc91cedb719c991701e9","datavalue":{"value":{"entity-type":"item","numeric-id":4732500,"id":"Q4732500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2658384$94555FAC-BA5C-43F3-9268-B0142EDA410D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bc306c3ae0db34df290d0134d71022d3a78131b","datavalue":{"value":{"entity-type":"item","numeric-id":2279268,"id":"Q2279268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2658384$8CF8FC90-0207-4C53-AD9C-D50AB06DFBCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e22d3b87a6e0c24126021bdbf5d90daeb7bbd07","datavalue":{"value":{"entity-type":"item","numeric-id":5435672,"id":"Q5435672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2658384$3C77511F-0712-486F-9D1F-C01D1D1AC41A","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":"Q2658384$02097A7A-C790-4FB3-99D0-5605683F1F29","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3054904fa5b0292efda2a2334be406745103810e","datavalue":{"value":"10.1007/S00493-020-4000-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2658384$D47F88B7-063C-4527-BBF2-67CDD18028F5","rank":"normal"}],"P1643":[{"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":"0569d1209c403befeb964c321b2e08811950a332","datavalue":{"value":{"amount":"+0.8806009292602539","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":"Q2658384$024F1376-497B-4AF4-8672-CB1C0E3F4A49","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":"1f1a725ca6f801211235aa07105b30062c77e583","datavalue":{"value":{"amount":"+0.8665121793746948","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":"Q2658384$8CF63050-8546-4147-B9E0-1DB5CEB830B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04b74d04c7079ff55d3ff12e9de908b4a7dd3301","datavalue":{"value":{"entity-type":"item","numeric-id":304175,"id":"Q304175"},"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":"Q2658384$35797D18-6951-4524-81B4-317E00EE3B86","rank":"normal"},{"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":"1dcbe2f06e5ba27f46cf97e4bf3cac40757fc181","datavalue":{"value":{"amount":"+0.846072256565094","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":"Q2658384$F8D9DFB9-4F11-4FAD-8AAE-99863ECAAA1E","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":"669f61cbcdd9a534556ebde949bf12630cb6aa1c","datavalue":{"value":{"amount":"+0.8410584926605225","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":"Q2658384$F83B25BD-ECCB-464C-A1A8-D457602C331E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2658384","badges":[]}}}}}