$ n$ points (no three being collinear) are given in a plane. Some points are connected and they form $ k$ segments. If no three of these segments form triangle ( equiv. there are no three points, such that each two of them are connected) prove that $ k \leq \left \lfloor \frac {n^{2}}{4}\right\rfloor$
Problem
Source: Federation of Bosnia, 2. Grades 2008.
Tags: floor function, function, combinatorics proposed, combinatorics
24.04.2008 00:22
This is Turan's theorem... Pierre.
08.10.2008 03:30
Let $ a-b$ mean $ a$ is connected to $ b$. Let the "points" be associated with the numbers from 1 to n. Call a permutation $ f$ of $ [n]$ a "relabeling" if $ a-b\iff f(a)-f(b)$ For given n consider a "connecting" of $ [n]$ with maximal number k connections, without a triangle. Thus, there exists a relabeling $ \pi_1$ of $ [n]$ so that $ \pi_1(1)-\pi_1(2),\pi_1(2)-\pi_1(3),...$ Clearly if this weren't the case, $ k$ wouldn't be maximal (we would add in extra connections). Then there exists a relabeling $ \pi_2$ so that $ \pi_2(p_1(i))-pi_2(p_1(i+3))$ whenever $ i,i+3$ are in $ [n]$. We continue in this way until we reach a function $ p_1\circ p_2\circ \cdots p_k$ that relabels our connections into: 1-2,2-3,3-4,... 1-4,2-5,3-6,... 1-6,2-7,3-8,... ... We verify that k has at most: k-1 + (k-3) + ... + 3 + 1 = (k/2)^2, if k is even k-1 + ... + 4 + 2 = (k^2-1)/4, if k is odd elements, solving the problem
08.10.2008 19:16
The following estimate is not rigorous but it help us solve this one in almost all cases. $ {k \choose 2} \leq 2 \vdots {n \choose 3}$
08.10.2008 21:07
pbornsztein wrote: This is Turan's theorem... Pierre. well,actually this is "Mantel's theorem" a special case of "Turan's theorem",Turan's theorem says that: if a simple graph on $ n$ vertices has more than $ M(n,p)$ edges,then it contains a $ K_p$ as a subgraph,where: $ M(n,p) = \frac {p - 2}{2(p - 1)}n^2 - \frac {r(p - 1 - r)}{2(p - 1)}$ in which $ n = t(p - 1) + r$ , $ 1\leq r\leq p - 1$ also another proof for Mantel's theorem is the following one: let $ G$ have $ n$ vertices,numbered from $ 1$ to $ n$,and no triangles.we give vertex $ i$ a weight $ z_i\geq 0$ such that $ \sum z_i=1$ and we wish to maximize $ S=\sum z_iz_j$,where the sum is taken over all edges $ \{i,j\}$.suppose that vertex $ k$ and vertex $ l$ are not joined.let the neighbors of $ k$ have total weight $ x$,and those of $ l$ total weight $ y$,where $ x\geq y$.since $ (z_k+\epsilon)x+(z_l-\epsilon)\geq z_kx+z_ly$,we do not decrease the value of $ S$ if we shift some of the weight of vertex $ l$ to the vertex $ k$.it follows that $ S$ is maximal if all of the weight is concentrated on some complete subgraph of $ G$,i.e. on one edge.therefore $ S\leq\frac 14$.on the other hand,taking all $ z_i$ equal to $ \frac 1n$ would yield a value of $ \frac{|E|}{n^2}$ for $ S$.therefore $ |E|\leq\frac 14 n^2$.
02.02.2018 15:52
Mantels theorem already in pss