Triangle-free subsets of the $r$-distance graph of the Hypercube
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913037608288256 |
|---|---|
| author | Mukkamala, Padmini Ravi, Ananthakrishnan |
| author_facet | Mukkamala, Padmini Ravi, Ananthakrishnan |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_18782 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Triangle-free subsets of the $r$-distance graph of the Hypercube Mukkamala, Padmini Ravi, Ananthakrishnan Combinatorics 05C30 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$. |
| title | Triangle-free subsets of the $r$-distance graph of the Hypercube |
| topic | Combinatorics 05C30 |
| url | https://arxiv.org/abs/2506.18782 |