Gregory Minton

Harvey Mudd College Mathematics 2008

Thesis Proposal: Proposal: Dot Product Representations of Graphs
Thesis Report: Report: Dot Product Representations of Graphs
Thesis Advisor: Prof. Kimberly Tucker
Second Reader: Prof. Michael Orrison

Dot Product Representations of Graphs

We study dot product representations of graphs. Given a vector space and a graph, a dot product representation of that graph is a mapping from the set of vertices to the vector space such that adjacent vertices have dot product one and nonadjacent vertices have dot product zero. The primary quantity of interest is the minimum dimension over a given field for which a given graph has a representation. In particular, we extend the study of these representations to fields other than the real numbers, looking at the complex numbers, rational numbers, and finite fields.

During this research, we built Java applets to compute the minimum dimension of a dot product representation (called the dot product dimension) over finite fields. The applet for the finite field of order two is here and an applet supporting more finite fields is here. These have basic user interfaces: clicking creates a vertex, which can then be dragged around. Shift-dragging one vertex to another creates an edge. The dot product dimension is reported in the upper-left corner, and (in the second applet) the pulldown selector changes the order of the finite field we work over. Since these applets use expoential-time algorithms (the runtime is roughly proportional to pn, where p is the order of the field and n is the number of vertices in the graph), we recommend not creating too many vertices.

The poster presented on this material at the 2008 AMS/MAA Joint Meetings Undergraduate Poster Session can be found here. The revised poster created for Harvey Mudd College's Presentation Days can be found here.