3
$\begingroup$

A hypergraph $H=(V,E)$ with $V$ non-empty is said to be connected if for all $S\subseteq V$ with $\emptyset \neq S \neq V$ there is $e\in E$ such that $e$ intersects both $S$ and $V\setminus S$.

Given a non-empty subset $T$ of $V$, we let $(T, E|_T)$ with $E|_T := \{e\cap T: e\in E\}$ be the subhypergraph induced by $T$. By slight abuse of nomenclature we call $T$ connected if its induced hypergraph $(T, E|_T)$ is connected.

If $\kappa\neq \emptyset$ we say that $H=(V,E)$ is colorable with $\kappa$ colors if there is a map $c:V\to \kappa$ such that the restriction $c|_e: e\to \kappa$ is non-constant whenever $e$ has more than $1$ element.

Conjecture. If $H=(V,E)$ is a hypergraph with $V$ non-empty, and $\kappa$ is a non-empty cardinal (finite or infinite) such that $H$ is not colorable with $\kappa$ colors, then there is a collection ${\cal S}$ consisting of $\kappa$ non-empty, connected, and pairwise disjoint subsets of $V$ such that

whenever $S_0\neq S_1\in{\cal S}$ then there is an edge $e\in E$ intersecting both $S_0$ and $S_1$.

Is this conjecture true?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ By replacing hyperedges with cliques, this conjecture would follow from the special case of graphs, so there is no need to consider hypergraphs. $\endgroup$
    – Will Sawin
    Commented Apr 7, 2022 at 20:03
  • 1
    $\begingroup$ for the graph case, is it possible that not being $\kappa$-colorable could be weakened to not being $(\kappa-1)$-degenerate? $\endgroup$
    – Zach Hunter
    Commented Apr 8, 2022 at 2:46
  • 1
    $\begingroup$ @WillSawin If you replace hyperedges by cliques, you change the chromatic number. For instance if ${\cal E}$ is a countable collection of infinite subsets of $\omega$, then $(\omega, {\cal E})$ is colorable with $2$ colors, but if you replace every hyperedge with a clique, then the resulting graph has chromatic number $\aleph_0$. So this conjecture is much weaker. $\endgroup$
    – Dominic van der Zypen
    Commented Apr 8, 2022 at 9:25
  • $\begingroup$ Your conjecture cannot be weaker because it includes graphs as a special case. $\endgroup$
    – Will Sawin
    Commented Apr 8, 2022 at 12:26
  • $\begingroup$ Unless I'm missing some subtle difference, it seems like you already asked this question three months ago... mathoverflow.net/questions/413206/… $\endgroup$
    – Louis D
    Commented Apr 8, 2022 at 20:41

0

Reset to default

You must log in to answer this question.