Lagmental Vicfred

Turán's Theorem Maximizes Edges without a Clique by Vicfred

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

The balanced complete (r minus one)-partite graph has the most edges among K_r-free graphs. A small computation will anchor the general statement before the abstraction takes over.

The mathematical object

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\).

$$ K_r\nsubseteq G $$

The typography mirrors the proof: first declare \(\mathsf D\), then state \(\mathsf C\). The symbol \(\Longrightarrow\) below is a logical dependency, not extra mathematical structure.

$$ e(G)\le e(T_{r-1}(n)) $$

One explicit computation

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

$$ e(T_{r-1}(n))=\frac12\left(n^2-\sum_{i=1}^{r-1}n_i^2\right),\qquad n_i\in\left\{\left\lfloor\frac n{r-1}\right\rfloor,\left\lceil\frac n{r-1}\right\rceil\right\} $$

Why the identity matters

The formula is reusable precisely because it says which pieces are structural and which belong only to the worked example.

$$ \begin{aligned} \mathsf{D}\;&:\quad K_r\nsubseteq G,\\[5pt] \mathsf{C}\;&:\quad e(G)\le e(T_{r-1}(n)). \end{aligned} $$

Where it can fail

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] e(G)\le e(T_{r-1}(n)) \end{gathered}} $$

The important habit is to remember what was fixed before the calculation began and what was proved only afterward. The final display preserves that order.

This article was posted on Sat 28 September 2024. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.