8
$\begingroup$

Assume that the natural numbers have been colored with two colors: lavender and periwinkle. You don't know the coloring. You may sample as many (possibly overlapping) sets of size $n$ as you would like, all at the same time. Your goal is to sample at least one homogeneous set.

Question. Let $c(n)$ be the least number of sets you must sample to guarantee a homogeneous set. What is $c(n)$?

I think that this question is unreasonably hard. What I really want is a pointer to the literature on this question, assuming it exists. I haven't been able to find anything.

What I know:

  • If I sample all subsets of $\{1, 2, \dots, 2n-1\}$ of size $n$, then I'm guaranteed a homogeneous set. Therefore, $c(n)\leq {2n-1 \choose n}$.
  • This is not always optimal. By iterating the fact that $c(2)=3$, I can show that $c(4)\leq 27$ and, in general, that $c(2^n)\leq 3^{2^n-1}$.
  • Here are some rough upper bounds on $c(n)$:
    • $c(1) = 1$
    • $c(2) = 3$
    • $c(3) \leq 10$
    • $c(4) \leq 27$
    • $c(5) \leq 100$
    • $c(6) \leq 270$
    • $c(7) \leq 1150$
Improve this question
$\endgroup$
5
  • $\begingroup$ Homogeneous means monochrome? Anyway, for $n=3$, sample $\{1,2,3\}$. Assume $2$ and $3$ are the same color. Sample $\{2,3,4\}$ and $\{2,3,5\}$. If neither is monochrome, then $\{1,4,5\}$ is. So $c(3)=4$. Am I right? $\endgroup$
    – Gerry Myerson
    Commented May 1 at 1:01
  • 1
    $\begingroup$ @GerryMyerson The samples must be chosen "all at the same time." $\endgroup$
    – RobPratt
    Commented May 1 at 1:02
  • $\begingroup$ @Rob, ah. I read the "you may sample" and the "as you would like" as permitting, rather than requiring, the samples to be taken at the same time, but, of course, you are right. $\endgroup$
    – Gerry Myerson
    Commented May 1 at 1:23
  • 3
    $\begingroup$ I think $c(3)\le7$, by 2-coloring the points of the Fano plane. For any 2-coloring, there's a monochromatic line. So, sample 123, 145, 167, 246, 257, 347, 356. $\endgroup$
    – Gerry Myerson
    Commented May 1 at 1:39
  • 1
    $\begingroup$ @GerryMyerson That's a beautiful example, thanks! This suggests that the rest of my upper bounds are pretty terrible. $\endgroup$
    – Joe Miller
    Commented May 1 at 5:29

1 Answer 1

Reset to default
11
$\begingroup$

You are seeking for the smallest number of edges $m(n)$ in a $n$-uniform hypergraph which does not have property B; see, e.g., here. Known estimates mentioned there are $\Omega(2^n\cdot\sqrt{n/\log n})\leq m(n)\leq O(2^n\cdot n^2)$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That's fantastic, thanks! I was able to get the upper bound of $2^{n+1}\cdot n^2$ using the probabilistic method and some optimization. The lower bound seems a lot more mysterious, but now I know where to look. $\endgroup$
    – Joe Miller
    Commented May 7 at 9:09

You must log in to answer this question.

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