##
**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