Triangle-Free Sets in Exact-Distance Hamming Graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.32789
curl -X POST /api/v1/records/arxiv/2610.32789/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.32789/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'