Pytania otagowane jako co.combinatorics

Pytania dotyczące kombinatoryki i dyskretnych struktur matematycznych

2
Czy można rozstrzygnąć, czy dany kształt może pokryć płaszczyznę?
Wiem, że nierozstrzygalne jest ustalenie, czy zestaw kafelków może kafelkować płaszczyznę, w wyniku Bergera korzystającego z kafelków Wanga . Moje pytanie brzmi: czy wiadomo również, że nierozstrzygalne jest ustalenie, czy pojedyncza dana płytka może ułożyć płytkę, monoedryczną płytkę. Jeśli to pozostanie nierozwiązane, chciałbym wiedzieć, jaka jest minimalna liczność zbioru płytek, …
5
Jaka jest maksymalna liczba trwałych małżeństw w przypadku problemu stabilnego małżeństwa?
Problem stabilnego małżeństwa: http://en.wikipedia.org/wiki/Stable_marriage_problem Zdaję sobie sprawę, że w przypadku SMP możliwe jest wiele innych stabilnych małżeństw, z wyjątkiem algorytmu Gale-Shapleya. Jeśli jednak otrzymamy tylko , liczbę mężczyzn / kobiet, zadajemy następujące pytanie: Czy możemy stworzyć listę preferencji, która daje maksymalną liczbę trwałych małżeństw? Jaka jest górna granica takiej liczby?nnn
1
Hipoteza odbudowy i częściowe 2-drzewa
Przypuszczenie o rekonstrukcji mówi, że wykresy (z co najmniej trzema wierzchołkami) są określane jednoznacznie przez ich podgrupy usunięte z wierzchołków. Ta hipoteza ma pięć dekad. Przeszukując odpowiednią literaturę, odkryłem, że następujące klasy grafów są rekonstruowalne: drzewa wykresy odłączone, wykresy, których dopełnienie jest odłączone regularne wykresy Maksymalne wykresy zewnętrzne maksymalne wykresy …
3
Reprezentowanie OR za pomocą wielomianów
Wiem, że w trywialny sposób funkcja OR dla zmiennych może być dokładnie reprezentowana przez wielomian jako taki: , czyli stopnia .nnnx1,…,xnx1,…,xnx_1,\ldots, x_np(x1,…,xn)p(x1,…,xn)p(x_1,\ldots,x_n)p(x1,…,xn)=1−∏ni=1(1−xi)p(x1,…,xn)=1−∏i=1n(1−xi)p(x_1,\ldots,x_n) = 1-\prod_{i = 1}^n\left(1-x_i\right)nnn Ale jak mogę pokazać, co wydaje się oczywiste, że jeśli jest wielomianem, który dokładnie reprezentuje funkcję OR (więc ), a następnie ?∀ x ∈ …
5
Dobre rozmieszczenie miejsc dla sekwencji posiłków i stolików wielkości k dla grupy osób
Biorąc pod uwagę zestaw SS.S osób, chciałbym im usiąść na sekwencji posiłków przy stolikach wielkości . (Oczywiście, jest wystarczająca ilość stolików, aby usiąść przy każdym posiłku.) Chciałbym tak ustawić, aby nikt nie dzielił stołu z tą samą osobą dwa razy. Typowe wartości to ikkk|S||S.||S||S|=45|S.|=45|S|=45k=5k=5k=5 i 6 do 10 posiłków. Mówiąc …
1
Cliquewidth of Almost Cographs
( Wysłałem to pytanie do MathOverflow dwa tygodnie temu, ale jak dotąd bez ścisłej odpowiedzi) Mam pytanie dotyczące miar szerokości wykresu niekierowanych prostych wykresów. Powszechnie wiadomo, że wykresy (wykresy, które można budować za pomocą operacji rozłącznego łączenia i uzupełniania, poczynając od izolowanych wierzchołków) mają najwyżej 2-krotność (Courcelle i in., Górne …
6
Rodziny wykresów z wielomianowymi algorytmami czasowymi do obliczania liczby chromatycznej
Post zaktualizowany 31 sierpnia : dodałem podsumowanie aktualnych odpowiedzi poniżej oryginalnego pytania. Dzięki za wszystkie interesujące odpowiedzi! Oczywiście każdy może nadal publikować wszelkie nowe ustalenia. Dla których rodzin grafów istnieje algorytm wielomianowy do obliczania liczby chromatycznej ?χ(G)χ(G)\chi(G) Problem można rozwiązać w czasie wielomianowym, gdy (wykresy dwudzielne). Na ogół, gdy χ …
4
Wybór społeczny, twierdzenie strzały i otwarte problemy?
W ostatnich miesiącach zacząłem wykładać na temat wyboru społecznego, twierdzenia strzały i powiązanych wyników. Po przeczytaniu o przełomowych wynikach zadałem sobie pytanie, co dzieje się z częściowymi preferencjami porządku, odpowiedź znajduje się w pracy Pini i in. : Agregowanie częściowo uporządkowanych preferencji: wyniki niemożliwości i możliwości . Następnie zastanawiałem się, …
2
Czy istnieją lokalne maksima w liczbie ruchów wymaganych do rozwiązania Kostki Rubika?
Peter Shor poruszył interesujący punkt w związku z próbą odpowiedzi na wcześniejsze pytanie dotyczące złożoności rozwiązania kostki Rubika n×n×nn×n×nn \times n \times n . Podjąłem dość naiwną próbę wykazania, że ​​musi być zawarta w NP. Jak zauważył Peter, moje podejście w niektórych przypadkach zawodzi. Jednym z potencjalnych przypadków takiego wystąpienia …
1
Liczba wyraźnych różnic liczb całkowitych wybranych z
Podczas moich badań spotkałem następujący wynik. limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n} \right] = 1 gdzie m=ω(n−−√)m=ω(n)m=\omega(\sqrt n) i a1,⋯,ama1,⋯,ama_1,\cdots,a_m są wybierane losowo z [n][n][n] . Szukam referencji / bezpośredniego dowodu. Skrzyżowane na MO
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.