5
$\begingroup$

Question. Does every hypergraph that does not admit a complete minor with $5$ elements have a coloring with $4$ colors?

Below are the definitions to make this precise.

If $H = (V, E)$ is a hypergraph and $W \subseteq V$, then we let the induced sub-hypergraph of $W$ be $H|_W := (W, E|_W)$, where $E|_W := \{e \cap W: e \in E \text{ and }e\cap W \neq \emptyset\}$.

We say that $H$ is connected if for every non-empty proper subset $T$ of $V$ there is $e\in E$ such that $e$ intersects both $T$ and $V \setminus T$.

If $S, T \subseteq V$ are non-empty and disjoint, we say that $S, T$ are connected to each other if there is $e\in E$ interesting both $S$ and $T$.

$H$ is said to have a complete minor with $n$ elements if there are $n$ non-empty mutually disjoint subsets that are connected to each other, and each subset is connected as an induced sub-hypergraph.

Finally, the hypergraph $H$ is colorable with $4$ colors if there is a map $c: V \to \{0,1,2,3\}$ such that for every $e \in E$ with $|e|>1$ the restriction $c|_e:e\to\{0,1,2,3\}$ is non-constant.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Relevant background: This result for graphs (not hypergraphs) is the $k=5$ case of Hadwiger's conjecture en.wikipedia.org/wiki/Hadwiger_conjecture_(graph_theory) . Wagner (1937) proved that this case of Hadwiger's conjecture is equivalent to the 4 color theorem, and therefore it is now known, since the 4 color theorem has been proved. Since hypergraphs are more general than graphs, a positive answer to this question should need to cite the 4 color theorem, or something of similar strength. $\endgroup$
    – David E Speyer
    Commented Jul 17 at 16:33
  • 1
    $\begingroup$ Another way one might define "$S$ and $T$ are connected to each other": there is an edge $e\in E$ intersecting both $S$ and $T$ and contained in $S\cup T$. This is equivalent to your definition for ordinary graphs but stronger for general hypergraphs. Maybe with this definition the answer to your question would be different or at least harder to come by. $\endgroup$
    – bof
    Commented Jul 18 at 9:35

1 Answer 1

Reset to default
5
$\begingroup$

This follows from the case of graphs (i.e. hypergraphs where all sets have size $\leq 2$). As I explained in the comments above, Hadwiger's conjecture says that a graph with no $K_k$ minor is $(k-1)$-colorable, so the current question for graphs is the $k=5$ case of Hadwiger's conjecture. In 1937, Wagner showed that the $k=5$ case of Hadwiger for graphs is equivalent to the $4$-color theorem; in 1976, Appel and Haken proved the $4$-color theorem. So the OP's conjecture is true for graphs, and now we need to prove the hypergraph case.

Let $H$ be a hypergraph with ground set $V$. Define $\Gamma(H)$ to be the graph with vertex set $V$ where $(i,j)$ is an edge of $\Gamma(H)$ if and only if there is some set $E$ in $H$ with $\{i,j \} \subseteq E$. The following lemmas are immediate from the definitions:

Lemma For any subset $W$ of $V$, $\Gamma(H|_W) = \Gamma(H)|_W$.

Lemma The hypergraph $H$ is connected if and only if the graph $\Gamma(H)$ is connected.

Lemma $S$ and $T$ are connected to each other in $H$ if and only if there is an edge from $S$ to $T$ in $\Gamma(H)$.

Combining these lemmas, $H$ has a $K_5$ minor if and only if $\Gamma(H)$ has a $K_5$ minor. Now, suppose that $H$ has no $K_5$ minor, so that $\Gamma(H)$ has no $K_5$ minor. By this case of Hadwiger's conjecture, the graph $\Gamma(H)$ is $4$-colorable; let $\chi : V \to \{ 0,1,2,3 \}$ be a $4$-coloring. Then I claim that $\chi$ is also a $4$-coloring of $H$.

Indeed, let $E$ be any edge of $H$ with $|E| \geq 2$, and let $i$, $j$ be two distinct elements of $E$. Then $(i,j)$ is an edge of $\Gamma(H$), so $\chi(i) \neq \chi(j)$, so $\chi : E \to \{0,1,2,3 \}$ is not constant, as desired. QED

The other direction of the last step doesn't work -- a coloring of $H$ doesn't always induce a coloring of $\Gamma(H)$. But, fortunately, that's not the direction we need.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ "$H$ has a $K_5$ minor if and only if $Γ(H)$ has a $K_5$ minor." Hm, if $H$ contains only one hyperedge, of size 5, then $\Gamma(H) =K_5$, right? $\endgroup$
    – Fedor Petrov
    Commented Jul 18 at 3:32
  • $\begingroup$ Can you comment a little more on the last paragraph? A casual reading of your argument makes it sound like colouring $H$ and $\Gamma(H)$ should be equivalent but aparently this is not the case. $\endgroup$
    – quarague
    Commented Jul 18 at 6:42
  • 3
    $\begingroup$ @quarague Suppose $H=(V,E)$ where $|V|=n\gt2$ and $E=\{V\}$. Then $\Gamma(H)=K_n$, so a proper colouring of the graph $\Gamma(H)$ needs $n$ colours, while a proper colouring of the hypergraph $H$ needs only $2$ colours. $\endgroup$
    – bof
    Commented Jul 18 at 9:50
  • 1
    $\begingroup$ @FedorPetrov Right. And, if I understand the OP's definitions correctly, your $H$ has a $K_5$-minor. $\endgroup$
    – David E Speyer
    Commented Jul 18 at 11:29
  • 1
    $\begingroup$ @quarague The OP's condition on a coloring is that $\chi |_E$ is non-constant for each edge of $E$ with $|E| \geq 2$. The condition for $\chi$ to be a coloring of $\Gamma(H)$ is that $\chi|_E$ is injective on each $E$. The latter is a stricter condition. $\endgroup$
    – David E Speyer
    Commented Jul 18 at 11:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .