First moments and existence certificates

Suppose a finite probability space contains candidate colorings and let $I_j$ indicate that obstruction j occurs. Their sum X is a nonnegative integer. If every candidate were defective, X would always be at least one, so its expectation would also be at least one. Therefore an expected obstruction count strictly below one guarantees a defect-free outcome. This is an averaging argument; it does not require that different obstruction events be independent or even approximately independent.

Computing each marginal probability is usually much easier than counting all successful colorings. For a k-element set whose vertices receive independent fair red or blue colors, being monochromatic has probability $2^{1-k}$. There are two acceptable monochromatic assignments among the $2^k$ equally likely assignments. When several sets overlap, their monochromatic events may interact strongly. Nevertheless their marginal probabilities add exactly when calculating the expected total count. The overlap becomes relevant for stronger probability estimates, not for linearity itself.

Markov’s inequality gives an upper bound on failure. Subtracting it from one gives a lower bound on success, useful when that lower bound is positive. An expected number of desirable features larger than one does not establish that a typical construction has such a feature. Rare outcomes with enormous counts can dominate the expectation. Conversely, for an integer score with expectation a, some outcome has score at least a, hence at least its ceiling. This is a different use of averaging from avoiding all bad features.

The strict inequality at the threshold matters. An expected obstruction count equal to one permits the obstruction count to be identically one, so it need not certify any valid outcome. If the expectation tends to zero along a sequence of models, the same argument does give success with probability tending to one. A fixed positive success lower bound proves existence and supports repeated randomized trials, but says nothing about how expensive it is to recognize a successful outcome.

A random construction should satisfy the easy structural requirements automatically. To build a two-coloring, randomize colors rather than arbitrary subsets of an unrelated sample space. To search for a sparse subgraph, retain edges independently and count both the retained resources and unwanted patterns. Parameters can balance these expectations, although simultaneous resource and defect constraints may require a combined score, a concentration inequality, or a subsequent deletion step. Separate expectation statements do not automatically occur in the same outcome.

A useful audit records the sample space, each bad event, the event probability, and the resulting numerical inequality. It also records what has not been shown: an explicit coloring, a sharp threshold, or a practical deterministic algorithm. This prevents a probabilistic proof from promising more than its certificate contains. The worked calculation uses only a finite hypergraph, independent vertex colors, and a union bound; no assumptions about intersections between its edges are needed.