Доказательство гипотезы Брауэра (ГБ) для всех графов с числом вершин $n>n_0$ в предположении, что ГБ выполняется при $n\leq n_0$ для некоторого $n_0 \leq 10^{24}$

В работе рассматривается проблема построения верхней оценки для суммы максимальных собственных чисел лапласиана графа. Статья посвящена доказательству гипотезы Брауэра, которая состоит в том, что сумма -максимальных собственных чисел лапласиана графа не превышает числа ребер графа плюс \( (t + 1)t⁄2 \). Отметим, что мы доказываем справедливость общей гипотезы Брауэра в предположении справедливости гипотезы для конечного числа графов с числом вершин меньше \( 10^{24 } \), т.е. полное доказательство гипотезы сводится к установлению ее справедливости для конечного числа графов. Доказательство данной гипотезы привлекает интерес большого числа специалистов. Имеется ряд результатов для специальных графов и доказательство справедливости гипотезы для почти всех случайных графов. Рассматриваемое нами доказательство использует индуктивный метод, имеющий ряд особенностей. Оригинальный метод предполагает построение различных оценок для собственных чисел лапласиана, который используется для построения шага индукции. Рассматриваются несколько вариантов метода в зависимости от величин координат собственных векторов лапласиана. Используется известный факт эквивалентности справедливости гипотезы Брауэра для самого графа и дополнения графа.

лапласиан графа, собственные значения

1. A.E. Brouwer, W.H. Haemers, Spectra of Graphs, Springer-Verlag, New York, 2012.

2. W.H. Haemers, A. Mohammadian, B. Tayfeh-Rezaie, "On the sum of Laplacian eigenvalues of graphs", Linear Algebra and its Applications, 432 (2010), 2214-2221.

3. Z. Du, B. Zhou, "Upper bounds for the sum of Laplacian eigenvalues of graphs", Linear Algebra and its Applications, 436:9 (2012), 3672-3683.

4. Mayank, On variants of the Grone-Merris conjecture, Master's Thesis, Eindhoven, 2010, 59 pp.

5. I. Rocha, "Brouwer's conjecture holds asymptotically almost surely", 2019, arXiv: 1906.05368v1.

6. V. Chvátal, P. L. Hammer, "Aggregation of inequalities in integer programming", Ann. of Disc. Math., 1 (1977), 145-162.

7. R. Grone, R. Merris, "The Laplacian spectrum of a graph. II", SIAM J. Disc. Math., 7 (1994), 221-229.

8. H. Bai, "The Grone-Merris conjecture", Trans. Amer. Math. Soc., 363:8 (2011), 4463-4474.

9. A.M. Duval, V. Reiner, "Shifted simplicial complexes are Laplacian integral", Trans. Amer. Math. Soc., 354 (2002), 4313-4344.

10. C. Helmberg, V. Trevisan, "Spectral threshold dominance, Brouwer's conjecture and maximality of Laplacian energy", Linear Algebra and its Applications, 512 (2017), 18-31.

11. C. Godsil, G. Royle, Algebraic Graph Theory, Springer-Verlag, New York, 2001.

12. R. Horn, C. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 2013.

13. V. Blinovsky, L.D. Speranca, "Proof of Brouwers Conjecture (BC) for all graphs with number of vertices n>n_0 assuming that BC holds for n<n_0 for some n_0", 2024, arXiv: 1908.08534v6.