Intersecting Systems

R. Ahlswede, N. Alon, P. L. Erdos, M. Ruszinkó, L. A. Székely

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

An intersecting system of type (∃, ∀, k, n) is a collection double-struck F sign = {ℱ1,...,ℱm} of pairwise disjoint families of k-subsets of an n-element set satisfying the following condition. For every ordered pair ℱi and ℱj of distinct members of double-struck F sign there exists an A ∈ ℱi that intersects every B ∈ ℱj. Let In(∃, ∀, k) denote the maximum possible cardinality of an intersecting system of type (∃, ∀, k, n). Ahlswede, Cai and Zhang conjectured that for every k ≥ 1, there exists an n0(k) so that In(∃, ∀, k) = (n-1k-1) for all n > n0(k). Here we show that this is true for k ≤ 3, but false for all k ≥ 8. We also prove some related results.

Original languageEnglish (US)
Pages (from-to)127-137
Number of pages11
JournalCombinatorics Probability and Computing
Volume6
Issue number2
DOIs
StatePublished - Jan 1 1997
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 'Intersecting Systems'. Together they form a unique fingerprint.

  • Cite this

    Ahlswede, R., Alon, N., Erdos, P. L., Ruszinkó, M., & Székely, L. A. (1997). Intersecting Systems. Combinatorics Probability and Computing, 6(2), 127-137. https://doi.org/10.1017/S0963548397003003