Turan's theorem - maximum number of edges.

Question

Question: 30 people need to place a call to each other using their cellular phones (one call per each pair). A cellular phone company gets 1 $ for each call between two people at distance between 800 and 1000 meters. The company is allowed to locate the people as it wishes so as to maximize its profit. What is the maximum possible profit of the company?

Thoughts: I know this is a question somehow related to Turan's theorem and the result is supposed to be the max number of edges. So I built a graph with n=30 vertices, and an edge between them iff the distance between 2 people is between 800 and 1000 meters. In order to somehow use Turan, I need to find out what kind of clique cannot be contained in this graph. $K_3$ and $K_4$ seem to be possible (ab+bc>ac can hold for some choices of distances). Need some other hint(s) to carry on...

The hardness in this problem is geometrical, not combinatorial. — Asinomás, Jan 24 '15 at 15:50
Nevermind, I see what you are thinking of, that is actually an excelent approach. — Asinomás, Jan 24 '15 at 15:51

Asinomás · Accepted Answer · 2015-01-24T17:07:04.343

1

A $K_4$ is impossible. Suppose it was possible, take the four points an consider the convex quadrilateral formed by the four points(clearly no three points are collinear) Now consider the largest angle of that quadrilateral, it is at least $90$ degrees (It is $\angle BAD$ in the drawing). The diagonal that that does not cut that angle is $BC$, by the cosine law it measures $\sqrt{BA^2+AC^2-2BA\cdot AC\cos(\angle BAC}$ Which is at least $\sqrt{800^2+800^2}=\sqrt{2}\cdot800\approx 1131$ since $\angle BAC$ is at least $90$ and then $cos(BAC)$ is not positive.

enter image description here

Therefore a $K_4$ is impossible so your graph has at most the same number of edges as the turan graph $T(30,3)$ which has $300$ edges. Notice that it is possible to build the Turan graph. To see this take an equilateral triangle with sides $900$ and make $10$ people stand really close to each of those vertices.

edited Jan 24 '15 at 17:07

answered Jan 24 '15 at 16:06

Asinomás

105,651

did you mean that T(30,3) has 300 edges? – jreing Jan 24 '15 at 17:06
Oh yeah. Edges. – Asinomás Jan 24 '15 at 17:06
This is a long shot since this post was last active way back, but how do you know that T(30,3) has 300 edges? – Epsilon31 Nov 20 '21 at 02:52
the turan graph $T(30,3)$ is the multipartite graph $K_{10,10,10}$ so it has $100$ edges between every pair of distinct parts. @Epsilon31 – Asinomás Nov 20 '21 at 10:54

Turan's theorem - maximum number of edges.

1 Answers1

Linked