Linear transformations of monotone functions on the discrete cube
type: Item
instance of: scholarly article
title: Linear transformations of monotone functions on the discrete cube
zbMATH Open document ID: 1182.94066
author: Nathan Keller
author: Haran Pilpel
published in: Discrete Mathematics
publication date: 2009-12-09T00:00:00Z
review text: 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.
reviewed by: L. Traldi
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 5644050
zbMATH Keywords: influences
zbMATH Keywords: Boolean functions
zbMATH Keywords: Fourier-Walsh expansion
zbMATH Keywords: discrete Fourier analysis
MaRDI profile type: Publication
full work available at URL: j.disc.2008.12.018
OpenAlex ID: W2044628801
cites work: Noise sensitivity of Boolean functions and applications to percolation
cites work: Q3830840
cites work: Q3726125
cites work: Boolean functions with low average sensitivity depend on few coordinates
cites work: Every monotone graph property has a sharp threshold
cites work: Q3597148
cites work: Monotone Boolean functions
cites work: Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces
DOI: 10.1016/J.DISC.2008.12.018
description: scientific article; zbMATH DE number 5644050