The Complexity of Finding Replicas Using Equality Tests - Frandsen, Gudmund Skovbjerg; Miltersen, Peter Bro; Skyum, Sven (DAIMI Report Series, 1993)
We prove (for fixed k) that at least (1/k - 1)(^n_2) - O(n) equality tests and no more than (2/k)(^n_2) + O(n) equality tests are needed in the worst case to determine whether a given set of n elements contains a subset of k identical elements. The upper bound is an improvement by a factor 2 compared to known results. We give tighter bounds for k = 3.