Хроматический полином квадрата

Рассмотрим квадрат, ABCD. Интуитивно мне показалось, что его хроматический полином является где есть цвета, доступные ..$\lambda(\lambda - 1)(\lambda - 1)(\lambda - 2)$$\lambda$

То есть есть способы в которых можно выбрать цвет для A, есть способы для выбора цветов для B и D (B и D смежны с A) и пути для цветов для C, чтобы быть выбранным.$\lambda$$\lambda - 1$$\lambda - 2$

Однако использование теоремы разложения (слайд 47, пример 11.33) и разложение квадрата на путь длины 3 и треугольник показывает, что мои первоначальные рассуждения неверны.

Не могли бы вы сказать мне, где я не так с моим мышлением.

Вы должны помнить, что диагонали вершин друг от друга могут быть одинаковыми! Ваша формула не учитывает это. Мы можем найти хроматическое число графа по принципу включения-исключения. Это очень общая методика подсчета, которая позволяет нам подсчитывать сложные структуры, если мы можем доказать определенные оценки для определенных подмножеств.

Основная идея заключается в том, что мы учитываем все возможные способы, которыми происходит какое-либо свойство. Затем мы удаляем некоторые «плохие» предметы. Тем не менее, мы, возможно, удалили слишком много, и нам нужно добавить некоторые «хорошие» элементы. Это продолжается до тех пор, пока мы не пройдем все подмножества.

Принцип включения-исключения говорит нам о том, что с учетом некоторого основания число элементов X, которые не входят ни в одно из подмножеств A i, равно ∑ 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$$

Пусть будет количеством цветов, и пусть X будет множеством всех возможных раскрасок (т. Е. | X | = λ 4 ), и пусть A e = { раскраска : e = ( i , j ) ∈ E , color ( i) ) = цвет ( j ) $\lambda$$X$$|X| = \lambda^4$

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

Прежде чем мы получим наш последний полином, нам нужно посчитать размер наших множеств и размер всех пересекающихся подмножеств.$A_{e}$

Обратите внимание, что . Это связано с тем, что мы просто раскрашиваем G, но всегда выбираем одинаковые цвета для соседних вершин. Мы идем вперед,$|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$$

Теперь подсчет с включением-исключением для этой проблемы не был так уж плох, потому что у нас был простой 4-тактный цикл. Если бы граф имел больше структуры, он быстро стал бы раздражающим, чтобы выяснить каждый размер пересечения для всех возможных пересечений.

Ответ Николай выше , и это одна помогли мне увидеть изъян в моем мышлении. Я подумал о том, чтобы более конкретно остановиться на Николае,

Вы должны помнить, что диагонали вершин друг от друга могут быть окрашены одинаково

а также получить хроматический полином, поправив мои неправильные рассуждения.

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

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