Triangle-Free Sets in Exact-Distance Hamming Graphs
Abstract
Let Tq(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 Tq(n,2h)=Oh(qn/nh). We extend the known distance-one formula and distance-two order to arbitrary integer alphabet sizes, obtaining Tq(n,1)=2qn−1 and Tq(n,2)=Θq(qn/n), and establish T3(n,4)=Θ(3n/n2). For general fixed distance, we prove Tq(n,r)=Ωq,r ( (qn√(log n))/(n(r+⌊ r/2⌋)/2) ) (q≥3), while we show that Tq(n,r)=Ωq,r(qn/n⌊(q−1)r/q⌋) holds for prime-power q and r≥2 via the extended BCH parity-check constructions. At distance three, we construct coordinate weights avoiding bounded-coefficient three-term relations and obtain Tq(n,3)≥ qn/[nexp(Oq(√(log n)))]. Our main ternary construction combines cap partitions, multicolor triangle Ramsey colorings, and a quadratic map to obtain T3(n,3)=Ω ( (loglog n)/(log n) 3n). A coordinate-line counting argument gives the complementary upper bound T3(n,3)≤(5/27+O(n−1))3n, together with an explicit bound for every fixed q≥3. Whether the ternary density tends to zero remains open.
Related
- Exact extremizers for ℓp-judicious bisections of triangle-free graphs
- Exact majority C-colourings of balanced Hamming graphs and grids
- The crossing number and the unit-distance crossing number of the Hamming graphs H(d,3)=K_3^{box d}, and their realizations over many coordinate fields
- Geometric triangle-free graphs of large chromatic number
- When are random regular triangle-free graphs bipartite?
BibTeX
@misc{csajbok2026trianglefree,
title = {{Triangle-Free Sets in Exact-Distance Hamming Graphs}},
author = {Bence Csajbók and Padmini Mukkamala and Zoltán Lóránt Nagy},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32789},
eprint = {2610.32789},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32789},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Triangle-Free Sets in Exact-Distance Hamming Graphs
AU - Bence Csajbók
AU - Padmini Mukkamala
AU - Zoltán Lóránt Nagy
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32789
UR - https://arxiv.org/abs/2610.32789
AB - 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 ( (q^n√(log n))/(n^(r+⌊ r/2⌋)/2) ) (q≥3), while we show that T_q(n,r)=Ω_q,r(q^n/n^⌊(q−1)r/q⌋) holds for prime-power q and r≥2 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)≥ q^n/[nexp(O_q(√(log n)))]. Our main ternary construction combines cap partitions, multicolor triangle Ramsey colorings, and a quadratic map to obtain T_3(n,3)=Ω ( (loglog n)/(log n) 3^n). A coordinate-line counting argument gives the complementary upper bound T_3(n,3)≤(5/27+O(n^−1))3^n, together with an explicit bound for every fixed q≥3. Whether the ternary density tends to zero remains open.
ER -