pith. sign in

arxiv: 2604.13475 · v1 · submitted 2026-04-15 · 🧮 math.CO

An ErdH{o}s-Ko-Rado theorem for binary codes

Shamil Asgarli , Chi Hoi Yip This is my paper

Pith reviewed 2026-05-10 13:35 UTC · model grok-4.3

classification 🧮 math.CO
keywords Erdős-Ko-Rado theoremintersecting familiesbinary codes3-wise intersectingstarswords
0
0 comments X

The pith

Every maximum 3-wise intersecting family of binary words is a star.

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

The paper proves a version of the Erdős-Ko-Rado theorem for intersecting families of words over small alphabets. For binary alphabets, although the largest intersecting families are not always stars, the largest families where any three words intersect must be stars. It also gives a new proof that for alphabets of size three or more, the largest intersecting families are exactly the stars. This matters because it identifies when the extremal examples in coding theory are the simple ones based on a fixed coordinate.

Core claim

We prove that every maximum 3-wise intersecting family is a star. We also present a new proof of the known result for alphabets of size at least 3: maximum intersecting families of words are exactly the stars.

What carries the argument

The star, consisting of all words that equal 1 in one fixed coordinate position.

If this is right

  • For sufficiently large word length, the maximum size of a 3-wise intersecting family in binary words equals the size of a star and is achieved only by stars.
  • For alphabets of size at least 3, maximum intersecting families of words coincide exactly with the stars.
  • The results extend the classical Erdős-Ko-Rado theorem to the setting of words over small alphabets.

Where Pith is reading between the lines

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

  • The proof techniques might apply to t-wise intersecting families for t greater than 3 in binary cases.
  • Similar results could hold for other notions of intersection such as in constant weight codes.
  • This distinction between 2-wise and 3-wise for binary suggests that the threshold for forcing stars depends on the intersection multiplicity.

Load-bearing premise

The word length n is sufficiently large.

What would settle it

A counterexample would be a 3-wise intersecting family of binary words with size equal to that of the largest star but not equal to any star.

read the original abstract

We study intersecting families of words from the Erd\H{o}s-Ko-Rado perspective. When the alphabet size is $2$, a maximum intersecting family is not necessarily a star. However, we prove that every maximum $3$-wise intersecting family is a star. We also present a new proof of the known result for alphabets of size at least $3$: maximum intersecting families of words are exactly the stars.

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.

Referee Report

2 major / 2 minor

Summary. The paper studies intersecting families of words from the Erdős-Ko-Rado perspective. For binary alphabets it proves that every maximum 3-wise intersecting family is a star (in contrast to the 2-wise case, where maximum intersecting families need not be stars). It also gives a new proof of the known result that, for alphabets of size at least 3, the maximum intersecting families are exactly the stars.

Significance. If the proofs hold, the work supplies a clean distinction between 2-wise and 3-wise intersecting families in the binary setting and supplies a new proof for the q≥3 case. The characterization that maximum 3-wise families are stars is a strong, falsifiable statement. The paper states its theorems precisely and distinguishes the intersecting and 3-wise intersecting cases logically.

major comments (2)
  1. [Abstract and Theorem statements] Abstract and main theorem statements: the results are asserted for sufficiently large n, but no explicit lower bound on n (or separate small-n case analysis) is supplied. Because the binary 2-wise case already admits non-star examples for small n, the precise range is load-bearing for the claim that every maximum 3-wise intersecting family is a star; the proof must either state the sharp threshold or verify the small-n regime directly.
  2. [Proof of the binary 3-wise result] Proof of the 3-wise binary case: the argument that a maximum 3-wise intersecting family must be a star relies on an implicit assumption that n exceeds some function of the intersection parameter 3. If this assumption is violated for any n covered by the theorem statement, the characterization fails; the manuscript should isolate the minimal n for which the argument applies.
minor comments (2)
  1. [Throughout] Notation: the terms 'words', 'codes', and 'binary codes' are used interchangeably; adopt a single consistent term after the introduction.
  2. [Introduction] References: ensure that all prior EKR results for words over alphabets of size q≥3 are cited explicitly so the novelty of the new proof is clear.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need to clarify the range of n in our statements. We address the major comments point by point below and will incorporate the necessary revisions.

read point-by-point responses

  1. Referee: [Abstract and Theorem statements] Abstract and main theorem statements: the results are asserted for sufficiently large n, but no explicit lower bound on n (or separate small-n case analysis) is supplied. Because the binary 2-wise case already admits non-star examples for small n, the precise range is load-bearing for the claim that every maximum 3-wise intersecting family is a star; the proof must either state the sharp threshold or verify the small-n regime directly.

    Authors: We agree that an explicit range is necessary for precision, given the known counterexamples in the 2-wise binary setting for small n. The combinatorial arguments in our proof of the 3-wise binary result (primarily double counting and averaging over coordinates) require n > 3. We will revise the manuscript to state the theorem explicitly for all n, adding a short direct verification that every maximum 3-wise intersecting family is a star when n = 1, 2, 3. This makes the claim self-contained without altering the main argument. revision: yes

  2. Referee: [Proof of the binary 3-wise result] Proof of the 3-wise binary case: the argument that a maximum 3-wise intersecting family must be a star relies on an implicit assumption that n exceeds some function of the intersection parameter 3. If this assumption is violated for any n covered by the theorem statement, the characterization fails; the manuscript should isolate the minimal n for which the argument applies.

    Authors: The referee correctly identifies that the write-up does not isolate the minimal n. The key steps assume n is large enough for the averaging arguments to guarantee a coordinate with sufficient coverage (specifically n > 3). In the revision we will add a sentence at the start of the proof section stating that the argument applies for n > 3, together with the small-n verification mentioned above. This isolates the threshold without requiring a new proof. revision: yes

Circularity Check

0 steps flagged

No circularity in direct combinatorial proofs

full rationale

The paper states and proves direct characterization theorems for maximum intersecting and 3-wise intersecting families of binary words, asserting that they are stars for sufficiently large n. These are standard EKR-style existence and uniqueness results established via combinatorial arguments in the manuscript. No derivation step reduces a claimed prediction or central result to a fitted parameter, self-referential definition, or load-bearing self-citation chain; the new proof for alphabets of size at least 3 is presented independently, and the binary 3-wise case is handled directly without importing uniqueness via prior author work. The implicit large-n assumption is a standard domain restriction for such theorems and does not create a circular reduction in the derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on the standard definition of intersecting families of words and the classical EKR theorem for sets; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • standard math The definition of k-wise intersecting family of words over an alphabet of size q
    Invoked in the statement of the main theorems.

pith-pipeline@v0.9.0 · 5357 in / 1207 out tokens · 52063 ms · 2026-05-10T13:35:59.971028+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

  1. [1]

    Engel and P

    K. Engel and P. Frankl. An Erd ¨os-Ko-Rado theorem for integer sequences of given rank.European J. Combin., 7(3):215–220, 1986

    work page 1986

  2. [2]

    Erd ˝os, C

    P. Erd ˝os, C. Ko, and R. Rado. Intersection theorems for systems of finite sets.Quart. J. Math. Oxford Ser. (2), 12:313–320, 1961

    work page 1961

  3. [3]

    Frankl and Z

    P. Frankl and Z. F ¨uredi. The Erd¨os-Ko-Rado theorem for integer sequences.SIAM J. Algebraic Discrete Methods, 1(4):376–381, 1980

    work page 1980

  4. [4]

    Frankl and N

    P. Frankl and N. Tokushige. The Erd ˝os–Ko–Rado theorem for integer sequences.Combinatorica, 19(1):55–63, 1999

    work page 1999

  5. [5]

    Godsil and K

    C. Godsil and K. Meagher.Erd ˝os-Ko-Rado theorems: algebraic approaches, volume 149 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2016

    work page 2016

  6. [6]

    H.-D. O. F. Gronau. More on the Erd ¨os-Ko-Rado theorem for integer sequences.J. Combin. Theory Ser. A, 35(3):279–288, 1983

    work page 1983

  7. [7]

    D. J. Kleitman. On a combinatorial conjecture of Erd ¨os.J. Combinatorial Theory, 1:209–214, 1966

    work page 1966

  8. [8]

    M. L. Livingston. An ordered version of the Erd ¨os-Ko-Rad´o theorem.J. Combin. Theory Ser. A, 26(2):162–165, 1979

    work page 1979

  9. [9]

    A. Moon. An analogue of the Erd ˝os-Ko-Rado theorem for the hamming schemesH(n, q).J. Combin. Theory Ser. A, 32(3):386–390, 1982. DEPARTMENT OFMATHEMATICS& COMPUTERSCIENCE, SANTACLARAUNIVERSITY, SANTACLARA, CA 95053, UNITEDSTATES Email address:sasgarli@scu.edu SCHOOL OFMATHEMATICS, GEORGIAINSTITUTE OFTECHNOLOGY, ATLANTA, GA 30332, UNITEDSTATES Email addre...

    work page 1982