PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
April 1, 2026Journal of Graph Theory0 citationsOpen Access

Sensitivity and Hamming Graphs

View Full Paper
SAS. García AsensioYFYuval FilmusIGIgnacio García‐Marco

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.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Asensio et al. (2026) studied this question.

synapsesocial.com/papers/69ccb63f16edfba7beb87f57https://doi.org/10.1002/jgt.70034
Ask AI
Helpful
Bookmark
Share
View Full Paper