Number of acquaintances
Source: 2002 Austrian-Polish, problem 9
September 23, 2006
combinatoricsgraph theory
Problem Statement
A set of persons is given. The family of subsets of containing exactly persons has the property that the number of acquaintance pairs in each such subset is the same. (It is assumed that the acquaintance relation is symmetric). Find the best lower estimation of the acquaintance pairs in the set .