The Probabilistic Method

0/75 solved

1 / 75

Each question is graded on a single answer: a check that this chapter's methods work, not a test of the reasoning behind them.

Colour every edge of

K_{n}

red or blue independently with probability

\frac{1}{2}

⁠. What is the probability that a fixed set of

4

vertices spans a monochromatic

K_{4}

⁠?

Read the section this question comes from

Your answer

comb-prob-20All Combinatorics chapters

About these 75 questions

Proving a structure exists by showing a random one works, sharpened by the moment methods, by deletion, and by the Lovász Local Lemma. This set covers the chapter The Probabilistic Method in Combinatorics: 25 easy, 36 medium and 14 hard questions, each graded instantly with a hint and a full step-by-step solution. Progress is saved in this browser only.

The Basic Idea — 11 questions
First and Second Moments — 11 questions
The Deletion Method — 11 questions
Why a Local Lemma Is Needed — 10 questions
The Local Lemma — 10 questions
Proof of the Local Lemma — 10 questions
Applications of the Local Lemma — 12 questions