Algebra liniowa i kombinatoryka

Opis

Warsztaty będą trwały dwa dni. Ich głównym celem będzie zaprezentowanie zastosowań algebry liniowej w rozwiązywaniu zadań z elementarnej teori grafów, kombinatoryki i geometrii. Zajęcia będą miały charakter "praktyczny" - planowanie jest wprowadzenie umiarkowanej ilości teorii przy jednoczesnym wyeksponowaniu zastosowań.

Program

• Metoda algebraiczna vs. zadania olimpijskie,
• lemat Spernera, twierdzenie Ko-Rado-Erdosa,
• zliczanie drzew spinających,
• opcjonalnie: lemat Dilwortha i częściowe porządki.

Wymagania

Znajomość podstawowych pojęć i narzędzi z poligonu działań (patrz opis), chęć nauczenia się podstaw algebry liniowej oraz zrobienie ok. połowy zadań kwalifikacyjnych.

Zadania kwalifikacyjne

Część 1.

1. Dane są funkcje \(f_{i}:A\rightarrow \mathbb{R}\) oraz parami różne elementy \(a_{1},...,a_{n} \in A\) takie, że \(f_{i}(a_{i}) = 1\) oraz \(\forall i \neq j\) \(f_{j}(a_{i}) = 0\)
Pokazać, że układ \((f_{i})\) jest liniowo niezależny (nad \(\mathbb{R}\)).

2. Udowodnić poniższe nierówności macierzowe:

a) \(rk(A+B) \leq rk(A) + rk(B), A\in \mathbb{R}^{m,n}\)

b) \(rk(AB) \leq min(rk(A),rk(B)), A\in \mathbb{R}^{m,n}, B\in \mathbb{R}^{n,k}\)

3. Dla \(A=[a_{ij}]^{n}_{i,j=1}\) - macierzy kwadratowej o wyrazach rzeczywistych oraz pewnego \(t \geq0\) zachodzą nast. warunki:

• \(\forall i \neq j \)  \(a_{ij} = t\)
• \(\forall i\) \(a_{ii} > t\)

Wykazać, że \(det(A) \neq 0\).

4. Jaki jest wymiar przestrzeni rzeczywistych wielomianów n zmiennych, które są afiniczne ze względu na każdą zmienną?
Funkcja \(f: \mathbb{R} \rightarrow \mathbb{R}\) jest afiniczna \(\iff\)jest postaci \(f(x) = ax + b\).

5. Niech \(P\) - skończony zbiór częściowo uporządkowany. Dowieść, że najmniejszy zbiór łańcuchów, których sumą mnogościową jest \(P\) ma tę samą moc, co najdłuższy antyłańcuch.

Część 2.

6. Dany jest ciąg \(ab+1\) liczb rzeczywistych. Pokazać, że zawiera on niemalejący podciąg długości \(a+1\) lub nierosnący podciąg o \(b+1\) wyrazach.

7. Mamy rodzinę \(H\) podzbiorów \(\{1,2,...,n\}\), spełniającą warunki:

• elementy \(H\) mają nieparzyste moce,
• przecięcie każdych dwóch różnych zbiorów z \(H\) ma parzyście wiele elementów.

Udowodnić, że \(|H| \leq n\).

8. Przypuśćmy, że \(A_{1}, ..., A_{n+2}\) - niepuste podzbiory \(\{1,...,n\}\). Pokazać, że istnieją niepuste, rozłączne podzbiory indeksów \(I, J\subset\{1,2,...,n+2\}\), takie że:

• \(\bigcup_{k \in I} A_{k} = \bigcup_{k \in J} A_k\),
•  \(\bigcap_{k \in I} A_k = \bigcap_{k \in J} A_k\).

9. Niech \(C = \{A_{1},...,A_{r}\}\) - rodzina różnych podzbiorów , taka że \(\forall i \neq j\)  \(|A_{i} \cap A_{j} |\)jest ustaloną liczbą z \(\{1,2,...,n\}\). Dowieść, że \(|C| \leq n\).

Kontakt

rami.ayoush@gmail.com