{"entities":{"Q2368586":{"pageid":2379329,"ns":120,"title":"Item:Q2368586","lastrevid":49819168,"modified":"2026-01-11T01:05:23Z","type":"item","id":"Q2368586","labels":{"en":{"language":"en","value":"The hardness of 3-uniform hypergraph coloring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5019518"}},"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":"Q2368586$EDC1AF40-B78D-46EC-B940-A132ECDEC4ED","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3fbaa83316fb2d6f98e5d6ff11b4402cdcec89fe","datavalue":{"value":{"text":"The hardness of 3-uniform hypergraph coloring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2368586$BC2D7FA7-0131-44DC-BD11-074100E8519D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fc5ef92f18a6fdf76ff68e36d39365a214b3f9be","datavalue":{"value":"1106.68080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368586$F693902C-C24E-40E7-BA74-89979F3ACB0D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d9f6b5d26f49366977cda1349aa1fe24902e4163","datavalue":{"value":{"entity-type":"item","numeric-id":375694,"id":"Q375694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368586$E1CF700E-F1EE-4B4C-A0EF-24EA188156A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce87ff208d821b7cefc09a782a58a804d8d79ecd","datavalue":{"value":{"entity-type":"item","numeric-id":1937354,"id":"Q1937354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368586$44AE7B37-CB1A-4498-A1AA-7C00240ECEBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d53c68acdd7f1baf096686dc4cd140fb6dc911d0","datavalue":{"value":{"entity-type":"item","numeric-id":645128,"id":"Q645128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368586$0BE16D91-86C2-4D06-B2B7-3BBA27F94A4E","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":"Q2368586$7D78C49C-08BB-4A88-8B91-914C4F0F9592","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0813cb7ea0a24463852b5266aae754b3e017488d","datavalue":{"value":{"time":"+2007-01-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2368586$4DE01932-5E8D-45BE-9450-DD1BB1D0733D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7d289d8767d0a4a6cee7e9d800558acebe1d6512","datavalue":{"value":"Not much is known about the hardness of the problem of approximate coloring of a hypergraph. The paper makes a step towards better understanding of the problem by proving that coloring a 3-uniform 2-colorable hypergraph with \\(c\\) colors is NP-hard for any constant \\(c\\). The proof is based on combining the layered PCP and Kneser graph and relies on high chromatic numbers of the Kneser graph and its induced subgraphs known as Schrijver graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2368586$8B2E7029-7AE1-4D89-A2AA-B390DA2EA7AC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368586$3D1E366E-73B7-47E3-8389-21C9AFFBBC2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368586$775D5D40-6679-4F82-ADD5-8BF6BBAFA933","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368586$B908E644-A826-4902-9E37-3B619D3CDFA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368586$FD82F390-9B57-400B-BA26-515F577076D1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5297d8bb0f4998d962e0ccb81b30a6eaeae81564","datavalue":{"value":"5019518","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368586$B0A3D271-4CC3-4E0C-8716-998E50B88D56","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"938bd8f53bd8e3b306aed6426b62d1b4d1e9148f","datavalue":{"value":"hypergraph coloring problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2368586$52EF5810-AC61-4EC2-BF62-6B8C79E8E5DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2368586$F76E2577-DE65-4669-B063-FF6174CA250E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2368586$9C0AA85D-2619-491B-83FF-590B53BF47AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e308f8cd20f2b6dc60e2e7dcb2f90061e94de011","datavalue":{"value":"Kneser graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2368586$148A3FAA-5487-40BA-9E15-01A16B9B76E6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4418b7d4f2a0250db5c25bb23e561efd56a43eb7","datavalue":{"value":{"entity-type":"item","numeric-id":587571,"id":"Q587571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368586$FFCA4929-AB42-4140-B796-A261B2AD313A","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"3e6e76231ab8404fa5530db100ab9a1a80b022e3","datavalue":{"value":{"entity-type":"item","numeric-id":20665,"id":"Q20665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368586$F93005F1-1968-46C0-9595-AC016FCB211C","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":"Q2368586$DD1DB26B-AC17-4F14-A482-474EFC43DF33","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fbef2549b6a423e6fbde7883ea47fb0fac378dac","datavalue":{"value":"https://doi.org/10.1007/s00493-005-0032-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q2368586$DA269260-1DEC-44B3-8F94-0F6F94254802","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"76d235ccc3228121ffe2b22a88c583f04379ed37","datavalue":{"value":"W3004384893","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368586$13630131-20C7-46B0-BB67-045C3ECCEF62","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"96d1e33930b0daa64661572e46cc654ed6be5e71","datavalue":{"value":"10.1007/S00493-005-0032-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368586$5772F2F1-3323-4B0F-805B-5DBB82E67F92","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f220ea6eb94e1f754308a21686020e5af1f9c36b","datavalue":{"value":{"entity-type":"item","numeric-id":2968154,"id":"Q2968154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fd4cf0e3affd702e38fe420715ec72dbf698f50","datavalue":{"value":{"amount":"+0.8739189505577087","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":"Q2368586$DB5DBF6C-F11F-49A0-822E-7E60E2DD48E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"072ccf319eeb7469ac38faed9e568ad860038720","datavalue":{"value":{"entity-type":"item","numeric-id":4252044,"id":"Q4252044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b447b0d9732d5196676a950d9871b1da0e5ddbd","datavalue":{"value":{"amount":"+0.8718565106391907","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":"Q2368586$75FE5A57-256F-4090-B36A-4799FC0C825E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6416eaa359825598578289893f52010508dd9876","datavalue":{"value":{"entity-type":"item","numeric-id":2851860,"id":"Q2851860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b447b0d9732d5196676a950d9871b1da0e5ddbd","datavalue":{"value":{"amount":"+0.8718565106391907","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":"Q2368586$46C3086A-1CBD-485F-B0B8-7F6084AEEAF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88e81a864a5d666a7c91a6389be9d274242f6329","datavalue":{"value":{"entity-type":"item","numeric-id":5002681,"id":"Q5002681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c65a6e744ac319145aba0c1c1124d7254334480","datavalue":{"value":{"amount":"+0.868168294429779","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":"Q2368586$A8F334BB-FE61-45BB-8092-0E1EB7023DAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad302b9f9c678b9cb9fe135c0f4196ec3262900a","datavalue":{"value":{"entity-type":"item","numeric-id":4820902,"id":"Q4820902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01ba31d09dc19254a3d4cb380c1ff67e3a65f977","datavalue":{"value":{"amount":"+0.8649172782897949","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":"Q2368586$09CDA350-9C43-4664-B9B6-E5FD4396077A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2368586","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2368586"}}}}}