Finding the maximal independent sets with dynamical systems

Abstract

Finding maximal independent sets is a classical problem in graph theory. In this thesis, we extend the related concepts in graph theory to k-uniform hypergraphs, attempting to find the maximal independent sets in hypergraphs using a dynamical systems approach. We establish a new method for transforming the maximal independent set problem into differential equations using the competitive Lotka-Volterra equations, commonly used in mathematical ecology, and we show that the trajectories of these systems can converge to a state that represents the indicator of a maximal independent set. In addition, we discuss the application of this method in combinatorics and establish a connection between this approach and the Lagrangian method for finding maximal cliques in k-uniform hypergraphs.