# Edge chromatic number of hypergraphs

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)$?
• 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. – bof Jan 11 '16 at 23:48
• @bof: How do you see that you can't have $X$ infinite or $|a|=2$? – Douglas Zare Jan 12 '16 at 0:45
• @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').$ – bof Jan 12 '16 at 1:36
• @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.$ – bof Jan 12 '16 at 1:56
• 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. – Fedor Petrov Jan 12 '16 at 9:45