Hostname: page-component-74656f9884-kv2lp Total loading time: 0 Render date: 2026-11-06T06:40:14.516Z Has data issue: false hasContentIssue false

Intersecting Systems

Published online by Cambridge University Press:  01 June 1997

R. AHLSWEDE
Affiliation:
Fakultät für Mathematik, Universität Bielefeld, P.O. Box 100131, D-33501 Bielefeld 1, Germany
N. ALON
Affiliation:
Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Ramat Aviv, Tel Aviv, Israel (e-mail: noga@math.tau.ac.il)
P. L. ERDŐS
Affiliation:
Mathematical Institute of the Hungarian Academy of Sciences, Budapest, P.O. Box 127, 1364 Hungary (e-mail: elp@math-inst.hu)
M. RUSZINKÓ
Affiliation:
Computer and Automation Research Institute of the Hungarian Academy of Sciences, Budapest, P.O. Box 63, 1518 Hungary (e-mail: ruszinko@lutra.sztaki.hu)
L. A. SZÉKELY
Affiliation:
Department of Computer Science, Eötvös University, Budapest, 1088 Hungary (e-mail: szekely@cs.elte.hu)
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.

An intersecting system of type (∃, ∀, k, n) is a collection []={[Fscr]1, ...,[Fscr]m} of pairwise disjoint families of k-subsets of an n-element set satisfying the following condition. For every ordered pair [Fscr]i and [Fscr]j of distinct members of [] there exists an A∈[Fscr]i that intersects every B∈[Fscr]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−1/k−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.

Information

Type
Research Article
Copyright
1997 Cambridge University Press