WorksMathematics
Triangle-Free Sets in Exact-Distance Hamming Graphs
Abstract
Let be the largest size of a vertex set inducing a triangle-free subgraph of the graph on whose edges join words at Hamming distance . 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 . We extend the known distance-one formula and distance-two order to arbitrary integer alphabet sizes, obtaining and , and establish . For general fixed distance, we prove while we show that holds for prime-power and via the extended BCH parity-check constructions. At distance three, we construct coordinate weights avoiding bounded-coefficient three-term relations and obtain Our main ternary construction combines cap partitions, multicolor triangle Ramsey colorings, and a quadratic map to obtain A coordinate-line counting argument gives the complementary upper bound , together with an explicit bound for every fixed . Whether the ternary density tends to zero remains open.
Introduction and statement of results
Write . The -ary Hamming graph has vertex set , and two vertices are connected if they are at Hamming distance , i.e., the vectors of the corresponding vertices differ in exactly one coordinate. Note that is the Cartesian product of complete graphs . A natural generalisation of the Hamming graph is the -distance Hamming graph , which has vertex set , and
Our aim is to study the maximum size of a triangle-free set of vertices in the -distance graph of the Hamming graph.
Definition 1.1 (Maximum triangle-free set of vertices in ).
This definition was introduced by Mukkamala and Ravi [16], who were mainly interested in the binary case .
In the terminology of extremal graph theory, it can also be expressed as the vertex Turán number
namely the largest number of vertices inducing no copy of in the fixed host graph . Vertex Turán problems for the Boolean cube were developed systematically by Johnson and Talbot [13], and related questions for the ternary cube were considered by Li and Hao [15]. The forbidden configurations in those works are embedded subcubes or prescribed small configurations, rather than equilateral triples in an exact-distance graph, so their results do not apply directly here.
There is an equivalent hypergraph formulation. Let be the 3-uniform hypergraph on whose hyperedges are the triples whose three pairwise Hamming distances are equal to . Then
Thus the problem may also be viewed as an independence problem in a highly structured 3-uniform hypergraph, as well as a problem in coding theory.
Exact-distance graphs are closely related to graph powers, with adjacency prescribed by equality of distances rather than by an upper bound on distance. Their structure under Cartesian and other standard products, including exact-distance graphs of hypercubes, was investigated by Brešar, Gastineau, Klavžar, and Togni [7]. In the Boolean cube, forbidding all pairs at one prescribed distance is precisely the classical one-forbidden-distance code problem. Its development includes the subset-sum constructions of Cohen and Zémor [9] and the systematic forbidden-distance bounds of Bassalygo, Cohen, and Zémor [3]. The problem considered here is a genuinely higher-order relaxation: prescribed-distance pairs may occur abundantly, but the graph that they span is required to have clique number at most two.
The binary version arose explicitly from the recursive theta-body method of Castro-Silva, de Oliveira Filho, Slot, and Vallentin [8]. Mukkamala and Ravi developed direct combinatorial bounds, proving in particular a uniform estimate for even , as well as exponentially small density when is a fixed positive fraction of , with and is even [16]. For fixed distance, the decisive result is due to Balogh, Chen, and Li [2]. For a graph and an integer , write
Thus and . In this notation, Balogh, Chen, and Li [2] proved that, for every fixed and ,
Alphabet restriction and the colorings developed below yield nonbinary extensions of this statement; see Corollary 3.3. Their proof brings together the theory of codes with one forbidden distance [3] and extremal estimates for sunflower-free set systems. Since is bipartite when is odd, the binary -distance problem is therefore complete:
The passage from two symbols to three yields new phenomena. A binary equilateral Hamming triangle can use only coordinates in which exactly one of its three vertices differs from the other two. Over an alphabet of size at least three, a coordinate may instead contain three distinct symbols. This second local configuration creates triangles at every distance and, for , couples the problem to affine lines, cap sets, and zero-sum Ramsey colorings. It is precisely here that the ternary theory separates from its binary precursor.
To highlight the distinction, suppose that are pairwise at distance . Let count the active coordinates at which , respectively, are the unique exceptional symbols, and let count the coordinates at which all three symbols are different. Comparing the three pairwise distances gives
This gives rise to the possible local types, indexed by , with active support of size . For only the type is available; for every type whose support size satisfies is realizable. This classification organizes both the general estimates and the constructions below.
Our first result is a universal upper bound for the -ary case.
Proposition 1.2 (Binary-subcube bound). For every fixed and every ,
At distance two, this upper bound is sharp for every fixed alphabet. At distance one, we have an exact formula. These give extensions of the work of Mukkamala and Ravi [16 Lemmas 4 and 5].
Theorem 1.3 (Distances one and two). For every fixed ,
The lower-bound construction for is an independent set in .
At Combinatorics 2026, A. Ravi asked whether
holds for every fixed and . Theorem 1.3 confirms this at distances one and two, whereas Theorem 1.5 disproves it already for . The fixed even-distance question remains open in general and motivates Conjecture 1.7.
At distance three we use two different constructions. For an arbitrary fixed alphabet, we construct coordinate weights avoiding all three-term relations with nonzero coefficients in . Their weighted sum gives a proper coloring of and hence a large independent set. For the ternary alphabet, a quadratic construction based on zero-sum Ramsey labelings yields substantially larger triangle-free sets.
Theorem 1.4 (Avoiding distance 3). For every fixed integer ,
In particular,
All logarithms without an indicated base are natural. During the preparation of this manuscript, we became aware of Yekhanin’s recent work [20], which gives a general construction of large codes for every fixed minimum Hamming distance at least four. The numerical bound in Theorem 1.4 can be derived from his distance-four case. Our construction using relation-avoiding weights was obtained independently, before the appearance of his preprint. We present it here in the exact-distance graph setting, where it provides a comparison with the larger triangle-free sets obtained by our ternary Ramsey construction.
Theorem 1.4 deliberately forbids every distance-three edge. For the ternary alphabet, we can obtain a substantially stronger bound by forbidding triangles only. The reason is that the type is an affine line
whereas the type can be separated by a linear statistic. A quadratic statistic built from a zero-sum-free labeling of the edges of a complete graph then eliminates the remaining affine-line triangles.
To state the result, let us recall that a cap set in is a vertex set which does not contain 3 collinear points. Let be the maximum size of a cap in and put
The limit exists because Cartesian products of caps give .
Theorem 1.5 (Ternary case, distance ). As ,
Along an infinite sequence of dimensions,
For , this improves the lower bound supplied by Theorem 1.4 to a density of order . The improvement comes from controlling triangles directly, while allowing edges within each class.
In the opposite direction, Proposition 2.6 gives an explicit constant-density upper bound for every fixed . In particular, we prove that
Whether this density tends to zero remains open.
For every prime power , the extended BCH construction in Proposition 3.1 gives
At and , it matches Proposition 1.2 and yields the following exact order.
Theorem 1.6 (Ternary case, distance ).
Theorems 1.3 and 1.6 suggest that the binary-subcube upper bound may give the correct power of at every fixed even distance. The general sparse hypergraph bound in Theorem 2.5 gives for . The BCH construction improves the polynomial exponent in some cases, but the even-distance upper bound is not matched in general.
Conjecture 1.7 (Fixed even distances). For every fixed and ,
The central open case is nevertheless the odd-distance ternary problem. Even for , there is no vanishing-density upper bound matching Theorem 1.5. For odd , the local classification introduces several exceptional-coordinate types simultaneously, and neither binary restriction nor a single quadratic statistic controls them all. Understanding how to combine higher-order algebraic labels with these local types appears to be the main structural obstacle.
The paper is organized as follows. § 2 establishes the local classification, the averaging principles, the sparse hypergraph lower bound, and the counting upper bound at distance three. § 3 settles distances one and two and presents the prime-power BCH construction, with ternary distance four as a corollary. § 4 gives the distance-three construction using relation-avoiding weights, and § 5 develops the ternary Ramsey construction. Finally, § 6 discusses the remaining questions and the converse connection to multicolor Ramsey upper bounds.
Preliminaries
Local structure and averaging
We first make precise the coordinatewise description used throughout the paper.
Definition 2.1. We call a coordinate active for a triple of vectors if its three entries are not all equal.
Proposition 2.2 (Local type classification). Suppose that satisfy
At each active coordinate, either exactly one of is exceptional and the other two agree, or all three symbols are distinct. If count the three exceptional-coordinate types and counts the all-distinct coordinates, then
In particular, , , and the active support has size .
Proof. Every active coordinate contributes to exactly two of the three pairwise distances if one symbol is exceptional, and to all three distances if the symbols are pairwise distinct. Consequently
Subtracting these equations gives , after which . The support calculation is .
In the binary cube an all-distinct coordinate is impossible, so Proposition 2.2 forces and . This recovers the familiar parity obstruction to binary equilateral triangles. If , every admissible pair satisfying is realizable.
We next give the two averaging arguments used to transfer bounds. Although elementary, they are especially useful because they preserve density exactly.
Lemma 2.3 (Coordinate-face averaging). If , then
Proof. Let be triangle-free. Choose coordinates to remain free and assign symbols independently and uniformly to the other coordinates. The resulting face is an isometric copy of , and each element of belongs to it with probability . Hence the expected size of the intersection is . Every such intersection is triangle-free in , so .
Lemma 2.4 (Alphabet restriction). If , then
Proof. In each coordinate choose a uniformly random -element subset of the -symbol alphabet, independently of the other coordinates. Their product is an isometric copy of . A fixed word lies in this copy with probability . Thus, for every triangle-free , the expected size of its intersection with the random copy is . Every intersection has size at most , proving the result.
Restriction-and-averaging arguments of this kind also occur in the literature on perfect hashing and trifferent codes. Bhandari and Khetan average translates of a code against fixed symbol-weight layers, and note the corresponding formulation for an arbitrary test set [4 Lemma 1.3 and Remark 1.4]. Bishnoi, Kielak, Kovács, Nagy, Somlai, Vizer, and Zheng use the resulting translate-density inequality together with coordinate-deletion recurrences in their generalized trifference problem [5 Proposition 1.3 and Lemma 2.5]. These are close variants of the same principle: a global extremal density is compared with the extremal density on a structured family of restrictions.
Taking and applying (1) proves Proposition 1.2.
A general lower bound from sparse hypergraph coloring
The local classification gives degree and codegree estimates for . Applying the sparse hypergraph coloring theorem of Cooper and Mubayi [10] then improves the elementary alteration bound by a factor of .
Theorem 2.5 (Sparse hypergraph bound). For fixed and fixed ,
For and fixed even , the same argument gives
Proof. Fix and a local type , and put . To construct an ordered pair of this type, choose disjoint coordinate sets of sizes for the three exceptional types and the all-distinct type. There are choices at each exceptional coordinate and choices at each all-distinct coordinate. Thus the number of ordered pairs is
where . Let and put . For fixed and , summing (3) over and dividing by two gives
The maximum pair codegree is the largest number of hyperedges containing a fixed pair of distinct vertices. A pair not at distance has codegree zero. Fix with , and let , so . For a common distance- neighbour , let count the coordinates outside at which differs from the common value of . Within , let count, respectively, the coordinates where , where , and where differs from both. The distance equations are
Hence and , so the codegree of is
The 3-uniform case of the theorem of Cooper and Mubayi [10] states that a hypergraph of maximum degree and maximum pair codegree at most has chromatic number for sufficiently large . Here , so we may take for all sufficiently large . Since $r-h>0,
Each color class is independent in and thus induces a triangle-free subgraph of . A largest class has size at least , proving the first assertion.
When and is even, only the type , survives. Then , and a distance- pair has codegree
Taking proves the binary assertion, which remains weaker than the sharp bound (1).
For comparison, elementary alteration uses only the vertex-degree estimate. With , selecting vertices with probability gives expected selected vertices and expected selected triangles. For sufficiently small , deleting one vertex from each surviving triangle gives vertices. The codegree estimate supplies the additional factor . For odd , the polynomial exponent is ; for it is .
An upper bound at distance three
Proposition 2.6. For every fixed integer ,
For the ternary alphabet, the following explicit bound holds:
Proof. Let be nonempty and triangle-free in , and let count its unordered pairs at distance . For , the graph contains both the -clique and the -clique , embedded into three alphabet symbols. Averaging isometric copies of the larger clique through any gives
Indeed, each copy contains at most one further point of , and the isometries fixing act transitively on its distance-three neighbours.
For each coordinate line , obtained by fixing all but one coordinate, let count the points of on , and let count those at distance one from . There are such lines, and
Counting pairs according to their distance gives
In particular, two points at distance three have exactly six coordinate lines at distance one from both: choose one of their three differing coordinates as the line direction, then one of two assignments on the remaining differing coordinates.
Expanding the square below cancels the term and gives the coefficient for . Thus, for sufficiently large , (5) yields
On the other hand, Cauchy–Schwarz and the first-moment identities give
Combining this with (6) proves the general bound. For , the same calculation gives an explicit bound. Indeed, the exact moment identities yield
For , the coefficient of is nonpositive, while (5) gives
Consequently, Cauchy–Schwarz and the first-moment identities give
Dividing proves the explicit ternary bound.
The clique input above is optimal: the classification of equidistant distance-three codes by Bogdanova and Katona [6 Theorem 2.4] implies
Our proof uses only the explicit cliques, but their maximality shows that the clique-averaging estimate (5) cannot be strengthened by choosing a larger clique.
Small distances and BCH constructions
The cases and
We start by proving Theorem 1.3. At unit distance, the answer comes from the geometry of coordinate lines.
Proof of Theorem 1.3 for . Fix a coordinate and all entries outside that coordinate. The resulting coordinate line is a copy of in , and a triangle-free set contains at most two of its points. The parallel coordinate lines partition the cube, so .
For the reverse inequality, identify the alphabet with and take
Every coordinate line meets in exactly two points. Hence is triangle-free and .
At distance two we use a checksum whose coefficients avoid all bounded two-term relations. The construction works over any alphabet and produces an independent set.
Proof of Theorem 1.3 for . Let . Choose a prime , with the implicit constant sufficiently large. On , join distinct whenever
for some .
This graph has maximum degree , because belongs to the fixed set . It therefore has an independent set of order ; our choice of the implicit constant allows us to select distinct elements from it.
Label the alphabet by and color by
If equally colored words differed in exactly two coordinates , then for some , contrary to the choice of the weights. Thus every color class is independent in . There are classes, so the largest has size . The matching upper bound follows from Proposition 1.2 with .
Extended BCH constructions over prime-power alphabets
The following construction uses the standard parity-check equations for extended Bose–Chaudhuri–Hocquenghem (BCH) codes, see also [21] for the fixed-distance coding context. We include the argument to record its consequences for triangle-free induced subgraphs at every fixed distance over a prime-power alphabet. A Vandermonde system excludes differences of small weight, while the Frobenius identity reduces the number of moments that must be recorded.
Proposition 3.1 (Prime-power BCH construction). Let be a prime power and let be integers. Put
There is a proper coloring of with fewer than colors whose nonempty color classes have minimum Hamming distance at least . Consequently,
Proof. Let be the smallest power of at least , and set . Thus . Choose distinct elements , and put
Then
Identify the alphabet with . For , write
and color by
Suppose distinct vertices have the same color, and put . Since , the Frobenius identity gives for every . Every positive integer at most is for some , so equality of colors implies
If and , the first equations are
with all coefficients equal to one in the equation for . Their Vandermonde determinant is , forcing , a contradiction. Every nonempty fiber therefore has minimum distance at least .
There are at most colors. The map is -linear, so its nonempty fibers have equal size, at least . Its first coordinate is surjective, so there are at least nonempty fibers. The union of two distinct fibers induces a bipartite graph and has size at least
which proves (7). ∎
If is a power of , taking improves the constant to . At ternary distance four the construction matches the binary-subcube upper bound, proving Theorem 1.6.
Corollary 3.2 (Ternary distance four). As ,
Proof. Taking and in Proposition 3.1 gives for . The matching upper bound follows from Proposition 1.2.
Excluding a fixed clique
The averaging and coloring arguments also apply when a larger fixed clique is forbidden.
Corollary 3.3. For every fixed , , and integer ,
For every fixed and ,
More generally, for every fixed prime power and fixed ,
Proof. Let induce a -free subgraph of . Intersecting with a uniformly random coordinatewise binary subcube and taking expectations gives
The upper bound follows from (1). For the lower bounds, the union of at most classes of a proper coloring is -free. The distance-two checksum uses colors, and Proposition 3.1 uses colors. Taking their largest classes proves the lower bounds. For and , the latter exponent is two, matching the upper bound.
Distance , -ary construction
We prove Theorem 1.4 by constructing coordinate weights with no bounded-coefficient relation involving three distinct indices. The main ingredient is the limited-ratio-free set construction of Erdős, Frankl, and Rödl [12], in the formulation of Theorem 2.5 of [14]; Alon and Shapira [1] developed a more general framework for avoiding systems of linear equations. A translation eliminates relations whose coefficients have nonzero sum, and a suitable modulus preserves the resulting avoidance property. The weighted coordinate sum then gives a proper coloring of .
Theorem 4.1 (Alon–Shapira, limited-ratio form). For every fixed positive integer , there is a constant such that for every there is a set satisfying
and containing no three distinct elements for which
Lemma 4.2 (Coefficient-avoiding weights). Let . For every fixed there is a constant with the following property. For every one can find an integer
and distinct residues such that
whenever are distinct and .
Proof. Apply Theorem 4.1 with . Increasing the implicit constant if necessary, choose
so that the theorem supplies a limited-ratio-free set of size at least . Indeed, taking
suffices for all large , and the remaining values may be absorbed into the constant.
Set
We claim that distinct satisfy no integer relation
Write , , and . If , then after permuting the variables and multiplying by if necessary, (8) has the form
The translation by cancels and produces a forbidden relation among . If instead , then
which again rules out (8).
Choose distinct elements of , represented by positive integers, and take . Every relevant three-term sum has absolute value less than ; congruence to zero modulo would therefore imply equality over the integers. The chosen residues have the desired property, and after adjusting . □
Proof of Theorem 1.4. Take from Lemma 4.2 and define
If and differ in exactly the three coordinates and have the same color, then
The three coefficients belong to , contradicting Lemma 4.2. Hence is a proper coloring of . At least one of its at most color classes has size at least
and this class is independent.
The proof gives a proper coloring of , so every color class is independent. In the next section we exploit the greater freedom of requiring the color classes to induce triangle-free subgraphs, using algebraic features specific to the ternary alphabet.
The ternary distance-three problem and Ramsey theory
We now exploit features special to . Proposition 2.2 leaves two types at distance three. For and , the triangle is an affine line
The second type has . A linear statistic will eliminate the mixed type, while a quadratic statistic will handle the affine lines. Recall the cap-size function and the constants and from (2). Cartesian products give , so Fekete’s lemma yields and
In characteristic three, the cap condition is equivalent to
Indeed, if two of agree then all three agree; otherwise the three points are distinct and form an affine line.
The edge-labeling parameter below is an additive analogue of a multicolor Ramsey problem, tailored to the quadratic Hamming lift.
Definition 5.1 (Zero-sum triangle Ramsey number). For an elementary abelian 3-group , let be the largest integer for which the edges of the complete graph can be labeled by elements so that
for every triple of distinct vertices .
We next derive the required estimate for . This is the key quantitative ingredient in the distance-three lower bound. The argument first packs the group with disjoint cap palettes and then amplifies an ordinary multicolor Ramsey coloring lexicographically.
Lemma 5.2 (Palette amplification). Let be an elementary abelian 3-group containing pairwise disjoint caps
If the edges of admit an -coloring with no monochromatic triangles, then
Proof. Fix such a coloring and bijections . Use as the vertex set of a complete graph. For distinct , let be the first coordinate at which they differ and label the edge by
Consider three distinct words , and let be the first coordinate at which they are not all equal. If are pairwise distinct, then all three edge labels belong to . They are not all equal, since has no monochromatic triangle. By (10), their sum therefore cannot be zero.
Suppose instead that exactly two entries agree, say . The edges and receive the same label , whereas the edge is decided at a later coordinate and receives a label . The palettes are disjoint, so ; hence, in characteristic three,
Thus no triangle has label sum zero, proving that .
It remains to produce sufficiently many disjoint caps. Partitioning into caps is equivalent to properly coloring the affine Steiner triple system . The following elementary translate-covering argument is a special case of the general relationship between fractional and integral covers. We include the proof to keep the subsequent construction self-contained.
Lemma 5.3 (Partition into caps). Let be a cap, put , and write . Then can be partitioned into at most
caps.
Proof. Choose independent uniformly random translates of , with equal to the right-hand side of (13). A fixed element of is missed by all the translates with probability
Consequently the expected number of uncovered elements is at most
Some collection of translates therefore covers . Order these translates and assign every element to the first translate containing it. The resulting nonempty parts are pairwise disjoint subsets of translates of , hence are caps, and they partition .
Lemma 5.4 (Equal cap palettes). Fix . For and
there are
pairwise disjoint caps of size , as .
Proof. Choose with . From the definition of and we have
so, for all sufficiently large , contains a cap of size at least . Lemma 5.3 partitions into
caps. Split every part into sets of size , discarding the remainder of each part. Fewer than elements are discarded, and
The remaining elements therefore form the asserted family of disjoint -element caps. □
Let be the least such that every -coloring of contains a monochromatic triangle. We use the following superexponential lower bound from [17 Chapter 9], announced recently by OpenAI.
Theorem 5.5 (Superexponential multicolor Ramsey bound). There is an absolute constant such that, for every integer ,
Consequently, as , there is an -coloring of some with no monochromatic triangle and
This result enables us to prove the zero-sum Ramsey estimate that drives the ternary distance-three construction.
Theorem 5.6 (Zero-sum Ramsey amplification). Let . Then
Proof. Fix and put . By Lemma 5.4, the group contains
pairwise disjoint caps of size . By Theorem 5.5, there is an -coloring of with no monochromatic triangle and
Lemma 5.2 gives , and hence
Thus . Since is arbitrary, (17) follows. □
Corollary 5.7. As , . More precisely, writing , we have .
Proof. The lower bound is Theorem 5.6. A labeling by can be regarded as an edge-coloring with colors. Every monochromatic triangle has label sum zero, so . The classical factorial upper bound gives the required upper estimate.
Theorem 5.8 (Zero-sum Ramsey input). Let and be defined by (2). For every sufficiently large there is an elementary abelian 3-group with and
Along an infinite sequence of values of , one may replace by .
Proof. Fix . Theorem 5.6 implies that for every sufficiently large power ,
Given a sufficiently large , choose the least power of three for which
Then (18) supplies the required labeling in . By the minimality of , the preceding power satisfies
and therefore
Together with , this shows that
Substitution in (19) yields
Letting tend to proves the first assertion. For the subsequence assertion, let tend to infinity. From (17) we may choose integers satisfying
It follows that
which proves the sharper estimate along the infinite sequence .
The available numerical value of is governed by a succession of explicit constructions. Edel’s generalized product caps yielded the longstanding bound [11]. Tyrrell obtained the first improvement in nearly two decades, reaching [19]; the program-search construction of Romera-Paredes et al. subsequently reached [18]. The construction of Zhai et al. [22] gives the explicit lower bound
Consequently the two constants in Theorem 1.5 may presently be taken to be at least
respectively.
The constants in Theorem 1.5 now follow from an explicit coloring. We include the reduction because it exposes the role of the two local types.
Proof of Theorem 1.5. Choose and a labeling satisfying (11). For define
and color by . This gives at most color classes.
Suppose first that form a triangle of type . Adding the same field element to all three entries in any coordinate shifts their -values equally, so it preserves whether these values coincide. We may therefore normalize every inactive coordinate to zero and the repeated symbol in each exceptional coordinate to zero. The three exceptional coordinates then contribute , , and , respectively, with . At the unique all-distinct coordinate, the entries form a permutation of . Hence
If these three values were equal to , then , , and . Since one of equals , one of would be zero, a contradiction. Thus a mixed triangle is not monochromatic.
It remains to consider a type- triangle. Write it as , with supported on three coordinates . If the three vertices have the same -value, then . Since the three nonzero entries of lie in , they must all be equal. The quadratic second difference is then
where the last equality is in characteristic three. This is nonzero by (11). Hence the three -values cannot all agree, and the coloring is triangle-free.
Its largest class has size at least . The first estimate in Theorem 5.8 gives
and the improved estimate along the distinguished subsequence gives the constant .
The construction uses exactly the algebra demanded by the local geometry: the linear coordinate excludes the mixed type and the quadratic coordinate excludes affine lines. In contrast, the proper coloring constructed in Section 4 separates every distance-three pair and is therefore uniform in but much less dense when .
Concluding remarks
At odd distances, binary restriction supplies no nontrivial upper bound, since every binary odd-distance graph is bipartite. Over , the type- triangles are affine lines , , with . The essential difficulty is to control these together with all types . At distance three there is only one additional type, and a single linear statistic removes it. For larger odd distances, a replacement may require higher-order labels that encode several exceptional-coordinate patterns at once.
We conclude with three open questions. First, can the lower bounds of Theorem 2.5 and Proposition 3.1 be improved to match the binary-subcube upper bound at every fixed even distance, as proposed in Conjecture 1.7? Second, can the constant-density upper bound of Proposition 2.6 be replaced by a vanishing-density bound? In particular, is , improving the current estimate
Third, can the triangle-free condition be used to improve on the BCH and sparse hypergraph bounds at larger odd distances? The ternary distance-three construction suggests that controlling triangles directly can be substantially more effective than excluding every edge.
There is also a quantitative connection between the upper bounds of and the multicolor triangle Ramsey numbers defined in § 5. Suppose that is a cap of size at least . Thus , , implies . Replacing the colors of a -edge-coloring without monochromatic triangles by distinct elements of therefore produces an edge-labeling without zero-sum triangles. Consequently,
The quadratic construction gives the complementary implication
Indeed, the construction partitions the hyperplane into at most triangle-free fibers, one of which has size at least . Combining these observations yields
whenever contains a cap of size at least . Thus sufficiently strong upper bounds for the distance-three problem would imply upper bounds for classical multicolor triangle Ramsey numbers.
The rate of any decay in is therefore relevant to Ramsey theory, beyond the qualitative question of whether this density tends to zero. The implications above transfer upper bounds; a positive-density lower bound for alone would not yield a converse Ramsey estimate.
The problem of forbidding larger cliques has already been considered in this setting. Balogh, Chen, and Li [2 Question 1.2 and Theorem 1.4] determined the order of for fixed and fixed even . Mukkamala and Ravi [16 Section 4, Problem 3] explicitly posed the corresponding problem over prime-power alphabets. The constructions above settle the case and , as for . Indeed, the proof of Theorem 1.5 shows that each fiber of the linear statistic contains no triangle of mixed type. Every triangle in such a fiber is therefore an affine line. A is impossible, since its triangles through a fixed edge would have to lie on the same affine line, which contains only three points. Each fiber thus gives a -free set of size . Conversely, the cosets of the two-dimensional subspace displayed in the proof of Proposition 2.6 partition into -cliques. A -free set meets each coset in at most three points, proving the matching upper bound. In particular, for every , so the question of vanishing density at ternary distance three is specific to the triangle-free problem.
AI declaration. AI-assisted tools were used in editing and preparing the manuscript: during the workshop, the authors used ChatGPT 5.6 Sol, which assisted them in obtaining the main results of the manuscript by building on their ideas. Later, they used ChatGPT 6 Astra for proofreading. The authors reviewed the resulting text and take full responsibility for the mathematical statements, proofs, and references.
Acknowledgement. The problem studied in this paper was posed at the Excellence Workshop, held in Szigliget, Hungary, on 4–9 August 2026. The authors thank the organizers for providing the opportunity for these discussions.
References
- [1]N. Alon and A. Shapira, Linear equations, arithmetic progressions and hypergraph property testing, Theory Comput. 1 (2005), 177–216.DOI
- [2]J. Balogh, C. Chen, and B. Li, Forbidding exactly one Hamming distance, arXiv:2604.05607, 2026.arxiv.org/abs/2604.05607
- [3]L. A. Bassalygo, G. D. Cohen, and G. Zémor, Codes with forbidden distances, Discrete Math. 213 (2000), 3–11. doi:10.1016/S0012-365X(99)00161-2.DOI
- [4]S. Bhandari and A. Khetan, Improved upper bound for the size of a trifferent code, Combinatorica 45 (2025), article no. 2, 14 pp. doi:10.1007/s00493-024-00130-2.DOI
- [5]A. Bishnoi, B. Kielak, B. Kovács, Z. L. Nagy, G. Somlai, M. Vizer, and Z. Zheng, The generalized trifference problem, IEEE Trans. Inform. Theory 72 (2026), no. 5, 2907–2914. doi:10.1109/TIT.2026.3665439.DOI
- [6]G. Bogdanova and G. O. H. Katona, All q-ary equidistant 3-codes, J. Combin. Inform. System Sci. 34 (2009), 161–167.
- [7]B. Brešar, N. Gastineau, S. Klavžar, and O. Togni, Exact distance graphs of product graphs, Graphs Combin. 35 (2019), 1555–1569. doi:10.1007/s00373-019-02089-0.DOI
- [8]D. Castro-Silva, F. M. de Oliveira Filho, L. Slot, and F. Vallentin, A recursive theta body for hypergraphs, Combinatorica 43 (2023), 909–938.
- [9]G. Cohen and G. Zémor, Subset sums and coding theory, Astérisque 258 (1999), 327–339. doi:10.24033/ast.458.
- [10]J. Cooper and D. Mubayi, Coloring sparse hypergraphs, SIAM J. Discrete Math. 30 (2016), no. 2, 1165–1180. doi:10.1137/140995805.DOI
- [11]Y. Edel, Extensions of generalized product caps, Des. Codes Cryptogr. 31 (2004), 5–14. doi:10.1023/A:1027365901231.DOI
- [12]P. Erdős, P. Frankl, and V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin. 2 (1986), 113–121.DOI
- [13]J. R. Johnson and J. Talbot, Vertex Turán problems in the hypercube, J. Combin. Theory Ser. A 117 (2010), no. 4, 454–465. doi:10.1016/j.jcta.2009.07.009.
- [14]B. Kovács and Z. L. Nagy, Multicolor Turán numbers II: a generalization of the Ruzsa–Szemerédi theorem and new results on cliques and odd cycles, J. Graph Theory 107 (2024), 629–641.
- [15]X.-C. Li and R.-X. Hao, The vertex Turán density in 3-ary n-cubes, Discrete Appl. Math. 311 (2022), 129–141. doi:10.1016/j.dam.2022.01.015.DOI
- [16]P. Mukkamala and A. Ravi, Triangle-free subsets of the r-distance graph of the hypercube, arXiv:2506.18782v4, 2026.arxiv.org/abs/2506.18782
- [17]OpenAI, Ten Advances in Mathematics and Theoretical Computer Science, Chapter 9, “Super-exponential lower bounds for R(3,…,3),” pp. 229–235, updated 6 August 2026. Available at https://cdn.openai.com/pdf/ten-proofs-oai.pdf.DOI
- [18]B. Romera-Paredes, M. Barekatain, A. Novikov, M. Balog, M. P. Kumar, E. Dupont, F. J. R. Ruiz, J. S. Ellenberg, P. Wang, O. Fawzi, P. Kohli, and A. Fawzi, Mathematical discoveries from program search with large language models, Nature 625 (2024), 468–475. doi:10.1038/s41586-023-06924-6.
- [19]F. Tyrrell, New lower bounds for cap sets, Discrete Anal. (2023), Paper No. 20, 18 pp. doi:10.19086/da.91076.DOI
- [20]S. Yekhanin, Nonlinear fixed-distance codes via real lifts of moment configurations, arXiv:2610.19960, 2026. https://arxiv.org/abs/2610.19960.
- [21]S. Yekhanin and I. Dumer, Long nonbinary codes exceeding the Gilbert–Varshamov bound for any fixed distance, IEEE Trans. Inform. Theory 50 (2004), no. 10, 2357–2362. doi:10.1109/TIT.2004.834744.DOI
- [22]Y. Zhai, Z. Wei, R. Li, K. Pan, S. Liu, L. Zhang, J. Ji, W. Zhang, Yu Zhang, and Yanyong Zhang, X-evolve: Solution space evolution powered by large language models, arXiv:2508.07932, 2025.arxiv.org/abs/2508.07932