Strong mm-ary sensitivity conjecture

Let mm be a positive integer, let ε\varepsilon be an mm-th primitive root of unity, and let H(n,m)H(n,m) be the Hamming graph. Write H1,,HmH_1,\dots,H_m for possibly empty induced subgraphs whose vertex sets partition the vertices of H(n,m)H(n,m), and let Δ(Hi)\Delta(H_i) denote the maximum degree of HiH_i. Strong mm-ary sensitivity conjecture. There exists μ>0\mu>0 such that, whenever

i=1mV(Hi)εi0,\sum_{i=1}^{m}|V(H_i)|\varepsilon^i\neq 0,

one has

max{Δ(H1),,Δ(Hm)}Ω(nμ).\max\{\Delta(H_1),\dots,\Delta(H_m)\}\in\Omega(n^\mu).

The paper presents this as a stronger, more natural open reformulation of the mm-ary sensitivity conjecture. Its claimed strength is supported by the paper's discussion, while the relationship to the preceding formulation is the subject of the stated context.

Sources & referencesView supporting material

Primary source

Sara Asensio, Ignacio García-Marco and Kolja Knauer, “Sensitivity of m-ary functions and low degree partitions of Hamming graphs”, arXiv:2409.16141 (2024).

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.