Positive-influence conjecture for simply-rooted Boolean functions

Let {0,1}n\{0,1\}^n be the Hamming cube, and let f:{0,1}n{1,1}f:\{0,1\}^n\to\{-1,1\} be a simply-rooted function, as defined in the paper. Let f^()\widehat f(\emptyset) denote its level-zero Fourier coefficient, let I+(f)I^+(f) denote its positive influence, and let k[0,n1]k\in[0,n-1] satisfy

f^()(12k).\widehat f(\emptyset)\leq -(1-2^{-k}).

Positive-influence conjecture. One has

I+(f)(k+1)2k.I^+(f)\leq (k+1)2^{-k}.

The conjecture proposes a sharp upper bound on positive influence in terms of the negative level-zero Fourier coefficient. The examples CkC_k described in the paper attain the bound, but the conjecture remains open; the corresponding edge-isoperimetric lower bound concerns total influence rather than positive influence.

Sources & referencesView supporting material

Primary source

Ilan Karpas, “Two Results on Union-Closed Families”, arXiv:1708.01434 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.