Combinatorics – Is the Chromatic Number of Hypergraphs Downward Continuous?

co.combinatoricsgraph-coloringshypergraphinfinite-combinatorics

Let $H=(V,E)$ be a hypergraph. The chromatic number $\chi(H)$ is the smallest cardinal $\kappa \leq |V|$ such that there is a map $c:V\to \kappa$ such that for all $e\in E$ having more than one element, the restriction $c|_e: e\to \kappa$ is not constant.

Question. If $H=(V,E)$ is a hypergraph with $V\neq \emptyset$ and $\kappa < \chi(H)$ is a non-empty cardinal, is there necessarily $E_0\subseteq E$ such that $\chi(V, E_0) = \kappa$?

Best Answer

Fred Galvin had conjectured that the answer is "yes" for graphs in [1] (conjecture 2), in his paper he showed that the variation of the problem to induced graphs is consistently false: Assume $2^{\aleph_0}=2^{\aleph_1}<2^{\aleph_2}$ there exists a graph $(V,E)$ with a chromatic number of $\aleph_2$ but for no subset $V'\subseteq V$ we have that the chromatic number of $(V', E\cap [V']^2)$ is $\aleph_1$.

Later in [2] Péter Komjáth had shown the consistency of the failure of the above conjecture: he gave a model in which $2^{\aleph_0}=2^{\aleph_2}=\aleph_3$ where there exists a graph with chromatic number of $\aleph_2$ but no subgraph with chromatic number $\aleph_1$.

Lastly, in [3] Shelah showed a partial positive direction: assume $V=L$, then for any $(V,E)$ and $\kappa$ such that $|V|<\kappa^{+\kappa}$ and $\chi(V,E)>\kappa$, then there exists a subgraph of chromatic number exactly $\kappa$. Further more, he had showed that under $V=L$ there is no counterexample of cardinality $\aleph_2$: every graph with cardinality $\aleph_2$ contains a subgraph in any smaller chromatic number.

[1] Galvin, F., Chromatic numbers of subgraphs, Period. Math. Hung. 4, 117-119 (1973). ZBL0278.05105.

[2] Komjáth, Péter, Consistency results on infinite graphs, Israel J. Math. 61, No. 3, 285-294 (1988). ZBL0668.05031.

[3] Shelah, Saharon, Incompactness for chromatic numbers of graphs, A tribute to Paul Erdős, 361-371 (1990). ZBL0727.05025.

Related Question