Hostname: page-component-7479d7b7d-jwnkl Total loading time: 0 Render date: 2024-07-16T00:49:01.739Z Has data issue: false hasContentIssue false

The Maximal Number of Triangles of Maximal Perimeter Length Determined by a Finite Set

Published online by Cambridge University Press:  20 November 2018

Béla Bollobás*
Affiliation:
Mathematical Institute, Oxford and Mathematical Institute, Budapest
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Suppose there are N not necessarily distinct points on a plane in such a position that any triangle (degenerate or non-degenerate) determined by these points has perimeter length at most 1. Denote by m the number of triangles with maximal perimeter length, (briefly, the number of maximal triangles), and put f(N) = max m where the maximum is taken over all permissible configurations. At the Colloquim on Graph Theory in Calgary, 1969, P. Erdös proposed the problem of determining f(N). He conjectured that the following construction gives the maximal number: place approximately half of the points at a point A and the others at B where AB = 1/2. The aim of this note is to prove this conjecture.

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1970

References

1. Turán, P., An extremal problem of graph theory, Mat és Fiz. Lapok 48 (1941), 436-452 (in Hungarian). See also P.Turán, On the theory of graphs, Coll. Math. 3 (1954), 19-30.Google Scholar