La conjetura de Brouwer

En el campo matemático de la teoría espectral de grafos , la conjetura de Brouwer es una conjetura de Andries Brouwer sobre cotas superiores para las sumas intermedias de los autovalores del laplaciano de un grafo en términos de su número de aristas. ^{[ 1 ]}

La conjetura afirma que si G es un grafo simple no dirigido y L ( G ) su matriz laplaciana, entonces sus autovalores λn ( L ( G )) ≤ λn _{− 1} ( L ( G )) ≤ ... ≤ λ1 ( L ₍ G ) ₎ satisfacen $${\displaystyle \sum _{i=1}^{t}\lambda _{i}(L(G))\leq m(G)+\left({\begin{array}{c}t+1\\2\end{array}}\right),\quad t=1,\ldots ,n}$$ donde m ( G ) es el número de aristas de G .

Brouwer confirmó mediante cálculos que la conjetura es válida para todos los grafos con como máximo 10 vértices. ^{[ 1 ]} Posteriormente se demostró que la conjetura también es válida para todos los grafos con hasta 11 vértices. ^{[ 2 ]}

También se sabe que la conjetura es válida para cualquier número de vértices si t = 1, 2, 3, n − 4, n − 3, n − 2, n − 1 y n . ^{[ 3 ]}

Para ciertos tipos de grafos, se sabe que la conjetura de Brouwer es válida para todo t y para cualquier número de vértices. En particular, se sabe que es válida para árboles, ^{[ 4 ]} y para grafos unicíclicos y bicíclicos. ^{[ 5 ]} También se demostró que la conjetura de Brouwer se cumple para dos grandes familias de grafos; la primera familia de grafos se obtiene a partir de una camarilla identificando cada uno de sus vértices con un vértice de un grafo c-cíclico arbitrario, y la segunda familia está compuesta por los grafos en los que la eliminación de las aristas del subgrafo bipartito completo maximal da como resultado un grafo cuyos componentes no triviales son grafos c-cíclicos. ^{[ 6 ]} Para ciertas secuencias de grafos aleatorios, la conjetura de Brouwer se cumple con una probabilidad que tiende a uno cuando el número de vértices tiende a infinito. ^{[ 7 ]}