String Quartets in Binary

Noga Alon, János Körner, Angelo Monti

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

Let M(n, A) denote the maximum possible cardinality of a family of binary strings of length n, such that for every four distinct members of the family there is a coordinate in which exactly two of them have a 1. We prove that M(n,A) ≤ 20.78n for all sufficiently large n. Let M(n, C) denote the maximum possible cardinality of a family of binary strings of length n, such that for every four distinct members of the family there is a coordinate in which exactly one of them has a 1. We show that there is an absolute constant c < 1/2 such that M(n, C) ≤ 2cn for all sufficiently large n. Some related questions are discussed as well.

Original languageEnglish (US)
Pages (from-to)381-390
Number of pages10
JournalCombinatorics Probability and Computing
Volume9
Issue number5
DOIs
StatePublished - Jan 1 2000
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'String Quartets in Binary'. Together they form a unique fingerprint.

  • Cite this