Brouwers gissning

Inom det matematiska området för spektralgrafteorin är Brouwers gissning en gissning av Andries Brouwer om övre gränser för de mellanliggande summorna av egenvärdena för en grafs Laplacian i termer av dess antal kanter.

Gissningen säger att om G är en enkel oriktad graf och L ( G ) dess Laplacian matris, då dess egenvärden λ _n ( L ( G )) ≤ λ _{n −1} ( L ( G )) ≤ ... ≤ λ ₁ ( L ( G )) tillfredsställa

$$\sum _{i=1}^{t}\lambda _{i}(L(G))\leq m(G)+\left({\begin{array}{c}t+1\\2\end{array}}\höger),\quad t=1 ,\ldots ,n$$

där m ( G ) är antalet kanter på G.

Toppmodern

Brouwer har genom beräkning bekräftat att gissningen är giltig för alla grafer med högst 10 hörn. Det är också känt att gissningen är giltig för vilket antal hörn som helst om t = 1, 2, n − 1 och n .

För vissa typer av grafer är Brouwers gissning känd för att vara giltig för alla t och för valfritt antal hörn. I synnerhet är det känt att det är giltigt för träd och för encykliska och bicykliska grafer. Det bevisades också att Brouwers gissningar gäller för två stora familjer av grafer; den första familjen av grafer erhålls från en klick genom att identifiera var och en av dess hörn till en vertex av en godtycklig c-cyklisk graf, och den andra familjen består av de grafer där borttagandet av kanterna på den maximala fullständiga tvådelade subgrafen ger en graf vars icke-triviala komponenter är en c-cyklisk graf. För vissa sekvenser av slumpmässiga grafer stämmer Brouwers gissning med sannolikhet som tenderar till ett eftersom antalet hörn tenderar till oändlighet.