Skip to main content
1 of 4

A form of Hadwiger's conjecture for hypergraphs

A hypergraph $H=(V,E)$ consists of a set $V$ and $E\subseteq {\mathcal P}(V)$. If $S\subseteq V$, we define $$E|_S = \{e\cap S: (e\in E) \land (e\cap S \neq \emptyset)\}$$ and call $(S, E|_S)$ the induced sub-hypergraph of $H$.

We say that $H=(V,E)$ is connected if for all $X \subseteq V$ with $\emptyset \neq X \neq V$ there is $e\in E$ such that $$e\cap X \neq \emptyset \neq e \cap (V\setminus X).$$

Let $H=(V,E)$ be a hypergraph and $\kappa\neq \emptyset$ be a cardinal. Then a map $c:V\to \kappa$ is said to be a colouring if for every $e\in E$ with $|e|\geq 2$ we have that the restriction $c\restriction_e$ is non-constant. The chromatic number $\chi(H)$ of $H$ is the smallest cardinal $\kappa$ such there is a colouring $c:V\to \kappa$.

If $H=(V,E)$ is a hypergraph and $S_1, S_2\subseteq V$ are disjoint, we say they are connected to each other if there is $e\in E$ such that $$e\cap S_1 \neq \emptyset \neq e\cap S_2.$$

A form of Hadwiger's conjecture for hypergraphs

Assume that $H=(V,E)$ is a hypergraph and let's assume $V\neq \emptyset \neq E$ to avoid pathologies. Let $\kappa \neq \emptyset$ be a cardinal such that there is no colouring $c:V\to \kappa$.

Then there is a collection ${\mathcal S}$ of non-empty, mutually disjoint subsets of $V$ with $|{\mathcal S}| = \kappa$ such that

  1. $(S, E|_S)$ is a connected hypergraph for each $S\in {\mathcal S}$, and
  2. whenever $S\neq T\in {\mathcal S}$ then $S, T$ are connected to each other.

(In the graph context, this amounts to saying that there is a complete minor of cardinality $\kappa$.)

Question. Does this version of Hadwiger's conjecture hold for hypergraphs with infinite chromatic number?

(A similar statement is known to hold for graphs with infinite chromatic number, but it is open whether it is valid for graphs with finite chromatic number.)