Skip to main content
MathOverflow

Return to Answer

added 7 characters in body
Source Link
Aaron Meyerowitz
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

I gave a longer answer before you clarified the problem. Here is a briefer one. I will mainly talk about $N=100$ and $k=20.$

Note that choosing $\frac{N}k$ groups the strategy and optimum outcome are the same for any of the four goals maximize/minimize the largest/smallest intersection. Only a partition into disjoint groups can ensure that the score is as small (or as large) as $\frac{k^2}N.$

Sticking to maximum intersection size with $N=100$ and $k=20$, one can be sure of a score of $20$ only by choosing $\binom{100}{20}\approx 5.4\cdot 10^{20}=O(N^{10})$ groups. Obviously there are lower numbers of groups that will ensure a score of at least $s$ for other $4 \leq s \lt 20.$ I will suggest that they are not much smaller in terms of polynomial order.

Consider this variation: You pick $a$ groups $X_1,\cdots,X_a$ and the other player picks $b$ groups $Y_1,\cdots,Y_b.$ (All groups $20$ out of $100.$ Your) Your goal is to maximize the guaranteed maximum among the $ab$ sizes $|X_i\cap Y_j|$$|X_i\cap Y_j|.$

If still $a=5,$ how do things improved for larger $b?$ The strategy is still the same for you. Here $b=\binom{100}{20}-4$ is enough to ensure a score of $20.$ On the other hand, Itit could happen that for $b=\binom{20}4^5\approx2.7\cdot 10^{18}=O(N^9)$ the groups $Y_1\cdots Y_b$ are exactly the ones using $4$ boxes from each of $X_1,X_2,X_3,X_4,X_5.$

Whatever this does show, it would scale up similarly for larger $N$ and $k=\frac{N}5.$

What if we were back to $b=1$ but now $a$ is $O(N^{9})?$ That would be in the spirit of your exact question. I suppose that here you could give up on three of the boxes and pick your groups from the other $97.$ Then you certainly can't be sure of a score over $17.$ There are $\binom{97}{17} \approx 3.7\cdot 10^{18}$ ways to pick $17$ boxes. So $a$ that large would guarantee that score of $17.$ Actually, a group of $20$ would cover $1140$ sets of size $17$ so a smaller $a$ might still guarantee a score of $17$ but nothing smaller that about $3\cdot 10^{15}$ possibly could (with that strategy of ignoring three.)

I gave a longer answer before you clarified the problem. Here is a briefer one. I will mainly talk about $N=100$ and $k=20.$

Note that choosing $\frac{N}k$ groups the strategy and optimum outcome are the same for any of the four goals maximize/minimize the largest/smallest intersection. Only a partition into disjoint groups can ensure that the score is as small (or as large) as $\frac{k^2}N.$

Sticking to maximum intersection size with $N=100$ and $k=20$, one can be sure of a score of $20$ only by choosing $\binom{100}{20}\approx 5.4\cdot 10^{20}=O(N^{10})$ groups. Obviously there are lower numbers of groups that will ensure a score of at least $s$ for other $4 \leq s \lt 20.$ I will suggest that they are not much smaller in terms of polynomial order.

Consider this variation: You pick $a$ groups $X_1,\cdots,X_a$ and the other player picks $b$ groups $Y_1,\cdots,Y_b.$ (All groups $20$ out of $100.$ Your goal is to maximize the guaranteed maximum among the $ab$ sizes $|X_i\cap Y_j|$ If still $a=5,$ how do things improved for larger $b?$ The strategy is still the same for you. Here $b=\binom{100}{20}-4$ is enough to ensure a score of $20.$ On the other hand, It could happen that for $b=\binom{20}4^5\approx2.7\cdot 10^{18}=O(N^9)$ the groups $Y_1\cdots Y_b$ are exactly the ones using $4$ boxes from each of $X_1,X_2,X_3,X_4,X_5.$

Whatever this does show, it would scale up similarly for larger $N$ and $k=\frac{N}5.$

What if we were back to $b=1$ but now $a$ is $O(N^{9})?$ That would be in the spirit of your exact question. I suppose that here you could give up on three of the boxes and pick your groups from the other $97.$ Then you certainly can't be sure of a score over $17.$ There are $\binom{97}{17} \approx 3.7\cdot 10^{18}$ ways to pick $17$ boxes. So $a$ that large would guarantee that score of $17.$ Actually, a group of $20$ would cover $1140$ sets of size $17$ so a smaller $a$ might still guarantee a score of $17$ but nothing smaller that about $3\cdot 10^{15}$ possibly could (with that strategy of ignoring three.)

I gave a longer answer before you clarified the problem. Here is a briefer one. I will mainly talk about $N=100$ and $k=20.$

Note that choosing $\frac{N}k$ groups the strategy and optimum outcome are the same for any of the four goals maximize/minimize the largest/smallest intersection. Only a partition into disjoint groups can ensure that the score is as small (or as large) as $\frac{k^2}N.$

Sticking to maximum intersection size with $N=100$ and $k=20$, one can be sure of a score of $20$ only by choosing $\binom{100}{20}\approx 5.4\cdot 10^{20}=O(N^{10})$ groups. Obviously there are lower numbers of groups that will ensure a score of at least $s$ for other $4 \leq s \lt 20.$ I will suggest that they are not much smaller in terms of polynomial order.

Consider this variation: You pick $a$ groups $X_1,\cdots,X_a$ and the other player picks $b$ groups $Y_1,\cdots,Y_b.$ (All groups $20$ out of $100.$) Your goal is to maximize the guaranteed maximum among the $ab$ sizes $|X_i\cap Y_j|.$

If still $a=5,$ how do things improved for larger $b?$ The strategy is still the same for you. Here $b=\binom{100}{20}-4$ is enough to ensure a score of $20.$ On the other hand, it could happen that for $b=\binom{20}4^5\approx2.7\cdot 10^{18}=O(N^9)$ the groups $Y_1\cdots Y_b$ are exactly the ones using $4$ boxes from each of $X_1,X_2,X_3,X_4,X_5.$

Whatever this does show, it would scale up similarly for larger $N$ and $k=\frac{N}5.$

What if we were back to $b=1$ but now $a$ is $O(N^{9})?$ That would be in the spirit of your exact question. I suppose that here you could give up on three of the boxes and pick your groups from the other $97.$ Then you certainly can't be sure of a score over $17.$ There are $\binom{97}{17} \approx 3.7\cdot 10^{18}$ ways to pick $17$ boxes. So $a$ that large would guarantee that score of $17.$ Actually, a group of $20$ would cover $1140$ sets of size $17$ so a smaller $a$ might still guarantee a score of $17$ but nothing smaller that about $3\cdot 10^{15}$ possibly could (with that strategy of ignoring three.)

Source Link
Aaron Meyerowitz
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

I gave a longer answer before you clarified the problem. Here is a briefer one. I will mainly talk about $N=100$ and $k=20.$

Note that choosing $\frac{N}k$ groups the strategy and optimum outcome are the same for any of the four goals maximize/minimize the largest/smallest intersection. Only a partition into disjoint groups can ensure that the score is as small (or as large) as $\frac{k^2}N.$

Sticking to maximum intersection size with $N=100$ and $k=20$, one can be sure of a score of $20$ only by choosing $\binom{100}{20}\approx 5.4\cdot 10^{20}=O(N^{10})$ groups. Obviously there are lower numbers of groups that will ensure a score of at least $s$ for other $4 \leq s \lt 20.$ I will suggest that they are not much smaller in terms of polynomial order.

Consider this variation: You pick $a$ groups $X_1,\cdots,X_a$ and the other player picks $b$ groups $Y_1,\cdots,Y_b.$ (All groups $20$ out of $100.$ Your goal is to maximize the guaranteed maximum among the $ab$ sizes $|X_i\cap Y_j|$ If still $a=5,$ how do things improved for larger $b?$ The strategy is still the same for you. Here $b=\binom{100}{20}-4$ is enough to ensure a score of $20.$ On the other hand, It could happen that for $b=\binom{20}4^5\approx2.7\cdot 10^{18}=O(N^9)$ the groups $Y_1\cdots Y_b$ are exactly the ones using $4$ boxes from each of $X_1,X_2,X_3,X_4,X_5.$

Whatever this does show, it would scale up similarly for larger $N$ and $k=\frac{N}5.$

What if we were back to $b=1$ but now $a$ is $O(N^{9})?$ That would be in the spirit of your exact question. I suppose that here you could give up on three of the boxes and pick your groups from the other $97.$ Then you certainly can't be sure of a score over $17.$ There are $\binom{97}{17} \approx 3.7\cdot 10^{18}$ ways to pick $17$ boxes. So $a$ that large would guarantee that score of $17.$ Actually, a group of $20$ would cover $1140$ sets of size $17$ so a smaller $a$ might still guarantee a score of $17$ but nothing smaller that about $3\cdot 10^{15}$ possibly could (with that strategy of ignoring three.)