What question did this study set out to answer?

To investigate the properties of Hamming graphs and their connection to sensitivity conjectures.

April 1, 2026Open Access

Sensitivity and Hamming Graphs

Key Points

To investigate the properties of Hamming graphs and their connection to sensitivity conjectures.
Developed an imbalanced partition approach for Hamming graphs.
Analyzed the maximum degree of induced subgraphs.
Examined and disproved the Strong k-ary Sensitivity Conjecture.
Provided proof for a weaker k-ary Sensitivity Conjecture with polynomial bounds.
Established a new partition method improving previous results in Hamming graphs.
Disproved the Strong k-ary Sensitivity Conjecture.
Showed sensitivity of k-ary functions has a lower bound defined by a polynomial in its degree.

Abstract

ABSTRACT For any we show that the Hamming graph admits an imbalanced partition into sets, each inducing a subgraph of low maximum degree. This improves previous results by Tandya and by Potechin and Tsang, and disproves the Strong ‐ary Sensitivity Conjecture of Asensio, García‐Marco, and Knauer. On the other hand, we prove their weaker ‐ary Sensitivity Conjecture by showing that the sensitivity of any ‐ary function is bounded from below by a polynomial expression in its degree.

Connected Papers

Building similarity graph...

Analyzing shared references across papers

Discussion

Authors

S. García Asensio

Yuval Filmus

Ignacio García‐Marco

Journals

Journal of Graph Theory

Actions

Institutions

Universitat de Barcelona

Technion – Israel Institute of Technology

Universidad de La Laguna

References and Citations

Connected Papers

Building similarity graph...

Analyzing shared references across papers

Sensitivity and Hamming Graphs

Key Points

Abstract

Citation Network

Connected Papers

Discussion

Authors

Journals

Actions

Institutions

References and Citations

Citation Network

Connected Papers

Discussion

Cite this study