Triangle-Free Sets in Exact-Distance Hamming Graphs

Source abstract

Let $T_q(n,r)$ be the largest size of a vertex set inducing a triangle-free subgraph of the graph on $[q]^n$ whose edges join words at Hamming distance $r$. We study this quantity for fixed alphabet size and fixed distance, with particular emphasis on the ternary cube. Alphabet restriction transfers the binary fixed-distance theorem of Balogh, Chen, and Li to give $T_q(n,2h)=O_h(q^n/n^h)$. We extend the known distance-one formula and distance-two order to arbitrary integer alphabet sizes, obtaining $T_q(n,1)=2q^{n-1}$ and $T_q(n,2)=Θ_q(q^n/n)$, and establish $T_3(n,4)=Θ(3^n/n^2)$. For general fixed distance, we prove $$T_q(n,r)=Ω_{q,r}\!\left( \frac{q^n\sqrt{\log n}}{n^{(r+\lfloor r/2\rfloor)/2}} \right)\qquad(q\ge3),$$ while we show that $T_q(n,r)=Ω_{q,r}(q^n/n^{\lfloor(q-1)r/q\rfloor})$ holds for prime-power $q$ and $r\ge2$ via the extended BCH parity-check constructions. At distance three, we construct coordinate weights avoiding bounded-coefficient three-term relations and obtain $$T_q(n,3)\ge q^n/[n\exp(O_q(\sqrt{\log n}))].$$ Our main ternary construction combines cap partitions, multicolor triangle Ramsey colorings, and a quadratic map to obtain $$T_3(n,3)=Ω\!\left( \frac{\log\log n}{\log n}\,3^n\right).$$ A coordinate-line counting argument gives the complementary upper bound $T_3(n,3)\le(5/27+O(n^{-1}))3^n$, together with an explicit bound for every fixed $q\ge3$. Whether the ternary density tends to zero remains open.