Chromiczny wielomian kwadratu

Rozważ kwadrat, ABCD. Intuicyjnie wydawało mi się, że jego wielomian chromatyczny to $\lambda(\lambda - 1)(\lambda - 1)(\lambda - 2)$ tam, gdzie dostępne są kolory $\lambda$ ..

Oznacza to, że istnieje $\lambda$ sposobów na wybranie koloru dla A, istnieją $\lambda - 1$ sposoby na wybranie kolorów dla B i D (B i D sąsiadują z A) i $\lambda - 2$ sposoby na wybranie kolorów dla C do być wybranym.

Jednak użycie twierdzenia o dekompozycji (slajd 47, przykład 11.33) i rozłożenie kwadratu na ścieżkę o długości 3 i trójkącie pokazuje, że moje początkowe rozumowanie jest błędne.

Czy mógłbyś mi powiedzieć, gdzie się mylę z moim myśleniem.

Musisz pamiętać, że wierzchołki ukośne od siebie mogą mieć takie same kolory! Twoja formuła tego nie bierze pod uwagę. Możemy znaleźć liczbę chromatyczną wykresu za pomocą zasady włączenia-wykluczenia. Jest to bardzo ogólna technika liczenia, która pozwala nam liczyć złożone struktury, jeśli możemy udowodnić pewne granice określonych podzbiorów.

Główną ideą jest to, że liczymy wszystkie możliwe sposoby, w jakie niektóre nieruchomości się zdarzają. Następnie usuwamy niektóre „złe” elementy. Być może jednak usunęliśmy zbyt wiele i musimy dodać z powrotem kilka „dobrych” przedmiotów. Trwa to w tę iz powrotem, dopóki nie przejdziemy przez wszystkie podzbiory.

Zasada włączenia-wykluczenia mówi nam, że biorąc pod uwagę pewne podstawy , liczba elementów X, które nie znajdują się w żadnym z podzbiorów A i, wynosi ∑ I ⊆ [ n ] ( - 1 ) | $|X|=n$$X$$A_i$

$$\sum_{I \subseteq [n]} (-1)^{|I|}|A_I| \text{, where } \\ I \text{ is the set of indices in } X \text{ and } A_I = \bigcap_{i \in I} A_i$$

Niech będzie liczbą kolorów, a niech X będzie zbiorem wszystkich możliwych kolorów (tj. | X | = λ 4 ), i niech A e = { kolorystyka : e = ( i , j ) ∈ E , kolor $\lambda$$X$$|X| = \lambda^4$

$$A_{e} = \{\text{coloring} : e=(i,j) \in E, \text{color}(i) = \text{color}(j) \}$$

Zanim przejdziemy nasz ostateczny wielomian, musimy liczyć wielkość naszych zestawów e i rozmiar wszystkich podzbiorów przecinających.$A_{e}$

Zauważ, że . Wynika to z faktu, że po prostu farbujemy G, ale zawsze wybieramy te same kolory dla sąsiednich wierzchołków. Idąc dalej mamy,$|A_{12}| = |A_{23}| = |A_{34}| = |A_{41}| = \lambda^3$$G$

$|A_{12} \cap A_{23} | = |A_{23} \cap A_{34} | = |A_{34} \cap A_{41}| = |A_{41} \cap A_{12}| = |A_{12} \cap A_{34}| = |A_{41} \cap A_{23}| = \lambda^2$

$|A_e \cap A_{e'} \cap A_{e''}| = \lambda$$|A_{12} \cap A_{23} \cap A_{34} \cap A_{41}| = \lambda$

$$\lambda^4 - 4\lambda^3 + 6\lambda^2 - 4\lambda + \lambda = \lambda^4 - 4\lambda^3 + 6\lambda^2 - 3\lambda$$

Teraz liczenie z wykluczeniem włączenia dla tego problemu nie było takie złe, ponieważ mieliśmy prosty 4-cyklowy. Gdyby wykres miał więcej struktur, szybko irytujące byłoby ustalenie każdego rozmiaru skrzyżowania dla wszystkich możliwych skrzyżowań.

Odpowiedź przez Mikołaja powyżej i ten pomógł mi zobaczyć lukę w moim myśleniu. Myślałem o bardziej szczegółowym opracowaniu Nicholasa,

Musisz pamiętać, że wierzchołki ukośne od siebie mogą mieć ten sam kolor

a także uzyskać wielomian chromatyczny, dostosowując się do mojego błędnego rozumowania.

$\lambda - 2$$\lambda - 1$

$P(ABCD, \lambda)$
$λ(λ−1)(1)(λ−1) + λ(λ−1)(λ−2)(λ−2)$