1
$\begingroup$

Let $\mathcal{F}$ be the family of all $k$-element subsets of $[n]$. What is the smallest $\ell$ such that we can partition $\mathcal{F}$ into $\ell$ families $F_1,\dots,F_\ell$ with the property that none of the $F_i$ contains two sets that intersect in at most two elements?

Of course, one can generalize this question to intersections of size at most $r$, but I couldn't even figure out this "simple" case. If no such lower bound is known, are there related problems I could look into?

Update: As pointed out in the comments, this is related to the the chromatic number of the generalized Kneser graph.

Update 2: Does finding such a lower bound become any easier if we assume $\mathcal{F}$ contains all subsets of $[n]$? (Of course, this assumption implies a trivial lower bound of ${n \choose 2} + n$ but is there anything better?)

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ In other words, you want the chromatic number of the generalized Kneser graph $K(n,k,2)$. $\endgroup$
    – bof
    Commented Apr 17, 2022 at 19:56
  • $\begingroup$ Yes, or any lower bound on it. $\endgroup$
    – wandering_lambda
    Commented Apr 17, 2022 at 19:58
  • 1
    $\begingroup$ for the family of all subsets, all sets with at most three elements must be of different color, right? $\endgroup$
    – Fedor Petrov
    Commented Apr 18, 2022 at 6:27
  • $\begingroup$ Yes, thus an easy lower bound would be $\sum_{i=1}^3{n \choose i}$. $\endgroup$
    – wandering_lambda
    Commented Apr 18, 2022 at 13:18

0

Reset to default

You must log in to answer this question.