Gabriel Coutinho

Affiliation: Universidade Federal de Minas Gerais, Belo Horizonte, Brazil

Title: Optimizing sums of eigenvalues

Abstract: In its original proof, Hoffman’s well known lower bound to the chromatic number is obtained after replacing several terms of a sum of eigenvalues by the smallest eigenvalue of the graph. This apparent waste is overshadowed by the fact that so many graphs meet the lower bound with equality, and that its optimized version is in fact equal to the ubiquitous Lovász theta number of the graph.

In this talk, we explore what happens if one decides to not replace all those eigenvalues by the smallest, but still insists in optimizing the bound. We will see that the resulting lower bound is better than the theta number, but no better than the fractional chromatic number. Connections to a variant of the theta number and to the quantum variant of the chromatic number will be made explicit.This talk is based on joint work with M.K. de Carli Silva and R. Grandsire.

You can watch the talk here, meanwhile you can access the slides here1, here2, here3 and here4.

This talk was given on February 7th, 2021

Title: Why are Hoffman’s bounds for alpha and chi truly duals of each other?

Abstract: Two of the most well known eigenvalue bounds for graph parameters look suspiciously related. Our goal in this talk is to confirm this suspicion by casting these bounds into a framework of semidefinite optimization that will give us almost for free a duality relation. As one should always expect in this context, we will see a connection to the Lovász theta function of a graph.

You can watch the talk here, and the slides are available here.

This talk was given on March 29th, 2021

Title: State transfer and the size of the graph

Abstract: If there is perfect state transfer between two vertices at distance d, how small can the graph be compared to d? This question is motivated by the fact that the known infinite families of graphs admitting state transfer at increasingly large distances are all obtained from graph products, thus their sizes grow exponentially compared to their diameter. On the other hand, building quantum systems with many qubits can be expensive. I will show that the size of graphs admitting state transfer is at least cubic in the diameter, and I will also discuss some improvements in the exponential upper bound due to A. Kay. Nevertheless, the question that motivates this talk remains open, and in the end we will discuss some possible research directions.

You can watch the talk here and the slides are available here.

This talk was given on August 17th, 2020