Locally monotone Boolean and pseudo-Boolean functions (Q444430): Difference between revisions

Several generalizations of monotonicity for Boolean functions \(f:\{0,1\}^n\longrightarrow\{0,1\}\) and pseudo-Boolean functions \(f:\{0,1\}^n\longrightarrow{\mathbb R}\) are introduced. They are defined in terms of the discrete partial derivatives \(\Delta_kf(\mathbf{x})=f(\mathbf{x}_k^1)-f(\mathbf{x}_k^0)\), where \(\mathbf{x}_k^i=(x_1,\dots,x_k=i,\dots,x_n)\) (\(i \in \{0,1\}\)), as follows: for \(p\in\{1,\dots,n\}\), \(f\) is said to be \(p\)-locally monotone if \[ \sum_{i\in[n]\setminus[k]}| x_i-y_i|<p\Longrightarrow\Delta_k f(\mathbf{x})-\Delta_k(\mathbf{y})\geq0. \] Any \(p\)-locally monotone pseudo-Boolean function is also \(p'\)-locally monotone for every \(p'\leq p\). Every pseudo-Boolean function \(f\) is 1-locally monotone, and \(f\) is \(n\)-locally monotone iff it is monotone (i.e., isotone or antitone). A 2-locally monotone function is said to be locally monotone. A section of a function \(f\) is the function obtained from \(f\) by replacing some of its variables by constants. Sample results: A function is \(p\)-locally monotone iff every \(p\)-ary section of it is monotone. A Boolean function \(f\) is locally monotone iff neither \(x\oplus y\) nor \(x\oplus y\oplus 1\) is a section of \(f\). The partial lattice derivatives of a pseudo-Boolean function are defined by \(\bigwedge_kf(\mathbf{x})=f(\mathbf{x}_k^0)\wedge f(\mathbf{x}_k^1)\) and \(\bigvee_kf(\mathbf{x})=f(\mathbf{x}_k^0)\vee f(\mathbf{x}_k^1)\). A Boolean function \(f\) is locally monotone iff \(\bigvee_k\bigwedge_j f=\bigwedge_j\bigvee_k f\) for every \(j\neq k\). A more general concept of \(p\)-permutability of lattice derivatives is defined and the relationship between this property and local monotonicity is studied in detail. If two functions \(f,g:\{0,1\}^n\to{\mathbb R}\) have equal lattice derivatives then either \(f=g\) or there is an injection \(\alpha:\{0,1\}\to{\mathbb R}\) such that \(f(\mathbf{x})=\alpha(x_1\oplus\dots\oplus x_n)\) and \(g(\mathbf{x})=\alpha(x_1\oplus\dots\oplus x_n\oplus 1)\). The last section deals with special properties of symmetric functions. Finally, two open problems are stated. The paper is carefully written, with illustrative examples and two counterexamples to certain suppositions. Interesting connections with game theory are established.