Events by date

Title: A recursive spectral bound for independence

Speaker: Bogdan Nica Affiliation: Indiana University-Purdue University Indianapolis Location: Contact Sabrina Lato for Zoom link

Abstract: We discuss an upper bound for the independence number of a graph, in the spirit of the well-known Hoffman bound. Our bound involves the largest Laplacian eigenvalue of the graph; more surprisingly, it also involves the independence number of a certain induced graph. We illustrate the bound on several examples.

Title: k-Connectedness and k-Factors in the Semi-Random Graph Process

Speaker: Hidde Koerts Affiliation: University of Waterloo Location: MC 6029

Abstract: The semi-random graph process is a single player graph game where the player is initially presented an edgeless graph with n vertices. In each round, the player is offered a vertex u uniformly at random and subsequently chooses a second vertex v deterministically according to some strategy, and adds edge uv to the graph. The objective for the player is then to ensure that the graph fulfils some specified property as fast as possible.