CJO - Abstract - 2-Bases of Quadruples

Cambridge Journals Online

Cambridge Journals Online
Skip to content
Combinatorics, Probability and Computing (2006), 15 : 131-141 Cambridge University Press
Copyright © 2006 Cambridge University Press
doi:10.1017/S0963548305007248 (About doi)
Published online by Cambridge University Press 03 Jan 2006
 
Combinatorics, Probability and Computing (2006), 15:131-141 Cambridge University Press
Copyright © 2006 Cambridge University Press
doi:10.1017/S0963548305007248

Paper

2-Bases of Quadruples

ZOLTÁN FÜREDI a1 1 and GYULA O. H. KATONA a2 2
a1 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)
a2 Rényi Institute of Mathematics of the Hungarian Academy of Sciences, Budapest, PO Box 127, Hungary-1364 (e-mail: ohkatona@renyi.hu)

Article author query
furedi z   [Google Scholar] 
katona go   [Google Scholar] 
 

Abstract

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 Erdos 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$.

(Received October 18 2004)
(Revised July 6 2005)


Dedication:
For Béla Bollobás on his 60th birthday

Footnotes

1 Research supported in part by Hungarian National Science Foundation grant OTKA T 032452, T 037846 and by National Science Foundation grant DMS 0140692.

2 Research supported by Hungarian National Science Foundation grants OTKA T 037846, T 038210, T 034702.


back to top
Cambridge University Press