Decision & Control: Graphons and Structural System Theory

Abstract: Graphons have recently been introduced by Lovasz, Sos, etc. to study very large graphs. A graphon can be understood as either the limit object of a convergent sequence of graphs, or, a statistical model from which to sample large random graphs. We take here the latter point of view and address the following problem pertinent to structural system theory: What is the probability that a random graph sampled from a graphon has a Hamiltonian decomposition? We have recently observed the following phenomenon: In the asymptotic regime where the size of the random graph goes to infinity, the probability tends to be either zero or one, depending on the underlying graphon---graphons for which this probability is equal to one are said to have the H-property. In this talk, we establish this “zero-one” property for the class of step-graphons and provide a geometric characterization of the H-property.

Bio: Xudong Chen is an Assistant Professor in the Department of Electrical, Computer, and Energy Engineering at the University of Colorado Boulder. Prior to that, he was a postdoctoral fellow in the Coordinated Science Laboratory at the University of Illinois Urbana-Champaign. He obtained the B.S. degree in Electronics Engineering from Tsinghua University, China, in 2009, and the Ph.D. degree in Electrical Engineering from Harvard University, Massachusetts, in 2014. He is an awardee of the 2020 Air Force Young Investigator Program, a recipient of the 2021 NSF CAREER award, and the recipient of the 2021 Donald P. Eckman award. His current research interests are in the area of control theory, stochastic processes, optimization, network science, and their applications in analysis and control of large-scale multi-agent systems.