On the colorability of bi-hypergraphs

NEW

Problem: Reconstructed statement. Work in finite $r$-uniform bi-hypergraphs $H=(V,E)$, i.e. mixed hypergraphs with $\mathcal C=\mathcal D=E\subseteq \binom Vr$. A coloring $c:V\to \mathbb N$ is proper if

Thus no edge is monochromatic and no edge is rainbow. A bi-hypergraph is minimal uncolorable if it is uncolorable, but every proper subhypergraph is colorable. Let $\mathcal{MUC}(n,r)$ be the set of minimal uncolorable $r$-uniform bi-hypergraphs on $n$ vertices. The conjecture is:

This is exactly Conjecture 1 in Zhang--Dong--Zhang.

Result: The conjecture is true.

Put

Let

and let $W=W_1\cup\cdots\cup W_{r-2}$, where the $W_i$'s are disjoint and $|W_i|=r-1$. Add vertices $z_1,\dots,z_t$.

For $t=0$, take the complete $r$-uniform hypergraph on $R\cup W$. It is uncolorable by the pigeonhole principle, and deleting any vertex leaves $(r-1)^2$ vertices, colorable with $r-1$ color classes of size $r-1$.

Assume $t\ge 1$. Define $G_t$ on

with edge set consisting of:

1. all $r$-subsets of $R\cup W$, except $R$;
2. all sets $\{z_i\}\cup T$, where $1\le i\le t$ and $T\in\binom W{r-1}$;
3. all sets $\{z_{i-1},z_i\}\cup T$, where $1\le i\le t$ and $T\in\binom W{r-2}$;
4. the final edge

First observe that in any proper coloring of the complete $r$-graph on $R\cup W$ with the single edge $R$ removed, the vertices of $R$ must be monochromatic, and $W$ must split into exactly $r-2$ color classes of size $r-1$. Indeed, if $R$ were not monochromatic, then no color class could have size $r$, and no $r$ distinct colors could occur; otherwise there would be a forbidden monochromatic or rainbow edge different from $R$. But then at most $(r-1)^2$ vertices could be colored, contradicting $|R\cup W|=(r-1)^2+1$.

Now suppose $G_t$ has a proper coloring. From the previous paragraph, $R$ has one color, say $\alpha$, and $W$ has $r-2$ other colors, each appearing $r-1$ times. Inductively, for each $i$, the edges $\{z_i\}\cup T$ forbid $z_i$ from having one of the $W$-colors, and the edges $\{z_{i-1},z_i\}\cup T$, with $T$ choosing one vertex from each $W_j$, forbid $z_i$ from having a new color. Hence every $z_i$ has color $\alpha$. Therefore $L_t$ is monochromatic, contradiction. So $G_t$ is uncolorable.

Also $G_t-v$ is colorable for every vertex $v$. If $v$ lies on the path $z_0,z_1,\dots,z_t$, color the component before $v$ and the fixed vertices $a_2,\dots,a_r$ with one color, the component after $v$ with a second color, and color each $W_j$ monochromatically with its own color. If $v\in L_t$, the edge $L_t$ disappears and the same coloring with only one path-color works. If $v\in W$, color $z_0,\dots,z_t,a_2$ with color $1$, color $a_3,\dots,a_r$ with color $2$, and color $W\setminus\{v\}$ using $r-3$ vertices of color $1$, one vertex of color $2$, and $r-1$ vertices in each of colors $3,\dots,r-1$. A direct check shows every remaining edge has between $2$ and $r-1$ colors.

Thus $G_t$ is vertex-critical uncolorable.

Finally, enlarge the nonedge set of $G_t$ maximally while preserving uncolorability. Equivalently, delete edges from $G_t$ until an edge-minimal uncolorable spanning subhypergraph $H_t$ is obtained. Since every $G_t-v$ is colorable, every $H_t-v$ is colorable too. Edge-minimality gives that deleting any edge makes $H_t$ colorable. Hence every proper subhypergraph of $H_t$ is colorable, so $H_t\in\mathcal{MUC}(n,r)$.

Therefore $\mathcal{MUC}(n,r)\ne\varnothing$ for all $r\ge3$ and $n\ge(r-1)^2+1$.

Citation: No prior resolution is used here. The reconstructed conjecture and notation are from Zhang, Dong, and Zhang, “On the colorability of bi-hypergraphs,” arXiv:2310.06464, Conjecture 1.