Consider the $m\times n$ ($m$ wide $n$ tall) grid $G_{m,n}$, and let $H_{m,n}$ be a random subgraph, where each edge of $G_{m,n}$ is an edge of $H$ independently with probability $\frac{1}{2}$. A horizontal crossing of $H_{m,n}$ is a path from a leftmost edge to a rightmost edge. Let $P_{m,n}$ be the probability that $H_{m,n}$ has a horizontal crossing.
In class today, we showed that $P_{n,n} = \frac{1}{2}$, and it was mentioned that one can find positive constants $c_k$ such that $P_{kn,n} \geq c_{k}$ for all $n$. Our professor breifly mentioned that proving the existence of such a $c_k$ is done in two steps, proving that $c_2$ exists, and then using the fact that $c_2$ exists to prove that $c_k$ exists for any $k$. Apparently, proving that $c_2$ exists is quite difficult. For my own curiosity, I'm trying to show the "easier" of the two statements, and as an example, I'm trying to show that the existence of $c_2$ implies the existence of $c_4$.
I would want to say that $c_4$ is some constant multiple of $c_2^2$ since a path from the far left to the far right of $H_{4n,n}$ is essentially two paths of length $2n$. However, there's no way to guarantee that these two shorter paths will "meet in the middle" giving a full path from the far left to the far right. Does anyone have any hints/thoughts on how I can proceed?
"show that the existence of $c_2$ implies the existence of $c_4$."
A path from the far left to far right of $H_{4n,n}$ needs two paths from the far left to far right of subgraphs $H_{2n,n}$. These give us some probability $c_2$ each, and since edges are independent, we get a probability of $c_2^2$ that each $H_{2n,n}$ subgraph of $H_{4n,n}$ is connected from left to right. Further we need that these two paths are connected.
Now we'll try to bound the probability that they'll meet in the middle. Note that $P_{n,n}=\frac{1}{2}$. $P_{2n,n}=P_{n,n}^2\times P(\text{two paths meet in the middle}) \geq c_2$.
Thus \begin{align*} P_{n,n}^2\times P(\text{two paths meet in the middle})&\geq c_2\\ \left(\frac{1}{2}\right)^2\times P(\text{two paths meet in the middle})&\geq c_2\\ P(\text{two paths meet in the middle}) \geq 4c_2 \end{align*}
Now we have all the ingredients to construct $c_4$.
\begin{align*} c_4 &\geq (c_2)^2 \times P(\text{two paths meet in the middle})\\ &\geq (c_2)^2 \times 4c_2\\ &\geq 4(c_2)^3 \end{align*}