Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-10T05:22:22.521Z Has data issue: false hasContentIssue false

2-Bases of Quadruples

Published online by Cambridge University Press:  03 January 2006

ZOLTÁN FÜREDI
Affiliation:
Rényi Institute of Mathematics of the Hungarian Academy of Sciences, Budapest, PO Box 127, Hungary-1364 and Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL61801, USA (e-mail: furedi@renyi.hu, z-furedi@math.uiuc.edu)
GYULA O. H. KATONA
Affiliation:
Rényi Institute of Mathematics of the Hungarian Academy of Sciences, Budapest, PO Box 127, Hungary-1364 (e-mail: ohkatona@renyi.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.

Let $\cal{B}(n, \leq 4)$ denote the subsets of $[n]:=\{ 1, 2, \dots, n\}$ of at most 4 elements. Suppose that $\cal{F}$ is a set system with the property that every member of $\cal{B}$ can be written as a union of (at most) two members of $\cal{F}$. (Such an $\cal{F}$ is called a 2-base of $\cal{B}$.) Here we answer a question of Erdős proving that \[|\FF|\geq 1+n+\binom{n}{2}- \Bigl\lfloor \frac{4}{3}n\Bigr\rfloor\], and this bound is best possible for $n\geq 8$.

Information

Type
Paper
Copyright
2006 Cambridge University Press