maths.free › Probability Theory › 11. Applying Probability to Combinatorics › Applying Probability to Ramsey Theory

Applying Probability to Ramsey Theory

The following theorem, due to P. Erdős, is a true classic, and is presented here in a manner that is faithful to how it was first published.

Applying Probability to Ramsey Theory

The following theorem, due to P. Erdős, is a true classic, and is presented here in a manner that is faithful to how it was first published. As we shall see later, it was subsequently recastbut that's getting the cart ahead of the horse.

Theorem

If\(n\) is a positive integer. Then \[\begin{aligned}\end{aligned}\]

Proof

Let \(t\) be an integer with \(t>n\) and consider the set \(\cgF\) of all labeled graphs with vertex set \(\{1,2,\dots,t\}\). Clearly, there are \(2^{C(t,2)}\) graphs in this family. Let \(\cgF_1\) denote the subfamily consisting of those graphs which contain a complete subgraph of size\(n\). It is easy to see that \[\begin{aligned}\end{aligned}\] Similarly, let \(\cgF_2\) denote the subfamily consisting of those graphs which contain an independent set of size\(n\). It follows that \[\begin{aligned}\end{aligned}\]

We want to take the integer \(t\) as large as we can while still guaranteeing that \(|\cgF_1|+|\cgF_2|\le |\cgF|\). This will imply that there is a graph \(G\) in \(\cgF\) which does not contain a complete subgraph of size \(n\) or an independent set of size\(n\). So consider the following inequality: \[\begin{aligned}\end{aligned}\] Now we ask how large can \(t\) be without violating inequality? To answer this, we use the trivial inequality \(\binom{t}{n}\le t^n/n!\) and the use the Stirling approximation for \(n!\). After some algebra and taking the \(n^{\text{th} }\) root of both sides, we see that we need only guarantee that \[\begin{aligned}\end{aligned}\]

Now let's take a second look at the proof of . We consider a probability space \((S,P)\) where the outcomes are graphs with vertex set \(\{1,2,\dots,t\}\). For each \(i\) and \(j\) with \(1\le i \lt j\le t\), edge \(ij\) is present in the graph with probability \(1/2\). Furthermore, the events for distinct pairs are independent.

Let \(X_1\) denote the random variable which counts the number of \(n\)-element subsets of \(\{1,2,\dots,t\}\) for which all \(\binom{n}{2}\) pairs are edges in the graph. Similarly, \(X_2\) is the random variable which counts the number of \(n\)-element independent subsets of \(\{1,2,\dots,t\}\). Then set \(X=X_1+X_2\).

By linearity of expectation, \(E(X)=E(X_1)+E(X_2)\) while \[\begin{aligned}\end{aligned}\] If \(E(X)\lt 1\), then there must exist a graph with vertex set \(\{1,2,\dots,t\}\) without a \(K_n\) or an \(I_n\). And the question of how large \(t\) can be while maintaining \(E(X)\lt 1\) leads to exactly the same calculation we had before.

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.

Symbols used here

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

imaginary unit
i² = −1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

\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.

QDialogButtonBox

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

@ action Probability Theory

Sample spaces and the axioms Random variables and expectation The common distributions The law of large numbers and the central limit theorem