Chromiczny wielomian kwadratu

11

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 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.

graph-theory colorings

— Abhijith Madhav
źródło

8

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 które nie znajdują się w żadnym z podzbiorów wynosi $|X|=n$ $X$ $A_i$

\sum_{ja \subseteq [n]} (- 1)^{| ja |} | {ZA}_{ja} |, gdzie ja jest zbiorem indeksów w X i {ZA}_{ja} = ⋂_{ja \in ja} {ZA}_{ja}

$\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 będzie zbiorem wszystkich możliwych kolorów (tj. ), i niech $\lambda$ $X$ $|X| = \lambda^4$

{ZA}_{mi} = {kolorowanie : mi = (ja, jot) \in mi, kolor (ja) = kolor (jot)}

$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 i rozmiar wszystkich podzbiorów przecinających. $A_{e}$

Zauważ, że . Wynika to z faktu, że po prostu farbujemy 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$

λ^{4} - 4 λ^{3)} + 6 λ^{2)} - 4 λ + λ = λ^{4} - 4 λ^{3)} + 6 λ^{2)} - 3) λ

$\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ń.

— Nicholas Mancuso
źródło

2

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)$

— Abhijith Madhav
źródło