Extremal set systems with weakly restricted intersections

Authors
Citation
Vh. Vu, Extremal set systems with weakly restricted intersections, COMBINATORI, 19(4), 1999, pp. 567-587
Citations number
15
Categorie Soggetti
Mathematics,"Computer Science & Engineering
Journal title
COMBINATORICA
ISSN journal
02099683 → ACNP
Volume
19
Issue
4
Year of publication
1999
Pages
567 - 587
Database
ISI
SICI code
0209-9683(1999)19:4<567:ESSWWR>2.0.ZU;2-8
Abstract
Problems concerning extremal set systems with intersections of restricted c ardinality are probably among the most popular problems in extremal combina torics, leading to many surprising discoveries and exciting questions. In t his paper, we discuss the "weak" versions of some problems of this type, wh ere the restricted intersection property is weakened by the possible existe nce of some (or maybe many) intersections having "exceptional" sizes. In pa rticular, we prove a tight upper bound for a weak version of the "odd town" problem. We also give a tight bound for a weak version of the nonuniform F isher inequality and see how the proof of this bound leads to an extremal s et theoretic characterization of Hadamard's matrices. Finally, we display a tight bound for a weak version of the "even town" problem, and use this bo und to tackle problems concerning systems with restricted multi-intersect i ons.