Ansensio–García-Marco–Knauer conjecture on induced degree-one subsets of the ternary Hamming graph

Let H(n,3)H(n,3) be the Hamming graph on Z3n{\mathbb Z}_3^n, and let UZ3nU\subseteq {\mathbb Z}_3^n induce a subgraph of maximum degree 11. Write α(H(n,3))\alpha(H(n,3)) for the independence number of H(n,3)H(n,3).

Ansensio–García-Marco–Knauer conjecture. All such subsets satisfy

U=α(H(n,3))+O(1).|U|=\alpha(H(n,3))+O(1).

The paper proves several bounds under additional hypotheses, including Uα(H(n,3))+729|U|\leq \alpha(H(n,3))+729 when UU is ii-saturated for some i[n]i\in[n]. The conjecture asks whether a bounded additive error remains valid without any saturation assumption; this remains open.

Sources & referencesView supporting material

Primary source

Aaron Potechin and Hing Yin Tsang, “On induced subgraphs of H(n,3) with maximum degree 1”, arXiv:2405.15004 (2026).

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.