Characterizing Singular Graphs with Games

Original graphs provided by the authors and redesigned by Eileen Odanaka Vavra

A FIRST-PERSON REPORT FROM A MATH STUDENT AND FACULTY RESEARCH GROUP

APRIL 2023
BY Riley Lane and Giovani Thai

Cal Poly provides unique opportunities for students to participate in research, and our math team had the fortune to be part of the 2022 Frost Summer Research Program. Our project was related to graph theory and game theory using methods to prove the non-singularity of various graph families.

Graph theory is a subject with numerous applications including networking and big data. A graph is defined by a set of vertices and an edge set that tell which vertices are adjacent to each other. For example, the Facebook social network graph can be represented by each person’s profile being a vertex, with edges between if people are “connected” or “friends” on Facebook.

Consider the following example of three people on Facebook: Archimedes, Blaise and Carl. Blaise is a friend of both Archimedes and Carl, but both Carl and Archimedes are only friends with Blaise. This can be represented in the graph to the right.

Each graph can be represented by an n×n matrix, with an entry of 1 if the vertices are connected by an edge and 0 if the vertices are not connected. In the Mathematica computation program, we can use a MatrixPlot function to show a black square if there is an entry of 1 in the matrix or white if the entry is 0.

Game theory is a broad field related to analyzing probabilities and determining expected outcomes when making decisions in competitive situations. Rock, paper, scissors (RPS) is a simple example of a two-player, zero-sum game. The term zero-sum simply means that one player's loss is the other's gain. The possible outcomes of RPS can be encoded in a 3x3 matrix, which is shown to the right. Our research hinged on the theory of these types of matrix games.

The ultimate goal of the project was to prove the non-singularity of the adjacency matrices for specific graph families. To do so, we analyzed a particular matrix game associated with a graph. The steps involved were generating data through computer exploration via Mathematica, conjecturing the best combination of rows and columns as probability vectors and then proving the optimality of our conjectures.

A non-singular matrix is one that has a multiplicative inverse, which means you can find another matrix so that when you multiply with the original, you obtain the identity matrix.

We know that in the real number system, every number other than zero has an inverse under the operation of multiplication. For example, consider the number 2.
The inverse of 2 is ½, because 2 ^. 1/2 = 1, where the number 1 is the identity element under multiplication in the real numbers.

In the context of linear algebra, the identity matrix is an n×n matrix with 1s along the main diagonal. The identity matrix represents the identity element with the operation of matrix multiplication. When seeking to prove the non-singularity of graph families, one way of interpreting this is that we proved for every graph belonging to a specific family, there exists a matrix that we could multiply to the original graph’s adjacency matrix to produce the identity matrix.

The inspiration for the project came from a theorem developed by Lloyd Shapley and Robert Snow in the 1950s. The Shapley-Snow theorem implies that if optimal play requires a player to use every choice with positive probability, then the associated game matrix must be invertible. Therefore, we analyzed a modified game where the row player was forbidden from selecting a specific vertex from the graph and then showed that this must strictly decrease the value of the game.  
One extremely useful idea in our research was to utilize regular partitions of our vertices to condense exceptionally large adjacency matrices into much smaller ones without losing crucial information.

Imagine a tangled set of cords in your living room. You’re trying to connect both your video game console and surround sound system to your TV. In your left hand, you have multiple cords linking your video game to your TV; in your right hand, you have multiple cords linking your surround sound to the TV. Our method condenses each bundle of cords into one cord in each hand. Using this analogy, we group together vertices and condense them to create an intersection probability matrix, which represents the likelihood that a vertex in one group will be connected to a vertex in another. Doing so allows us to simplify the problem while simultaneously retaining vital information to prove non-singularity.

Our team of three undergraduates (Lane, Thai and Matthew Moscot) and one graduate student (Cameron Klig) was led by mathematics Professor Jeffrey Liese. Together, we collaborated and brainstormed how to approach each graph family. Having diverse mathematical backgrounds not only gives everyone the opportunity to learn about various math fields and the connections between them, but also lets everyone contribute their own knowledge and creativity to find innovative approaches.

This research has given us the opportunity to present at both Cal Poly’s Frost Research Poster Symposium and the first CSU Mathematical Conference in Northridge, California.

Research contact: Jeffrey Liese, jliese@calpoly.edu