{"entities":{"Q1715058":{"pageid":1725799,"ns":120,"title":"Item:Q1715058","lastrevid":53339657,"modified":"2026-01-24T18:43:50Z","type":"item","id":"Q1715058","labels":{"en":{"language":"en","value":"Strong inapproximability results on balanced rainbow-colorable hypergraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7011196"}},"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":"Q1715058$8206BCED-E230-4C29-8701-281EA8037EB2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ac14b9100cb36da7a0e78c84c5ab46f787eb04c8","datavalue":{"value":{"text":"Strong inapproximability results on balanced rainbow-colorable hypergraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1715058$1586ADCE-D254-4A87-9AD4-B3215F6C540B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9aede123c663efd0498f5a9d721aaf09bac790b3","datavalue":{"value":"1424.05087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715058$B7DC74D7-759B-414E-970C-F99A7458F147","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c036cc59d8136b1c1d330e12aacdea4899ce840","datavalue":{"value":{"entity-type":"item","numeric-id":293456,"id":"Q293456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715058$3A56C1BE-1C85-4D62-B5B3-3A4C4D3DE0C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4da5d9d00c29a1438e24839583d2fe7db0d0793a","datavalue":{"value":{"entity-type":"item","numeric-id":315528,"id":"Q315528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715058$EA1BD945-DB9D-4C4F-B3B7-6C01BF5929F2","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":"Q1715058$53576D2E-9BBF-4172-A522-19C0D0405CA3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3f4145805478faad59761c3ff4a8cc3fff513172","datavalue":{"value":{"time":"+2019-02-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1715058$7F028899-55F0-493E-A2C2-448FB87D5607","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8d8fbd7f04fdec8f71a758d86bed95022d7c0d6e","datavalue":{"value":"The problem of coloring a hypergraph with few colors is a fundamental optimization problem. A $K$-uniform hypergraph $H=(V,E)$ is said to be $k$-colorable if there exists a coloring $c:V\\to \\{1, \\dots, k\\}$ of its vertices with $k$ colors so that no hyperedge is monochromatic. The problem of determining if a $K$-uniform hypergraph is $2$- colorable is a classic NP-hard problem when $K \\geq 3$.  Here, the authors are interested in the question of determining whether coloring a hypergraph remains hard even if we are promised that the hypergraph admits a coloring with natural stronger properties. A coloring of a hypergraph is called rainbow if every hyperedge contains at least one vertex from each color. The coloring is called perfectly balanced when each color appears the same number of times. The main result is to prove a strong hardness result that rules out coloring a hypergraph with $O(1)$ colors even when we are given that the hypergraph has a rainbow $k$-coloring with good balance between the colors (for any $k \\geq 3$).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715058$4B1D87F6-879A-49BC-AA11-7440BBF6B715","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c373609087678f84cf49ac586680a31002124e72","datavalue":{"value":{"entity-type":"item","numeric-id":267204,"id":"Q267204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715058$58055E63-5B84-479F-9D16-833FAF59D2D0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715058$1483D6A1-6191-4D11-8CB3-AC52F6410BF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715058$043A6717-E5ED-485C-AFC2-761BD504AB1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715058$E0EAA6C8-EB63-4E57-B247-E756B4ECCDAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fedc54d041dbaf3922f156ba09e5514c44ab5169","datavalue":{"value":"60E15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715058$B3705E1B-60F0-4DE7-83EA-12285B790794","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aca2d5a784c52da5c5c27b0b026499c8e513e159","datavalue":{"value":"7011196","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715058$1F03FACA-50DB-49CE-B311-89E564A10165","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63a0b5bbdbffeb2f6d94dda6a7bccbc2173775aa","datavalue":{"value":"hypergraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715058$4938ABE7-7D70-4157-87D6-45DFBF03F585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ebf3277d7d1ea9f34c28dc422c33c5d6fe975fd","datavalue":{"value":"$K$-uniform hyperhraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715058$A7314872-4C61-4CE7-8FCB-B342DF3B8FAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00a0c7232fc5da431e8c266a4e22fc3ec4d72f83","datavalue":{"value":"rainbow $k$-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715058$4D719C76-CEC4-4F1E-BE2B-14FFB9D5CCB7","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":"Q1715058$33392B18-A20D-41DF-86BA-A31AFF3A890B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2b869cbad65e27f5b6739d9c1ddf32230aa9650a","datavalue":{"value":"https://doi.org/10.1007/s00493-016-3383-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1715058$4FA4D0AA-CB45-47D5-82D2-763C1AA289D0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5f6b11928be699eb567b8dca9fe3072299e1ea2d","datavalue":{"value":"W2775735346","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715058$DC3FBD47-3738-4F15-A56E-6FC28A784523","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fcd47a825af8b0969561e16d92beabfc63e19cfc","datavalue":{"value":"10.1007/S00493-016-3383-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715058$F4FBF94E-395A-464F-98C4-C32006D172A3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f34829994cf5de7544b91fa6d8cd2405a894c155","datavalue":{"value":{"entity-type":"item","numeric-id":5363095,"id":"Q5363095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c65f9b08760677ad62c0f100fffa2534b0090ab","datavalue":{"value":{"amount":"+0.916061282157898","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":"Q1715058$AD7FCEBE-C6A8-4229-BFC5-B3378D450E94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbc7ad396290807ccd47afc0c78fa24f59fb6029","datavalue":{"value":{"entity-type":"item","numeric-id":5136325,"id":"Q5136325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b5242e6fc0fc51356d74b945929b3b099e57495","datavalue":{"value":{"amount":"+0.8991902470588684","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":"Q1715058$AF682D7E-C279-4AC0-91E4-AFBE71955F69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42ec180c8e5ded0214cc4f1cc13e1bf8e67d10e7","datavalue":{"value":{"entity-type":"item","numeric-id":2368586,"id":"Q2368586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"840b8501be016d502f6d6831ebcd3a0f9c0207c0","datavalue":{"value":{"amount":"+0.8634912967681885","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":"Q1715058$1D87D6EC-4562-4223-AA5D-0B0865C11572","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa51b8e4db803b1f193c82e622277e7836fb5be8","datavalue":{"value":{"entity-type":"item","numeric-id":5217824,"id":"Q5217824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ff2bd6693ce0497f9ee8a4f2f740c3f1c040038","datavalue":{"value":{"amount":"+0.8630356192588806","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":"Q1715058$BBAE3B5A-1C5B-4DA4-B29F-0A0229E0F59A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"050a6ec46dcd85ebc8afcdbeec3d47beb6da1db5","datavalue":{"value":{"entity-type":"item","numeric-id":5368748,"id":"Q5368748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ff97f6383aa88fc567d57e40b40a6dd15b51a4f","datavalue":{"value":{"amount":"+0.8389138579368591","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":"Q1715058$86B163A6-ADE2-4A39-AA0F-CFF675F52DAA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1715058","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1715058"}}}}}