1 W przestrzeni Zofia Miechowicz Otwock

2 Naturalna analogia? ZBIÓR PRZESTRZEŃ LINIOWA PODZBIÓR PODPRZESTRZEŃMOC WYMIAR

3 Ile tego jest? Podzbiorów k-elementowych zbioru n-elementowegoPodprzestrzeni k-wymiarowych przestrzeni n-wymiarowej F – skończone ciało rzędu q

4 Ile tego jest? Podprzestrzeni k-wymiarowych przestrzeni n-wymiarowej F – skończone ciało rzędu q - niezależne Na ile sposobów? . . .

5 Ile tego jest? F – skończone ciało rzędu q - niezależneNa ile sposobów? Ile mają baz?

6 Ile tego jest? Podzbiorów k-elementowych zbioru n-elementowegoPodprzestrzeni k-wymiarowych przestrzeni n-wymiarowej F – skończone ciało q elementowe

7 Ile tego jest? - Współczynnik dwumianowy NewtonaIsaac Newton - Współczynnik dwumianowy Newtona Carl Friedrich Gauss - Współczynnik dwumianowy Gaussa Do znalezienia formuły na sumy Gaussa

8 Ile tego jest? Jako funkcja zmiennej q

9 Ile tego jest? - niezależne Donald Knuth 1938ZREDUKOWANA POSTAĆ SCHODKOWA elementarne operacje na wierszach pierwszy niezerowy element od lewej w każdym wierszu to 1 wszystkie pozostałe elementy w kolumnie, w której jest jedynka wiodąca to zera w każdym wierszu jedynka wiodąca pojawia się na prawo od jedynki wiodącej w poprzednim wierszu JEŻELI DWIE MACIERZE W TEJ POSTACI GENERUJĄ WIERSZOWO TĘ SAMĄ PRZESTRZEŃ, TO SĄ RÓWNE

10 Ile tego jest? Donald Knuth 1938

11 Ile tego jest? Donald Knuth 1938w każdym wierszu usuń wszystkie elementy na lewo od jedynki wiodącej

12 Ile tego jest? Donald Knuth 1938w każdym wierszu usuń wszystkie elementy na lewo od jedynki wiodącej

13 Ile tego jest? Donald Knuth 1938w każdym wierszu usuń wszystkie elementy na lewo od jedynki wiodącej usuń kolumny, zawierające pierwsze jedynki

14 Ile tego jest? Donald Knuth 1938w każdym wierszu usuń wszystkie elementy na lewo od jedynki wiodącej usuń kolumny, zawierające pierwsze jedynki

15 Ile tego jest? k Donald Knuth 1938 Podprzestrzeni k-wymiarowychn-k Podprzestrzeni k-wymiarowych przestrzeni n-wymiarowej jest tyle samo, co takich obrazków w każdym wierszu usuń wszystkie elementy na lewo od jedynki wiodącej usuń kolumny, zawierające pierwsze jedynki zamień wszystkie pozostałe elementy na *

16 Ile tego jest? Donald Knuth 1938 WRACAMY! 1 ,

17 Ile tego jest? Donald Knuth 1938 WRACAMY! * * * 1 1 * * * * 1

18 Ile tego jest? Donald Knuth 1938 WRACAMY! * * * 1 dowolnie * * 1 * * 1

19 Ile tego jest? 1 2 1 1 3 1 1 1 Donald Knuth 1938 WRACAMY! dowolnie na1 2 1 1 3 1 1 1 liczba * dowolnie na sposobów

20 Ile tego jest? 1 2 1 1 3 1 1 1 Donald Knuth 1938 WRACAMY! dowolnie na1 2 1 1 3 1 1 1 dowolnie na sposobów

21 Ile tego jest? Donald Knuth 1938

22 * Ile tego jest? a1 a2 Donald Knuth 1938 a3 Diagram Ferrersan=a1+a2+…+ak ai – nierozróżnialne

23 * Ile tego jest? a1 n - kresek a2 k – kresek poziomych n-kDonald Knuth 1938 * a1 k n-k n - kresek a2 k – kresek poziomych a3 – ścieżek

24 Twierdzenie Ramseya Kolorując dowolnie dwoma kolorami krawędzie grafu pełnego K6 znajdziemy jednokolorową indukowaną klikę K3.

25 Twierdzenie Ramseya

26 Twierdzenie Ramseya Ponadto ?

27 Najmniejsze takie n oznaczamy przez R(k)Twierdzenie Ramseya Dla każego k istnieje taka liczba n, że przy dowolnym dwukolorowaniu krawędzi grafu pełnego Kn znajdziemy jednokolorową indukowaną klikę Kk. Najmniejsze takie n oznaczamy przez R(k) (k-ta liczba Ramseya ) Frank Ramsey (1903 – 1930)

28 Liczby Ramseya R(2) = 2 R(3) = 6 R(4) = 18 Graf Paleya

29 Twierdzenie Ramseya Frank Ramsey (1903 – 1930) Dla każdej liczby naturalnej s istnieje taka liczba naturalna n=R(s), że dla dowolnego dwukolorowania dwuelementowych podzbiorów zbioru [n] istnieje s-elementowy podzbiór [n], którego wszystkie dwuelementowe podzbiory są w tym samym kolorze

30 Twierdzenie Ramseya {1,2} {1,2,3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4}Gian-Carlo Rota ( ) {1,2} {1,2,3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,3} {1,4} {2,3} {2,4} {3,4} {1} {2} {3} {4} { } Dla każdej liczby naturalnej s istnieje taka liczba naturalna n=R(s), że dla dowolnego dwukolorowania dwuelementowych podzbiorów zbioru [n] istnieje s-elementowy podzbiór [n], którego wszystkie dwuelementowe podzbiory są w tym samym kolorze

31 Twierdzenie Ramseya {1,2,3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2}Gian-Carlo Rota ( ) {1,2,3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} {1} {2} {3} {4} { } Dla każdej liczby naturalnej s istnieje taka liczba naturalna n=R(s), że dla dowolnego dwukolorowania dwuelementowych podzbiorów zbioru [n] istnieje s-elementowy podzbiór [n], którego wszystkie dwuelementowe podzbiory są w tym samym kolorze

32 Twierdzenie Ramseya {1,2,3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2}Gian-Carlo Rota ( ) {1,2,3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} {1} {2} {3} {4} { } Dla każdej liczby naturalnej s istnieje taka liczba naturalna n=R(s), że dla dowolnego dwukolorowania dwuelementowych podzbiorów zbioru [n] istnieje s-elementowy podzbiór [n], którego wszystkie dwuelementowe podzbiory są w tym samym kolorze

33 Twierdzenie Ramseya Gian-Carlo Rota ( ) krata podzbirów zbioru n-elementowego dowolna krata geometryczna krata podprzestrzeni przestrzeni wektorowej Dla każdej liczby naturalnej s istnieje taka liczba naturalna n=R(s), że dla dowolnego dwukolorowania dwuelementowych podzbiorów zbioru [n] istnieje s-elementowy podzbiór [n], którego wszystkie dwuelementowe podzbiory są w tym samym kolorze

34 Twierdzenie Ramseya Gian-Carlo Rota ( ) krata podzbirów zbioru n-elementowego dowolna krata geometryczna krata podprzestrzeni przestrzeni wektorowej Dla każdej liczby naturalnej s istnieje taka liczba naturalna n=R(s), że dla dowolnego dwukolorowania dwuelementowych podzbiorów zbioru [n] istnieje s-elementowy podzbiór [n], którego wszystkie dwuelementowe podzbiory są w tym samym kolorze

35 Twierdzenie Ramseya

36 Twierdzenie Ramseya Kostki kombinatoryczne 111 011 110 010 001 101 100 000 trzy wymiary jeden wymiar 1 dwa wymiary 00 10 11 01 itd… cztery wymiary? 1 – kostki (różnią się na jednej współrzędnej)

37 zawsze znajdziemy czerwoną s-kostkę, lub niebieską t-kostkę.Twierdzenie Ramseya Dla dowolnych liczb naturalnych k,s,t istnieje taka liczba naturalna n, że dla dowolnego dwukolorowania k-kostek w przestrzeni n-wymiarowej zawsze znajdziemy czerwoną s-kostkę, lub niebieską t-kostkę.

38 Twierdzenie Ramseya Nagroda Pólyi 1971

39 Twierdzenie Ramseya Dla dowolnych liczb naturalnych s,t,k istnieje taka liczba naturalna n, że dla dowolnego k-kolorowania t-wymiarowych podprzestrzeni przestezeni n-wymiarowej znajdziemy s-wymiarową przestrzeń, której wszystkie t-wymiarowe podprzestrzenie są jednobarwne.

40 Liczby Ramseya Jak to szacować?Dla dowolnych liczb naturalnych s,t,k istnieje taka liczba naturalna n, że dla dowolnego k-kolorowania t-wymiarowych podprzestrzeni przestezeni n-wymiarowej znajdziemy s-wymiarową przestrzeń, której wszystkie t-wymiarowe podprzestrzenie są jednobarwne.

41 Liczby Ramseya Jak to szacować? Największa liczba na świecie

42 Jak być innym Kwadraty łacińskie 1 2 3 4

43 Jak być innym 1 2 3 4 4 1 2 3 3 4 1 2 2 3 4 1 Kwadraty łacińskieRonald Fisher ( ) i tablica-okno ku jego pamięci Caius College w Cambridge Leonard Euler (1707 – 1783) 1 2 3 4 4 1 2 3 3 4 1 2 2 3 4 1

44 Czasem więcej, znaczy mniejJak być innym Czasem więcej, znaczy mniej 1 2 3 4 4 1 2 3 n 3 4 1 2 2 3 4 1 n

45 Czasem więcej, znaczy mniejJak być innym Czasem więcej, znaczy mniej 1,2, 3,4 1,2, 3,4 1,2, 3,4 1,2, 3,4 1 2 3 4 1,2, 3,4 1,2, 3,4 1,2, 3,4 1,2, 3,4 4 1 2 3 n 1,2, 3,4 1,2, 3,4 1,2, 3,4 1,2, 3,4 3 4 1 2 1,2, 3,4 1,2, 3,4 1,2, 3,4 1,2, 3,4 2 3 4 1 n

46 Czasem więcej, znaczy mniej Niespodziewany problemJak być innym Czasem więcej, znaczy mniej 1,2, 3,4 1,2, 5,9 1,2, 3,4 2,4, 5,9 W każdym polu mamy n liczb do wyboru Globalnie liczb może być więcej niż n 1,2, 3,5 4,5, 6,7 1,2, 3,4 2,4, 5,9 n Niespodziewany problem 2,4, 5,6 1,2, 3,4 1,2, 5,7 1,3, 5,8 1,2 2,3 1,2, 4,6 5,6, 7,8 5,6, 7,8 1,2, 3,4 n 1,2 2,3

47 Czasem więcej, znaczy mniej Niespodziewany problemJak być innym Czasem więcej, znaczy mniej 1,2, 3,4 1,2, 5,9 1,2, 3,4 2,4, 5,9 W każdym polu mamy n liczb do wyboru Globalnie liczb może być więcej niż n 1,2, 3,5 4,5, 6,7 1,2, 3,4 2,4, 5,9 n Niespodziewany problem 2,4, 5,6 1,2, 3,4 1,2, 5,7 1,3, 5,8 1 3 1,2, 4,6 5,6, 7,8 5,6, 7,8 1,2, 3,4 n 1,2 2,3

48 Czasem więcej, znaczy mniej Niespodziewany problemJak być innym Czasem więcej, znaczy mniej 1,2, 3,4 1,2, 5,9 1,2, 3,4 2,4, 5,9 W każdym polu mamy n liczb do wyboru Globalnie liczb może być więcej niż n 1,2, 3,5 4,5, 6,7 1,2, 3,4 2,4, 5,9 n Niespodziewany problem 2,4, 5,6 1,2, 3,4 1,2, 5,7 1,3, 5,8 1 3 1,2, 4,6 5,6, 7,8 5,6, 7,8 1,2, 3,4 n ? 2 2,3

49 Czasem więcej, znaczy mniejJak być innym Czasem więcej, znaczy mniej 1,2, 3,4 1,2, 5,9 1,2, 3,4 2,4, 5,9 Czy zawsze da się skonstruować kwadrat łaciński mając w każdym polu listę rozmiaru n ? 1,2, 3,5 4,5, 6,7 1,2, 3,4 2,4, 5,9 n 2,4, 5,6 1,2, 3,4 1,2, 5,7 1,3, 5,8 2 3 1 1 1,2 2,3 3 1,2, 4,6 5,6, 7,8 5,6, 7,8 1,2, 3,4 n ? ? 2 2 2,3 2,3

50 Czasem więcej, znaczy mniejJak być innym Czasem więcej, znaczy mniej Hipoteza Dinitza (1978) 1,2, 3,4 1,2, 5,9 1,2, 3,4 2,4, 5,9 Czy zawsze da się skonstruować kwadrat łaciński mając w każdym polu listę rozmiaru n ? 1,2, 3,5 4,5, 6,7 1,2, 3,4 2,4, 5,9 n TAK! - Fred Galvin 1994 2,4, 5,6 1,2, 3,4 1,2, 5,7 1,3, 5,8 1,2, 4,6 5,6, 7,8 5,6, 7,8 1,2, 3,4 Jeff Dinitz n

51 Jak być innym n n Prostszy przypadek Czy zawsze da się skonstruować1,2, 3,4 1,2, 3,4 1,2, 3,4 1,2, 3,4 Czy zawsze da się skonstruować kwadrat łaciński mając w każdym polu listę rozmiaru n, przy czym wszystkie listy w tym samym wierszu są jednakowe? 4,5, 6,7 4,5, 6,7 4,5, 6,7 4,5, 6,7 n 2,4, 5,6 2,4, 5,6 2,4, 5,6 2,4, 5,6 1,2, 4,6 1,2, 4,6 1,2, 4,6 1,2, 4,6 n

52 Jak być innym 1 2 3 4 4 5 6 7 2 4 5 6 1 2 4 6 Prostszy przypadek 1,2,3,4 1,2, 3,4 1,2, 3,4 1,2, 3,4 1 2 3 4 4,5, 6,7 4,5, 6,7 4,5, 6,7 4,5, 6,7 4 5 6 7 2,4, 5,6 2,4, 5,6 2,4, 5,6 2,4, 5,6 2 4 5 6 1,2, 4,6 1,2, 4,6 1,2, 4,6 1,2, 4,6 1 2 4 6

53 Jak być innym 1 2 3 4 4 5 6 7 2 4 5 6 6 2 4 1 Prostszy przypadek 1,2,3,4 1,2, 3,4 1,2, 3,4 1,2, 3,4 1 2 3 4 4,5, 6,7 4,5, 6,7 4,5, 6,7 4,5, 6,7 4 5 6 7 2,4, 5,6 2,4, 5,6 2,4, 5,6 2,4, 5,6 2 4 5 6 1,2, 4,6 1,2, 4,6 1,2, 4,6 1,2, 4,6 6 2 4 1

54 Jak być innym R1 R1 R2 R3 Rn R4 1 2 3 4 5 6 7 Prostszy przypadek 1 2 3Koning: ..

55 Jak być innym Prostszy przypadek R1 1 2 3 4 R1 R2 R3 R4 1 2 3 4 5 6 7 4 5 6 7 2 4 5 6 Rn 1 2 4 6 Koning: ..

56 Jak być innym Prostszy przypadek R1 1 3 2 4 R1 R2 R3 R4 1 2 3 4 5 6 7 4 5 6 7 2 4 5 6 Rn 6 2 4 1 Koning: ..

57 Jak być niezależnym B1 Bn V – n wymiarowa przestrzeń wektorowaBi- bazy przestrzeni V Hipoteza: Da się przepermutować elementy w każdym wierszu w taki sposób, żeby w każdej kolumnie otrzymać bazę V

58 Jak być niezależnym B1 Bn C1 Cn V – n wymiarowa przestrzeń wektorowaBi- bazy przestrzeni V Hipoteza: Da się przepermutować elementy w każdym wierszu w taki sposób, żeby w każdej kolumnie otrzymać bazę V Bn Gian-Carlo Rota ( ) C1 Cn bazy?

59 L nxn [n] 1 2 3 4 L – parzysty, jeżeli L – nieparzysty, jeżeli

60 Jak być niezależnym L nxn [n] 1 2 3 4 n - nieparzystele(n)– liczba parzystych kwadratów łacińskich rozmiaru n 1 2 3 4 lo(n)– liczba nieparzystych kwadratów łacińskich rozmiaru n n - nieparzyste Kwadrat nieparzysty otrzymujemy z parzystego (i odwrotnie) zamieniając miejscami dwa wiersze, lub dwie kolumny.

61 Jak być niezależnym L nxn [n] 1 2 3 4 Hipoteza:Dla parzystych n liczba parzystych kwadratów łacińskich rozmiaru n jest różna od liczby nieparzystych kwadratów łacińskich rozmiaru n. 1 2 3 4 Noga Alon Michael Tarsi

62 Hipoteza Alona - TarsiegoJak być niezależnym Hipoteza Alona - Tarsiego Hipoteza Roty

63 Jak być niezależnym B1 Bk Jest prawdziwa: Słabsza wersja:Dla n=2,3,4,6,8 - Marini Obecnie dla n<26 Dla n=p+1 (p-liczba pierwsza) – A.A. Drisko Hipoteza Alona-Tarsiego Dla n=p-1 (p-liczba pierwsza) – D.G. Glynn Słabsza wersja: V – n wymiarowa przestrzeń wektorowa B1 Bk Bi- bazy przestrzeni V Możemy tak spermutować elementy w wierszach, żeby kolumny były zbiorami niezależnymi, jeżeli: - J. Geelen, K. Webb

64 Dziękuję za uwagę