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

About 2 years old · traced to

Let H(n,3)H(n,3) be the Hamming graph on Z3n{\mathbb Z}_3^n, and let U⊆Z3nU\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.

References

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.