2026-08-16T20:05:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15542 2024-03-06T10:55:33Z ddc:004 open_access

Property B: Two-Coloring Non-Uniform Hypergraphs Radhakrishnan, Jaikumar Srinivasan, Aravind Hypergraph coloring Propery B The following is a classical question of Erdős (Nordisk Matematisk Tidskrift, 1963) and of Erdős and Lovász (Colloquia Mathematica Societatis János Bolyai, vol. 10, 1975). Given a hypergraph ℱ with minimum edge-size k, what is the largest function g(k) such that if the expected number of monochromatic edges in ℱ is at most g(k) when the vertices of ℱ are colored red and blue randomly and independently, then we are guaranteed that ℱ is two-colorable? Duraj, Gutowski and Kozik (ICALP 2018) have shown that g(k) ≥ Ω(log k). On the other hand, if ℱ is k-uniform, the lower bound on g(k) is much higher: g(k) ≥ Ω(√{k / log k}) (Radhakrishnan and Srinivasan, Rand. Struct. Alg., 2000). In order to bridge this gap, we define a family of locally-almost-uniform hypergraphs, for which we show, via the randomized algorithm of Cherkashin and Kozik (Rand. Struct. Alg., 2015), that g(k) can be much higher than Ω(log k), e.g., 2^Ω(√{log k}) under suitable conditions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jaikumar Radhakrishnan and Aravind Srinivasan 2021 Is Part Of LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2021.31 urn:nbn:de:0030-drops-155428 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.31 eng https://creativecommons.org/licenses/by/4.0/legalcode