Lagmental Vicfred

Alteration Repairs a Random Structure after Sampling by Vicfred

tags: mathematics, extremal combinatorics, probabilistic method, Ramsey theory

One may sample a large object and delete one element from each surviving bad configuration. I will separate the object being defined from the consequence being claimed.

Statement

Extremal combinatorics asks how large a structure can be while avoiding a forbidden configuration. The probabilistic method proves existence by showing \(\mathbf P(X=0)>0\) or \(\mathbf E[X]<1\).

$$ Y=|S|-X,\qquad X=\#\{\text{bad configurations in }S\} $$

I read the first line as input and the second as output. The symbols \(\forall\) and \(\exists\) are not interchangeable, and neither may be upgraded silently to \(\Longleftrightarrow\).

$$ \exists\,S'\ \text{valid with }|S'|\ge\mathbf E[|S|-X] $$

Worked algebra

An explicit case prevents the notation from becoming ceremonial. Every subscript and superscript in the display contributes to the value.

$$ \mathbf E[Y]=np-\binom{k}{2}p^2\quad\Longrightarrow\quad\max_{0\le p\le1}\mathbf E[Y]\ \text{gives a deterministic lower bound} $$

Conceptual compression

The invariant statement is the one that does not depend on a convenient choice of coordinates, representatives, basis, or enumeration.

$$ \begin{aligned} \mathsf{D}\;&:\quad Y=|S|-X,\qquad X=\#\{\text{bad configurations in }S\},\\[5pt] \mathsf{C}\;&:\quad \exists\,S'\ \text{valid with }|S'|\ge\mathbf E[|S|-X]. \end{aligned} $$

Caveat

An expectation below one proves that some outcome has zero bad objects only when the bad-object count is a nonnegative integer.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \exists\,S'\ \text{valid with }|S'|\ge\mathbf E[|S|-X] \end{gathered}} $$

I would use the boxed line as a reference later, while returning to the full display whenever a hypothesis becomes uncertain. That division keeps compression from becoming ambiguity.

This article was posted on Tue 01 January 2013. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.