A note on M-convex functions on jump systems (Q2217499): Difference between revisions

Let \(x,y\in \mathbb{Z}^{n}\). A vector \(s\in \mathbb{Z}^{n}\) is said to be an \((x,y)\)-increment if either \(s\) or \(-s\) is one of the \(n\) unit vectors and \(x\wedge y\leq x+s\leq x\vee y\). Let \(f:\mathbb{Z}^{n}\rightarrow \mathbb{R\cup \{+\infty \}}\). One says that \(f\) is jump M-convex if for any \(x,y\in \mathrm{dom}~f\) and any \((x,y)\)-increment \(s\), there exists an \((x+s,y)\)-increment \(t\) such that \(x+s+t,~y-s-t\in \mathrm{dom}~f\) and \(f(x)+f(y)\geq f(x+s+t)+f(y-s-t)\). One says that \(f\) is jump M\(^{\sharp}\)-convex if for any \(x,y\in \mathrm{dom}~f\) and any \((x,y)\)-increment \(s\), one of the following two conditions holds: (i) \(x+s,~y-s\in \mathrm{dom}~f\), and \(f(x)+f(y)\geq f(x+s)+f(y-s)\), (ii) there exists an \((x+s,y)\)-increment \(t\) such that \(x+s+t,~y-s-t\in \mathrm{dom}~f\) and \(f(x)+f(y)\geq f(x+s+t)+f(y-s-t)\). For \(x\in \mathbb{Z}^{n}\), define \(\pi (x)=0\) if the component sum of \(x\) is even and \(\pi (x)=1\) otherwise. The main result states that \(f\) is jump M\(^{\sharp }\)-convex if and only if the function \(\widetilde{f}:\mathbb{Z}^{n+1}\rightarrow \mathbb{R\cup \{+\infty \}}\) defined by \(\widetilde{f}(x_{0},x)=f(x)\) if \(x_{0}=\pi (x)\) and \(\widetilde{f}(x_{0},x)=+\infty \) otherwise is jump M-convex.