8
$\begingroup$

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)$?
Improve this question
$\endgroup$
8
  • 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
    Commented Jan 11, 2016 at 23:48
  • $\begingroup$ @bof: How do you see that you can't have $X$ infinite or $|a|=2$? $\endgroup$
    – Douglas Zare
    Commented Jan 12, 2016 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
    Commented Jan 12, 2016 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
    Commented Jan 12, 2016 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
    Commented Jan 12, 2016 at 9:45

1 Answer 1

Reset to default
5
$\begingroup$

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

https://en.m.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Faber%E2%80%93Lov%C3%A1sz_conjecture

Improve this answer
$\endgroup$
3
  • $\begingroup$ Can you be a bit more precise about how the stated question is equivalent to the EFL conjecture? $\endgroup$
    – Sam Hopkins
    Commented Jan 12, 2016 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
    Commented Jan 12, 2016 at 19:08
  • $\begingroup$ Oh right... brilliant thanks, Fedor! $\endgroup$
    – Dominic van der Zypen
    Commented Jan 12, 2016 at 19:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .