PhD Defence: The Presence of Cliques in Networks and Hyperbolicity Theorems for Choosability with Separation

PhD Candidate: Zhiyuan Zhang

Supervisors: Dr. Anthony Bonato and Dr. Michelle Delcourt

Abstract

In this thesis, we first focus on topics related to complex network modeling and applications, and later on, problems related to graph coloring on surfaces. We introduce the frustum model, a novel, deterministic evolving network model for complex networks inspired by the prevalence of dense substructures in real-world networks. Defined by an evolving rule that mimics the evolution and extension of these dense substructures, we demonstrate that networks generated by the frustum model exhibit important complex network properties, such as densification and the small-world property.

To complement our theoretical analysis of the frustum model and support its key motivation, we conduct an empirical study on the emergence of dense substructures using the graphlet counting method. This method characterizes a network by the frequency of small graphs' appearance and has been shown to be effective for measuring networks with different features. The computational expense had become the largest barrier to its application. As a computationally cheaper counterpart, we restrict the method to counting only various-sized cliques, which serve as a simplified representation of dense substructures. We investigate the role of clique counts in real-world network data and their robustness in measuring network similarity. 

We then study a list-coloring problem for graphs on surfaces when every two lists of adjacent vertices have at most one shared color, known as the choosability with 1-separation. In 1997, Thomassen famously proved the 5-Choosability Theorem for planar graphs via an innovative precolor extension method; this method has found various applications since then. Based on the precoloring extension method, Postle and Thomas introduced the hyperbolic structural theorems, a topological framework for coloring problems for graphs on surfaces. This framework has structural and algorithmic implications for any coloring problem whose critical graphs exhibit a certain isoperimetric property. We show that the hyperbolic structural theorems apply to 4-choosability with 1-separation for graphs on surfaces. We conclude with a chapter of open problems.