Almost All 3-uniform Hypergraphs are Class 1
Source: arxiv.org/abs/2611.05622
The chromatic index $χ'(H)$ of a hypergraph $H$ is the smallest number of colors needed to color its edges so that no two adjacent edges share the same color. The chromatic index is trivially bounded below by the maximum degree $Δ(H)$, and when $χ'(H)= Δ(H)$, we say that $H$ is Class 1. It is well known that almost every 2-graph is Class 1, and we extend this result to 3-graphs. We show for $n^{-2/3-1/200}\leq p \leq 0.99$ that the $3$-uniform binomial random hypergraph $H\sim H_{n,p}^{(3)}$ is Class 1 with high probability. We also show that this result doesn't hold for uniformities above…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.05622
curl -X POST /api/v1/records/arxiv/2611.05622/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.05622/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'