[36] From among n 3

triangles with vertices chosen from n points in the unit square, let Tn be the one with the smallest area, and let An be the area of Tn. Heilbronn’s triangle problem asks for the maximum value Δn assumed by An over all choices of n points. We consider the average case: Show that if the n points are chosen independently and at random (with a uniform distribution), then there exist positive constants c and C such that c/n3 < μn < C/n3 for all large enough values of n, where μn is the expectation of An. Moreover, c/n3 < An < C/n3, with probability close to one.

Comments. Hint: Put the n points on the intersections of a k×k grid and show that the description of the arrangement can be compressed significantly below the maximum, both if the smallest triangle has too large an area and if it has too small an area, independent of k. Source: [T. Jiang, M. Li, and P.M.B. Vit´anyi, Random Struct. Alg., 20:2(2002), 206–219], which also contains literature pointers to other related results. A generalization of the average case result is given in [G. Grimmett and S.

Janson, Random Struct. Alg., 23:2(2003), 206–223]. History: H.A. Heilbronn conjectured that Δn = O(1/n2) in 1950, and P. Erd˝os proved that

Δn = Ω(1/n2) in 1950. K.F. Roth proved that Δn = O(1/n√log log n)

in 1951. W.M. Schmidt improved Roth’s bound to O(1/n√log n) in 1972.

Roth further improved this to O(1/n1.105) and O(1/n1.117) in 1972. J.

Koml´os, J. Pintz, and E. Szemer´edi further improved this to O(1/n8/7−)

in 1981 and they proved an Ω(log n/n2) lower bound in 1982. The problem has many generalizations and several dedicated websites.