maths.free › Probability Theory › 11. Applying Probability to Combinatorics › A First Taste of Ramsey Theory

A First Taste of Ramsey Theory

Bob likes to think of himself as a wild and crazy guy, totally unpredictable. Most guys do. But Alice says that Bob can't change his basic nature, which is excruciatingly boring.

A First Taste of Ramsey Theory

Bob likes to think of himself as a wild and crazy guy, totally unpredictable. Most guys do. But Alice says that Bob can't change his basic nature, which is excruciatingly boring. Carlos remarks that perhaps we shouldn't be so hard on Bob, because under certain circumstances, we can all be forced to be dull and repetitive.

Recall that when \(n\) is a positive integer, we let \([n]=\{1,2,\dots,n\}\). In this chapter, when \(X\) is a set and \(k\) is a non-negative integer with \(k\le |X|\), we borrow from our in-line notation for binomial coefficients and let \(C(X,k)\)\(C(X,k)\)family of all \(k\)-element subsets of \(X\) denote the family of all \(k\)-element subsets of \(X\). So \(|C([n],k)|=C(n,k)\) whenever \(0\le k\le n\).

Recall that the asserts that if \(n+1\) pigeons are placed in \(n\) holes, then there must be some hole into which two or more pigeons have been placed. More formally, if \(n\) and \(k\) are positive integers, \(t>n(k-1)\) and \(f:[t]\longrightarrow[n]\) is any function, then there is a \(k\)-element subset \(H\subseteq [t]\) and an element \(j\in[n]\) so that \(f(i)=j\) for every \(i\in H\).

We now embark on a study of an elegant extension of this basic result, one that continues to fascinate and challenge.

Returning to the discussion at the start of this section, you might say that an induced subgraph \(H\) of a graph \(G\) is boring if it is either a complete subgraph or an independent set. In either case, exactly every pair of vertices in \(H\) behaves in exactly the same boring way. So is boredom inevitable? The answer is yesat least in a relative sense. As a starter, let's show that any graph on six (or more) vertices has a boring subgraph of size three.

Lemma

Let \(G\) be any graph with six of more vertices. Then either \(G\) contains a complete subgraph of size\(3\) or an independent set of size\(3\).

Proof

Let \(x\) be any vertex in \(G\). Then split the remaining vertices into two sets \(S_1\) and \(S_2\) with \(S_1\) being the neighbors of \(x\) and \(S_2\) the non-neighbors. Since \(G\) has at least six vertices, we know that either \(|S_1|\ge 3\) or \(|S_2|\ge 3\). Suppose first that \(|S_1|\ge 3\) and let \(y_1\), \(y_2\) and \(y_3\) be distinct vertices from \(S_1\). If \(y_iy_j\) is an edge in \(G\) for some distinct pair \(i, j\in\{1,23\}\), then \(\{x,y_i,y_j\}\) is a complete subgraph of size \(3\) in \(G\). On the other hand, if there are no edges among the vertices in \(\{y_1,y_2,y_3\}\), then we have an independent set of size\(3\).

The argument when \(|S_2|\ge3\) is dual.

Next, here is the statement that generalizes this result.

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

Symbols used here

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

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.

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

Mere i Probability Theory

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