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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Optimal Achromatic Coloring of 3-Uniform Tight Cycles

  • Srimanta Bhattacharya,
  • Pawan Kumar,
  • Deepak Rajendraprasad,
  • Jishnu Sen

摘要

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.