著色圖的等價類之研究

Abstract

Vogandiagram G 是一種擁有下面兩種性質的 Dynkindiagram。 首先, G 有一個自同構函數 θ 使得 θ^2 = 1; 其次被 θ 固定的點可能是著色或不著色。每一個 Vogandiagram 都會對應一個簡單的實李代數。而我們說兩個 diagram 等價是指它們能表示為同一個李代數。Borel-deSiebenthal 證明每一個有著色點的 Vogandiagram 都等價於恰有一個著色點的 Vogan diagram。蔡孟傑教授和他的學生胡舉卿也利用組合的方法重新證明了這個定理。 本論文主要的工作是將蔡孟傑教授跟胡舉卿的工作描述在更一般圖的情況, 而不只限制在 Dynkindiagrams 上。假設 G 是一個圖, G 的一個著色是指一個函數 c : V(G) → Z_2 , 對於每一個點 i 滿足 c(i) = 1 (0) , 我們稱它為著色 (不著色)。 我們常稱著色 (非著色) 點為黑(白) 點。 我們也常把一個著色 c 所決定的黑點的集合 B 稱為一個著色。 在一個著色 B 中對於每一個點 i, 翻轉點 i 會改變它鄰點的顏色, 黑色的點變白色而白點變黑點。如果一個著色 B_1 能透過一些翻轉之後變成另一個著色 B_2, 則我們說 B_1 等價於另一個著色 B_2 。我們通常以 B_1 ~ B_2 表示 B_1 等價於 B_2 。我們也通常標示 |B| 為著色 B 的黑點個數。 而在一個圖 G 中, 我們用 [B] 去表示包含著色 B 的等價纇。 我們定義 p([B])=min{|A| : A ~ B} 而且 p(G) = max{p([B]): B 是 G 的一個著色 }. 在這篇論文中我們將會討論 p(G) 在一般的圖形上。 特別是在樹圖、圓、 仙人掌圖跟完全多部圖我們都做出了一些結果。

A Vogan diagram is a Dynkin diagram with two extra data: There is an automorphism θ on the diagram with θ^2 = 1, and the vertices fixed by θ may be painted or unpainted. Each Vogan diagram corresponds to a real simple Lie algebra. Two diagrams are said to be equivalent if they represent the same Lie algebra. Borel-de Siebenthal proved that every Vogan diagram with painted vertices is equivalent to one with a single painted vertex. Chuah and Hu reproved the theorem combinatorially. We describe Chuah and Hu's work in a more general setting by considering all graphs rather only Dynkin diagrams. Suppose G is a graph. A painting of G is a mapping c : V(G) → Z_2 , for which vertices i with c(i) = 1 (0) are called painted(unpainted). We also call painted(unpainted)vertices black(white). As a painting c and the set B of all black vertices determine each other, we use B as a painting. For any black vertex i in a painting B, the flip operation F[i] transforms B to the painting BΔN(i),where N(i) = {j : ij in E(G)} and XΔY =(X-Y)∪(Y-X). A painting B_1 is equivalent to another painting B_2 , denoted by B_1 ~ B_2, if B_1 can be transformed to B_2 by a sequence of flips. We also denote |B| be the number of black vertices of painting B. In a graph G, we use [B] to denote the equivalence class containing a painting B. Define p([B])=min{|A| : A ~B} and p(G) = max{p([B]): B is a painting of G}. In this thes is we study p(G) for general graphs. In particular, we establish results on trees, cycles, cacti and complete r-partitegraphs.