maths.free › Probability Theory › 11. Applying Probability to Combinatorics › Ramsey's Theorem

Ramsey's Theorem

By this time, you are probably not surprised to see that there is a very general form of Ramsey's theorem. We have a bounded number of bins or colors and we are placing the subsets of a fixed size into these categories.

Ramsey's Theorem

By this time, you are probably not surprised to see that there is a very general form of Ramsey's theorem. We have a bounded number of bins or colors and we are placing the subsets of a fixed size into these categories. The conclusion is that there is a large set which is treated uniformly.

Here's the formal statement.

We don't include the proof of this general statement here, but the more ambitious students may attempt it on their own. Note that the case \(s=1\) is just the , while the case \(s=r=2\) is just . An argument using double induction is required for the proof in the general case. The first induction is on \(r\) and the second is on \(s\).

Symbols used here

x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
y',\ y''
first and second derivative of y
Prime notation for derivatives with respect to x (or t).
i
imaginary unit
i² = −1.
\leq,\ \geq
less/greater than or equal
Inequalities that allow equality; < and > exclude it.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
\int f(x)\,dx,\ \int_a^b
integral
Antiderivative (indefinite) or signed area from a to b (definite).
A \cup B,\ A \cap B,\ A \setminus B
union, intersection, difference
In either; in both; in A but not B.
\bar{x},\ \mu
sample mean, population mean
Average of the data; average of the whole population.
\sigma,\ s,\ \sigma^2
standard deviation, sample s.d., variance
Typical distance from the mean; its square.
P(A),\ P(A \mid B)
probability, conditional probability
Chance of A; chance of A given that B happened.
E[X],\ \operatorname{Var}(X)
expected value, variance
Probability-weighted average of X; its spread.
N(\mu, \sigma^2),\ z
normal distribution, z-score
The bell curve with mean μ and variance σ²; (x − μ)/σ.
\mu(A),\ \sigma\text{-algebra}
measure of A
Size of a set; the family of sets that can be measured.

Questions people ask

What is the difference between probability and statistics?

Probability goes from a known model to what the data should look like; statistics goes from data back to the model. Probability theory is the deductive half.

What does the law of large numbers promise?

That the average of many independent samples converges to the expected value. It says nothing about any single trial.

Prøv din egen

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Mer i Probability Theory

Sample spaces and the axiomsRandom variables and expectationThe common distributionsThe law of large numbers and the central limit theorem