4
$\begingroup$

Let $H=(V,E)$ be a hypergraph. If $\kappa>0$ is a cardinal, we say the hypergraph $H$ is $\kappa$-chromatic if there is a function $c:V\to\kappa$ such that for all $e\in E$ the restriction $c|_e$ is not constant (that is, the vertices of every edge are colored with at least $2$ colors).

We say that $H$ is a clique hypergraph if for all $e,f \in E$ we have $e\cap f \neq \emptyset$ and we call $H$ $\kappa$-regular for some cardinal $\kappa$, if $|e| = \kappa$ for all $e\in E$.

Question. If $\kappa \geq \aleph_0$ and $H=(V,E)$ is a $\kappa$-regular clique hypergraph that is $3$-chromatic, but not $2$-chromatic, are there $e\neq f\in E$ such that $|e\cap f| = \kappa$?

$\endgroup$
  • $\begingroup$ If we manage to well-order all edges so that each edge has less than $\kappa$ vertices of all previous edges, we may colour by transfinite induction. $\endgroup$ – Fedor Petrov Jul 9 '17 at 17:31
  • $\begingroup$ The question of whether such a well-ordering is always possible could be a nice MO problem in its own right! $\endgroup$ – Dominic van der Zypen Jul 9 '17 at 18:55
  • $\begingroup$ I think this is relevant: P. Erdős, S. Shelah: Separability properties of almost-disjoint families of sets, Israel J. Math. 12 (1972), 207--214 renyi.mta.hu/~p_erdos/1972-21.pdf $\endgroup$ – Péter Komjáth Jul 10 '17 at 5:26

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.