Skip to main content
added 255 characters in body
Source Link

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?)

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?

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?)

Source Link

Partitioning of a set family that avoids small intersections

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?