A common variable minimax theorem for graphs

Abstract

Let $G = {G_{1} = (V, E_{1}), \dots, G_{m} = (V, E_{m})}$ be a collection of $m$ graphs defined on a common set of vertices $V$ but with different edge sets $E_{1}, \dots, E_{m}$ . Informally, a function $f : V \to R$ is smooth with respect to $G_{k} = (V, E_{k})$ if $f (u) \sim f (v)$ whenever $(u, v) \in E_{k}$ . We study the problem of understanding whether there exists a nonconstant function that is smooth with respect to all graphs in $G$ , simultaneously, and how to find it if it exists.