Notices

OF THE

AMERICAN

MATHEMATICAL

SOCIETY

CODEN, AMNOAN Pages 89 - 156; A289 – A424 February 1972

Volume 19, Number 2 Issue 136

Abstract (page A – 382)

* 693-A11. DAVID W. MATULA, Washington University. St. Louis, Missouri 63150. The employee party problem.

A set of n employees have intermingled such that each pair have met with (independent) probability p. The boss wishes to host a party for a maximum number of the n employees such that every pair of the employees invited have met, and wonders how big a party to plan. Let D_np be the random variable giving the size of the largest subset of employees every pair of which have met. We show that the density of D_np is quite spiked. For example, with n = 1000, p = .5, we exhibit bounds showing that Prob{D_1000,.5 = 15} > .8. Our main result is the following. Theorem. For any 0 < p = 1/b < 1, є > 0, let d= 2 log_bn – 2 log_b log_bn + 2 log_b(e/2) +1. Then lim_n→∞ Prob{ └d – є┘≤ D_np ≤ └d + є┘} = 1. (Received January 25, 1972.)

Manuscript

Manuscript (The Employee Party Problem) is a pdf file of the manuscript provided with the presentation at the 693 rd AMS meeting in St. Louis, April, 1972.