1
$\begingroup$

I am looking in the literature for references to combinatorial result of the kind of the one below. I am quite sure they (or some variations of them) should have been studied intensively, but now I am unable to find a reference. Thank you in advance for any suggestion.

"Let $X$ be a finite set and let $\mathfrak{P}$ be a finite collection of partitions of $X$. Then, [under some hypotheses...], there exists a partition $P$ [satisfying some restrictions, e.g., having $k$ parts...] of $X$ such that for all $p \in P$ and for all $Q \in \mathfrak{P}$ there exists $q \in Q$ such that $p \cap q = \emptyset$."

I give also a more concrete (and figurative example), hoping to make clear the kind of problems I have in mind:

"There are finitely many people. Each of them is from London, Paris, or Rome; and is (as usual) male or female. If [hypotheses] then the people can be split into two teams, so that no team has players from all the mentioned cities and of both the two sexes"

Improve this question
$\endgroup$
1
  • $\begingroup$ When you say "partition" do you mean a partitioning of $X$ into two sets, or into an arbitrary number of sets? $\endgroup$
    – Jon Noel
    Commented Jul 7, 2017 at 21:47

1 Answer 1

Reset to default
1
$\begingroup$

If I'm not mistaken, all you need is that $\mathfrak{P}$ does not contain the trivial partition $\{X\}$ and you may as well always choose $P=\{\{x\}: x\in X\}$.

Suppose that $\mathfrak{P}$ does not contain the trivial partition. Then let $P=\{\{x\}: x\in X\}$. For each $\{x\}\in P$ and $Q\in \mathfrak{P}$, let $q$ be any element of $Q$ which does not contain $x$ (such a set $q$ must exist as $Q$ is not the trivial partition). Then $\{x\}\cap q = \emptyset$, as desired.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Of course, the partition into all singletons always work. Indeed, I didn't meant only "under some hypotheses...", but also I wanted that $P$ satisfies some restrictions (for example being a partition into two subsets, as you mentioned), I'm going to fix it. Anyway, I'm not looking for an answer/proof for a specific problem, but to a reference where results of this flavor are given. I'm also going to add a more concrete example. $\endgroup$
    – sercej
    Commented Jul 8, 2017 at 10:43

You must log in to answer this question.

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