# zbMATH — the first resource for mathematics

A property of random graphs. (English) Zbl 0572.05036
A graph is said to have property $$P(n)$$ if for any two disjoint vertex sets $$A$$ and $$B$$ with $$|A\cup B| =k$$ there is another vertex which is joined to every vertex in $$A$$ and no vertex in $$B$$. Let $$f(n)$$ be the largest integer such that there is a graph of order $$n$$ having property $$P(f(n))$$. Probabilistic methods are used to prove bounds on $$f(n)$$.
Reviewer: O.Frank

##### MSC:
 05C35 Extremal problems in graph theory 60C05 Combinatorial probability 05C80 Random graphs (graph-theoretic aspects)
##### Keywords:
extremal graphs; Probabilistic methods