On Optimal Achromatic Coloring of 3-Uniform Tight Cycles
摘要
For two integers n and k, \(n > k \geqslant 2\) , an n-vertex k-uniform tight cycle \(TC^k_n\) is a hypergraph on n vertices which can be arranged in a cyclic sequence such that every set of k consecutive vertices (and only those) form an edge. A vertex-coloring of a hypergraph H is called achromatic if every edge of H contains vertices of at least two colors and every pair of distinct colors appears together on vertices of some edge. The achromatic number \(\psi (H)\) is the maximum number of colors possible in an achromatic coloring of H. In this paper, we study the achromatic number of k-uniform tight cycles and give early results on the 3-uniform case. We find it more natural to study an extremal function \(f_k(t)\) which denotes the smallest n for which \(\psi (TC^k_n)= t\) . We give a general lower bound for \(f_k(t)\) and an upper bound matching the same for many values of t when \(k = 3\) . We can extend this to infinitely many values of t when \(k=3\) if a well-known conjecture on the infinitude of Sophie Germain primes is true. We also introduce a new conjecture and show that, if this conjecture is true, then \(f_3(t) = t \left\lceil \frac{t-1}{4} \right\rceil \) for all \(t \geqslant 3\) except for \(t=9\) . We have computationally verified this conjecture for t up to 101.