Date of Award
Doctor of Philosophy
This thesis applies techniques from fractional graph theory to develop fractional versions of graph parameters related to minimum rank and zero forcing. Projective rank, a graph parameter with applications to quantum information, is formally related to $r$-fold generalizations of orthogonal representations for graphs. Using similar techniques, fractional minimum positive semidefinite rank is defined via $r$-fold generalizations of faithful orthogonal representations and $r$-fold minimum positive semidefinite rank, and it is shown that the fractional minimum positive semidefinite rank of any graph equals the projective rank of the complement of the graph. An alternate characterization of $r$-fold minimum positive semidefinite rank that considers the ranks of certain Hermitian matrices is also presented. Motivated by the connections between zero forcing games and minimum rank problems, an $r$-fold analogue of the positive semidefinite zero forcing process is introduced and used to define the fractional positive semidefinite forcing number of a graph. An analysis of the $r$-fold positive semidefinite forcing game leads to a three-color forcing game that allows computation of fractional positive semidefinite forcing number without appealing to the $r$-fold game. The three-color approach is applied to the standard zero forcing game and it is shown that the skew zero forcing number of a graph is exactly the parameter obtained by applying the fractionalization technique to the standard zero forcing game. Graphs whose skew zero forcing number equals zero are characterized via the three-color approach and an algorithm.
Kevin Francis Palmowski
Palmowski, Kevin Francis, "A fractional approach to minimum rank and zero forcing" (2015). Graduate Theses and Dissertations. 14924.