0
$\begingroup$

Apologies if the title is unclear, I couldn't think of a good way to express what I want.

Given the usual 2D representation of the complete graph $K_n$ as a regular $n$-gon with each pair of vertices joined, let $U_n$ be the set of the disjoint regions of space delimited by the edges of the graph (so $|U_3|=1, |U_4|=4, |U_5|=11...$). Further, label the nodes of $K_n$ as $p_1, ..., p_n$.

What is the size of the largest subset $S_n \subset U_n$ such that $\forall s \in S_n \exists i, j, k \in K_n$ with $s \subset \triangle ijk$ and $t \not\subset \triangle ijk \forall t \in S_n, t \ne s$? That is, How many points can I place inside drawing of $K_n$ such that each triangle formed by three points on the exterior of $K_n$ contains at most one point?

In case it helps clarify what I'm trying to do, I'm working on a puzzle where letters are encoded by giving three points from a discrete set defining a triangle in which the letter is written. For instance, for $K_4$:

1-------2
|\  A  /|
| \   / |
|  \ /  | 
|   X   |
|  / \  |
| /   \ |
|/  B  \|
3-------4

"A" can be encoded as 123 or 124; B as 234 or 134. No further letters can be unambiguously encoded.

Playing around with pencil and paper, it seems as though $K_n$ can define $n-2$ letters unambiguously, but I haven't investigated far, and I can't immediately come up with a proof.

1 Answers 1

1

Let $P\ $ be the number of point that can be placed in $K_n$.

$P \le n-2$

To see this consider three adjacent vertex. Without loss of generality let them be named 1, 2, and 3. Consider the triangle 1-2-3, and notice that it is cut by $n-3$ lines all of which start at vertex 2. (There is $n-1$ lines starting from vertex 2, but two of them are the lines 1-2 and 2-3). Thus the triangle 1-2-3 is divided in $n-2$ smaller triangles. Then notice that the extension of all those small triangles are triangles that have all of their vertices on the perimeter of $K_n$. So all of the space of $K_n$ is divided into $n-2$ triangles. Thus if there is more than $n-2$ points (letter) one of those triangle must contain at least two points (letter).

$P \ge n - 2$

To see this take an edge, say 1-2 and consider all the triangles that have this edge and another vertex on the perimeter of $K_n$. There is $n-2$ of them because there is $n-2$ vertices once we remove the vertices 1 and 2. Now each of those triangle contain smaller triangles when $n \ge 5$. For each big triangle place a point in the smaller triangle that is closest to the third vertex (i.e. the vertex that is not 1 or 2). In this way you can place $n-2$ points. It should be clear that each of the smaller triangle that contain a point is not contained in any of the other big triangle because all the big triangles here share the edge 1-2 and a different vertex. Since we know that the formula works for $n \le 4$ we are done.

Thus $P = n - 2$

Note that the proof that $P \ge n - 2$ only shows that there is a one to one map between the points and the big triangle constructed. The proof does not show that each possible big triangle (including those that don't have the edge 1-2) unambiguously determines a point (letter).