2
$\begingroup$

I am trying to prove that if there exists a real number $0 < p <1$ such that $$\binom{n}{k}p^k + \binom{n}{q}(1-p)^q < 1$$ for some $k, q \in [n],$ Then $R(k,q) > n.$ I see by the construction of this problem that they are suggesting some form of probabilistic method, i.e. on a random edge 2-coloring of the graph $K_n,$ where the probability of an edge getting the color $1$ is $p$ (and thus the probability of an edge getting the color $2$ is $1-p$), $P(\text{Getting a monochromatic } K_k \vee \text{Getting a monochromatic } K_q) < 1.$ The tough part is finding this particular probability. I can see by the definition of a union of events that $$P(\text{Getting a monochromatic } K_k \vee \text{Getting a monochromatic } K_q)$$ $$\leq P(\text{Getting a monochromatic } K_k) + P(\text{Getting a monochromatic } K_q),$$ But I am having issues with both of the counting proofs for this particular part of the problem. Any suggestions?

$\endgroup$
1
$\begingroup$

I think your statement is false, for example it would imply $R(k,2)>k$. I could only show that $R(k,q)>n$ when given that for some $p\in(0,1)$ we have the weaker inequality $${n\choose k}p^{k(k-1)/2}+{n\choose q}(1-p)^{q(q-1)/2}<1.$$ In $K_n$, colour every edge independently, with probability $p$ colour it blue and red otherwise. For every $K_k\subset K_n$, there is a probability of $p^{k(k-1)/2}$ that $K_k$ is completely blue. Hence the expected number of blue $K_k$'s is ${n\choose k}p^{k(k-1)/2}$. Similarly, the expected number of red $K_q$'s is ${n\choose q}(1-p)^{q(q-1)/2}$.

Because ${n\choose k}p^{k(k-1)/2}+{n\choose q}(1-p)^{q(q-1)/2}<1$, there is a particular colouring of $K_n$ with no blue $K_k$ or red $K_q$, thus $R(k,q)> n$.

$\endgroup$

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.