{"entities":{"Q1590179":{"pageid":1600919,"ns":120,"title":"Item:Q1590179","lastrevid":72269619,"modified":"2026-04-14T03:46:07Z","type":"item","id":"Q1590179","labels":{"en":{"language":"en","value":"Dimension, graph and hypergraph coloring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1545465"}},"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":"Q1590179$9540F696-40D1-4954-AC11-9E8DB0885B51","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"082237dbc37591f59812e684ce26aac3d4693227","datavalue":{"value":{"text":"Dimension, graph and hypergraph coloring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1590179$8DBD0ACA-6C17-4543-9A39-54F27D1B760B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ace4aef057d1065f81de4a221f0aff4b5070287d","datavalue":{"value":"0968.06002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1590179$7D58DAEC-67F1-4561-BEAE-E00194173229","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4b6ade81dd66dfdf71039e737d8d0c2a50384c0c","datavalue":{"value":"10.1023/A:1006429830221","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1590179$5661C912-C004-4B8F-856F-5B93F374EC69","rank":"normal"}],"P16":[{"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":"Q1590179$B2295FF1-3FCD-49F5-940C-EA314E45D629","rank":"normal"},{"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":"Q1590179$88560BB6-26DF-422D-964E-1A275F653B65","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":"Q1590179$AB1F8BD9-8FB2-4D5B-A2DE-BDDB7EBF7503","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f3bd111750c8b25e26eea9a9c3e259543f891eef","datavalue":{"value":{"time":"+2001-09-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1590179$4A28D411-255F-4DD5-B0EA-5ED027208AA8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d1c396d97d4bf635ba4672a2a035ddadf0524c15","datavalue":{"value":"A linear extension \\(L\\) of a poset \\(P\\) reverses an incomparable pair \\((x,y)\\) of \\(P\\) if \\(x>y\\) in \\(L\\). A set \\(S\\) of incomparable pairs forms a strict alternating cycle of \\(P\\) if no linear extension of \\(P\\) reverses all pairs in \\(S\\) but for all \\(T \\subset S\\) there is a linear extension of \\(P\\) which reverses all pairs in \\(T\\). For a poset \\(P = (X,\\leq)\\) let \\(H_P = (V,E)\\) be the hypergraph of incomparable pairs defined by \\(V = \\{(x,y) : x,y \\in X\\) and \\(x \\|y\\}\\) and \\(E = \\{S : S \\subseteq V\\) is a strict alternating cycle of \\(P\\}\\). The graph of incomparable pairs is \\(G_P = (V,E')\\) with \\(E' = \\{S : S \\in E\\) and \\(|S|=2\\}\\). Then dim\\((P) = \\chi(H_P) \\geq \\chi(G_P)\\). The paper provides a new proof of the following theorem by Cogis: dim\\((P)=2\\) if and only if \\(\\chi(G_P)=2\\) for every poset \\(P\\) that is not a total order. For all \\(t \\geq 2\\) a poset \\(P_t\\) of dimension dim\\((P_t) \\geq (3/2)^{t-1}\\) is constructed such that the chromatic number fulfills \\(\\chi(G_{P_t}) \\leq 3t-4\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1590179$90E9EFBA-3EB6-473F-AAD2-CFBCDA5FF79E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f3d0b1de78ad0e32d646815f9dc7561538cada7","datavalue":{"value":"06A07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1590179$B18A6807-184E-4A94-BE4B-CE7987C848D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1590179$C823EC2A-5F0D-437D-954F-1435CC012305","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1590179$2296E3B4-4247-4383-95FA-8AEC9270C51C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1590179$9AA7013D-9588-4024-A1C8-ACC2A2840355","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"498ae2d3861b89d94b004dfffa5c72916aa3e1c9","datavalue":{"value":"1545465","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1590179$053138FC-F1F3-43C9-A57A-3B458E6F1884","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4768181659397122937393c61764e2f954409467","datavalue":{"value":"dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q1590179$1B257830-B851-4CDE-B57B-CA0530009F8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1590179$8C2054E9-F87F-4D47-AB44-9F80347326F5","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":"Q1590179$D4FE57B1-F1DB-4055-BF80-EB04901E4739","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cbe608ec5b1db09f9bcaeb67a15b0ca1a11cfea","datavalue":{"value":{"entity-type":"item","numeric-id":5965146,"id":"Q5965146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"941b8a7a1d6929c2e6db5679f6ee972af868c55e","datavalue":{"value":{"amount":"+0.8029084801673889","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":"Q1590179$5CFD01C4-E832-4495-9AB6-E72CEB88D44E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e80e13c029ba7f3e80ab0b3d9e92931663f025c","datavalue":{"value":{"entity-type":"item","numeric-id":1319081,"id":"Q1319081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04ea1dd4e4d0046ac3794186791d7894dce1f92c","datavalue":{"value":{"amount":"+0.7908341288566589","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":"Q1590179$D7DA7CBA-B49D-4CDB-B5C1-AE4A14A007EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b3d7a4b216e8c8cfec2ddd01194cfcbf23b97d4","datavalue":{"value":{"entity-type":"item","numeric-id":2279688,"id":"Q2279688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c764442fda0f34b6277fd9e7a3bc875bc349bfe5","datavalue":{"value":{"amount":"+0.7798678874969482","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":"Q1590179$02DB7F25-C43C-479C-9B51-E076541E46BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8820ab984d9febdbb791cb7bb5571fc48350184a","datavalue":{"value":{"entity-type":"item","numeric-id":2706893,"id":"Q2706893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0444121284b4dc2c658991b9a34fd00cf25fb243","datavalue":{"value":{"amount":"+0.778256356716156","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":"Q1590179$97256219-57E9-431F-8E55-B8615FEE5F67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"176ce16b1e5ed341377817b53341a0bb8dcb1708","datavalue":{"value":{"entity-type":"item","numeric-id":4004146,"id":"Q4004146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6927831e241e42297cabc125d338860f5a8e9e4c","datavalue":{"value":{"amount":"+0.7765774130821228","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":"Q1590179$F4F809FD-C64C-4E77-9B63-19497D7AE77A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Dimension, graph and hypergraph coloring","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Dimension,_graph_and_hypergraph_coloring"}}}}}