Pytania otagowane jako co.combinatorics

Pytania dotyczące kombinatoryki i dyskretnych struktur matematycznych

2
kompletność rozpoznania różnicy dwóch permutacji
Shor stwierdził w swoim komentarzu do odpowiedzi anonimowego łosia na to pytanie. Czy potrafisz określić sumę dwóch permutacji w czasie wielomianowym? , To jest -Complete do określenia różnicę dwóch permutacji. Niestety, nie widzę prostą redukcję od problemu sumy permutacji i warto mieć N P zmniejszenie -completeness dla problemu różnicy permutacji.NPNPNPNPNPNP …

5
Powody, dla których wykres może nie być
Rozważając nieco to pytanie , próbowałem zidentyfikować wszystkie różne powody, dla których wykres może nie być k kolorowy. Są to jedyne 2 powody, które udało mi się dotychczas zidentyfikować:G=(VG,EG)G=(VG,EG)G = (V_G,E_G)kkk zawiera klikę o rozmiarze k + 1 . To oczywisty powód.GGGk+1k+1k+1 Istnieje podrozdział z G, taki że oba poniższe …

2
Kolorowanie płaskich wykresów
Rozważ zestaw płaskich wykresów, w których wszystkie ściany wewnętrzne są trójkątami. Jeśli jest punkt wewnętrzny nieparzystego stopnia, wykres nie może być trójkolorowy. Jeśli każdy punkt wewnętrzny ma równy stopień, czy zawsze może być trójkolorowy? Idealnie chciałbym mały kontrprzykład.

1
Grupowanie konsensusowe za pomocą ustawionej unii
Zadałem już to pytanie jakiś czas temu na MathOverflow , ale zgodnie z moją najlepszą wiedzą jest ono nadal otwarte, więc zamieszczam je ponownie w nadziei, że ktoś o nim usłyszy. Opis problemu Niech , i będą trzema partycjami w niepustych częściach (oznaczonych przez , i ) zestawu { }. …



4
Do czego służą wykresy nieskończone?
Właśnie przeczytałem na niemieckiej Wikipedii, że nieskończony wykres to wykres z nieskończoną liczbą węzłów lub nieskończoną liczbą krawędzi. Znam tylko aplikacje i algorytmy dla grafów skończonych. Do czego służą wykresy nieskończone? Jakie są ich zastosowania? Nie wyobrażam sobie algorytmów, które działałyby na nieskończonych grafach, ponieważ nie można przechowywać nieskończonego wykresu. …

2
Jawna zrównoważona macierz
Czy możliwe jest zbudowanie wyraźnej macierzy z , tak aby każda podmacierz zawiera mniej niż ?N×NN×NN \times N 0/10/10/1N1.5N1.5N^{1.5}N0.499×N0.499N0.499×N0.499N^{0.499} \times N^{0.499}N0.501N0.501N^{0.501} Lub prawdopodobnie możliwe jest zbudowanie jawnego zestawu uderzeń dla takiej właściwości. Łatwo zauważyć, że macierz losowa ma tę właściwość z prawdopodobieństwem wykładniczo bliskim . Również lemat mieszania ekspandera nie …


2
Liniowo niezależne współczynniki Fouriera
Podstawową właściwością przestrzeni wektorowych jest to, że przestrzeń wektorowa V⊆Fn2V⊆F2nV \subseteq \mathbb{F}_2^n o wymiarze n−dn−dn-d można scharakteryzować ddd liniowo niezależnymi wiązaniami liniowymi - to znaczy istnieją ddd liniowo niezależne wektory w1,…,wd∈Fn2w1,…,wd∈F2nw_1, \ldots, w_d \in \mathbb{F}_2^n , które są prostopadłe do VVV . Z punktu widzenia Fouriera jest to równoważne ze …

2
Aksjomaty dla najkrótszych ścieżek
Załóżmy, że mamy niekierowany wykres ważony G=(V,E,w)G=(V,E,w)G = (V, E, w) (z wagami nieujemnymi). Załóżmy, że wszystkie najkrótsze ścieżki w GGG są unikalne. Załóżmy, że mamy (sekwencje nieważonych krawędzi), ale nie znam samegoCzy możemy wytworzyć dowolny który dałby te ścieżki jako najkrótsze w czasie wielomianowym? Wersja słabsza: czy możemy zdecydować …


11
Modele losowych wykresów dla rzeczywistych sieci komputerowych
Interesują mnie modele losowych wykresów, które są podobne do wykresów rzeczywistych sieci komputerowych. Nie jestem pewien, czy wspólny dobrze zbadany model ( wierzchołków, każda możliwa krawędź jest wybierana z prawdopodobieństwem ) nadaje się do badania rzeczywistych sieci komputerowych (prawda?).n pG ( n , p )sol(n,p)G(n,p)nnnppp jakie modele losowych wykresów są …

1
Konstrukcja wykresów, w których każda para wierzchołków ma unikalnego wspólnego sąsiada
Niech będzie prostym wykresem na wierzchołkach bez wierzchołka stopnia . Załóżmy, że dla dowolnych dwóch wierzchołków istnieje unikalny wierzchołek przylegający do nich obu. Jest to ćwiczenie z Kursu kombinatoryki van Linta i Wilsona, aby udowodnić, że taki wykres jest regularny.GGGnnn(n>3)(n>3)(n > 3)n−1n−1n − 1GGG Moje pytanie brzmi jednak, czy w …


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.