Brouwer for large graphs - Quantum Calculus

Theorem: if a graph G=(V,E) with n=|V| vertices and m=|E| edges and maximal vertex degree d satisfies $n\geq 4d^2$ , then G satisfies the Brouwer conjecture $S_k=\sum_{j=1}^k \lambda_j \leq m+k(k+1)/2=B_k, \forall 1 \leq k \leq n$ .

This adds confidence that the conjecture is true. As mentioned in the video (and now having worked on it for 3 weeks and wrapping up), the conjecture is a bit strange, as it compares convex down spectral function $S_k$ adding up the largest k eigenvalues of the Kirchhoff Laplacian with a concave up function $B_k$ . I had been more familiar with questions relating functions that have the same concavity, like $D_k \leq S_k \leq 2 D_k$ . (Something I worked on in 2022 and was so proud about to submit it to a journal.) Apropos, I think also edge induction works for proving the upper and lower bounds for the eigenvalues (at lest for finite simple graphs). For quivers, there was definitely the need to extend the calculus first like establishing that the Kirchhoff matrix of a quiver can be written as $latex K=F^T F= div(grad).

The proof of the above theorem is in the following video: it was what came out when trying to understand the conjecture. (I think it is always a good attitude at first to approach a problem without fear and have the problem earn respect by battling it.. I still think that a proof of the conjecture is in reach but one never knows. Like in Goldbach, the confidence comes from trying out small cases and arguing that if the objects get larger, the chance of failure gets smaller and smaller that it fails. In the case of Brouwer, the problem has not yet aged long. It is only about 20 years old.

The pictures at the beginning and end were taken on the same Saturday morning. As all summers, I like to make also longer runs when it is hot. Last Tueday, when it was 35 degrees, I had a nice run through Sommerville, Charlestown and Cambridge. There are some nice green parts along the Mystic in Charlestown (some seen on the video I made while flying over it). I like technically simpler math problems like the Brouwer problem because one can think about it and especially about strategies while running.

Author: oliverknill