2026/07/21 by Raina Mary Thomas, Yasmeen Akhtar
Mathematics · #math.CO #msc:05C35 #msc:05C60 #msc:05C65 #msc:05D05 #msc:68R05
arxiv created 2026/07/31 · arxiv updated 2026/08/03
Qualitative independence hypergraphs provide a useful combinatorial framework for analyzing the existence and structure of covering arrays. In this work, we study the uniform and almost-uniform 3-qualitative independence hypergraphs 3-UQI(n,2) and 3-AUQI(n,2), and establish a structural correspondence between these families and merged Johnson graphs, with emphasis on their cores. Focusing on the smallest unresolved instance, 3-QI(8,2), we classify all of its strongly independent sets and determine its strong independence number. Using this, along with its strong chromatic number and the size of the largest 3-clique, we show that 3-QI(8,2) is a core. For n>8, we further identify sufficient conditions under which 3-UQI(n,2) and 3-AUQI(n,2) are cores.