Return to Question

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.)

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

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?

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.)

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.)

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

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.)

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.)