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