Why is the maximal value of a clique continuous on the compact set of all distributions?

22 Views Asked by At

My book says the following:

Consider an arbitrary probability $x = (x_{v} : v \in V)$ on the set of vertices, that is, $x_{v} \geq 0$ and $\sum_{v \in V} x_{v} = 1$. To every distribution $x$ we associate the "maximal value of a clique"

$ \lambda(x) = \max_{C \in \mathcal{C}} \sum_{v \in C} x_{v} $

and finally we set

$ \lambda(G) = \min_{x} \lambda(x) = \min_{x} \max_{C \in \mathcal{C}} \sum_{v \in C} x_{v} $

To be precise we should use inf instead of min, but the minimum exists because $ \lambda(x)$ is continuous on the compact set of all distributions.

Why is $\lambda(x)$ continuous on the compact set of all distributions? And do you know of a good book that explains this and I can use as a reference?

1

There are 1 best solutions below

0
On

First, the monomial $\sum_{v\in C} x_v$ is a continuous function. Furthermore, the maximum of finitely many continuous functions is continuous. So, $\lambda(x)$ is continuous.

Second, the set of distributions equals $\{x_1, x_2, \dots, x_{|V(G)|} : x_v \geq 0 \text{ for all } v \in V(G) \text{ and } \sum_{v \in V(G)} x_v = 1\}$, which is a compact subset of $\mathbb{R}^{|V(G)|}$.

Finally, a continuous function attains its maximum and minimum values on a compact set.