Исследование квадратичных форм Картана-Титса тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

рV Б ОД з 1 ДВГ да

На правах рукописи

Колмыков Владислав Алексеевич

ИССЛЕДОВАНИЕ КВАДРАТИЧНЫХ ФОРМ КАРТАНА-ТИТСА

Специальность 01.01.06 - математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Москва - 1998

Работа выполнена в отделе алгебры Математического института имени В.А. Стеклова Российской Академии Наук.

член-корреспондент РАН, доктор физико-математических наук, профессор Ю.И. Манин

ведущий научный сотрудник, доктор физико-математических наук В.А. Псковских старший научный сотрудник, кандидат физико-математическ наук И.В. Станкевич

Московский государственный университет

Защита состоится " вЛ/^У-Ч -г ^/^1998 года в часов на заседании специализированного совета Д 002 3802 по присуждению учёной степени кандидата физико-математических наук в МИ им. В.А. Стеклова РАН по адресу: 117966, Москва. ГСП-1, ул. Губки-па, 8 .

С диссертацией можно ознакомиться в библиотеке МИ РАН.

Автореферат разослан "/''' " • 1998 года.

^ Учёный секретарь специализированного совета, доктор физико-математических наук, ведущий научный сотрудник

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. 1) Граф Кокстера1 - это граф, каждому ребру которого сопоставлеп элемент множества {3,4, 5,...,+оо} (называемый порядком ребра). Такие графы играют важную роль в некоторых классификационных вопросах алгебры и анализа. С каждым графом Кокстера С связана (все определения см.ниже) квадратичная форма2 Картана-Тптса 13Среди графов Кокстера центральное место занимают простые и расширенные графы Дынкина3, т.е. связные графы Кокстера. для которых Во > 0, соответственно Вс > 0 (последнее означает У1Вс(х) > О А Зх^0 Вс{х) = 0). Упомянутые объекты играют фундаментальную роль в исследованиях, посвященных алгебре и геометрии простанств с системой отражений.

В 1973 г. И.Н.Бернштейн,И.М.Гельфанд,В.А.Пономарёв опубликовали работу4 , которая уже послужила началом нескольких циклов исследований ряда авторов.Один из её логических ходов явился отправной точкой и для настоящего диссертационного исследования.Суть этого хода в следующем: вектор х определённым образом отклонили от диагонали пространства, на котором определена форма Картана-Титса, при этом количество графов, для которых Вс(х) > 0, резко сократилось. Вероятно.это является частным случаем общего утверждения о классе форм Картана-Титса (ср.ниже теорему 2.3.1). А

В 1994г. было введено* понятие отклонения ш(С) = ¡¿(Во) нулевого конуса Во от диагонали пространства, на котором определена эта форма, и для трёх классов деревьев было найдено выражение ^(С) через топологические характеристики дерева С? (этот результат процитирован ниже в теореме 2.2.3).

2) Первоначально планировалось ограничится написанием небольшой статьи, в которой и)(0) вычислялось бы для всех деревьев и обосновать упомянутый выше эффект сокращения количества графов.

'Бурбаки H. Группы и алгебры Ли. Группы Кокстера и системы Титса. Группы, порожденные отражениями. Системы корней: Пер. с франц - М.: Мир, 1972. - С23

2Бурбаки II. Указ. соч.-С.113. 3Бурбаки H. Указ. соч.- С.241-248.

4Берн:лтей1! И.II., Гельфапд II.N1., Пономарев В.А. Функторы Кокстера и теорема Габриеля // Успехи ыаг. наук. - 1973. - Т.28, вып.2 (170). - С.19-33.

5Колмыков В.А., Купцов B.C., Субботин В.Ф. Об одном инварианте формы Картана-Титса деревьев / Воронеж, гос. ун-т. - Воронеж, 1994. - 15 с. - Деп. в ВИНИТИ 14.01.94, N 222-13?i.

Однако уже на самых ранних этапах изучения отклонения выяснилось, что это понятие многими способами связано с фундаментальными понятиями простых и расширенных графов Дынккпна, а также с другими интересными вопросами математики.

Казалось бы, что простые и расширенные графы Дынкина дои йены играть скромную роль в этих вопросах: самое большее, что можно ожидать, - это какая-то особенность чисел uj(G), где G - граф Дынкина. Однако роль графов Дынкина оказывается неизмеримо большей.

Например, они "управляют" формулами, выражающими lu(T) через другие характеристики дерева Т: формулы различаются в зависимости от того, какому расширенному графу Дынкина "родственно" дерево Т (множество Т всех деревьев естественно разбивается на 5 классов:

т = т> п 4 И ¿т Н4 ]iv

см. теорему 2.1.1 и замечание к ней, и для каждого класса существует своя формула, выражающая и>{Т) через другие характеристики дерева Т (теоремы 2.2.1 - 2.2.3)).

Удивительно и то, что графы Дынкина управляют решениями теоретико -графовых задач типа: найти все деревья, для которых и(Т) € А/, где М - некоторое подмножество R. Беря М равным [2; +оо], (2; +со], Z, {1 + 6 N}, и т.п. всякий раз удавалось найти (вообще говоря многозначную) операцию с>/></ на множестве всех деревьев и набор Рг/тгд/ графов Дынкина так, что и>{Т) £ М <=> Т €Е орм(Т>упм), иными словами и~1{М) - орм(Т>упи) (см.,например теорему 2.5.1.).

Приведем еще один интересный факт, связанный с понятием отклонения.

Среди рассматриваемых форм Картана-Титса мы выделяем класс Z, состоящий из неприводимых форм, сужение которых на диагональ пространства является неотрицательно-определенной формой, Оказывается, что

ui(Z) Г) Z = {1; 2; 3; 4; 6; +оо}.

Множество {1; 2; 3; 4; 6;+оо} часто появляется в разных вопросах математики. Например. {1; 2; 3; 4; 6; +оо} - множество всевозможных

ериодов неустойчивости периодических циклических графов (это — дин из результатов главы 3). Другой пример из классики5 : если п-•анговая решетка Г в Л" устойчива относительно действия группы 5ейля IV, а Счу ~ соответствующий граф Кокстера, то т(и,у) € 1; 2; 3; 4; б; +со} Уи, V (= У{С]у).

Замечание. Упомянутые утверждения о неустойчивости графов I устойчивости решёток опираются (в конечном счёте) на известное ещё пифагорейцам) утверждение: <3 П соз(тгЦ) = {0; ±0,5; ±1}. К гожелешпо. утверждение об и(2) не удалось вывести из того же песочника; найденное доказательство опирается на (не тривиальные) георемы, выражающие отклонение через топологические характеристики.

Цель работы. 1) Исследование отклонения формы Картана-Титса деревьев |вывод универсальной формулы,выяснение структуры множества отклонений деревьев,нахождение связи с известными классическими понятиями). 2) Получение новых классификационных теорем об устойчивости переодических графов.

Методы исследования. Основной результат гл.1 получен методами квадратичного программирования, причём пришлось (§§1.1-1.2) развить эти методы в случае форм и многогранников специальных видов. Многие результаты гл.2 получены при помощи решения диофантовых уравнений и неравенств. Результаты гл.З получены при помощи сочетания классических соотношений (для определителей (Силь-вестр),для многочленов (Чебышев)) и современных формул (для характеристических многочленов (0,1)-матриц (А.Швенк), для характеристических многочленов периодических (0,1)-матрип (В.А.Калмыков и В.Ф.Субботин)).

Научная новизна. 1) Исследована новая задача квадратичного программирования. 2) Для нового (наиболее широкого) класса деревьев выведены формулы, выражающие отклонение через геометрические характеристики. 3) Найдены новые связи понятия отклонения и определённости для форм Картана-Титса. 4) Доказаны новые утверждения о расположении нулевого конуса формы Картана-Титса в пространстве IV1. 5) Выведены новые реккуректные формулы для характеристических многочленов графов. 6) Полученны новые классификационные теоремы об устойчивости переодических циклических графов.

Теоретическая и практическая ценность. Диссертационная работа носит теоретический характер.Её результаты и методы могут быть использованы в разделах математики, изучающих алгебраические и геометрические свойства линейных пространств с системой отражений. Результаты §§1.1-1.2 могут быть использованы в теории и практике квадратичною программирования (в ситуации, когда коэффициенты формы удовлетворяют специальной системе неравенств). Результаты §3.3 могут быть применены в теоретической химии (для описания особенностей химиче-

6Б\<рб;1Ки II Ука.з. соч С.103.

ских связей в молекулах углеводородов с эффектом гг-сопряжения).

Публикации. По теме диссертации опубликовано 11 работ. Кроме этого опубликовано еще две работы, написанные в соавторстве, однако в диссертации использованы лишь формулировки нескольких утверждений из этих работ, которые необходимы для расчетов.

Основные результаты диссертации опубликованы в работах,список которых приводится в конце автореферата.

Апробация работы. Результаты диссертации докладывались па следующих семинарах и конференциях: 1) Семинар А.И. Кострикина (МГУ, май 1993 г.). 2) Семинар Э.Б. Винберга (МГУ, февраль 1998 г.). 3) Воронежская математическая школа "Понтрягинские чтения-YIII" (май, 1997 г.). 4) Межвузовская конференция "Молекулярные графы в химических исследованиях" (Калинин, май 1990 г.)

Структура и объём диссертации. Диссертация состоит из введения, трёх глав и списка цнтированацной литературы. Объём диссертации 75 страниц. Список цитированной литературы - 21 наименование.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Диссертация в основном посвящена исследованию квадратичных форм Картана-Титса и графов Кокстера.

Во Введении освящается история вопроса, приводятся основные определения и результаты. Текст Введения в основном совпадает с текстом настоящего автореферата.

Глава 1, §§1.1-1.2. Исследования точек минимума квадратичной формы на многограннике относятся к теории квадратичного программирования. Эти исследования разделяются на два направления: 1) теоретическое изучение поведения квадратичной формы на многограннике и 2) создание алгоритмов, позволяющих точпо или приближенно находить точки минимума.

§§1.1-1.2 главы 1 представляют теоретическое исследование задачи квадратичного программирования

В{.х) — min, х 6 К = [а, Ь]п, (*)

где 0 < а < b - вещественные числа. Здесь многогранник — это куб в пространстве R", а квадратичная форма В(х) обладает пекоторыми специальными свойствами. Отметим, что в отличие от почти традиционной постановки задач квадратичного программирования, мы не требуем выпуклости вниз функции у = В{х) (т.е. неотрицательной определенности квадратичной формы В(х)).

Несмотря на отказ от выпуклости вниз функции у = В(х), нам все-таки удалось усмотреть и использовать это поистине замечательное свойство — выпуклость, однако, не применительно к функции у = В(х), а к решениям задачи (*). Оказывается, вектора из Rn можно интерпретировать как функции на некотором геометрическом объекте, причем решения задачи (*) будут функциями, выпуклыми вверх (т.е. вогнутыми). В этом п состоит основной технический прием первой главы. Упомянутый геометрический объект — это некий граф (см.ниже), построенный по квадратичной форме В(х).

Всякое решение задачи (*) принадлежит границе ЭК куба К = [а: &]". Это означает, что у всякого решения задачи (*) найдется хотя бы одна координата, принадлежащая множеству {а; &}. Одпако, если форма В(х) — отделенная (определение см. ниже), а относительные размеры кубика К = [а; Ь]п невелики (т.е. l(K) £ < 2), то можно утверждать, что '"большое" число координат решения задачи (*) оказывается равным Ь.

Квадратичная форма В : R" —» R, В(х) = хВх1 (матрица В -симметрическая) называется отделенной, если

Ьц > 0, bij £ (-оо; -^max(bu, bj})] U {0} при i ф j.

Сопоставим форме В граф Gß следующим образом: вершины Gß - это элементы множества {1. 2,..., n}; inj смежны (обозначается ludJ Либо judt), если и тильки если bij < 0.

Пример. В(х) = (2; + ... + х2п) - (xi + xi)x$ - (^з-г-"4 + 14I5 + ... + хп-\хп) (п > 4), Gß = Z 1,1,n-з ~~ трехлучевая звезда с лучами длины 1,1 и гг — 3:

Верпшна г графа Gß называется главной отпосителыю задачи ("), если выполнена импликация {х - решение задачи (*)} => {т,- = 6}.

Смысл слов "большое" число координат оказывается равным Ь" (см. выше) раскрывается тремя нижеследующими теоремами.

Определение. Подмножество множества вершин графа называется выпуклым, если: 1) вместе с любыми двумя вершинами и и v оно содержит все вершины любого простого пути, соединяющего и и v; 2) вместе с любой вершиной и оно содержит и все вершины любого простого цикла, проходящего через и.

Теорема 1.1.1. Если В - отделенная квадратичпая форма, т( множество главных вершин графа Gg является выпуклым.

Определение. Вершина и графа G называется узлом, если е< степень deg и > 3.

Теорема 1.1.2. Если В — отделенная квадратичная форма l(K) d= | < то вешний узел графа Gв является главной верши ной.

Определение. Квадратичная форма называется неприводимо! относительно базиса {/;},• (по умолчанию - относительно некоторой стандартного базиса) пространства, если ни при какой перенумера ции этого базиса матрица формы не является блочно-дпагоналыю! с квадратными блоками на диагонали.

Теорема 1.1.3. Пусть В - неприводимая отделенная квадратич ная форма. Gb ф £u,n-з (п > 4) и 1(К) £ < 2. Тогда всякий узел графа Gß является главной вершиной.

Теоремы §§1.1 - 1.2 используются в § 1.4.

Глава 1, §1.3. Граф Кокстера - это граф без петель и крат ных ребер, каждой паре (и. v) вершин которого сопоставлен элемен' т(и, и) 6 N = {1,2,..., +оо} следующим образом: 1) m(u,v) — 1 4= и = и; 2) т(и. в) = 2 » « п и не соединены ребром и и ф и.

Если и и и соединены ребром, то т(и, и) называется порядког. ребра Ни.

С этого момента и до конца второй главы под словом, "граф (соответственно ''дерево ') понимается конечный граф (соответп стпвснпо конечное дерево) Кокстера. каждое ребро которого имеет, порядок 3.

Пусть G - граф, V{G) - множество его вершин. Через Kai

обычно, обозначается пространство всех вещественных функций, оп ределеиных на множестве V(G). Для элементов пространства Rl удобно использовать обозначения /и вместо /(и).

На пространстве определена квадратичная форма Картана

Титса Ва{х) = - £ xuxvcos-т^у (здесь d= 0). u,u6V(G) '

Диагональ d — {¿(RK'G') пространства R^^' - это {х G RK(G'|xu -xv Vu,v е V(G)} = {ie|i 6 R}, где e(u) = 1. Ясно, что Bc(e) = x(G

(эйлерова характеристика 7 графа G. Известно, что для связного графа G имеем: > 0 G - дерево.

Определение. Форма Вд называется древесной, если G - дерево.

Лемма 1.3.1. 8 Если Вд ~ неприводимая форма Картана-Тнтса, то Bc\d > О Bq древеспа.

Сейчас мы введем "меру отклонения" нулевого конуса 5° *== { х | В ( х ) = 0} древесной формы Картана-Титса В от диагонали d. Пусть Ka{G) =f {х € R/^l 1 < хи < а Vu £ V(G)}.

Прежде, чем давать формальное определение отклопения, поясним в общих чертах, о чем идет речь. Множество В0 нулей квадратичной формы В является конусом. Пусть сужение В на диагональ ¿является неотрицательной формой. Начнем "распускать" куб I\a{G), увеличивая а, до тех пор, пока куб Ka(G) не коснется конуса В0. То значение от, при котором это произойдет (возможно а = 1, если d С В°), и называется отклонением и/(В). Если Ka(G) ни при каком « не пересекается с В0, то отклонение полагаем рапным +со.

Определение.9 Отклонением древесной формы Картана-Титса Вс, (или дерева Кокстера G) называется число

w(B) = и{Ва) = u{G) = sup{a| 1 < ß < а =>

=> 4zeKßiG}BG(x) > 0} e R

Сразу возникает вопрос: для каких деревьев и! = +оо? Оказывается и! = +оо только для графов Дынкина А„, Dn, Ец, Ej, Е$ (см. п.1 теоремы 2.5.1), то есть для тех деревевьев, для которых В > 0.

Глава 1, §1.4. Здесь доказывается важнейшая теорема главы 1, на которой строится дальнейший расчет в главе 2. Суть этой теоремы состоит в том, что если tü(B) ф 4-ос, то куб КЫ(В) имеет в точности одну точку пересечения с конусом BQ, и координаты этой "точки прикосновения" удается выразить через топологические характеристики дерева, ассоциированного с формой В.

Напомним сначала несколько определений из теории графов. Степенью deg и вершины и называется количество примыкающих к пей

7Масси У., Столлингс Дж. Алгебраическая топология. Введение: Пер. с англ.- М.: Мир, 1977. - С.217.

8Колмыков В.А., Купцов В С., Субботин В Ф. Указ. сон.

9Колмыков В.А., Купцов B.C., Субботин В.Ф. Указ. соч.

ребер. Простым путем [и, и] па графе называется множество попарнс различных вершин {шд,..., ги„}, (п > 1) таких, что гио = и, и>п = v, и ivi соединены ребром Уг € {1,...,гг}. Число тг называете! длиной пути [и, и] (или, если - дерево, расстоянием ¿„„от и до « ¿ии 0). Путь [и, и] называется каноническим, если ¿еди, ¿еду ф 1 и (хи 6 [и,«] А ш 0 ¿едги = 2. Концевым путем называете!

канонический путь [гг, и], для которого ¿еду = 1, ¿еди ф 1.

Определение. Выпуклая оболочка (то есть пересечение всех выпуклых надмножеств) множества узлов графа б называется телом графа С; вершины, принадлежащие телу, называются телесными.

Теорема 1.4.2. Если и (С) Ф +оо, то

1) А'ш(о(С) п ВЬ состоит из единственного элемента (обозначаемого хс);

2) Хц = и>(С) для любой телесной вершины и:

3) Если и-концевая вершина концевого пути длиньг I, то х„ = тах( 1. и1{С)/(1 + 1)).

4) Для любого концевого пути [и, у] н любой вершины а этогс концевого пути х% — (х^с1а си иу •

Определение. хс называется точкой прикосновения.

Глава 2, § 2.1. При изучении отклонений выясняется, что множество всех деревьев естественно разбивается на о классов (формулы, выражающие и через другие характеристики дерева, различны для згих классов).

Через т(Т) будем обозначать число концевых путей дерева Т (определение концевого пути см. выше). Звездой (точнее, «-лучевой звездой) .....называется граф. получающийся следующим образом: в графах ... А/,+1 (1 < ¿1 < ... <1е) фиксируется по одной концевой вершине, затем фиксированные вершины отождествляются в одну вершину, называемую центром звезды. Числа 1\, ... называются длинами лучей звезды.

Теорема 2.1.1. Множество Т всех деревьев разбивается на 5 классов:

1) V {т е т\ з„Д, ст} = {гет| т(Т) > 4}.

2) £6 {Т 6 Т - V \Ё6 СТ} = {гм,г\ р > 2}.

3) ¿7 =г {Т 6 Т - V - 41 Е7 С Т V (Ё7 2 Т А Ёй С Т А |К(Г)| >

12)} - {гмА (р = 1, я > 3) V (р = 1, ч = 2, г > 8)}.

4) = £т\ Ё8СТ} = {2М,Г| р = 1, ? = 2; 5 < г < 7}.

5) -р'Мт-Т)- - ¿7 - 4 - {Л,, Д.,Я6,#7,

Замечание.

Нижеследующие 12 утверждений мы приводим без доказательства, так как в дальнейшем мы на них нигде не ссылаемся, а нужны они нам лишь для полноты изложения.

1а) {б £ Т>\ Ва > 0} = {Д}(.

16) V* {(7е £к\ Во >0} = {£'*}.

1в) Из графов класса наименьшее число вершин имеет граф Еь.

2а) ¿в = {гр,я,г\ 1 < и{гм,г) < р + 1}.

26) £т = {2„,,.г| р + 1 < и(%Р1Я:Г) < ? + 1}.

2в) ¿8 = \г,л,г\ ч +1 < < г +1}.

2г) V = {Д„} и г + 1 < и{Яр.,,г) < +оо}.

Коразмерность минимальной по включению грани кубика на которой лежит хс' (точка прикосновения), обозначим сосИтО. Если и(<3) = +оо, то сосИтС "=/ 1.

За) ТеТ<# соИт Т = 1.

36) Т е ¿8 сойгт Т = 2.

Зв) Т е ¿- со(Иш Т = 3.

Зг) соЛт Г — I.

Зд) Т £ Х> сойгтТ > 5 (отметим, что если Г с "С, то сосИтп Т — и + т — У /,.

1=1

здесь и- число вершины дерева, т- число концевых путей. ...../т - длины концевых

путей).

т —1

Определение. Сумму обратных длин концевых путей Е /,• будем называть гармонией дерева Т и обозначать 7'(Т).

Множество V можно разбить па классы Тгп деревьев с тп концевыми путями: V = и^=4Тт.

Определение. Пусть X С К. Наименьший (по включению) из полуинтервалов, интервалов и отрезков (в том числе бесконечных), содержащих Л", обозначим соX (т.к. это - выпуклая оболочка множества X).

Пример. со-у{Тт) = (0;т], со-/(£6) = (0; 1,5], со-у(£7) = (1; 1|].

Введем четыре вещественные функции, которые связаны с классами деревьев и которые будут нам необходимы для выражения ш(Г) через топологические характеристики дерева Т.

Определение, а) (1: Ц^_4({т} х со-у(Тт)) —* Я;

¿(т; 7) = (7 + т)/(7 + /т? -2(7 + т));

6) ё, : соу(£,-) —> Л;

еб(7) = (7 + 3)/(7 + %Д^7)

eib) = (7 + 1)/(7 - 1 + у/2 5 - 1, 57)

¿8(7) = (27 - 1)/(27 - 3 + v/17/3-107/3).

Глава 2, § 2.2. В этом параграфе доказана одна из основных теорем диссертации, выражающая отклонение через другие характеристики дерева, и на которой основано дальнейшее изучение отклонения. Сначала поясним в общих чертах, за счет чего удается выразить и> через другие характеристики. Так как среди координат точки прикосновения xG есть хотя бы одна, рапная ш, а форма Вд содержит всю информацию о G, то мы получаем уравнение, связывающее и с этой информацией: Bq{xg) — Q.

Теорема 2.2.1 Т G V => ЦТ) = +ос.

Теорема 2.2.2. Г € V => ЦТ) = ¿(ш(Т), 7(Т)).

Теорема 2.2.3.10 Т G £к => ЦТ) = {k{l{T)). _

Замечание 1. Напомним, что £> U ¿"5 U £7 U оg U "Р есть разбиение множества б rex деревьев.

Замечание 2. Теоремы 2.2.1-2.2.3 показывают, что л зависит лишь от количества концевых путей т(Т) и их длин Ц, ..., im и не зависит от "более глубокой" структуры дерева.

Глава 2, § 2.3.

Теорема 2.3.1. I) Ц'Р) = +ос: Ц£к) = {v/84-б; З.о: 6};

соЦ£-) = (2;4]; соы(£«) = (л/3;3].

сошф) = (I; 2]; соиз(Т -V) = (1; 6]

2)cou{Tm) = Im (^ я-^ЗШ]

3) Последовательность полуинтервалов {/„} "монотонно стремится к 1", т.е. a) /m+i лежит левее Im; б) Vf>03,v(n > N => /„ С (1; 1-Й))-

4) Для каждого класса Т,п, £к функция, выражающая и через 7 -строго возрастающая.

Глава 2, §§ 2.4-2.5. Как сообщалось в начале автореферата и как показывают приведенные выше теоремы 2.2.1-2.2.3, графы Дынки-на "управляют" формулами, выражающими отклонение ЦТ) через другие характеристики дерева Т (через гп(Т) и 7(Т)).

Вторая неожиданная "встреча" с графами Дынкина происходит при решении теоретико-графовых задач типа: пайти все деревья, для которых ЦТ) 6 М, где М — некоторое подмножество R.

10Колмыков В.А., Купцов B.C., Субботин В.Ф. Указ. соч.

Приведем сейчас лишь наиболее яркие результаты из §§ 2.4 - 2.5.

Выше мы определили s-лучевую звезду Zilt.._jr В дальнейшем удобно полагать — А?+г+ь где 0 < q < г.

Определим многозначное отображение * : Т —♦ Т так: Z*qr — •Zp+i,g+i,r+b ПРП 0 < р < g < г; далее Т* = Т, если Т e.V.

Примеры, а) D\ — -^1,1,1 = ^2,2,2 = Ё$\

б) -4* = {^i,,,r}i+r=n+i; ({А„}„)* = {Zp,q,r}p~i.

Соответствие G *-* Во определяет * на множестве древесных форм.

Напомним еще, что В > 0 означает УхВ(х) > О Л 3I7io В(х) — 0.

Множество древесных форм Картана-Титса, удовлетворяющих условию U, обозначается {U}. Например, {В > 0} означает {Bq\ G G

Теорема 2.5.1.

1) {и (В) = +со} = {В > 0}

2){w(B) > 6} = {В>0}

3) {сj(B) > 2} = {Л > 0} U {В > 0}*

4){ш(В) > 2} = {В > 0}и{В > 0}*

5) {оо (В) > v/З} = {В > 0} U {В > 0}* U {В > ()}" U ...

6) {ui(B) £ Z} = {B>0}U{B>0}*

7) {w(B) € Z} = G {2; 3:4: 6}}

8) и-1 (2) = фп = Dl Щ, Я?, ¿¡} о/'ЧЗ) = Ёв, "-'О*) = Ёт, и;-1(6) = Д

Глава 2, § 2.6. Напомним, что в этой главе мы рассматриваем только формы, ассоциированные с конечными графами Кокстера, все порядки ребер которых равны 3.

Форма Bq называется цептрально-неотрицательно-определенной, если Bc\d > 0- Класс неприводимых центральтю-неотрицательно- определенных форм Картана - Титса обозначим 2.

Заметим, что данное в § 1.3 определение отклонения корректно не только для древесных форм (т.е. для неприводимых форм, для которых Bc\d > 0), но оно корректно и для центрально-неотрнца-тельно - определенных форм. Этим определением мы и будем пользоваться для продолжения функции и на Z. Следующее утверждение является простым следствием теоремы 2.5.1.

Теорема 2.6.1. ш(2) П Z = {1; 2; 3; 4; 6; -fco}.

Глава 3. Введение. Ясно, что строение нулевого конуса Bq и его расположение в пространстве Rl io> относительно куба Ka{G) 11 относительно прямых {R-"}f6i/(G) в значительной степени определяется спектром матрицы формы Bq относительно стандартного базиса пространства Rv Нетрудно подметить, что этот спектр полностью определяется спектром матрицы смежности графа G.

Определение. Пусть G - граф у которого п вершин. Занумеруем числами 1,2,3 ...п вершины графа. Матрицей смежности Ад в этой нумерации называется п х и - матрица, у которой на диагонали стоят нули, а a,-j—ый внедиагональный элемент равен 1, если г-ая и j-ая вершины соединены ребром, и равен 0 в противном случае. Характеристический многочлен матрицы Ас не зависит от того, каким образом мы нумеровали вершины графа. Этот многочлен называется характеристическим многочленом графа G и обозначается G{А), а множество его корней (их п штук с учетом кратности и все они вещественны) называется спектром графа G.

Глава 3, § 3.1. Если М С V'(G'), то через Gм обозначим граф, получающийся из графа G удалением всех вершин v £ Л/. Если а и ß - различные вершины графа G, то через Gaß обозначим граф, получающийся из G удалением вершин а и /3.

Определение. Двукорневым графом с упорядоченными корнями называется граф, в котором отмечены (зафиксированы) две вершины, эти вершины называются корнями, причем один из корней считается первым, другой - вторым. Первый корень G обычно обозначают c*(G), или просто а, если ясно, о каком графе идет речь. Второй корень графа G обозначают ß(G) (или, просто ß).

Теорема 3.1.1.

[£ CWA)]2 - Ga(\)Gß(\) - G(X)Ga,(X).

Суммирование ведется но всевозможным простым путям, соединяющим а и ß.

Глава 3, § 3.2.

Определение. Пусть Н - двукорневой граф с упорядоченными корнями, гс-натуральное число, большее или равное 3. Возьмём п экземпляров графа Н, занумерованных элементами из Zn, затем

проведём отождествление = ЫТЬ+х) Уг, полученный граф обо-

значается Сп[Н].

Пример. Граф Рц состоит из двух вершин, соединенных ребром. Тогда С„[Р-2] - так называемый простой п- вершинный цикл. Такой цикл часто обозначается Сп.

Оказывается, что характеристический многочлен графа Сп[#] можно выразить через характеристический многочлен графа Сп.

Теорема 3.2.1. а) Для тех А € И-, для которых На(Х)Н,?(Л) -Н{\)Нав{\) ф 0,(т.е. Е Н[оД(Л) ф 0) имеем:

С„[Я](А) = ( Е Я[а;Д](А)У (Я-(Л)гТ7АШ-)

\м] ) \ ]

б) Для тех А € К., для которых На(Х)Нр(\) - Н(Х)Нп0(Х) = 0, имеем: Сп[Н}{А) = (Яа(А) + Н0(А) - ХНа0{\))"

Глава 3, § 3.3. Определение. Граф называется устойчивым, если в его спектре нет нуля (пли в эквивалентной формулировке: если его матрица смежности невырождена).

Мотивировка определения. Сопоставим молекуле углеводорода его "углеродный граф" следующим образом: атомы углерода заменим вершинами, а углерод-углеродные связи заменим ребрами. Теоретические распеты для так называемых сопряженных углеводородов показывают, что углеводороды с. устойчивыми графами устойчивее (в различных смыслах этого слова) углеводородов с неустойчивыми графами. Несмотря на довольно сильные допущения, эта модель (так называемая модель Хюккеля) исключительно хорошо согласована с экспериментальными данными, и более того, современная теория углеводородов очень часто опирается на эту модель и соответственно на классическую теорию спектров графов " .

Теорема 3.3.1. Для каждого двукорпевого графа Н с упорядоченными корнями существует р{Н) € N = {1,2,3,... со} такое, что для всех допустимых п (т.е.натуральных п > 3) имеем:

Сп[Н] не устойчив п кратпо р(Я).

Теорема 3.3.2. {р(Н)}н = {1; 2;3; 4; 6;+ос}.

псм., например: Цветкович Д., Дуб М., Захс X. Спектры графов. Тюрг- 1: применение: Пер. с англ. - Киев: Наукова Думка, 1934. - С 244-254.

Основные результаты диссертации опубликованы в работах:

1. Колмыков В.А. Спектры составных графов-Ш (извлечение корня из М{X типы циклической периодичности) / Воронеж, гос. ун-т. - Воронеж, 1985. - 18с. Деп. в ВИНИТИ 18.07.85, N 5255-85.

2. Колмыков В.А. Спектры составных графов-1У (улучшение формул Швенка / Воронеж, гос. ун-т. - Воронеж, 1985. - 6с. - Деп. в ВИНИТИ 18.07.85, N 5256-85,

3. Колмыков В.А. Несколько соотношений для характеристических многочл< нов графов // Математические исследования в химической информатике. - Новос> бирск, 1990. - Вып. 136: Вычислительные системы.- С.35-37.

4. Колмыков В.А. Новые рекуррентные формулы для характеристических мне гочленов графов // Молекулярные графы в химических исследованиях: Тез. дою межвуз. конф. 21-26 мая 1990 г. - Калинин, 1990. - С.36.

5. Колмыков В.А. Спектры периодических графов типа "цикл" и устойч! вость углеводородов // Современные проблемы механики и математической физик1 Тез.докл. (21-28 января 1994 г.).- Воронеж, 1994. - С.54.

6. Колмыков В.А. Топологическое строение множества отклонений фор Картана-Титса деревьев и схемы Дынкина // ХХУ1 Воронежская зимняя матем. тическая школа. - Воронеж, 1994. - С.57.

7. Колмыков В.А. О нулевом конусе формы Картана-Титса // Глобальный стохастический анализ. - Воронеж: Изд-во ВГУ, 1995. - С.51-56.

8. Колмыков В.А. Несколько замечаний о форме Картана-Титса // Н-я Межд; иародная конф. "Алгебраические, вероятностные, геометрические, комбинаторнь и функциональные методы теории чисел": Тез.докл. 25-30 сентября 1995 г. - Вор< неж, 1995. - С.вб

9. Колмыков В.А. Об исследованиях квадратичных форм Картапа-Титса 1 Вестн. Воронеж, гос. уп-та. Сер. 2: Естеств. науки. - 1996. - N 2. - С.205-210.

10. Колмыков В.А. О квадратичпом программировании отделепных форм Воронеж, гос. ун-т. - Воронеж, 1996. - 12 с. - Деп. в ВИНИТИ 29.01.97, N 263 - В9

11. Колмыков В.А. О квадратичпом программировании отделенных форм , "Понтрягинские чтения - УШ" на Воронежской весенней математической шко.1 "Современные методы в теории краевых задач": Тез. докл. (4-8 мая 1997 г.). Воронеж, 1997. - С.73.

Заказ А- -2Л1-Р™ ,2.9. В,......98 г. Тир. 1В0_ экз. Лаборатория оперативной полиграфии ВГУ.