4
$\begingroup$

I was asked to post a different question following a wording error on my previous question, so here it is.

Given a set family $\mathcal{F}$ of $[n]$ (with certain additional properties), such that every element of $[n]$ lies in exactly $K$ sets in $\mathcal{F}$, what properties of $\mathcal{F}$ are sufficient to guarantee that we can partition $\mathcal{F}$ into $K$ subfamilies $\mathcal{F}_i$ such that each subfamily is a partition of $[n]$?

What I am looking for is a nontrivial sufficient condition that guarantees the existence of such a partition of $\mathcal{F}$(e.g. in the style of Hall's theorem), and whether any papers have studied these kinds of questions before.

I feel this kind of question is very natural, and greatly appreciate any reference on this type of question.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
+50
$\begingroup$

This problem is NP-complete, a nice reference is this answer here by András Salamon: https://cstheory.stackexchange.com/a/356/419

If you are interested in results about the complete family, see Baranyai's theorem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for the references! $\endgroup$
    – abacaba
    Commented Mar 22, 2023 at 21:49

You must log in to answer this question.

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