Linear transformations of monotone functions on the discrete cube
In the paper under review, the authors present two conjectures regarding Boolean functions \(f:\{0,1\}^{n}\rightarrow \{0,1\}\), invertible linear transformations \(L\in GL_{n}(2)\), and the ``total influence'' \(I(f)\), discussed by \textit{M. Ben Or}, \textit{N Linial} and \textit{M. Saks} [in: Combinatorics, Proc. 7th Hung. Colloq., Eger/Hung. 1987, Colloq. Math. Soc. János Bolyai 52, 75--112 (1988; Zbl 0675.90107)]. The first conjecture is that if \(f\) is monotone then \(I(f)\leq I(f\circ L)\) for every \(L\in GL_{n}(2)\). The second conjecture is that if \(f\) is monotone then the composition \(f\circ L\) can only be monotone if it coincides with \(f\) up to a permutation of the coordinates. The authors verify the second conjecture in the special case where \(f\) is upper triangular.
scientific article; zbMATH DE number 5644050