AN ERDŐS–KO–RADO THEOREM FOR BINARY CODES

Abstract We study intersecting families of words from the Erdős–Ko–Rado perspective. When the alphabet size is <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content" display="inline"> <mml:mn>2</mml:mn> </mml:math> $2$ 2 , a maximum intersecting family is not necessarily a star. However, we prove that every maximum <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content" display="inline"> <mml:mn>3</mml:mn> </mml:math> $3$ 3 -wise intersecting family is a star. We also present a new proof of the known result for alphabets of size at least <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content" display="inline"> <mml:mn>3</mml:mn> </mml:math> $3$ 3 : maximum intersecting families of words are exactly the stars.