圖秩的研究

Abstract

給定圖 $G$ 和體 $F$，$G$ 佈於 $F$ 的最小秩 $mr^F(G)$是所有佈於 $F$ 可決定 $G$ 的對稱方陣中最小的秩。圖的最小秩問題是等價於圖的最大零維數 ($M^F(G)$) 問題。Barioli 等人 [1] 提出圖的參數 $Z(G)$ 作為 $M^F(G)$ 的上界，這篇論文中的目標是[1] 中提出的一個問題︰哪類的圖具有 $Z(G)=M^F(G)$ 的性質。 在第二章中，我們證明了如果 $G$ 是區塊圖，則$Z(G)=M^F(G)$。推廣了 [1] 中的結果。我們也證明了如果 $|F|= infty$ 且 $G$是單位區間圖，則$Z(G)=M^F(G)$。在第三章中，我們證明 $d$ 維的hypercube $Q_d$，$M^F(Q_d)$ 和所佈於的體 $F$ 是無關的，推廣了 [1] 中的結果。我們還提供幾類圖具有 $Z(G)=M^F(G)$ 的性質。在第四章中pp 我們提供幾類圖pp 具有特別形式的最優矩陣。在第五章中，我們研究 cograph 的秩，且回答 Royle [28]所提出的問題。對於 cograph 的秩，我們給予不同的方式證明。

The minimum rank problem is, for a given graph $G$ and a field $F$, to determine the smallest possible rank among all symmetric matrices over $F$ whose off-diagonal pattern of zero-nonzero entries is described by $G$. The solution to the minimum rank problem is equivalent to the determination of the maximum nullity $M^F(G)$ among the same family of matrices. Recently, in [1], a new graph parameter $Z(G)$, the zero forcing number, has been introduced as a technique to bound $M^F(G)$ from above. At the end of the paper [1]} the authors posed the following attractive question: What is the class of graphs $G$ for which $Z(G)=M^F(G)$ for some field $F$? Our goal of this thesis is to investigate which graphs has the property $Z(G)=M^F(G)$ and to determine $M^F(G)$. In Chapter 2, we show that if $G$ is a block-clique graph, then $Z(G)=M^F(G)$. The assertion for block-clique graphs generalizes Proposition 3.23 of [1]. We also show that if $F$ is infinite and $G$ is a unit interval graph, then $Z(G)=M^F(G)$. In Chapter 3, we show that for the $d$-dimensional hypercube $Q_d$, $M^F(Q_d)$ is field independent. This result generalizes Theorem 3.1 of [1] We also give several families of product graphs $G$ which are demonstrated that $Z(G)=M^F(G)$ for every field $F$. In Chapter 4, we give several families of graphs $G$ which has a universally optimal matrix and has field independent minimum rank. In Chapter 5, we answer a question posed by Royle [28] by giving an elementary short proof for a more general setting of this rank property of cographs.