maths.free › Probability Theory › 11. Applying Probability to Combinatorics › Applying Probability to Combinatorics: exercises

Applying Probability to Combinatorics: exercises

Applying Probability to Combinatorics: exercises — from Keller & Trotter, Applied Combinatorics.

Practice (5)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. Consider a random graph with vertex set \(\{1,2,\dot,n\}\). If the edge probability is \(p=1/2\), then let \(X\) denote the number of complete subgraphs of size \(t=2\log n\) and let \(Y\) denote the number of independent sets of size \(t=2\log n\).

    1. Show that \(E(X+Y)\lt 1\), when \(n\) is sufficiently large.

    2. Use the result from parta to show that \(\omega(G)\) is less than \(2\log n\), while the chromatic number of \(G\) is at least \(n/(2\log n)\) (both statements holding with high probability). As a result, the basic inequality \(\chi(G)\ge\omega(G)\) is far from being tight for a random graph.

  2. We form a random tournament as follows. Start with a complete graph with vertex set \(\{1,2,\dots,n\}\). For each distinct pair \(i\), \(j\) with \(1\le i\lt j\le n\), flip a fair coin. If the result is heads, orient the edge from \(i\) to \(j\), which we denote by \((x,y)\). If the toss is tails, then the edge is oriented from \(j\) to \(i\), denoted \((y,x)\). Show that when \(n\) is large, with high probability, the following statement is true: For every set \(S\) of size \(\log n/10\), there is a vertex \(x\) so that \((x,y)\) in \(T\) for every \(y\in S\).

  3. Let \(T\) be a random tournament on \(n\) vertices. Show that with high probability, the following statement is true: For every pair \(x\), \(y\) of distinct vertices, either (1)\((x,y)\) in \(T\), or (2)there is a vertex \(z\) for which both \((x,z)\) and \((z,y)\) are in \(T\).

  4. Many statements for random graphs exhibit a threshold behavior. Show that a random graph with edge probability \(p=10\log n/n\) almost certainly has no isolated vertices, while a random graph with edge probability \(p=\log n/(10 n)\) almost certainly has at least one isolated vertices.

  5. In the sense of the preceding problem, determine the threshold probability for a graph to be connected.

Symbols used here

\log_b x,\ \ln x
logarithm, natural log
The exponent b must be raised to for x; ln uses base e.
x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
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.

Cobalah sendiri

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

Lebih dalam Probability Theory

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