2
$\begingroup$

I came across the following simple question that seems to be open:

Let $U$ be a set of $n$ elements. Let $P_1$ be a partition of $U$ into $k\le n$ "blocks" (i.e. disjoint subsets) and let $P_2 \ne P_1$ be another distinct partition of $U$ into $k$ blocks.

Question: How large can we choose $k$ such that there exist $x,y \in U$ with the property that $x$ and $y$ are contained in a block in $P_1$ and also contained in a block of $P_2$?

Remarks:

  • An equivalent way to think about this is how large we need to choose $n$ as a function of $k$ to ensure that there exist such blocks with common elements.

  • Clearly, for any constant $k$, we can make $n$ large enough to ensure the existence of such $x,y$ that lie in the same block in both partitions. I am much more interested in the case where $k$ is a function that grows with $n$. For instance, is it still true if $k \ge \sqrt{n}$?

  • This seems to be related to the social golfer problem, defined as follows: "32 golfers play golf once a week in groups of 4. Schedule these golfers to play for as many weeks as possible without any two golfers playing together in a group more than once." However, I could not find asymptotic bounds for this problem but rather only specific instances that people have solved.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Why the downvote? $\endgroup$
    – somebody
    Commented Dec 29, 2023 at 23:25
  • 2
    $\begingroup$ $k=\sqrt{n}$ is about right. Larger won't work because we can take the sets of $P_1$ to be $k$ sets of size $k$ and then the $j$th set of $P_2$ as the $j$th element of each set of $P_1$. On the other hand, if both partitions have $<\sqrt{n}$ sets, then there is a set with $\ge \sqrt{n}$ elements, and the property holds by the pigeonhole principle. $\endgroup$
    – Christian Remling
    Commented Dec 30, 2023 at 0:32

0

Reset to default

You must log in to answer this question.