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$?

Improve this question
$\endgroup$
3
  • $\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
    Commented Jul 9, 2017 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
    Commented Jul 9, 2017 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
    Commented Jul 10, 2017 at 5:26

0

Reset to default

You must log in to answer this question.