Uncontrollable Networks for Laplacian Leader-Follower Dynamics

a thesis by K.V. Schneider

University of Colorado Boulder - Department of Mathematics - 2021

In 2020 I began a mathematics research project with the University of Colorado Boulder under the mentorship of Professor Sean O'Rourke. In this study, I analyzed some mathematical properties of networks, or graphs as mathematicians prefers. Every network is either essentially controllable, conditionally controllable, or completely uncontrollable. These classes refer to how many of the eigenvalues of the Laplacian matrix of the network have a zero inner product with the non-zero, non-identity binary vectors (Schneider 1.5.2). Sorry, I'm still working on a clean real world analogy for these classes. There are two ways a graph can be completely controllable, either degenerate or nondegenerate. I pondered on the difference between these two frequently during the study.

Use the following two buttons to create a random network. Below is a visual representation of the graph generated along with it's determined controllability class.
Generate new random graph:
Choose number of nodes:
Abstract:

In this paper, we study characterizations of controllability for Laplacian leader-follower dynamics. Our discussion relies on the classification of graphs (networks) into three controllability classes: essentially controllable, completely uncontrollable, and conditionally controllable. In particular, this paper will show characteristics of graphs and their Laplacian matrices which give rise to complete uncontrollability. The controllability classes mentioned require the additional specification of the control vectors; here, we focus on the set of binary control vectors. We show that any Laplacian matrix with repeated eigenvalues will always have completely uncontrollable Laplacian leader-follower dynamics. This fact will allow us to make several deductions regarding the controllability properties of certain graph structures. Specifically, we prove that every circulant graph will have completely uncontrollable Laplacian leader-follower dynamics. We also show that for any biregular graph, if the difference in size between the two vertex sets is greater than one, then the Laplacian leader-follower dynamics are completely uncontrollable. In addition, we prove a similar bound for bipartite graphs in general.

Thanks to Professor Sean O'Rourke, Professor Nathaniel Thiem, and Professor Michael Calkins for taking the time to be on my Thesis Defense Committee.
Special thanks to Professor O'Rourke for mentoring me along this project and meeting with me weekly through COVID-19 quartine.