Does Ramsey theory prove that all sufficiently long random sequences can be slightly compressed? First, my apologies if this has already been asked and answered. I did search this community for five to ten minutes looking for similar questions and found none.
My lay understanding of Ramsey theory is that “in any large enough piece of disorder you can find a small piece of order”. See Inevitable patterns in mathematics: Some topics in Ramsey theory (pdf). In other words, "complete randomness is
impossible". See Excursions for Students (pdf).
If I understand such claims correctly, then in any sufficiently long random sequence, eg a random string of zeros and ones, r, there must be a substring s of length n that manifests some kind of pattern. If so, then it must be possible to compress s based on the pattern it manifests. If we can compress s, then we can compress r by some small degree, since s is a substring of r.  (I realize that a sufficiently long r may be quite long indeed to generate a patterned substring s of length n, where n is say 100 or more.)
This question seems related to the incompressibility method, but I couldn't find any discussion of this particular issue. 
 A: You can try to compress a string in this way, but the overhead from the compression will always exceed the gain from compression.
In fact, the argument that this will always happen is very similar to the "probabilistic method" lower bounds for many Ramsey-type problems.
For instance, consider Ramsey's theorem: the claim that for any $k$, if $n$ is sufficiently large, any red-blue coloring of the edges of the complete graph $K_n$ will contain a clique $K_k$ whose edges all have one color.
First, a brief aside to prove a lower bound on $n$ for this to happen. The probabilistic construction for the lower bound says that a sufficiently large $n$ must satisfy $\binom nk \ge 2^{\binom{k}{2}-1}$ (which is a bound roughly like $n \ge 2^{k/2}$). To prove this, suppose that $\binom nk < 2^{\binom{k}{2}-1}$, and take a random red-blue coloring of $K_n$. The number of cliques of size $k$ is $\binom nk$, and each is entirely red with probability $2^{-\binom k2}$ and entirely blue with probability $2^{-\binom k2}$. So the average number of monochromatic cliques is $\binom nk 2^{1-\binom k2}$, which is less than $1$ by assumption; therefore it's possible that the random coloring will not have a monochromatic clique.
Now let's go back to the compression idea. If we use Ramsey's theorem to try to compress a coloring of $K_n$, we should specify a particular clique of size $k$ which happens to be monochromatic, and then save space by just specifying the color of that clique - instead of specifying the colors of all $\binom k2$ edges in the clique individually. This saves $\binom k2 - 1$ bits of storage. However, we need $\log_2 \binom nk$ bits of storage to specify which clique we're using. The overall benefit is
$$
    \binom k2 - 1 - \log_2 \binom nk = \log_2 \left(2^{\binom k2 - 1} / \binom nk\right)
$$
and by the probabilistic lower bound, the term inside the log is at most $1$, which means that the log is nonpositive. That is, we can never benefit from this compression scheme.
This is not a coincidence: in general, the threshold at which the probabilistic lower bound for the Ramsey-type problem works is exactly the same as the threshold at which we stop being able to compress efficiently, because the calculation for both is the same.
Below that threshold, we can win by spotting the ordered substructure we are looking for - if it exists, which it might not. Above that threshold, the ordered substructure typically exists - but we no longer benefit from using it, because the cost outweighs the gain.
(In cases such as Ramsey's theorem, where there is a gap between the expected-value lower bound and the best known upper bound, there is an interval which is the worst of both worlds. We don't save anything by exploiting the ordered substructure, and we also don't know if one exists.)
