Pytania otagowane jako ramsey-theory

6
Siatka
Aktualizacja : Zestaw przeszkód (tj. „Bariera” NxM pomiędzy rozmiarami siatki do barwienia i bezbarwności) dla wszystkich 4-kolorów bez monochromatycznych prostokątów jest teraz znany . Czy ktoś ma ochotę wypróbować 5 kolorów? ;) Z teorii Ramseya wynika następujące pytanie . Rozważmy -coloring z n -by- m wykres siatki. Występuje, gdy cztery …
2
Zastosowanie liczb Ramseya
Definicja liczb Ramseya jest następująca: Niech jest dodatnią liczbą taką, że każdy wykres zamówienia na przynajmniej R ( , b ) obejmuje albo klika w ciągu wierzchołków lub zestaw się na stałym b wierzchołków.R(a,b)R(a,b)R(a,b)R(a,b)R(a,b)R(a,b)aaabbb Pracuję nad jakimś rozszerzeniem Ramsey Numbers. Chociaż badanie ma pewne teoretyczne zainteresowania, ważne byłoby poznanie motywacji …
1
Twierdzenie Ramseya dla zbiorów zbiorów
Podczas eksploracji różnych technik dowodzenia dolnych granic dla algorytmów rozproszonych przyszło mi do głowy, że następujący wariant twierdzenia Ramseya może mieć zastosowania - jeśli to prawda. Podano parametry: kkk , KKK , nnn , a następnie wybrano NNN aby było wystarczająco duże. Terminologia: podzbiór mmm jest podzbiorem rozmiaru mmm . …
2
Rozszerzenia twierdzenia Ramseya: monochromatyczne, ale różnorodne
Jako kontynuacja mojego poprzedniego pytania , które rozwiązał Hsien-Chih Chang, oto kolejna próba znalezienia odpowiedniego uogólnienia twierdzenia Ramseya. (Nie musisz czytać poprzedniego pytania; ten post jest samodzielny.) Parametry: podane są liczby całkowite , a następnie jest wybierane jako wystarczająco duże. Terminologia: podzbiór jest podzbiorem rozmiaru .1≪d≪k≪n1≪d≪k≪n1 \ll d \ll k …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.