Skip to main content
4 of 4
added 69 characters in body

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 statement amounts to saying that there is a complete minor of cardinality $\kappa$, and it is true for graphs with infinite chromatic number, but it is not known whether the statement holds for graphs $G$ with $\chi(G) < \aleph_0$.)

Question. Is the form of Hadwiger's conjecture for hypergraphs presented above true?