betaFeedback

WorksMathematics

Almost All 3-uniform Hypergraphs are Class 1

Abstract

The chromatic index χ′(H)χ'(H) of a hypergraph HH 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)Δ(H), and when χ′(H)=Δ(H)χ'(H)= Δ(H), we say that HH 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≤p≤0.99n^{-2/3-1/200}\leq p \leq 0.99 that the 33-uniform binomial random hypergraph H∼Hn,p(3)H\sim H_{n,p}^{(3)} is Class 1 with high probability. We also show that this result doesn't hold for uniformities above 33. For a broad range of pp, when k≥4k \geq 4 and k∤nk \nmid n, the hypergraph H∼Hn,p(k)H \sim H_{n,p}^{(k)} is with high probability not Class 1.

Introduction

How many colors are needed to color the edges of a graph or hypergraph so that no two intersecting edges receive the same color? Equivalently, how many matchings are needed to partition its edge set? This question is one of the classical problems in graph theory, with connections to combinatorial optimization, scheduling, communication networks, and design theory (e.g. [3, 16, 22]).

Formally, a proper edge-coloring of a hypergraph HH is an assignment of colors to the edges of HH such that any two intersecting edges receive different colors. Thus every color class is a matching. The chromatic index χ′(H)\chi'(H) is the smallest integer ℓ\ell such that E(H)E(H) can be partitioned into ℓ\ell matchings.

The most basic lower bound comes from the maximum degree. Indeed, all edges incident to a fixed vertex must receive distinct colors, and therefore

χ′(H)≥Δ(H).\chi'(H)\ge\Delta(H).

For ordinary graphs, this trivial lower bound is remarkably close to the truth: Vizing’s theorem [35] states that every graph GG satisfies

χ′(G)∈{Δ(G),Δ(G)+1}.\chi'(G)\in\{\Delta(G),\Delta(G)+1\}.

This gives the classical distinction between Class 1 graphs, for which χ′(G)=Δ(G)\chi'(G)=\Delta(G), and Class 2 graphs, for which χ′(G)=Δ(G)+1\chi'(G)=\Delta(G)+1.

At first sight, Vizing’s theorem seems to almost settle the edge-coloring problem for graphs. However, the remaining distinction between Class 1 and Class 2 is itself highly nontrivial: deciding whether a graph is Class 1 is NP-hard [19]. Nevertheless, many important graph classes are known to be Class 1. König’s line-coloring theorem [29] shows that every bipartite graph is Class 1, while Erdős and Wilson [7] proved that almost all graphs are Class 1. More recently, Class 1 results have been obtained for sufficiently pseudorandom regular graphs [9], and related decomposition results for pseudorandom graphs further illustrate how delicate exact edge-coloring questions can be even in the graph setting [8]. These results naturally motivate the broader question of when the lower bound χ′(H)≥Δ(H)\chi'(H) \ge\Delta(H) is attained exactly.

The situation changes substantially for hypergraphs. For k≥3k \ge3, there is no analogue of Vizing’s theorem for kk-uniform hypergraphs, which we also call kk-graphs. A construction of Alon and Kim [1] shows that, for infinitely many kk, there exist kk-graphs HH with

χ′(H)≥(k−2+1k−1)Δ(H).\chi'(H) \ge\left(k - 2 + \frac{1}{k-1}\right)\Delta(H).

They also conjectured that this bound should be asymptotically sharp for unrestricted kk-graphs. The best current bound on the conjecture is due to Frederickson, Hao and Kelly [14]. An important feature of the Alon and Kim construction is that the kk-graph is intersecting, so all the color classes have size exactly one. We will see that under additional constraints this bound can be substantially improved.

Answering a question of Erdős and Hanani regarding packings and covering of sets, Rödl [12, 33] developed a semi-random method now called nibbling. The method, in its standard form, allows us to obtain an almost perfect matching in an almost-regular hypergraph as long as its maximum codegree is much smaller than its maximum degree. More precisely, let Δ2(H)\Delta_2(H) be the maximum codegree of HH, i.e., the maximum deg⁡H(u,v)\deg_H(u,v) for every u,v∈V(H)u,v \in V(H). The authors in [12] showed that if HH is a kk-graph with deg⁡(v)=(1+o(1))D\deg(v)=(1+o(1))D for all vertices vv and Δ2(H)=o(D)\Delta_2(H)=o(D), then HH contains a matching of size (1−o(1))nk(1-o(1))\frac{n}{k}. Since its introduction, the nibble method has been developed and refined in many directions, becoming a fundamental technique for constructing large matchings, independent sets and approximate decompositions in hypergraphs (see [2, 23, 27]).

The nibble method is well suited to study the chromatic index of hypergraphs under the same codegree restriction introduced above. The obvious idea is to simply apply nibbling repeatedly to obtain a large set of nearly-perfect matchings. An even better strategy is to build an auxiliary hypergraph where near-perfect matchings correspond to good colorings in the original graph. In this direction, Pippenger and Spencer showed that an almost DD-regular kk-graph HH with codegree o(D)o(D) satisfies χ′(H)=(1+o(1))D\chi'(H)=(1+o(1))D. Their original proof does not provide any explicit estimate on the o(1)o(1) error term. The first explicit quantitative improvements were obtained by Molloy and Reed [32], who gave an explicit bound in terms of the maximum codegree. More precisely, they showed that if HH is a kk-graph with Δ(H)≤D\Delta(H) \le D and Δ2(H)≤C\Delta_2(H) \le C with C=o(D)C=o(D), then

χ′(H)≤D+D(DC)−1/klog⁡4(DC).\chi'(H) \le D + D\left(\frac{D}{C}\right)^{-1/k}\log^4\left(\frac{D}{C}\right).

More recently, this bound was improved even further in the work of Kang, Kühn, Methuku and Osthus [25] and Gould and Kelly [17]. These quantitative improvements still leave an error term of polynomial order in DD. This might indicate a possible natural barrier on the pure nibble method, as suggested in [17].

In a certain sense, the condition Δ2(H)=o(D)\Delta_2(H)=o(D) can be viewed as a pseudorandom condition on the hypergraph HH. Indeed, let HH be an instance of the binomial random hypergraph Hn,p(k)H_{n,p}^{(k)}, i.e., the hypergraph obtained by selecting each edge of the complete kk-graph on nn vertices independently at random with probability pp. Then it is well known that for an appropriate range of pp, the maximum codegree Δ2(H)=O(pnk−2)\Delta_2(H)=O(pn^{k-2}) is much smaller than Δ(H)=Θ(pnk−1)\Delta(H)=\Theta(pn^{k-1}).

Because nibbling, the most fruitful technique in this area, only requires pseudorandomness, comparatively few papers have studied the chromatic index of random hypergraphs specifically.

Kurauskas and Rybarczyk [30] proved that, even if the uniformity kk increases slowly with respect to nn, a random uniform hypergraph admits an edge coloring with (1+o(1))Δ(H)(1+o(1))\Delta(H) colors with high probability. Ferber and Vu [11] studied a natural counterpart to the coloring problem: they used a technique called online sprinkling to show that H∼Hn,p(k)H \sim H_{n,p}^{(k)} contains (1−o(1))Δ(H)(1-o(1))\Delta(H) edge-disjoint perfect matchings. Despite these works, the best previously known asymptotics for the chromatic index of the binomial random hypergraph Hn,p(k)H_{n,p}^{(k)} came from the pseudorandom nibbling. The error term is different for various regimes of pp but is always polynomial. For example, when p=1/2p=1/2, the best known result is due to Gould and Kelly:

Theorem 1.1 ([17]). For any ε>0\varepsilon>0, if H∼Hn,1/2(3)H\sim H_{n,1/2}^{(3)}, then with high probability,

χ′(H)≤Δ(H)+Δ(H)1+εn−1/2.\chi'(H)\leq\Delta(H)+\Delta(H)^{1+\varepsilon}n^{-1/2}.

These results leave open a natural question: For random hypergraphs, can the error term be eliminated completely? Are random hypergraphs Class 1? When k≥4k\geq4, the answer is no. A simple averaging argument (see § 3) shows that when k≥4k\geq4 and k∤nk\nmid n, χ′(Hn,p(k))>Δ(Hn,p(k))\chi'(H_{n,p}^{(k)})>\Delta(H_{n,p}^{(k)}). Our main result shows that when k=3k=3 and n−2/3−1/200≤p≤0.99n^{-2/3-1/200}\leq p\leq0.99, the answer is yes.

Theorem 1.2. For p:=p(n)p:=p(n) satisfying n−2/3−1/200≤p≤0.99n^{-2/3-1/200}\leq p\leq0.99, a random 3-graph H∼Hn,p(3)H\sim H_{n,p}^{(3)} with high probability satisfies

χ′(H)=Δ(H).\chi'(H)=\Delta(H).

We make two remarks about the range of pp in Theorem 1.2. First, the upper bound p≤0.99p\leq0.99 can be relaxed to p≤1−o(1)p\leq1-o(1), although our current approach still requires pp to be bounded away from 11. We chose the stated bound for simplicity of presentation. Second, while the methods developed in this paper do not extend below the threshold p=n−2/3−1/200p=n^{-2/3-1/200}, different techniques can be used to prove that χ′(H)=Δ(H)\chi'(H)=\Delta(H) throughout the range polylog⁡(n)/n≤p≤n−2/3\operatorname{polylog}(n)/n\leq p\leq n^{-2/3}. This complementary regime will be addressed in forthcoming work.

Finally, we’ll formally state that there is no direct analogue to the result of Erdős and Wilson [7] and Theorem 1.2 for uniformity k≥4k\geq4. This is proved in § 3.

Proposition 1.3. Let k≥4k\geq4 and nn be integers such that nn is not a multiple of kk. For p:=p(n)p:=p(n) satisfying p≥Clog⁡n/nk−3p\geq C\log n/n^{k-3} the following holds for sufficiently large nn. The random kk-graph H∼Hn,p(k)H\sim H_{n,p}^{(k)} with high probability satisfies χ′(H)>Δ(H)\chi'(H)>\Delta(H).

Proof overview and probabilistic tools

Proof overview

The following simple observation guides our proof:

Observation 2.1. With high probability, HH has a unique vertex x⋆x_\star of maximum degree, and

deg⁡H(x⋆)−deg⁡H(y)≥pn2log⁡2n\deg_H(x_\star)-\deg_H(y)\geq\frac{\sqrt{pn^2}}{\log^2 n}

for every y≠x⋆y\ne x_\star (Theorem 9.1). Further, a proper edge-coloring uses exactly Δ(H)=deg⁡H(x⋆)\Delta(H)=\deg_H(x_\star) colors if and only if every color class contains an edge incident to x⋆x_\star.

With this degree gap in hand, we might try the following naive proof strategy: Reserve a reservoir E⋆E_\star of edges incident to x⋆x_\star, with ∣E⋆∣|E_\star| smaller than the degree gap, and define

H~:=H∖E⋆.\widetilde{H}:=H\setminus E_\star.

Since the reservoir is smaller than the gap, x⋆x_\star remains the unique maximum-degree vertex of H~\widetilde{H}. Now apply an existing chromatic-index theorem for hypergraphs with small codegrees (see [17, 25]). Such a theorem colors H~\widetilde{H} using nearly Δ(H~)\Delta(\widetilde{H}) matchings. Since x⋆x_\star has degree Δ(H~)\Delta(\widetilde{H}) in H~\widetilde{H}, exactly Δ(H~)\Delta(\widetilde{H}) of these matchings must contain an edge with x⋆x_\star. The additional matchings, coming from the error term in the chromatic-index theorem, do not contain x⋆x_\star.

To obtain an optimal edge-coloring of HH, we must repair each of the matchings not containing x⋆x_\star. Ideally, we could simply insert a reserved edge from E⋆E_\star into each of them. We would then put the unused edges of E⋆E_\star into singleton color classes. This would yield a proper edge-coloring of HH where each color class contains x⋆x_\star.

Unfortunately, this strategy does not work. During the repair procedure, each reserved edge can only be used once. Thus, for our strategy to succeed, we need more reserved edges than there are deficient matchings. The difficulty is that the number of deficient matchings is equal to the error term in the previously-known chromatic-index bounds, which is much larger than the degree gap.

If our starting hypergraph was sparser, the error term from the available chromatic index bounds would be smaller. If the error term was reduced to less than the degree gap, our idea would work. With this in mind, we modify our approach. For simplicity, we will start by assuming that 3∣n3 \mid n, so perfect matchings exist.

Suppose that we found a large set of perfect matchings K\mathcal{K} that covered almost all of H∼Hn,p(3)H \sim H_{n,p}^{(3)}. Let the remainder graph RR contain all the edges not in K\mathcal{K}. Then RR is sparse, has small codegrees, and still satisfies

deg⁡R(x⋆)−deg⁡R(y)≥pn2log⁡2nfor every y≠x⋆.\deg_R(x_\star)-\deg_R(y)\ge\frac{\sqrt{pn^2}}{\log^2 n}\qquad\text{for every }y\ne x_\star.

Our previous strategy is now viable: we reserve edges containing x⋆x_\star inside RR, apply a hypergraph chromatic-index theorem to the rest of RR, and then use a greedy algorithm to repair the deficient matchings (see Proposition 10.1). Because RR is sparse, the error in the chromatic-index theorem is now much smaller than the degree gap, so the repair step works. This yields a proper edge-coloring of RR with Δ(R)\Delta(R) colors. We combine this with K\mathcal{K} to obtain a proper edge-coloring of HH with Δ(H)\Delta(H) colors.

2.1.1. Overview of the Iterative Process. The core of this paper is an iterative procedure to find this large set of perfect matchings K\mathcal{K}. We have to use a method other than nibbling: while the matchings obtained from nibbling in a naive way are near-perfect, they are still not large enough to suitably sparsify the graph. The problem of packing a large set of perfect matchings in K\mathcal{K} has previously been attacked using online sprinkling (see [11]). This technique actually works when pp is very small and HH is sparse, and is the main idea in our forthcoming work for the sparse case. However, it fails when HH is dense. Therefore, in § 7, we introduce a different sparsification step, called Stage I, that removes perfect matchings by “projecting” the 3-graph into bipartite 2-graphs. Unfortunately, even after an application of Stage I, the graph is too dense to use our finishing strategy. We would like to apply Stage I repeatedly, but the output of Stage I is not pseudorandom enough to be used as input for the next application of Stage I. This motivates our actual approach: a 2-stage iterative absorption scheme used to apply Stage I multiple times.

References

  1. [1]N. Alon and J. H. Kim, On the degree, size, and chromatic index of a uniform hypergraph, journal of combinatorial theory, Series A 77 (1997), no. 1, 165–170. ↑2DOI
  2. [2]N. Alon, J. H. Kim, and J. Spencer, Nearly perfect matchings in regular simple hypergraphs, Israel Journal of Mathematics 100 (1997), 171–187. ↑2DOI
  3. [3]Z. Baranyai, On the factorization of the complete uniform hypergraph, Infinite and finite sets, 1975, pp. 91–108. ↑1
  4. [4]B. Bollobás, Random graphs, Second, Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001. MR1864966 ↑63, 64
  5. [5]B. Bollobás and B. Bollobás, Random graphs, Springer, 1998. ↑46
  6. [6]R. Diestel, Graph theory, Fifth, Graduate Texts in Mathematics, vol. 173, Springer, Berlin, 2017. MR3644391 ↑16
  7. [7]P. Erdős and R. J. Wilson, On the chromatic index of almost all graphs, Journal of Combinatorial Theory, Series B 23 (1977), no. 2–3, 255–257. ↑1, 3DOI
  8. [8]A. Ferber, B. Frederickson, D. Mao, L. Yepremyan, and Y. Zhu, Regular bipartite decompositions of pseudorandom graphs, 2024. ↑2arxiv.org/abs/2410.12981
  9. [9]A. Ferber and V. Jain, 1-factorizations of pseudorandom graphs, 2018 ieee 59th annual symposium on foundations of computer science (focs), 2018, pp. 698–708. ↑1, 25arxiv.org/abs/1803.10361
  10. [10]A. Ferber, G. Kronenberg, and E. Long, Packing, counting and covering hamilton cycles in random directed graphs, Israel Journal of Mathematics 220 (2017), 57–87. ↑25
  11. [11]A. Ferber and V. Vu, Packing perfect matchings in random hypergraphs, Random Structures & Algorithms 52 (2018), no. 3, 367–378. ↑3, 4arxiv.org/abs/1606.09492
  12. [12]P. Frankl and V. Rödl, Ner perfect coverings in graphs and hypergraphs, European Journal of Combinatorics 6 (1985), no. 4, 317–326. ↑2DOI
  13. [13]K. Frankston, J. Kahn, B. Narayanan, and J. Park, Thresholds versus fractional expectation-thresholds, Annals of Mathematics 194 (2021), no. 2, 475–495. ↑42, 43arxiv.org/abs/1910.13433
  14. [14]S. Frederickson, Y. Hao, and T. Kelly, Improved bounds for the chromatic index of k-uniform hypergraphs, arXiv preprint arXiv:2607.03573 (2026). ↑2arxiv.org/abs/2607.03573
  15. [15]D. A Freedman, On tail probabilities for martingales, the Annals of Probability (1975), 100–118. ↑7DOI
  16. [16]S. Gandham, M. Dawande, and R. Prakash, Link scheduling in wireless sensor networks: Distributed edge-coloring revisited, Journal of Parallel and Distributed Computing 68 (2008), no. 8, 1122–1134. ↑1DOI
  17. [17]S. Gould and T. Kelly, Advancing the Rödl nibble: New bounds on matchings and the list chromatic index of hypergraphs, arXiv preprint arXiv:2511.11375 (2025). ↑2, 3, 4arxiv.org/abs/2511.11375
  18. [18]D. Hefetz, D. Kühn, J. Lapinskas, and D. Osthus, Optimal covers with hamilton cycles in random graphs, Combinatorica 34 (2014), no. 5, 573–596. ↑46
  19. [19]I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981), no. 4, 718–720. MR635430 ↑1DOI
  20. [20]V. Jain and H. T. Pham, Optimal thresholds for Latin squares, Steiner triple systems, and edge colorings, Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024, pp. 1425–1436. MR4699302 ↑15arxiv.org/abs/2212.06109
  21. [21]S. Janson, A. Ruciński, and T. Łuczak, Random Graphs, John Wiley & Sons, 2000. ↑7
  22. [22]T. Januario, S. Urrutia, C. C. Ribeiro, and D. de Werra, Edge coloring: A natural model for sports scheduling, European Journal of Operational Research 254 (2016), no. 1, 1–8. ↑1
  23. [23]J. Kahn, Asymptotically good list-colorings, Journal of Combinatorial Theory, Series A 73 (1996), no. 1, 1–59. ↑2DOI
  24. [24]D. Y. Kang, T. Kelly, D. Kühn, A. Methuku, and D. Osthus, Thresholds for latin squares and steiner triple systems: Bounds within a logarithmic factor, Transactions of the American Mathematical Society 376 (2023), no. 09, 6623–6662. ↑6, 15, 16, 63arxiv.org/abs/2206.14472
  25. [25]D. Y. Kang, D. Kühn, A. Methuku, and D. Osthus, New bounds on the size of nearly perfect matchings in almost regular hypergraphs, Journal of the London Mathematical Society 108 (2023), no. 5, 1701–1746. ↑2, 4, 6, 32, 33DOI
  26. [26]P. Keevash, The optimal edge-colouring threshold, 2022. ↑15arxiv.org/abs/2212.04397
  27. [27]J. H. Kim, The ramsey number r(3, t) has order of magnitude t² / log t, Random Structures & Algorithms 7 (1995), no. 3, 173–207. ↑2DOI
  28. [28]F. Knox, D. Kühn, and D. Osthus, Edge-disjoint hamilton cycles in random graphs, Random Structures & Algorithms 46 (2015), no. 3, 397–445. ↑46
  29. [29]D. König, Über graphen und ihre anwendung auf determinantentheorie und mengenlehre, Mathematische Annalen 77 (1916), no. 4, 453–465. ↑1DOI
  30. [30]V. Kurauskas and K. Rybarczyk, On the chromatic index of random uniform hypergraphs, SIAM Journal on Discrete Mathematics 29 (2015), no. 1, 541–558. ↑3DOI
  31. [31]C. McDiarmid, Concentration for independent permutations, Combinatorics, Probability and Computing 11 (2002), no. 2, 163–178. ↑8DOI
  32. [32]M. Molloy and B. Reed, Near-optimal list colorings, Random Structures & Algorithms 17 (2000), no. 3-4, 376–402. ↑2, 6, 32doi.org/10.1002/1098-2418(200010/12)17:3/4<376::aid-rsa10>3.0.co;2-0
  33. [33]V. Rödl, On a packing and covering problem, European Journal of Combinatorics 6 (1985), no. 1, 69–78. ↑2DOI
  34. [34]J. Tropp, Freedman's inequality for matrix martingales (2011). ↑7arxiv.org/abs/1101.3039
  35. [35]V. G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret analiz 3 (1964), 25–30. ↑1

Paper details

vlnc:W_bp5wha6w
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents