## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  408.04002
Autor:  Erdös, Paul; Rothschild, B.L.; Singhi, N.M.
Title:  Characterizing cliques in hypergraphs. (In English)
Source:  Ars Comb. 4, 81-118 (1977).
Review:  The paper studies the set-theoretic analogue of a result of MacWilliams on affine spaces, with generalisations. Let \binom Xr denote the collection of all r-element subsets of X. A subset E of \binom Xr is an r-uniform hypergraph, and a subset of the form \binom Yr for some Y\subset X is a clique. If |X| = n, |E| = 1, the authors examine the question: for which n,l,r,j is it true that cliques are characterised by the property that, for any j-set S, |E\cap\binom Sr| = \binom hr for some h (o \leq h \leq n)? This holds if n is sufficiently large (depending on l, r and j); the authors find sharp bounds and characterise extremal cases. Stronger results are obtained for graphs (r = 2).
Reviewer:  P.J.Cameron
Classif.:  * 04A20 Combinatorial set theory
05C65 Hypergraphs
05A05 Combinatorial choice problems
05C35 Extremal problems (graph theory)
Keywords:  combinatorial set theory; uniform hypergraph; subset; clique

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag