Combinatorics, Probability and Computing

The Clarkson–Shor Technique Revisited and Extended

a1 School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA (e-mail: [email protected])


We provide an alternative, simpler and more general derivation of the Clarkson–Shor probabilistic technique [7] and use it to obtain several extensions and new combinatorial bounds.

(Received October 18 2001)
(Revised September 26 2002)


1 Work on this paper was supported by NSF Grants CCR-97-32101 and CCR-00-98246, by a grant from the US–Israeli Binational Science Foundation, by a grant from the Israeli Academy of Sciences Center of Excellence program in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University.