Jedynki w macierzy

[mol_ksiazkowy]

Dana jest macierz kwadratowa \(\displaystyle{ A}\) wymiaru \(\displaystyle{ n}\) , o elementach \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\), która nie ma podmacierzy \(\displaystyle{ \left[\begin{array}{cc}a_{i,r}&a_{i,s}\\ a_{j,r}&a_{j,s} \end{array}\right]}\) zbudowanej z samych jedynek.
Udowodnić, że ilość jedynek w \(\displaystyle{ A}\) nie jest większa niż \(\displaystyle{ n \sqrt{2n-1}}\)

[Mruczek]

To jest bardzo znany problem. Robimy z tej macierzy graf dwudzielny, który ma po \(\displaystyle{ n}\) wierzchołków z każdej strony - jeden zbiór wierzchołków odpowiada kolumnom, a drugi wierszom tej macierzy. Łączymy krawędzią tylko te pary wierzchołków, dla których w odpowiadających im polach macierzy (kolumnie i wierszu) stoi jedynka.
Teraz podmacierz z samymi jedynkami odpowiada cyklowi długości \(\displaystyle{ 4}\) w tym grafie, a my szukamy maksymalnej liczby krawędzi (czyli jedynek) w takim grafie tak aby nie miał cyklu długości \(\displaystyle{ 4}\).

Rozwiązanie np. tutaj (rozdział 2.2):
... /44-49.pdf

Podane tam szacowanie należy osłabić:
\(\displaystyle{ |E| \le \frac{n}{4}(1 + \sqrt{4n - 3} ) \le n \sqrt{2n - 1}}\)
\(\displaystyle{ 1 + \sqrt{4n - 3} \le 4\sqrt{2n - 1}}\), do kwadratu
\(\displaystyle{ 1 + 4n - 3 +2\sqrt{4n - 3} \le 16(2n - 1)}\)
\(\displaystyle{ 2\sqrt{4n - 3} \le 28n - 14}\)
\(\displaystyle{ \sqrt{4n - 3} \le 14n - 7}\)
\(\displaystyle{ \sqrt{4n - 3} \le 2n \le 7n \le 14n - 7n \le 14n - 7}\)