Triangle-free subsets of the r-distance graph of the Hypercube
Preprint
(2026)
Author(s)
Padmini Mukkamala (Budapest Institute of Technology and Economics, Budapest, Hungary. )
Ananthakrishnan Ravi (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Research Group
Discrete Mathematics and Optimization
DOI related publication
https://doi.org/10.48550/arXiv.2506.18782
Final published version
To reference this document use
https://resolver.tudelft.nl/uuid:2c221943-598c-4255-a71a-fd95b0c2d86c
More Info
expand_more
expand_more
Publication Year
2026
Language
English
Research Group
Discrete Mathematics and Optimization
Downloads counter
4
Abstract
Given the r-distance graph on the hypercube \mathbb{F}_2^n, where two vertices are adjacent if their Hamming distance is exactly r, we study the maximum size T(n,r) of a triangle-free set of vertices. For even r\le n/2, we prove T(n,r)=O\!\left(\frac{r2^n}{n+1}\right).
We also obtain lower bounds in various regimes of r as a function of n.