A fractional approach to minimum rank and zero forcing

Thumbnail Image
Date
2015-01-01
Authors
Palmowski, Kevin
Major Professor
Advisor
Leslie Hogben
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Mathematics
Abstract

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.

Comments
Description
Keywords
Citation
Source
Subject Categories
Copyright
Thu Jan 01 00:00:00 UTC 2015