Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-02-06T04:43:14.069Z Has data issue: false hasContentIssue false
  • English
  • Français

String Quartets in Binary

Published online by Cambridge University Press:  14 February 2001

NOGA ALON ,
JÁNOS KÖRNER  and
ANGELO MONTI
NOGA ALON
Affiliation:
Department of Mathematics, Tel Aviv University, Ramat Aviv, Tel Aviv 69978, Israel (e-mail: noga@math.tau.ac.il)
JÁNOS KÖRNER
Affiliation:
Department of Computer Science, University of Rome I ‘La Sapienza’, Via Salaria 113, 00198 Roma, Italy (e-mail: korner@dsi.uniroma1.it, monti@dsi.uniroma1.it)
ANGELO MONTI
Affiliation:
Department of Computer Science, University of Rome I ‘La Sapienza’, Via Salaria 113, 00198 Roma, Italy (e-mail: korner@dsi.uniroma1.it, monti@dsi.uniroma1.it)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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) [les ] 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) [les ] 2cn for all sufficiently large n. Some related questions are discussed as well.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 9 , Issue 5 , September 2000 , pp. 381 - 390
Copyright
2000 Cambridge University Press