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}]_{i,j=1}^{n}$ - macierzy kwadratowej o wyrazach rzeczywistych oraz pewnego $t \geq 0$ 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,2,...,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 $\{1,2,...,n \}$, taka że $\forall i \neq j$ $|A_{i} \cap A_{j}|$ jest ustaloną liczbą z $\{1,2,...,n \}$. Dowieść, że $|C| \leq n$.

Kontakt

moc.liamg|hsuoya.imar#moc.liamg|hsuoya.imar

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License