Binary Codes with a Forbidden Distance

@misc{jiang2026binary,
  title = {{Binary Codes with a Forbidden Distance}},
  author = {Jianwei Jiang and Chunhua Yang},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.04523},
  eprint = {2611.04523},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.04523},
}

TY  - UNPB
TI  - Binary Codes with a Forbidden Distance
AU  - Jianwei Jiang
AU  - Chunhua Yang
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.04523
UR  - https://arxiv.org/abs/2611.04523
AB  - The maximum size of a t-intersecting code in the set of words of length n over an alphabet of size m, a problem posed by Frankl and Füredi, was determined independently by Ahlswede and Khachatrian and by Frankl and Tokushige. Extending this result to the forbidden-intersection setting, Keevash, Lifshitz, Long and Minzer proved that, for m greater than two and n sufficiently large in terms of t, (t minus one)-avoiding codes have the same maximum size and the same extremal ball constructions as t-intersecting codes. They also raised the binary case. Here, t-intersecting requires every two distinct words to agree in at least t coordinates, while (t minus one)-avoiding forbids agreement in exactly t minus one coordinates. We solve the binary case for all t at least three and n at least the square of the sum of t and one. If the forbidden Hamming distance n minus t plus one is odd, the maximum size of a (t minus one)-avoiding code strictly exceeds the maximum t-intersecting size. If it is even, the two maxima coincide, but their extremal families differ: some maximum (t minus one)-avoiding codes are not t-intersecting. We also determine all maximum avoiding codes in the even case. For odd forbidden distances, weight parity and a fixed-point-free pairing determine the maximum, while the diameter theorem gives the comparison with t-intersecting codes. For even forbidden distances, parity splitting and coordinate deletion reduce the problem to avoiding two consecutive distances. Connected components, disjoint neighbourhoods, and Harper's vertex-isoperimetric theorem yield the upper bound, which is attained by a t-intersecting construction. The diameter theorem then determines the extremal structure, and elementary binomial estimates give the stated parameter range.
ER  -