paper

Almost All 3-uniform Hypergraphs are Class 1

arXiv:2611.05622

Abstract

The chromatic index of a hypergraph 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 , and when , we say that 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 that the -uniform binomial random hypergraph is Class 1 with high probability. We also show that this result doesn't hold for uniformities above . For a broad range of , when and , the hypergraph is with high probability not Class 1.