Let $n ≥7$, and let $C$ be a collection of 15 distinct 5-element subsets of [n]. Prove that it is possible to color each element of $[n]$ yellow or orange so that each set belonging to $C$ has elements of both colors.

I know this is an applicaiton of Ramsey theory, but I'm not sure how to approach it since we could pick any n more than 7.

Maybe I'm completely wrong and it might not be ramsey theory related!

Also, I'm not sure how we'd relate this to a graph since we're coloring elements (vertices) as opposed to the edges themselves.

Thank you.

  • $\begingroup$ You don't have to consider all of the $n$-set. You can ignore anything that isn't in one of the 15 sets in $C$. S $\endgroup$ – MJD Nov 27 '19 at 12:16

Colour the elements randomly (independently and uniformly). The expected number of monochromatic subsets is $\frac{15}{16}\lt1$. Hence at least one colouring must be contributing to this expectation with $0$ monochromatic sets.

  • $\begingroup$ How did you get 15/16 sorry? $\endgroup$ – thomas_stafford_22 Nov 27 '19 at 12:07
  • 1
    $\begingroup$ Each set can be colored in 32 ways, of which 2 are monochromatic. A randomly-colored set is monochromatic with probability $\frac2{32}=\frac1{16}$. You have 15 such sets, so the expected number of monochomatic sets is$\frac{15}{16}$. $\endgroup$ – MJD Nov 27 '19 at 12:23
  • $\begingroup$ So how does it being less than 1 mean that it's possible sorry? $\endgroup$ – thomas_stafford_22 Nov 27 '19 at 12:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.