On the colorability of bi-hypergraphs

NEW

Problem: In the paper’s notation, $\ell(n,r)$ is the minimum number of edges in a minimal uncolorable $r$-uniform bi-hypergraph of order $n$, or $\infty$ if none exists. For a $3$-uniform bi-hypergraph $H=(V,E)$, a coloring $c:V\to\mathbb N$ is proper exactly when every edge has exactly two colors. The reconstructed conjecture is:

Result: The conjecture is true.

Zhang–Dong–Zhang already construct a minimal uncolorable $3$-uniform bi-hypergraph on $7$ vertices with $11$ edges, so $\ell(7,3)\le 11$. One such example has vertices

and edges

It remains to exclude $10$ edges. Since their Theorem $m(3)=10$ implies every $3$-uniform bi-hypergraph with at most $9$ edges is colorable, any $10$-edge uncolorable example minimal on $7$ vertices must have no isolated vertex. Thus it suffices to check that no $10$-edge subset of $\binom{[7]}3$ covering all seven vertices is uncolorable.

This finite check is exact. A coloring depends only on its partition of $[7]$; there are $877$ such partitions. For a triple $e$, mark the partitions under which $e$ is bad, i.e. has $1$ or $3$ colors. A hypergraph is uncolorable iff its chosen triples’ bad-partition sets cover all $877$ partitions.

The following deterministic exhaustive verifier enumerates all $10$-subsets of $\binom{[7]}3$, with only monotone pruning:

from itertools import combinations

n = 7
T = list(combinations(range(n), 3))

def rgs(n):
    a = [0]*n
    def rec(i, m):
        if i == n:
            yield tuple(a); return
        for x in range(m+2):
            a[i] = x
            yield from rec(i+1, max(m, x))
    yield from rec(1, 0)

P = list(rgs(n))
ALLP = (1 << len(P)) - 1
ALLV = (1 << n) - 1

bad, vert = [], []
for t in T:
    b = 0
    for i,p in enumerate(P):
        if len({p[x] for x in t}) != 2:
            b |= 1 << i
    bad.append(b)
    v = 0
    for x in t:
        v |= 1 << x
    vert.append(v)

N = len(T)
sufB = [0]*(N+1)
sufV = [0]*(N+1)
for i in range(N-1, -1, -1):
    sufB[i] = sufB[i+1] | bad[i]
    sufV[i] = sufV[i+1] | vert[i]

def dfs(i, k, B, V):
    if k == 10:
        return B == ALLP and V == ALLV
    if i == N or k + (N-i) < 10:
        return False
    if (B | sufB[i]) != ALLP:
        return False
    if (V | sufV[i]) != ALLV:
        return False
    return dfs(i+1, k+1, B | bad[i], V | vert[i]) or dfs(i+1, k, B, V)

print(dfs(0, 0, 0, 0))

It prints False. Therefore no $10$-edge uncolorable $3$-uniform bi-hypergraph on $7$ non-isolated vertices exists. Hence $\ell(7,3)\ge 11$. Combined with the $11$-edge construction, $\ell(7,3)=11$.

Citation: Definitions, $m(3)=10$, and the $11$-edge upper construction are from Meiqiao Zhang, Fengming Dong, Ruixue Zhang, “On the colorability of bi-hypergraphs,” arXiv:2310.06464. The exclusion of the $10$-edge order-$7$ case above is the new part.