Prove existence by averaging and alteration

Try

Randomness can prove a deterministic object exists. Place every vertex of a graph independently on one of two sides with equal probability. Each edge crosses the cut with probability one-half, so a graph with m edges has expected cut size m/2. At least one actual cut therefore has size at least m/2. The conclusion is existence of a concrete partition, not that every random trial achieves the expectation.

Predict

Predict whether the edge-crossing indicators must be independent for the expectation calculation. They do not. Linearity gives the expectation of a sum from the individual expectations even when events share vertices or otherwise depend on one another. Independence matters for some product probabilities and variance simplifications, but adding expectations is a separate algebraic fact.

Experiment

For a triangle, enumerate cuts by the side assigned to its three vertices.

Assignment pattern	Number of assignments	Crossing edges
All on one side	2	0
One separated from the other two	6	2

The average is 12/8=3/2, equal to half the three edges. Since cut size is an integer, some cut has at least two edges. The average itself need not be an attainable value.

Overlapping constraints: count true clauses

A Boolean bit takes the value zero (false) or one (true). A literal is a bit or its negation; a clause is an OR of literals. Start with three independent fair bits x1, x2, x3. Each three-literal clause using each bit once is false on exactly one of the eight assignments. For example, x1 OR NOT x2 OR x3 is false only on (0, 1, 0).

Use seven such clauses, one forbidding each row except (1, 1, 1). Each is true with probability 7/8, so the expected number of true clauses is 49/8 = 6.125. If every assignment made at most six clauses true, the average could not exceed six. Therefore some assignment makes all seven true. The assignment (1, 1, 1) is a witness. The clauses share bits: their truth indicators are not independent. Linearity still adds their probabilities.

Choose bits without lowering the expected score

Three independent fair bits initially give eight equally likely assignments. A clause is an OR; the score counts true clauses. State is temporary and does not award mastery.

Clause family Seven clauses: one omitted forbidden rowEight clauses: all forbidden rowsRepeated literal, tautology and empty clause

Clauses: (x1 ∨ x2 ∨ x3) AND (¬x1 ∨ x2 ∨ x3) AND (x1 ∨ ¬x2 ∨ x3) AND (¬x1 ∨ ¬x2 ∨ x3) AND (x1 ∨ x2 ∨ ¬x3) AND (¬x1 ∨ x2 ∨ ¬x3) AND (x1 ∨ ¬x2 ∨ ¬x3).

Initial mean: 6.125. Guaranteed achievable integer score: 7 of 7. This is not a guarantee for every assignment.

Chosen prefix: none. Remaining assignments: 8. Conditional mean: 6.125.

Predict the better branch, then choose x1. Unchosen bits remain independent and fair.

Choose 0: next mean 6Choose 1: next mean 6.25

Reset choices

The two next means average to the current mean. Choosing a branch at least as large preserves the proof invariant. Displayed values come from clause probabilities; the table evaluates each assignment directly.

Bits x1, x2, x3	True clauses	Matches prefix?
0, 0, 0	6 / 7	yes
1, 0, 0	6 / 7	yes
0, 1, 0	6 / 7	yes
1, 1, 0	6 / 7	yes
0, 0, 1	6 / 7	yes
1, 0, 1	6 / 7	yes
0, 1, 1	6 / 7	yes
1, 1, 1	7 / 7	yes

Why the threshold is strict

For m clauses, each with k distinct variables and no variable appearing with both signs, the failure probability of one clause is 2 to the power −k. The expected number of failed clauses is m times that probability. If m is strictly less than 2 to the power k, this expectation is below one. Some assignment therefore has zero failures. Independence of the underlying bits establishes each clause probability; independence between clauses is neither claimed nor required.

The boundary cannot be included: the eight-clause setting forbids every row once. Every assignment satisfies seven clauses and fails one, so an average of seven does not imply satisfaction of all eight. More generally, if clause j has d_j distinct variables after repeated literals are removed, and is not a tautology, its satisfaction probability is 1 minus 2 to the power −d_j. A clause containing both a bit and its negation is always true. An empty OR is false. Thus repeating x1 three times still gives probability one-half, not seven-eighths. Normalize the actual clause before applying a formula.

Construct a witness by conditional expectations

Let S be the number of satisfied clauses. After a prefix of bits is fixed, all remaining bits are independent and fair. The current conditional mean is the average of the two conditional means obtained by fixing the next bit to zero or one. At least one child is at least the current mean. Choose such a child at every step. Inductively the conditional mean never decreases; when every bit is fixed, it equals the actual integer score. This constructs a score at least the ceiling of the initial mean, where the ceiling is the least integer no smaller than that mean.

To compute a child mean, inspect each clause: an already true literal makes its probability one; otherwise remove assigned false literals and duplicates. Opposite unassigned literals make a tautology; a residual clause on d distinct unassigned variables has probability 1 minus 2 to the power −d, including zero when d is zero. Add these values. No enumeration of all assignments is needed for this conditional calculation. A direct implementation scans the clauses for each candidate bit value; bit-operation cost also depends on the rational numbers used. The eight-row table is a bounded independent check, not evidence that exhaustive search scales efficiently.

Try the syntax-boundary setting. Its initial mean is 1/2 + 3/4 + 1 + 0 = 9/4, forcing an achievable score of three. It can never satisfy all four clauses because the empty clause is false. Explain why the invariant guarantees an integer score, rather than a satisfying assignment in every case.

Understand

The basic probabilistic method chooses a finite distribution over candidate objects, defines a useful random variable, and proves its average forces a desirable outcome. For a nonnegative integer count X of bad features, E[X]< 1 implies P(X=0)>0: if every outcome had at least one bad feature, the expectation would be at least one. For a score Y, some outcome has Y≥E[Y]. These conclusions require the random construction and the score to be precisely specified. They do not by themselves give an efficient search algorithm or a large success probability.

Apply

Alteration strengthens the method by repairing a random object. Choose a random graph on n vertices with independent edge probability p. It has expected edge count C(n, 2)p and expected triangle count C(n, 3)p³. In any realized graph with m edges and t triangles, delete one edge from each remaining triangle until none remain; at most t deletions occur because deletion creates no triangle. Thus some triangle-free graph has at least C(n, 2)p−C(n, 3)p³ edges. The objective is the combined score m−t, not separate claims that one realization simultaneously beats both individual expectations. Selecting p can optimize this lower bound.

Continue

Another construction gives an independent set: choose a uniformly random vertex ordering and retain every vertex earlier than all its neighbors. Adjacent vertices cannot both survive. A vertex of degree d is first among its closed neighborhood with probability 1/(d+1), so some independent set has size at leastΣ_v1/(d(v)+1). This is the Caro–Wei bound, proved by a local ordering rule and averaging. A derandomized implementation may use conditional expectations, but it must show those conditional values can be computed efficiently. The existence proof alone does not establish that algorithmic claim.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with measure when a random structure appears.