台灣大學數學系

九十一學年度第二學期博士班資格考試題

離散數學

 

May 10, 2003

 

[回上頁]

 

1. (17 %) Suppose $A$ is an $n$-set and $f_m = \vert{\cal F}_m\vert$ for $0 \le m \le 2$, where ${\cal F}_m = \{B: B \subseteq A$ and $\vert B\vert \equiv m$ (mod 3)$\}$. Determine $f_0, f_1$ and $f_2$.

 

  2. (17 %) Recall that Ramsey's theorem is as follows. Suppose $a_1, a_2, \ldots, a_r,t$ are positive integers such that each $a_i \ge t$. There exists a positive integer $n$ with the following property: If all the $t$-subsets of an $n$-set are colored with $r$ colors, then there is an $i$ and an $a_i$-subset all of whose $t$-subsets are colored by the $i$th color. We denote by $R(a_1, a_2, \ldots, a_r; t)$ the smallest $n$ for which Ramsey's theorem holds. (2-1) Prove that for any five points in the plane, no three colinear, some four of the points form a convex quadrilateral. (2-2) Prove that for a set of $n$ points in the plane, if every four points form a convex quadrilateral, then all $n$ points form a convex polygon. (2-3) Prove that for any $R(n,5;4)$ points in the plane, no three colinear, some set of $n$ of the points form a convex polygon. 

 

3. (16 %) Let $d_1, d_2, \ldots, d_n$ be positive integers, with $n \ge 2$. Prove that there exists a tree with vertex degrees $d_1, d_2, \ldots, d_n$ if and only if $\sum_{i=1}^n d_i = 2n-2$. 

 

4. (17 %) A doubly stochastic matrix is a nonnegative real matrix in which every row and every column sums to $1$. Prove that a doubly stochastic matrix $Q$ can be expressed $Q = c_1 P_1 + c_2 P_2 + \ldots + c_m P_m$, where $c_1, c_2, \ldots, c_m$ are nonnegative real numbers summing to $1$ and $P_1, P_2, \ldots, P_m$ are permutation matrices. For example,

$$\left(\begin{array}{clr} 1/2 & 1/3 & 1/6 \\ 0 & 1/6 & 5/6 \\ ... ...in{array}{clr} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{array} \right).$$

5. (17 %) Let $G$ be a graph having no induced subgraph isomorphic to $P_4$. Prove that its chromatic number $\chi(G)$ is equal to its clique number $\omega(G)$. 6. (16 %) The $k$th power of the $n$-path is the graph $P_n^k$ whose vertex set is $V(P_n^k) = \{ 1, 2, \ldots, n \}$ and edge set is $E(P_n^k) = \{ ij: 1 \le i < j \le n$ and $\vert i-j\vert \le k \}$. Determine all pairs $(n,k)$ for which $P_n^k$ is planar. Give reasons.

[回上頁]