mateforum.ro

Fie \( D^2 \) discul inchis de raza unitate din \( \mathbb{R}^2 \) si \( n \ge 2 \) un numar intreg fixat.
Determinati numarul maxim de segmente de lungime supraunitara avand capetele in \( A_1, ..., A_n \), cand \( \{A_j\} \) parcurge seturile de puncte, nu neaparat distincte, apartinand lui \( D^2 \).

[ DMO 2008, Problema 4 ]

Indicatie: Interpretati enuntul dpdv combinatoric.

Evident daca determinam numarul minim de segmente de lungime \( \leq 1 \) problema este rezolvata.

Se demonstreaza usor faptul ca din oricare 6 puncte exista cel putin 2 astfel incat lungimea segmentului determinat de acestea este \( \leq 1\ (*) \)(se foloseste argumentul unghiului la centru!).

Acum sa transpunem problema in limbaj de grafuri.

Fie \( G=(V;E) \), \( |G|=n \). Punem muchie intre varfurile \( i \) si \( j \) daca \( A_{i}A_{j}\leq 1. \)

Din relatia \( (*) \) rezulta ca \( \alpha(G)\leq 5 \) (partea independenta - nr. maxim de vf. fara muchie intre ele dintr-un graf).

Daca ne uitam la graful complementar lui \( G \) avem ca \( \omega(\bar{G})\leq 5 \) (indicele ciclomatic). Deci \( G \) nu contine un \( K_{6}. \)

Din Teorema lui Turan rezulta ca:
\( |\bar{E}|\leq\frac{6-2}{6-1}\cdot\frac{n^2}{2}=\frac{2}{5}\cdot n^2 \).

De aici numarul cerut este \( \lfloor\frac{2}{5}\cdot n^2 \rfloor. \)

Observatie! Revenim in demonstratie la \( 5\geq\alpha(G). \)

Sa enuntam Teorema Caro-Wei:

Fie \( G=(V;E) \) un graf si \( \alpha(G) \) partea independenta a acestuia. Atunci are loc inegalitatea:

\( \alpha(G)\geq\sum_{v\in V}\frac{1}{d(v)+1}. \)

De aici revenind la problema rezulta:

\( 5\geq\alpha(G)\geq\sum_{v\in V}\frac{1}{d(v)+1}\geq n\cdot\frac{1}{\frac{\sum_{v\in V}d(v)}{n}+1}=\frac{n^2}{2|E|+n}, \) unde am aplicat Inegalitatea lui Jensen pentru functia convexa \( f(x)=\frac{1}{x+1}. \)

\( \Longrightarrow |E|\geq\frac{n(n-5)}{10}\Longrightarrow |\bar{E}|\leq (^n _2)-\frac{n(n-5)}{10}=\frac{2}{5}\cdot n^2. \)

La pagina 6 e enuntata. Demonstratie nu am gasit (teorema e recenta)!

www.cs.rhul.ac.uk/~gutin/paperstsp/ch5sec2.ps

Eu am intalnit teorema folosita de Bogdan sub numele de Teorema lui Turan (e de fapt unul din multele rezultatele ale lui Turan, folosita pentru a demonstra celebra teorema care ii poarta numele).
Ea apare la pagina 248 in "Additive Combinatorics" de Terence Tao si Van Vu, de la Cambridge University Press (aparuta in 2006), dar si la pagina 209 in "Proofs from the Book" de M. Aigner si G. Ziegler, in capitolul "Turan's Graph Theorem". In ambele surse este demonstrata folosind metoda probabilistica.