The arity gap of order-preserving functions and extensions of pseudo-Boolean functions (Q412326): Difference between revisions

The arity gap (\(\text{gap}f\)) of a function \(f:A^n\to B\) that depends on all of its variables (\(n\geq2\)) is essentially the minimum decrease in the number of essential variables when variables of \(f\) are identified. In a previous paper, the first two authors [Discrete Math. 309, No. 20, 5905--5912 (2009; Zbl 1200.08001)] described all pseudo-Boolean functions \(f:\{0,1\}^n\to{\mathbb R}\) for which \(\text{gap}f=2\) and proved that \(\text{gap}f=1\) in the remaining cases. Every pseudo-Boolean function \(f\) can be written in the form \(f(\mathbf{x})=\sum_{S\subseteq[n]}m(S)\prod_{i\in S}x_i\;(\mathbf{x}\in\{0,1\}^n)\). The Owen extension (Lovász extension) of \(f\) is the function \(F_f:{\mathbb R}^n\to{\mathbb R}\) obtained from the above formula by taking \(\mathbf{x}\in{\mathbb R}\) (by taking \(\mathbf{x}\in{\mathbb R}\) and replacing \(\prod x_i\) by \(\bigwedge x_i\)). It is proved that \(\text{gap}F_f=\text{gap}f\) and a theorem similar to the above one holds for \(F_f\). If \(A\) and \(B\) are posets, \(A\) being upward directed and downward directed, and \(f:A^n\to B\) \((n\geq2)\) is an order-preserving function that depends on all of its variables, then \(\text{gap}f=2\) if and only if \(n=3\) and there is a non-constant order-preserving function \(h:A\to B\) such that \(f(x,x,y)=f(x,y,x)=f(y,x,x)=h(x)\); otherwise \(\text{gap}f=1\).