Strong mm-ary sensitivity conjecture

About 2 years old · traced to

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=1m∣V(Hi)∣εi≠0,\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.

References

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.