The Minimum Rank Problem Over Finite Fields

We have two main results. Our first main result is a sharp bound for the number of vertices in a minimal forbidden subgraph for the graphs having minimum rank at most 3 over the finite field of order 2. We also list all 62 such minimal forbidden subgraphs and show that many of these are minimal forbidden subgraphs for any field. Our second main result is a structural characterization of all graphs having minimum rank at most k for any k over any finite field. This characterization leads to a very strong connection to projective geometry and we apply projective geometry results to the minimum rank problem.

Name thesis:degree_name

PhD

Grantor dc:publisher

Brigham Young University - Provo

Author dc:creator

• Grout, Jason Nicholas

• minimum rank
• symmetric matrix
• forbidden subgraph
• field of two elements
• finite field
• projective geometry
• polarity
• rank 3
• Mathematics

Language dc:language

English

Repository record dc:identifier

https://scholarsarchive.byu.edu/etd/982

OAI identifier oai:identifier

oai:scholarsarchive.byu.edu:etd-1981