Does a colouring of a graph on two colours always have certain kinda of triangles

102 Views Asked by At

Is there a planar point set such that no matter how you colour the points with two colours can you can always find a triangle with exactly one point inside so that all four points have the same colour?

I'm not really sure how to start working on this graph problem any advice?

1

There are 1 best solutions below

1
On BEST ANSWER

Yes, this can be done with a set of $22$ points. I apologize for the clumsy description below; I don't know how to draw pictures.

Start with a point $O$ and three points $P_1,Q_1,R_1$ spaced $120^\circ$ apart on a circle centered at $O$; e.g., $0$ and the three cube roots of unity. On the same circle choose points $P_0,P_2$ near $P_1$, points $Q_0,Q_2$ near $Q_1$, and points $R_0,R_2$ near $R_1$, so that each of the $27$ triangles $P_iQ_jR_k$ has $O$ in its interior. We may assume that the points are labelled $P_0,P_1,P_2,Q_0,Q_1,Q_2,R_0,R_1,R_2$ in counterclockwise order.

Call the two colours red and blue, and assume without loss of generality that $O$ is coloured red. If each of the three clusters contains a red point, then we have a red triangle $P_iQ_jR_k$ having the red point $O$ in its interior, and no other points; the additional $12$ points will be placed outside the circle. Thus we may assume that one of the clusters consists of three blue points. Without loss of generality, $P_0,P_1,P_2$ are coloured blue.

Next, choose points $U_0,U_1,U_2,U_3$ as follows: they are outside the circle, they all lie on a straight line parallel to the line segment $P_0P_2$, and the $12$ line segments $U_iP_j$ do not intersect the circle. Thus for each $i=0,1,2,3$, the triangle $U_iP_0P_2$ has the point $P_1$ in its interior. Now, perturb the points $U_i$ slightly, so that each $U_i$ still forms a triangle $ U_iP_0P_2$ with only the point $P_1$ in its interior, but instead of $U_0,U_1,U_2,U_3$ being collinear, one of them lies in the interior of the triangle formed by the other three. If $P_0,P_1,P_2$ are all blue then, whether one of the $U_i$ is blue or whether all four of them are red, we have the configuration we want.

Of course, we have to choose four more points $V_0,V_1,V_2,V_3$ which do the same trick if $Q_0,Q_1,Q_2$ are all of one colour, and four more points $W_0,W_1,W_2$ for $R_0,R_1,R_2$, making $22$ points in all.

Update: Well, actually, $13$ points are enough. Please consider the clumsy, inefficient $22$-point construction described above as a hint.