Bariz - Problem

Source: Bulgarian MO 2002 4th round day 1 problem 3

Tags: combinatorics unsolved, combinatorics

mitrov

06.09.2014 20:57

Given are $n^2$ points in the plane, such that no three of them are collinear, where $n \geq 4$ is the positive integer of the form $3k+1$. What is the minimal number of connecting segments among the points, such that for each $n$-plet of points we can find four points, which are all connected to each other? Proposed by Alexander Ivanov and Emil Kolev

Consider the Turán's graph $T(n,3) = K_{k,k,k+1}$, the complete tripartite graph on three shores of $k$, $k$ and $k+1$ vertices, having $t(n,3) = 3k^2+2k$ edges, and the complete graph $K_n$ on $3k+1$ vertices, having $k_n = 3k(3k+1)/2$ edges. Then the graph $G = T(n,3) * K_n$, having $m= t(n,3) + n^2 + k_n$ edges, doesn't have the property required, but any graph on $n^2$ vertices, and even one more edge than $m$, does have the property, since any subgraph of order $n$ will have more that $t(n,3)$ edges, thus contain a $K_4$.