A common variable minimax theorem for graphs

Abstract

Let $\mathcal{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 \mathbb{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 $\mathcal{G}$, simultaneously, and how to find it if it exists.

21 pages, 11 figures

References in corpus (1)

• Spectral Discovery of Jointly Smooth Features for Multimodal Data