This is question Selection problem in a collection of non-empty sets with a simplification in criterion 3.

Is there a set $X\neq\emptyset$ and a collection ${\cal F}\subseteq {\cal P}(X)\setminus\{\emptyset\}$ of non-empty subsets of $X$ with the following properties?

  1. $a\in {\cal F} \implies |a|\geq 2$,
  2. $a\neq b\in {\cal F} \implies |a\cap b| \leq 1$, and
  3. there is no function $f: {\cal F} \to X$ such that

    • if $a, b\in {\cal F}$ with $a\ne b$ and $a\cap b\neq \emptyset$ then $f(a)\neq f(b)$?
  • 3
    $\begingroup$ Interesting question. It's not a Selection problem any more since $f(a)\in a$ is not required. I'd call it "edge chromatic numbers of hypergraphs". Of course there is no such $\mathcal F$ with $X$ infinite or with $|a|=2$ for all $a\in\mathcal F.$ A projective plane won't do because the number of lines is equal to the number of points. $\endgroup$ – bof Jan 11 '16 at 23:48
  • $\begingroup$ @bof: How do you see that you can't have $X$ infinite or $|a|=2$? $\endgroup$ – Douglas Zare Jan 12 '16 at 0:45
  • $\begingroup$ @DouglasZare If $X$ is infinite then there is an injection $i:\binom X2\to X$. If $\mathcal F$ satisfies (1) then for each $a\in\mathcal F$ we can choose $a'\subseteq a$ with $|a'|=2.$ If (2) also holds, then $a\to a'$ is an injection, and so is $a\to i(a'),$ so we can define $f(a)=i(a').$ $\endgroup$ – bof Jan 12 '16 at 1:36
  • $\begingroup$ @DouglasZare Suppose $|a|=2$ for all $a\in\mathcal F.$ We may assume $|X|=n\lt\infty.$ Then the question is, can a graph of order $n$ have edge chromatic number greater than $n$? I.e., can the complete graph $K_n$ have edge chromatic number greater than $n$? It's an elementary result in graph theory that $K_n\ (n\gt1)$ has edge chromatic number $n$ or $n-1$ according as $n$ is odd or even. We could also cite Vizing's theorem: a simple graph $G$ has $\chi'(G)\le\Delta(G)+1$ where $\chi'$ is the edge chromatic number and $\Delta$ the maximum degree, so $\chi'(K_n)\le\Delta(K_n)+1=n.$ $\endgroup$ – bof Jan 12 '16 at 1:56
  • 2
    $\begingroup$ This if true would generalize famous result (Fisher inequality?) that if any two sets $a\ne b$ from $\mathcal{F}$ satisfy $|a\cap b|=1$, then $|\mathcal{F}|\leqslant |X|$. Which has different proofs, including linear algebraic, but none of them is obvious. We should probably try to examine these proofs on generalizability in this chromatic direction. $\endgroup$ – Fedor Petrov Jan 12 '16 at 9:45

This is equivalent reformulation of Erdös-Faber-Lovász conjecture, see Wikipedia page about it.


  • $\begingroup$ Can you be a bit more precise about how the stated question is equivalent to the EFL conjecture? $\endgroup$ – Sam Hopkins Jan 12 '16 at 19:07
  • 1
    $\begingroup$ It is precisely explained in Wikipedia. After introducing some notations and simple reasoning they conclude: "Thus, the Erdős–Faber–Lovász conjecture is equivalent to the statement that any simple hypergraph with n vertices has chromatic index (edge coloring number) at most n." $\endgroup$ – Fedor Petrov Jan 12 '16 at 19:08
  • $\begingroup$ Oh right... brilliant thanks, Fedor! $\endgroup$ – Dominic van der Zypen Jan 12 '16 at 19:21

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.