maths.free › Probability Theory › Applying Probability to Combinatorics › The Probabilistic Method

The Probabilistic Method

At the outset of this chapter, we presented Erdős' original proof for the lower bound for the Ramsey number R(n,n) using counting. Later, we recast the proof in a probabilistic setting.

The Probabilistic Method

At the outset of this chapter, we presented Erdős' original proof for the lower bound for the Ramsey number \(R(n,n)\) using counting. Later, we recast the proof in a probabilistic setting. History has shown that this second perspective is the right one. To illustrate the power of this approach, we present a classic theorem, which is also due to Erdős, showing that there are graphs with large girth and large chromatic number.

The girth \(g\) of a graph \(G\) is the smallest integer for which \(G\) contains a cycle on \(g\) vertices. The girth of a forest is taken to be infinite, while the girth of a graph is three if and only if it has a triangle. You can check the families of triangle-free, large chromatic number, graphs constructed in and see that each has girth four.

Theorem: Erdős

For every pair \(g,t\) of integers with \(g\ge3\), there exists a graph \(G\) with \(\chi(G)>t\) and the girth of \(G\) greater than \(g\).

Proof

Before proceeding with the details of the argument, let's pause to get the general idea behind the proof. We choose integers \(n\) and \(s\) with \(n>s\), and it will eventually be clear how large they need to be in terms of \(g\) and \(t\). We will then consider a random graph on vertex set \(\{1,2,\dots,n\}\), and just as before, for each \(i\) and \(j\) with \(1\le i\lt j\le n\), the probability that the pair \(ij\) is an edge is \(p\), but now \(p\) will depend on \(n\). Of course, the probability that any given pair is an edge is completely independent of all other pairs.

Our first goal is to choose the values of \(n\), \(s\) and \(p\) so that with high probability, a random graph does not have an independent set of size \(s\). You might think as a second goal, we would try to get a random graph without small cycles. But this goal is too restrictive. Instead, we just try to get a graph in which there are relatively few small cycles. In fact, we want the number of small cycles to be less than \(n/2\). Then we will remove one vertex from each small cycles, resulting in a graph with at least \(n/2\) vertices, having no small cycles and no independent set of size\(s\). The chromatic number of this graph is at least \(n/2s\), so we will want to have the inequality \(n>2st\).

Now for some details. Let \(X_1\) be the random variable that counts the number of \(s\)-element independent sets. Then \[\begin{aligned}\end{aligned}\] Now we want \(E(X_1)\lt 1/4\). Since \(C(n,s)\le n^s=e^{s\ln n}\) and \((1-p)^{C(s,2)}\le e^{-ps^2/2}\), it suffices to set \(s=2\ln n/p\). By , the probability that \(X_1\) exceeds \(1/2\ge 2E(X_1)\) is less than \(1/2\).

Now let \(X_2\) count the number of cycles in \(G\) of size at most \(g\). Then \[\begin{aligned}\end{aligned}\] Now, we want \(E(X_2)\le n/4\), and an easy calculation shows that \(g(np)^g\le n/4\) when \(p=n^{1/g-1}/10\). Again by , the probability that \(X_2\) exceeds \(n/2\ge 2E(X_2)\) is less than \(1/2\).

We conclude that there is a graph \(G\) for which \(X_1=0\) and \(X_2\le n/2\). Remove a vertex from each of the small cycles in \(G\) and let \(H\) be the graph that remains. Clearly, \(H\) has at least \(n/2\) vertices, no cycle of size at most\(g\) and no independent set of size \(s\). Finally, the inequality \(n>2st\) requires \(n^{1/g}/(40\ln n)>t\).

Gaining Intuition with the Probabilistic Method

Experienced researchers are able to simplify the calculations in an argument of this type, as they know what can safely be discarded and what can not. Here's a quick tour of the essential steps. We want \(E(X_1)\) to be small, so we set \(n^se^{-ps^2}=1\) and get \(s=\ln n/p\). We want the number of small cycles to be about \(n\) so we set \((gp)^g=n\) and get \(p=n^{1/g-1}\). Finally, we want \(n=st\) which requires \(n^{1/g}=t\). The rest is just paying attention to details.

이제 너 계산기는 이것을 해결하지 않지만, 그 조각은 계산 가능합니다. 아래의 하나를 시도하거나 자신의 것을 입력하십시오.

자신의 작업을 유지

무료 계정은 모든 수업에 노트를 추가, 당신이 완료 한 기록, 당신이 해결 한 문제를 한 곳에, 그리고 당신이이 페이지에 대해 물어 수업 지도자. 수학 자체는 모두에게 열려 있습니다, 로그인 여부.

가입하기 로그인

여기서 사용된 기호

기호를 탭하면 전체 정의, 이미지 및 각 문자의 의미를 확인할 수 있습니다.

사람들이 묻는 질문

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.

이 페이지의 일부는 다음에서 변경되었습니다. Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). 여기서 압축하고 다시 설명; 오류는 우리의.

에 더 Probability Theory

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