Let $X$ be an infinite set, and let $(A_n)_{n\in\omega}$ be a collection of subsets of $X$ with the following properties:

  1. $|A_m\cap A_n| \leq 1$ for $m\neq n\in \omega$, and
  2. $|A_n|=\aleph_0$ for all $n\in \omega$.

We consider the following statement:

(EFL$_\omega$:) There is $f:X\to \omega$ such that for all $n\in\omega$ the restriction $f|_{A_n}:A_n\to\omega$ is a bijection.

Questions. Is (EFL$_\omega$) true? Or does (EFL$_\omega$) imply the original Erdös-Faber-Lovasz conjecture?


If I understand it correctly, it's false. Let $x \notin A_0 = \{1,2,\dots \}$. Then let $A_i$ all meet at $x$, and also each meet $A$ at $i$ (add extra elements as necessary; they should be irrelevant). Then $f(x) \neq f(i)$ for any $i$, so $f(x) \notin f(A)$.

This didn't work in the finite case because the sets meeting $A$ cannot exhaust $A$, as the number of such sets is strictly less than the number of elements of $A$. When working over infinite sets, this is no longer true.

  • 1
    $\begingroup$ Nice construction, thanks! (There is one typo, I guess by $A$ you mean $A_0$?) $\endgroup$ – Dominic van der Zypen Sep 5 '18 at 8:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.