Property B for random non-uniform hypergraphs
We show that, in random hypergraphs with several permitted edge sizes, non-uniformity affects existential and algorithmic bounds for 2-colorability (Property B) in fundamentally different ways. Assigning weight $2^{-k}$ to each $k$-edge, we obtain upper and lower bounds in terms of the total edge weight that asymptotically match the uniform bounds as the minimum permitted edge size grows, regardless of how edges are distributed among sizes. We also extend the best-known algorithm for 2-coloring random uniform hypergraphs to the non-uniform setting. With weight $\frac{k}{2^k}$ assigned to…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.07379
curl -X POST /api/v1/records/arxiv/2610.07379/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.07379/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'