Triangle-free subsets of the $r$-distance graph of the Hypercube

Ananthakrishnan Ravi; Padmini Mukkamala

arxiv: 2506.18782 · v2 · submitted 2025-06-23 · 🧮 math.CO

Triangle-free subsets of the r-distance graph of the Hypercube

Padmini Mukkamala , Ananthakrishnan Ravi This is my paper

Pith reviewed 2026-05-19 07:59 UTC · model grok-4.3

classification 🧮 math.CO

keywords hypercuber-distance graphtriangle-free setsHamming distanceextremal graph theorycombinatorial boundsbinary codes

0 comments

The pith

For even r at most n/2 the largest triangle-free set in the hypercube r-distance graph has size O(r 2^n / (n+1)).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies sets of binary strings of length n in which no two differ in exactly r positions and no three form a triangle under that exact-difference adjacency. It proves that when r is even and at most n/2 the largest such set has size at most a constant times r times the total number of strings divided by n plus one. This shows the sets must be noticeably smaller than the full hypercube once n grows. The authors also give lower bounds that match the upper bound order in several ranges of r relative to n.

Core claim

In the graph whose vertices are all 2^n binary vectors of length n and whose edges connect pairs at Hamming distance exactly r, the maximum number of vertices inducing no triangle is T(n,r) = O(r 2^n / (n+1)) whenever r is even and r ≤ n/2.

What carries the argument

The r-distance graph on the hypercube, with the size of its largest triangle-free vertex subset T(n,r) bounded by a direct combinatorial counting argument that exploits even parity of r.

If this is right

Any triangle-free subset is forced to omit a positive fraction of the vertices that grows with n/r.
Lower bounds of matching order exist for T(n,r) in several regimes of r as a function of n.
The bound is specific to even r and does not automatically transfer to odd r.
The same counting technique limits how large a set can be while avoiding both exact-r pairs and r-r-r triangles.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same style of argument might yield bounds for forbidden larger cliques or for other distance graphs on the hypercube.
One could check the bound numerically for moderate n by enumerating small even r and comparing against the predicted order.
If the bound extends to odd r it would unify the picture for all fixed distances.

Load-bearing premise

The upper-bound argument requires r to be even and at most n/2; without that restriction the claimed order may not hold.

What would settle it

Exhibit an explicit triangle-free set of size larger than C r 2^n / (n+1) for some fixed C, even r ≤ n/2, and arbitrarily large n.

read the original 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$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper proves a new O(r 2^n / (n+1)) upper bound on the largest triangle-free set in the even-r distance graph of the hypercube for r ≤ n/2, with the combinatorial argument holding up on inspection.

read the letter

The main takeaway is that for even r at most n/2, the maximum triangle-free subset T(n,r) in the r-distance graph on the n-cube satisfies T(n,r) = O(r 2^n / (n+1)). The proof uses a direct counting or averaging argument over the hypercube structure, and the stress-test confirms no unjustified steps or inconsistencies in the stated regime. They also supply lower bounds across different r ranges, which gives some context for how sharp the upper bound might be. The quantitative form of the upper bound does not appear in the prior literature referenced in the abstract, so that part is new. The restriction to even r is built into the argument and makes sense given how parity affects distance-r triangles. On the softer side, the result stays narrow because it does not cover odd r or r larger than n/2, and the lower bounds are only sketched in the abstract so their tightness relative to the upper bound is not fully clear from the summary. The O-notation is standard but leaves the leading constant implicit. This work sits in extremal graph theory on hypercubes and could interest people doing coding-theory constructions that avoid short cycles in distance graphs. A reader already following boolean-lattice problems or induced-subgraph questions on the cube would get concrete value from the explicit bound. I would send it to peer review; the claim is specific, the proof checks out, and it adds a usable quantitative statement even if the scope is limited.

Referee Report

0 major / 3 minor

Summary. The paper studies the maximum size T(n,r) of a triangle-free vertex subset in the r-distance graph of the hypercube F_2^n (edges between vectors of exact Hamming distance r). For even r ≤ n/2 it proves the upper bound T(n,r) = O(r 2^n / (n+1)) by a combinatorial counting argument; it also supplies lower bounds on T(n,r) in several regimes of r relative to n.

Significance. The upper bound supplies a concrete quantitative estimate on the independence number of the r-distance hypercube graph in the stated regime, which is of interest in extremal set theory and coding theory. The combinatorial proof technique and the accompanying lower bounds together indicate the order of magnitude of T(n,r) for even r ≤ n/2.

minor comments (3)

The abstract states the upper bound only for even r ≤ n/2; the introduction should explicitly note whether the parity and size restrictions are required by the argument or are merely the regime in which the proof is presented.
In the lower-bound sections, the explicit constructions or probabilistic methods used to obtain the matching lower bounds should be summarized with a short statement of the achieved order of magnitude.
Notation for the r-distance graph and for T(n,r) is introduced in the abstract; a single consolidated definition paragraph early in the paper would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our manuscript on triangle-free subsets in the r-distance hypercube graph and for recommending minor revision. We are encouraged by the assessment that the upper bound provides a concrete quantitative estimate on the independence number of interest in extremal set theory and coding theory, and that the combinatorial argument together with the lower bounds indicates the order of magnitude of T(n,r) for even r ≤ n/2.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper derives the upper bound T(n,r) = O(r 2^n / (n+1)) for even r ≤ n/2 via an explicit combinatorial counting and averaging argument on the hypercube's r-distance graph. This argument operates directly from the definition of triangle-free sets and the structure of the graph without any reduction to fitted parameters, self-referential definitions, or load-bearing self-citations. The proof remains self-contained within the stated parity and size regime, with the O-notation following from the averaging technique rather than from any input that presupposes the target bound.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are identifiable from the abstract alone; the result is stated as a direct combinatorial bound without visible auxiliary constants or new objects.

pith-pipeline@v0.9.0 · 5608 in / 1071 out tokens · 38149 ms · 2026-05-19T07:59:35.309017+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean (and Cost/FunctionalEquation.lean) reality_from_one_distinction; Jcost uniqueness unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 6. When 2r ≤ n and r is even, any triangle-free subset ... O(r 2^n / (n+1)) ... using shadows at level k-r/2 and Frankl's bound |F| ≤ 2 binom(n-(k-r/2)-1, r/2-1)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Forbidding Exactly One Hamming Distance
math.CO 2026-04 unverdicted novelty 6.0

The s-independence number of the exact-r-distance graph on the hypercube is asymptotically Θ(2^n / n^{r/2}) for fixed s ≥ 2 and even r ≥ 2.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages · cited by 1 Pith paper · 2 internal anchors

[1]

Hamiltonian uniform subset graphs

Bor-Liang Chen, Ko-Wei Lih. Hamiltonian uniform subset graphs. Journal of Combinatorial Theory B, 42:257–263, 1987

work page 1987
[2]

Paul Erd˝ os, A problem on independent r-tuples, Ann. Univ. Sci. Budapest. 8, 93–95, 1965

work page 1965
[3]

Peter Frankl, Vojtˇ ech R¨ odl, Forbidden intersections, Transactions of the American Mathemat- ical Society, 300 (1): 259–286, 1987

work page 1987
[4]

Peter Frankl, The shifting technique in extremal set theory, Surveys in Combinatorics 123, 81–110, 1987

work page 1987
[5]

Peter Frankl, Andrey Kupavskii, The Erd˝ os Matching Conjecture and concentration inequali- ties, arXiv:1806.08855, 2018

work page arXiv 2018
[6]

Lovasz, On the Shannon capacity of a graph, IEEE Transactions on Information Theory, vol

L. Lovasz, On the Shannon capacity of a graph, IEEE Transactions on Information Theory, vol. 25, no. 1, pp. 1-7, 1979

work page 1979
[7]

Gr¨ otschel, L

M. Gr¨ otschel, L. Lov´ asz, A. Schrijver: Relaxations of vertex packing. J. Comb. Theory, Series B 40, 330–343, 1986

work page 1986
[8]

Manuel Kauers, Ryan O’Donnell, Li-Yang Tan, Yuan Zhou, Hypercontractive inequalities via SOS, and the Frankl–R¨ odl graph, arXiv:1212.5324, 2012

work page internal anchor Pith review Pith/arXiv arXiv 2012
[9]

Martin, Bal´ azs Patk´ os, A note on the Erd˝ os Matching Conjecture, arXiv:2404.12971, 2024

Ryan R. Martin, Bal´ azs Patk´ os, A note on the Erd˝ os Matching Conjecture, arXiv:2404.12971, 2024

work page arXiv 2024
[10]

Kleitman, On a combinatorial conjecture of Erd˝ os, J

D. Kleitman, On a combinatorial conjecture of Erd˝ os, J. Combin. Theory Ser. A 43, 85–90, 1986

work page 1986
[11]

Hao Huang, Oleksiy Klurman, Cosmin Pohoata, On subsets of the hypercube with prescribed Hamming distances, arXiv:1812.05989, 2018. 6

work page internal anchor Pith review Pith/arXiv arXiv 2018
[12]

Castro-Silva, D., de Oliveira Filho, F.M., Slot, L. et al. A Recursive Theta Body for Hyper- graphs. Combinatorica 43, 909–938, 2023. 7

work page 2023

[1] [1]

Hamiltonian uniform subset graphs

Bor-Liang Chen, Ko-Wei Lih. Hamiltonian uniform subset graphs. Journal of Combinatorial Theory B, 42:257–263, 1987

work page 1987

[2] [2]

Paul Erd˝ os, A problem on independent r-tuples, Ann. Univ. Sci. Budapest. 8, 93–95, 1965

work page 1965

[3] [3]

Peter Frankl, Vojtˇ ech R¨ odl, Forbidden intersections, Transactions of the American Mathemat- ical Society, 300 (1): 259–286, 1987

work page 1987

[4] [4]

Peter Frankl, The shifting technique in extremal set theory, Surveys in Combinatorics 123, 81–110, 1987

work page 1987

[5] [5]

Peter Frankl, Andrey Kupavskii, The Erd˝ os Matching Conjecture and concentration inequali- ties, arXiv:1806.08855, 2018

work page arXiv 2018

[6] [6]

Lovasz, On the Shannon capacity of a graph, IEEE Transactions on Information Theory, vol

L. Lovasz, On the Shannon capacity of a graph, IEEE Transactions on Information Theory, vol. 25, no. 1, pp. 1-7, 1979

work page 1979

[7] [7]

Gr¨ otschel, L

M. Gr¨ otschel, L. Lov´ asz, A. Schrijver: Relaxations of vertex packing. J. Comb. Theory, Series B 40, 330–343, 1986

work page 1986

[8] [8]

Manuel Kauers, Ryan O’Donnell, Li-Yang Tan, Yuan Zhou, Hypercontractive inequalities via SOS, and the Frankl–R¨ odl graph, arXiv:1212.5324, 2012

work page internal anchor Pith review Pith/arXiv arXiv 2012

[9] [9]

Martin, Bal´ azs Patk´ os, A note on the Erd˝ os Matching Conjecture, arXiv:2404.12971, 2024

Ryan R. Martin, Bal´ azs Patk´ os, A note on the Erd˝ os Matching Conjecture, arXiv:2404.12971, 2024

work page arXiv 2024

[10] [10]

Kleitman, On a combinatorial conjecture of Erd˝ os, J

D. Kleitman, On a combinatorial conjecture of Erd˝ os, J. Combin. Theory Ser. A 43, 85–90, 1986

work page 1986

[11] [11]

Hao Huang, Oleksiy Klurman, Cosmin Pohoata, On subsets of the hypercube with prescribed Hamming distances, arXiv:1812.05989, 2018. 6

work page internal anchor Pith review Pith/arXiv arXiv 2018

[12] [12]

Castro-Silva, D., de Oliveira Filho, F.M., Slot, L. et al. A Recursive Theta Body for Hyper- graphs. Combinatorica 43, 909–938, 2023. 7

work page 2023