The probabilistic method proves that a combinatorial object exists by defining a random object and showing that the desired property has positive probability. No efficient procedure for finding the object is required.
If a graph has edges and triangles, successively delete one edge from a remaining triangle. No new triangle is created and at most deletions are needed, so a triangle-free subgraph has at least edges. A random-graph expectation lower bound on therefore proves existence of a large triangle-free graph. With edge probability , the expectation is ; this is a useful existence bound but is not within a constant factor of the sharp quadratic Mantel theorem bound.
For any fixed density strictly below one, random subsets of an integer interval can have that density yet avoid arithmetic progressions longer than a constant times the logarithm of the interval length. A union bound over possible progressions bounds their occurrence, while concentration of the random cardinality supplies a dense realization. Passing to a subset gives an exact prescribed cardinality.
