Skip to main content

Math 426/529: Extremal Combinatorics

Jonathan A. Noel

Appendix C Convexity

Throughout the notes, we apply many “convexity” arguments. Most of these involve “sums of squares,” see Corollary C.0.6 below. Convexity also arises in some of the entropy-based proofs.
described in detail following the image
“Convexity.”

Definition C.0.1.

Let \(I\subseteq \mathbb{R}\) be an interval (of possibly infinite length). A function \(\varphi:I\to \mathbb{R}\) is said to be convex if, for all \(x,y\in I\) and \(t\in [0,1]\text{,}\)
\begin{equation} \varphi(tx + (1-t)y) \leq t\varphi(x)+(1-t)\varphi(y)\text{.}\tag{C.0.1} \end{equation}
Recall that a subset \(S\) of \(\mathbb{R}^n\) is convex if, for every \(x,y\in S\) and \(\lambda\in [0,1]\text{,}\) it holds that \(\lambda x+(1-\lambda)y\in S\text{.}\) This provides us with another way to think of a convex function. A function is convex if and only if the region in \(\mathbb{R}^2\) above the graph of the function is a convex subset of \(\mathbb{R}^2\text{.}\)

Observation C.0.2.

A twice-differentiable function \(\varphi:I\to \mathbb{R}\) is convex if and only if its second derivative is positive everywhere on \(I\text{.}\)
In particular, all of the functions \(x^p\) for \(p\geq 1\) are convex. The function \(x\log(x)\) on \((0,\infty)\) is also convex. The following theorem, known as Jensen’s Inequality, is a fundamental fact about convex functions which is used throughout mathematics.

Proof.

We proceed by induction on \(n\text{.}\) The case \(n=1\) is trivial, as both sides of the inequality evaluate to \(\varphi(z_i)\text{.}\) Now, suppose that \(n\geq2\text{.}\) Define
\begin{equation*} A:=\sum_{i=1}^na_i \end{equation*}
\begin{equation*} t:=\frac{a_1}{A}\text{,} \end{equation*}
\begin{equation*} x:=z_1\text{,} \end{equation*}
and
\begin{equation*} y:=\sum_{i=2}^{n}\frac{a_i z_i}{A-a_1}\text{.} \end{equation*}
Since \(I\) is an interval (which is a convex set) and \(\sum_{i=2}^{n}\frac{a_i}{A-a_1}=1\text{,}\) we have \(y\in I\text{.}\) Therefore, by (C.0.1),
\begin{equation*} \varphi\left(\frac{\sum_{i=1}^na_iz_i}{\sum_{i=1}^n a_i}\right) = \varphi(tx+(1-t)y)\leq t\varphi(x)+(1-t)\varphi(y) \end{equation*}
\begin{equation*} =\frac{a_1\varphi(z_1)}{A} + \frac{(A-a_1)\varphi(y)}{A}\text{.} \end{equation*}
By induction,
\begin{equation*} \varphi(y)\leq \sum_{i=2}^{n}\frac{a_i\varphi(z_i)}{A-a_1}\text{.} \end{equation*}
Putting the last two inequalities together completes the proof.
As a consequence, we obtain a version of Hölder’s Inequality.

Proof.

We assume all of the \(x_i\) and \(y_i\) are positive (to avoid dividing by zero). The general case will follow easily from this. For \(1\leq i\leq n\text{,}\) let
\begin{equation*} z_i:=\frac{|x_i|}{|y_i|^{q-1}} \end{equation*}
and
\begin{equation*} a_i:=|y_i|^q\text{.} \end{equation*}
The function \(x^p\) is convex, and so Jensen’s Inequality tells us that
\begin{equation*} \left(\frac{\sum_{i=1}^n a_iz_i}{\sum_{i=1}^na_i}\right)^p \leq \frac{\sum_{i=1}^n a_i z_i^p}{\sum_{i=1}^na_i} \end{equation*}
\begin{equation*} \Longrightarrow \frac{\sum_{i=1}^n a_iz_i}{\sum_{i=1}^na_i}\leq \left(\frac{\sum_{i=1}^n a_i z_i^p}{\sum_{i=1}^na_i}\right)^{1/p} \end{equation*}
\begin{equation*} \Longrightarrow \sum_{i=1}^n a_iz_i\leq \left(\sum_{i=1}^n a_i z_i^p\right)^{1/p}\left(\sum_{i=1}^na_i\right)^{(p-1)/p}\text{.} \end{equation*}
Note that \(\frac{p-1}{p}=\frac{1}{q}\text{,}\) and so we can substitute that in for the last exponent in the above expression. Let’s also plug in the values of \(z_i\) and \(a_i\text{.}\) We get
\begin{equation*} \sum_{i=1}^n|y_i|^q\left(\frac{|x_i|}{|y_i|^{q-1}}\right)\leq \left(\sum_{i=1}^n|y_i|^q\left(\frac{|x_i|}{|y_i|^{q-1}}\right)^p\right)^{1/p}\left(\sum_{i=1}^n|y_i|^q\right)^{1/q} \end{equation*}
\begin{equation*} \Longrightarrow \sum_{i=1}^n|x_iy_i|\leq \left(\sum_{i=1}^n|x_i|^p\right)^{1/p}\left(\sum_{i=1}^n|y_i|^q\right)^{1/q} \end{equation*}
which is exactly what we set out to prove.

Proof.

Let \(q=\frac{p}{p-1}\) and define \(y_i=1\) for \(1\leq i\leq n\text{.}\) Apply Lemma C.0.4.
In particular, in the case \(p=2\text{,}\) we get the following:
PrevTopNext