Важнейшие научные результаты Института математики за 2007 год

1. Доказана теорема, устанавливающая, что нормы корней многочлена над нормированным полем однозначно определены нормами коэффициентов этого многочлена.

Ю. Л. Ершов. Теорема о нормах корней и коэффициентов, ДАН, 417, N 5, 2007, 1-3.

2. Установлены оценки тьюринговой сложности для ряда классов вычислимых моделей высокого ранга.

Найдена точная характеризация тьюринговой степеней и m-степеней сложности индексных множеств всех вычислимых моделей невычислимого ранга Скотта и всех моделей типа Харрисона и всех моделей типа Маккая. Модели типа Харрисона - это вычислимые модели с невычислимым рангом Скотта, когда есть на-боры элементов в этой модели, имеющие невычислимый ранг Скотта. Модели типа Маккая – это вычислимые модели с невычислимым рангом Скотта, когда нет наборов элементов в этой модели, имеющих невычислимый ранг Скотта. Разработаны новые методы построения структур типа Маккая и типа Харрисона. Исследована зависимость определимости классов вычислимых моделей и их алгоритмической сложности через сложность их индексных множеств. Доказана m-полнота индексных множеств для классов разрешимых моделей, разрешимых моделей счетно-категоричных теорий, вычислимых моделей с разрешимыми теориями в соответствующих классах утонченной арифметической иерархии.

Calvert W., Fokina E. B., Goncharov S. S., Knight J. F., Kudinov O. V., Morozov A. S., Puzarenko V. G. Index sets for classes of high rank structures // Journal of Symbolic Logic, 2007, v.72, No.4, 1418-1446.
Фокина Е. Б. Индексные множества разрешимых моделей // СМЖ, 2007, т.48, N 5, 1167-1179.
Fokina E. B. Index Sets of Computable Structures with Decidable Theories// Computation and Logic in the Real World - Third Conference of Computability in Europe, CiE 2007, Siena, Italy, June 2007, Proceedings, Lecture Notes in Computer Science, 2007, 4497, 290-296.

3. Решены известные проблемы существования семейств Скотта и сложности описания определимых отношений в вычислимых моделях для предельных уровней гиперарифметической иерархии.

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

Chisholm J., Fokina E., Harizanov V. S., Knight J. F., Miller S. Intrinsic bounds on complexity and definability at limit levels// Journal of Mathematical Logic, 2007.
Goncharov S. S. Definability Problems over Computable Models// Межд. Конф. «Теория функций, алгебра и математическая логика», посвященная 90-летию академика А. Д. Тайманова, Алматы, 2007, 73-75.

4. Охарактеризована сложность счетных структур, сигма-представимых в наследственно-конечной надстройке над упорядоченным полем вещественных чисел.

Охарактеризованы счетные структуры, сигма-представимые в наследственно-конечной надстройке над упорядоченным полем вещественных чисел, полем комплексных чисел и телом кватернионов. Очевидно, что если мы разрешим использование параметров над вещественными числами, то любая счетная структура конечной сигнатуры имеет такое представление. Если отказаться от параметров, то при определенных условиях любая счетная сигма-определимая над полем вещественных чисел структура констуктивизируема. Однако в общем случае такие структуры будут гиперарифметическими, и гиперарифметика является неулучшаемой верхней оценкой сложности таких структур. Определимость над телом кватернионов ведет себя точно так же, как и определимость над вещественными числами. Замечено, что любая счетная структура, сигмаопределимая над полем комплексных чисел, возможно и с параметрами, констурктивизируема.

Морозов А. С. ДАН 2007, т.416, N 5, 594–596.

5. Описано строение конечных и счетных решёток относительно аксиоматизируемых классов.

Понятие относительно аксиоматизируемого класса алгебраических систем является естественным обобщением таких понятий как аксиоматизируемый класс, многообразие, подмногообразие, квазимногообразие, подквазимногообразие, универсально аксиоматизируемый класс, экзистенциально аксиоматизируемый класс, Π_n-аксиоматизируемый класс, ∑_n-аксиоматизируемый класс. Для квазимногообразий известна открытая проблема Биркгофа-Мальцева: описать решетки подквазимногообразий различных квазимногообразий. Цель данной работы - решить аналогичную проблему для относительно аксиоматизируемых классов. Исследованы решётки относительно аксиоматизируемых классов. Полностью решён вопрос о строении конечных и счетных решёток относительно аксиоматизируемых классов. Доказано, что счетные решетки относительно аксиоматизируемых подклассов некоторых классов - это в точности все счетные полные решетки. Доказано, что конечные решетки относительно аксиоматизируемых классов - это в точности все конечные решетки.

Palchunov D. E. Lattices of relatively axiomatizable classes // Lecture Notes in Artificial Intelligence, 2007, Proceedings, N4390, 221-239.

6. Доказано существование малых стабильных теорий конечного языка, имеющих бесконечный вес.

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

Судоплатов С. В. Малые стабильные генерические графы с бесконечным весом. Двудольные орграфы // Матем. труды. 2006. Т.9, N 2. С. 154-171.
Судоплатов С. В. Малые стабильные генерические графы с бесконечным весом. Безразвилочные орграфы // Матем. труды. 2007. Т.10, N 1. С. 191-207.

7. Установлено, что полная теория (p,1)-стабильна тогда и только тогда, когда она определимо интерпретируется в теории языка, состоящего из одноместных предикатов.

Работа посвящена исследованию одного из вариантов E*-стабильности полных теорий, называемого (p,1)-стабильностью. Целью работы являлось дать описание класса (p,1)-стабильных теорий. Результатом работы является теорема о том, что полная теория T является (p,1)-стабильной тогда и только тогда, когда она определимо интерпретируется в теории T’ языка, содержащего только одноместные предикатные символы.

Русалеев М. А. Характеризация (p,1)-стабильных теорий // Алгебра и логика. 2007. Т.46, Т 3. С. 346-359.

8. Решены проблемы сопряжённости и существования картеровых подгрупп в конечных группах.

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

Вдовин Е. П. Картеровы подгруппы почти простых групп, Алгебра и логика, т.46 (2007), N 2, 157-216.
Вдовин Е. П. О существовании картеровых подгрупп, Труды ИММ, N 1 (2007), 79-88.
Вдовин Е. П. Сопряжённость картеровых подгрупп в конечных группах, Доклады РАН, т.415 (2007), N 3, 300-303.

9. Решены проблема Холла-Виланда-Шеметкова о замкнутости относительно расширений класса конечных групп, для которых верна P-теорема Силова, и проблема Гросса-Мазурова о замкнутости этого класса относительно нормальных подгрупп.

Пусть P – некоторое множество простых чисел. Следуя Виланду, говорят, что для конечной группы верна P-теорема Силова, если все ее максимальные р-подгруппы сопряжены, т.е. имеет место аналог теоремы Силова для р-подгрупп. В обзорном докладе Х. Виланда на Международном математическом конгрессе в Эдинбурге в 1958 году сформулирована проблема, восходящая к работам Ф. Холла: верно ли, что класс групп, для которых верна P-теорема Силова, замкнут относительно расширений? Эта проблема записана Л. А. Шеметковым в Коуровскую тетрадь под номером 3.62. В работе Ф. Гросса 1986 года сформулирована другая проблема, впоследствии также записанная в Коуровскую тетрадь В. Д. Мазуровым под номером 13.33: верно ли, что класс групп, для которых верна P-теорема Силова, замкнут относительно нормальных подгрупп? Доказана теорема, дающая положительное решение обеих проблем.
Теорема. Пусть G – конечная группа и A – ее нормальная подгруппа. Тогда для группы G верна P-теорема Силова если и только если она верна для каждой из групп A и G/A.

Contemporary mathematics, v.402 (2006), 229-265.

10. Для любого множества P простых чисел найден список всех простых групп для которых верна P-теорема Силова. Доказано, что для конечной группы верна P-теорема Силова тогда и только тогда, когда она верна для каждого композиционного фактора группы.

Пусть P – некоторое множество простых чисел. Говорят, что для конечной группы верна P-теорема Силова, если все ее максимальные р-подгруппы сопряжены, т.е. имеет место аналог теоремы Силова для р-подгрупп. Для любого множества P простых чисел найден список всех простых групп для которых верна P-теорема Силова. Доказано, что для конечной группы верна P-теорема Силова тогда и только тогда, когда все ее композиционные факторы лежат в этом списке.

ДАН, т.417 (2007), N 5.

11. Доказана нетеровость по уравнениям свободных разрешимых и близких к ним групп.

Нетеровость группы по уравнениям означает, что всякая система уравнений над этой группой эквивалентна некоторой конечной подсистеме. Это свойство равносильно нетеровости топологии Зарисского над группой. В случае его отсутствия алгебраическая геометрия над группой практически не поддается изучению. Доказанный результат дает надежду, в частности, на возможность построения теории размерности в алгебраической геометрии над указанными группами.

Гупта Ч. К., Романовский Н. С., Нетеровость по уравнениям некоторых разрешимых групп, Алгебра и логика, 46, N 1 (2007), 46-59.

12. Получены двусторонние оценки сложности для счетного семейства трехмерных многообразий Лёбелля.

Для замкнутых ориентируемых трехмерных многообразий С. В. Матвеевым было введено понятие сложности, которое в определенном смысле отражает интуитивное представление о сложности их строения. Проблема оценивания и вычисления сложности является трудной задачей, актуальной в контексте перечисления и классификации трехмерных многообразий. В настоящее время точные значения сложности известны только для табличных многообразий (36820 многообразий сложности не выше 12) и для нескольких серий многообразий с краем. В работе получены двусторонние оценки сложности для счетного семейства замкнутых гиперболических многообразий, называемых многообразиями Лёбелля, обобщающих первый пример замкнутого трехмерного гиперболического многообразия, построенный Ф. Лёбеллем в 1931 г. Оценки сверху основаны на построении фундаментальных многогранников. Принципиальная новизна подхода авторов состоит в том, что оценки снизу основаны на вычислении гиперболических объёмов многообразий.

Веснин А. Ю., Матвеев С. В., Петронио К. Двусторонние оценки сложности многообразий Лёбелля // Доклады РАН, 2007. Т.416. N 3. C. 295-297.

13. Получена количественная характеристика близости геометрий касательных конусов пространства Карно – Каратеодори.

Разработан новый метод для исследования геометрии пространств Карно – Каратеодори. Он позволяет доказать новые количественные характеристики близости как геометрий касательных конусов пространства Карно – Каратеодори, так и геометрий исходного пространства и касательного конуса. Из него выведены фундаментальные результаты теории: теорема Рашевского – Чоу, локальные аппроксимационные теоремы, Ball-Box теорема, оценки для сравнения метрик и др. Разработанные методы также позволяют получить упомянутые результаты при минимальной гладкости векторных полей: класса C^1,α, 0≤α≤1.

Водопьянов С. К., Карманова М. Б. Локальная геометрия многообразий Карно в условиях минимальной гладкости // Докл. АН. 2007. Т.413, N 3. С. 305-311.

14. Построены новые примеры полных римановых метрик с группой голономии Spin(7), которые, в частности, являются решениями уравнений Эйнштейна с нулевой космологической постоянной.

Рассмотрен класс римановых метрик, получающихся гладкими разрешениями конусных метрик над компактными семимерными 3-сасакиевыми многообразиями. Каждая из рассматриваемых метрик задается четырьмя функциональными параметрами, зависящими от переменной, меняющейся вдоль образующей конуса. Получена система нелинейных ОДУ на функциональные параметры, гарантирующая, что рассматриваемая метрика имеет группу голономии Spin(7). Полученная система полностью исследована, и доказано существование однопараметрического семейства попарно негомотетичных метрик с группой голономии Spin(7); исследовано их асимптотическое поведение на бесконечности. В частности, найденные метрики являются решениями уравнения Эйнштейна в вакууме.

Базайкин Я. В. О новых примерах полных некомпактных метрик с группой голономии Spin(7). // Сибирский математический журнал. Т.48 (2007), N 1, С. 11-32.

15. В теории поверхностей при минимальных условиях гладкости доказана устойчивость в теореме Бонне.

Рассмотрены n-мерные поверхности в пространстве Rⁿ⁺¹, параметризации которых суть функции, имеющие обобщенные в смысле Соболева вторые производные, интегрируемые в степени p>n. Он определил первый и второй фундаментальный тензоры поверхности. Условия Петерсона - Кодацци для таких поверхностей выполняются в некотором обобщенном смысле. Ю.Г. Решетняк доказал, что если первый и второй фундаментальный тензор одной поверхности близки к первому, соответственно, второму фундаментальному тензору другой, то поверхности с точностью движения пространства Rⁿ⁺¹ близки друг к другу. Отличие фундаментальных тензоров и близость поверхностьей определяются посредством подходящей W-нормы. Доказательства опираются на принадлежащее Ю. Е. Боровскому обобщение теоремы Фробениуса о вполне интегрируемых системах дифференциальных уравнений. Применяются также интегральные представления функции через дифференциальные операторы, удовлетворяющие условию полной интегрируемости, полученные Ю. Г. Решетняком ранее.

Reshetnyak Yu. G. On the stability in Bonnet's theorem of the surface theory // Georgian Math. J. 2007. V.14. No.3. P. 543-564.

16. Доказано, что каждая ограниченная плоская область однозначно определяется условием (глобальной) изометричности границ в относительных метриках.

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

Коробков М. В. Необходимые и достаточные условия однозначной определенности плоских областей // Доклады АН. 2007. Т.416, N 4. С. 443-445.

17. Доказана регулярность решений систем линейных дифференциальных уравнений при условии медленного изменения старших коэффициентов.

В 2001 году И. В. Скрыпник предложил в качестве важной задачи получить ответы на следующие два вопроса. Насколько условие медленного изменения старших коэффициентов системы l-го порядка, состоящей из k линейных дифференциальных уравнений в частных производных относительно m искомых вещественных (комплексных) функций от n независимых вещественных переменных, существенно в формулировке следующей теоремы (принадлежащей А. П. Копылову)?
Теорема. Если число p>n и коэффициенты системы и правые части ее уравнений – измеримые вещественные (соответственно комплексные) функции, причем эта система удовлетворяет также следующим условиям: (i) она равномерно эллиптическая, (ii) остальные ее коэффициенты и правые части локально суммируемы в некоторой степени q>p, то при условии (iii) достаточно медленного изменения старших коэффициентов каждое W^l_p,loc-решение системы является ее W^l_p,loc-решением. И нельзя ли от этого условия отказаться вовсе? Получен полный ответ на вопросы И. В. Скрыпника (основной результат): отказаться от условия (iii) медленного изменения старших коэффициентов рассматриваемой в этой теореме системы можно только лишь в том случае, когда коэффициенты и правые части вещественны, искомая функция всего лишь одна и порядок системы первый.

Kopylov A. P. Stability and Regularity of Solutions to Elliptic Systems of Partial Differential Equations // In: The Interaction of Analysis and Geometry: proceedings of the International School-Conference on Analysis and Geometry, devoted to the 75th anniversary of Yurii Reshetnyak, August 23-September 3, 2004, Novosibirsk, Russia / V. I. Burenkov, T. Iwaniec, S. K. Vodopyanov, editors. p. cm. (Contemporary mathematics, v.424, Amer. Math. Soc., Providence, RI, 2007). P. 137-153.

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

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

Trakhinin Y. On existence of compressible current-vortex sheets: variable coefficients linear analysis. Arch. Ration. Mech. Anal. 177 (2005), 331-366.
Trakhinin Y. Dissipative symmetrizers of hyperbolic problems and their applications to shock waves and characteristic discon-tinuities. SIAM J. Math. Anal.37 (2006), 1988-2024.
Trakhinin Y. Existence and stability of compressible and incompressible current-vortex sheets. In: Analysis and Simulation of Fluid Dynamics (ed. Calgaro C., Coulombel J.-F., Goudon T.), pp. 229-246. Advances in Mathematical Fluid Mechanics, Ba-sel: Birkhauser Verlag, 2006.
Trakhinin Y. The existence of current-vortex sheets in ideal compressible magnetohydrodynamics. Arch. Ration. Mech. Anal., 68 pages (принята к печати).

19. Завершен цикл исследований асимптотического поведения распределения осциллирующего случайного блуждания с двумя уровнями переключений. В частности, получены асимптотические разложения для достационарного и стационарного распределений в случае, когда расстояние между регулирующими границами неограниченно увеличивается.

Построение и изучение марковских моделей управляемых (или регулируемых) случайных блужданий является весьма важным разделом современной теории вероятностей. Как правило, подобные исследования находят применение в построении стохастических моделей систем массового обслуживания, в задачах теории хранения запасов, в финансовой математике и других областях. В работе изучается марковское случайное блуждание, порожденное суммами независимых случайных величин, скачки которого меняют свое распределение в зависимости от того, в какой из трех зон находится блуждающая частица. Эта модель широко используется в приложениях. Например, легко представить большой склад продукции, в который ежедневно поступают и из которого ежедневно вывозятся партии товара случайного объема. Если количество остающегося на складе товара приближается к нулю, то принимается решение об увеличении поступления (первый уровень регулировки), при затоваривании склада также необходима регулировка (второй уровень). В работах В. И. Лотова и Д. К. Кима разработан сложный аналитический метод анализа введенных процессов в предположении, что расстояние между регулирующими границами неограниченно увеличивается. Конечным итогом явилось нахождение главных членов асимптотики стационарного распределения изучаемого случайного блуждания с двумя уровнями регулировки и полные асимптотические разложения распределения в фиксированный момент времени в достационарном режиме.

Ким Д. К., Лотов В. И. Об осциллирующих случайных блужданиях с двумя уровнями переключений. Математические труды. 2003. Т.6, N 1. С. 34-74.
Ким Д. К., Лотов В. И. Асимптотика стационарного распределения осциллирующего случайного блуждания. Сиб. мат. журнал. 2004. Т.45, N 5. C. 1112-1129.
Kim D. K. Asymptotic analysis of oscillating random walk with two levels of switching. Siberian Advances in Mathematics, 2006, v.16, No 2, 62-92.

20. Для класса цепей Маркова, описывающих динамику изменения качественного или количественного состава биологических популяций, разработаны методы получения оценок для случайного времени попадания в поглощающее состояние. Для двух типов моделей оценено среднее время вырождения и стабилизации популяций.

Для моделей динамики популяций с жестко фиксированным объемом и однополыми частицами разных типов, порождающих потомков своего типа, получена оценка среднего времени фиксации, то есть времени, когда все частицы станут однотипными. При этом все частицы имеют равные возможности, то есть распределение численности потомства и вероятность его отсутствия для всех частиц одинаковы. Фиксацию можно интерпретировать как момент времени, когда вся популяция будет состоять из родственников особи, тип которой случайно победил в процессе случайного биологического отбора. В общем случае формула достаточно сложна, но, если начать с N частиц разных типов, то время фиксации пропорционально объему популяции. Популяции с ограничениями на максимальную численность потомства и возможностью гибели особей, размножающихся независимо друг от друга частиц в каждый дискретный момент времени, с вероятностью единица вырождаются. Численное моделирование таких процессов для популяций среднего и большого размеров практически никогда не приводит к вырождению в силу того, что типичное время вырождения огромно, а также из-за накопления ошибок округления. При выполнении ряда конкретных условий получены экспоненциальные оценки для среднего времени вырождения в терминах стандартных характеристик ветвящихся процессов. Если допустить, что K - верхняя граница численности популяции или ее среднего, то доказано, что для некоторого числа q из интервала (0,1) среднее время вырождения процесса имеет порядок q^-k.

Клоков С. А., Топчий В. А. Оценки среднего времени фиксации в популяциях постоянного объема // Сибирский матема-тический журнал. - т.34, N 6, 2006, с.1275-1288.
Klokov S. A., Topchii V. A. On the Time of Supplanting All Particles by Particles of One Type in a Fixed Size Population.// Si-berian Advances in Mathematics, 2006, vol.16, No.2, p.93-107.
Klokov S. A. Upper Estimates Of Mean Extinction Time Of A Population With A Constant Carrying Capacity. // Submitted.

21. Создан и успешно апробирован пакет программ STEP+, предназначенный для численного исследования автономных систем и систем нелинейных уравнений в зависимости от параметров моделей (моделирование процессов в биологии, катализе, нанотехнологиях и т.д.).

Предлагаемая разработка является переработанной версией под WINDOWS пакета программ STEP. Использование пакета позволяет изучать в рамках модели, представленной автономной системой, такие нелинейные эффекты как гистерезис, сильная параметрическая чувствительность, возникновение автоколебаний и т.д. Для осуществления запуска расчетных программ и задания расчетных параметров задачи с помощью пользовательского интерфейса была создана программа для генерации DLL-библиотеки. Благодаря специальному способу задания правых частей системы дифференциальных уравнений, генератор также находит аналитически матрицу Якоби системы и матрицу частных производных по параметрам. Пакет STEP+ реализован в среде визуального программирования Visual Basic.NET и предназначен для использования в операционной системе WINDOWS 2000\XP. В настоящее время пакет STEP+ используется в Институте цитологии и генетики СО РАН и Московской государственной академии тонкой химической технологии им. М.В.Ломоносова (МИТХТ).

Фадеев С. И., Покровская С. А., Березин А. Ю., Гайнова И. А. Пакет программ "STEP" для численного исследования систем нелинейных уравнений и автономных систем общего вида. Описание работы пакета "STEP" на примерах задач из учебного курса "Инженерная химия каталитических процессов" // Учебное пособие. Новосибирский гос. университет, кафедра дифференциальных уравнений, кафедра катализа и адсорбции. - 1998. -178 с.
Пакет STEP+ выставлен на сайте Института математики им. С. Л. Соболева: http://math.nsc.ru/AP/step/main.htm

22. Получено обобщение теоремы Хайнала-Семереди об уравновешенных раскрасках для графов с данной максимальной степенью на графы с данной суммой степеней концов ребер. Дан полиномиальный алгоритм построения раскраски в условиях этой теоремы.

В некоторых приложениях раскраски как задачи о разбиениях есть дополнительное требование, чтобы цветовые классы были не слишком большими или примерно одного размера. Одной из моделей, учитывающих это требование, является уравновешенная раскраска - правильная раскраска, в которой размеры цветовых классов различаются не более чем на 1. Уравновешенную раскраску графа G можно также рассматривать как разбиение дополнения к G на клики почти одинакового размера. Классическим результатом об уравновешенных раскрасках является теорема Хайнала-Семереди 1970 года, утверждающая, что каждый граф с максимальной степенью не более r можно уравновешенно раскрасить в (r+1) цвет. Мы даем простое доказательство этого результата. Из доказательства легко вытекает полиномиальный алгоритм для таких раскрасок. Также доказано следующее расширение этой теоремы:
Если для каждого ребра xy графа G сумма степеней x и y не превышает 2r+1, то G имеет уравновешенную раскраску в (r+1) цветов.

A. V. Kostochka, G. Yu Extremal problems on packing of graphs // Oberwolfach reports, 2006, 1, 55-57.
A. V. Kostochka, H. Kaul Extremal Graphs for a Graph Packing Theorem of Sauer and Spencer, Combinatorics, Probability and Computing, 2007, 16, 409-416.
A. V. Kostochka, G. Yu Ore-type graph packing problems, Combinatorics, Probability and Computing, 2007, 16, 167-169.

23. Получена новая верхняя оценка для корреляционной иммунности несбалансированных буле-вых функций, улучшающая ранее известные оценки Бирбрауэра и Таранникова. Построен новый класс функций, на которых эта оценка достигается.

Корреляционная иммунность - одна из важнейших характеристик булевой функции в криптографии. Важная задача - построение функций с наивысшей возможной корреляционной иммунностью. Для этого требуются как хорошие конструкции, так и точные верхние оценки на возможное значение иммунности. Получена но-вая верхняя оценка для несбалансированных неконстантных булевых функций, значительно улучшающая ранее известные. А именно, доказано, что корреляционная иммунность такой функции от n переменных не превосходит 2n/3-1. Доказано, что функция, достигающая этой оценки, является совершенной 2-раскраской. Построена новая серия таких функций в размерностях n=12k.

Fon-Der-Flaass D. G. A bound on correlation immunity // Сибирские электронные матем. Известия, 2007, 4, 133-135.
Фон-дер-Флаасс Д. Г. Совершенные 2-раскраски 12-мерного куба, достигающие границы корреляционной иммунно-сти // Сибирские электронные матем. Известия, 2007, 4, 292-295.

24. Для решения задачи двух коммивояжеров с рёберно непересекающимися маршрутами в полном графе с весами 1 и 2 построен полиномиальный алгоритм с гарантированной оценкой точности 6/5.

В полном n-вершинном графе с весами ребер 1 и 2 требуется отыскать два реберно непересекаюшихся маршрута коммивояжера минимального суммарного веса. Известно, что задача NP-трудна. Построен алгоритм с временной сложностью n³ и гарантированной оценкой точности 6/5, наилучшей на настоящий момент.

Гимади Э. Х., Глазков Ю. В., Глебов А. Н. Приближённые алгоритмы решения задачи о двух коммивояжёрах в полном графе с весами рёбер 1 и 2 // Дискретный анализ и исследование операций. Серия 2, 2007, Т.14(2), С. 3-26

25. Предложена новая иерархия мер нелинейности булевых функций. Построены и исследованы бент-функции с более сильными нелинейными свойствами: k-бент-функции.

Одной из важных характеристик булевой функции в криптографии является мера ее нелинейности. Максимальная нелинейность достигается на бент-функциях, вопрос описания которых остается открытым. В рамках теоретико-кодового подхода рассмотрено обобщение класса бент-функций. А именно предложено понятие k-бент-функции - функции максимально нелинейной при k различных типах линейности одновременно. Обычные бент-функции представляют собой класс 1-бент-функций. При k>j класс k-бент-функций является собственным подклассом класса j-бент-функций. Для каждого допустимого k такие k-бент-функции найдены, и исследованы их свойства.

Токарева Н. Н. Бент-функции с более сильными свойствами нелинейности: k-бент-функции // Дискр. Анализ и исслед. операций, 2007, сер.1, Т.14, N4, С. 76-102.
Tokareva N. N. On k-bent functions // Вестник ТГУ. Приложение. 2007. № 23. С. 74-76.

26. Получены достаточные и некоторые необходимые условия существования графа с заданными диаметром, числом вершинной связности и вектором разнообразия шаров.

Пусть T(G)= (t₀,t₁,…,t_d), где t_i - число различных шаров радиуса i в метрическом пространстве обыкновенного графа G диаметра d с метрикой пути. Вектор T(G) называется вектором разнообразия шаров графа G. Доказано, что для любых целых чисел d≥2, k≥1 и целочисленного набора T=(t₀,t₁,…,t_d) такого, что t₀≥t₁≥…≥t_d=1 при t_d-1≥d²k+3, существует граф диаметра d с числом вершинной связности k и вектором разнообразия шаров T. Доказано, что при t₀<(d-1)k+2 графа с такими параметрами не существует.

Рычков К. Л. Об условиях существования графа с заданным диаметром, числом вершинной связности и вектором разнообразия шаров // Дискр. Анализ и исслед. операций, 2007, сер.1, Т.14, N4, С. 43-56

27. Разработан универсальный подход к построению методов интеллектуального анализа данных, основанный на функции конкурентного сходства.

Большое разнообразие методов и алгоритмов интеллектуального анализа данных (Data Mining) свидетельствует об отсутствии единого подхода к решению задач не только разных типов, но и задач одного и того же типа. Предложен подход, основанный на гипотезе о том, что в процессе решения задач классификации, распознавания образов, выбора признаков, прогнозирования и т.п. человек использует один и тот же механизм оценки сходства и различий. Формализация этого механизма имеет вид функции конкурентного сходства (FRiS-функции). Использование FRiS-функции воспроизводит человеческий способ оценки сходства, унифицирует подходы и методы решения задач Data Mining, обеспечивает инвариантность методов к параметрам задач, повышает качество решения известных задач и позволяет решать ряд новых задач (в частности, задачу автоматического выбора числа кластеров и проблему Колмогорова о "пригодности" признаков).

Nikolay Zagoruiko, Irina Borisova, Olga Kutnenko FRiS-Function as Criteria for a Selection of Attributes // Proc. Of 7th Open Russian-Germany Workshop "Pattern Recognition and Image Understanding" (ORGW-07). Karlsruhe, August 2007, p. 3-7. (Пленарный доклад).
Загоруйко Н. Г. Проблемы построения эмпирической теории интеллектуального анализа данных // Материалы Всероссийской конференции с международным участием "Знания-Онтологии-Теории" (ЗОНТ-07). Новосибирск, сентябрь 2007, т.1, с. 4-13. (Пленарный доклад).
Борисова И. А., Дюбанов В. В. Загоруйко Н. Г., Кутненко О. А. Использование FRiS-функции для построения решающего правила и выбора признаков (задача комбинированного типа DX). // Материалы Всероссийской конференции с международным участием "Знания-Онтологии-Теории" (ЗОНТ-07). Новосибирск, сентябрь 2007, т.1, с. 37-44.
Борисова И. А., Загоруйко Н. Г. Функция конкурентного сходства в задаче таксономии // Материалы Всероссийской конференции с международным участием "Знания-Онтологии-Теории" (ЗОНТ-07). Новосибирск, сентябрь 2007, т.2, с.  67-76.
N. Zagoruiko, I. Borisova, V. Dubanov, O. Kutnenko Function of Rival Similarity in Pattern Recognition // Proc. International Conference "Pattern Recognition and Image Analysis" (PRIA-07), Yoshkar-Ola, October 2007, p. 63-66. (Пленарный доклад).
Загоруйко Н. Г. Интеллектуальный анализ данных (ИАД), основанный на функции конкурентного сходства // Журнал "Автометрия" (в печати).
И. А. Борисова, Н. Г. Загоруйко, О. А. Кутненко Критерии информативности и пригодности подмножества признаков, основанные на функции сходства // Журнал "Заводская лаборатория" (в печати).

28. Изучена сложность и найдены решения ряда новых задач комбинаторной оптимизации, возникающих при реализации апостериорного подхода к помехоустойчивому анализу и распознаванию числовых последовательностей, имеющих квазипериодическую структуру; обоснованы точные и приближенные полиномиальные алгоритмы решения этих задач.

Исследуется нетрадиционный комбинаторный подход к проблеме помехоустойчивого анализа и распознавания числовых последовательностей, имеющих квазипериодическую структуру. Анализируются задачи, типичные для широкого спектра приложений (техническая и медицинской диагностика, биометрика, электронная разведка, геофизика), в которых требуется найти и извлечь полезную информацию из дискретных сигналов с целью принятия решения о некотором объекте или явлении. Традиционные подходы к проблеме, опирающиеся на фундаментальные работы Колмогорова, Котельникова, Пугачева, Харкевича, Ширяева, Андерсона, Вальда, Винера, Калмана и др., не требуют решения задач комбинаторной оптимизации. Напротив, реализация изучаемого нетрадиционного подхода сводится к решению этих, как правило, неисследованных экстремальных задач. Совокупность этих задач в настоящее время включает более трех сотен элементов. Установлено, что весомая часть этой совокупности относится к классу NP-трудных задач. Статус вычислительной сложности другой части задач пока не установлен и какие-либо алгоритмы с оценками для их решения неизвестны. Для ряда задач из этой совокупности удалось обосновать точные полиномиальные алгоритмы. Это позволило построить алгоритмы, гарантирующие оптимальность (в смысле максимума правдоподобия) решения следующих задач апостериорного анализа и распознавания числовых последовательностей:
• совместного обнаружения и идентификации квазипериодических фрагментов в последовательности по их обрывкам (случай неизвестного числа фрагментов);
• совместного обнаружения квазипериодических фрагментов из эталонного набора и ее разбиения на участки, включающие серии одинаковых фрагментов (случай неизвестного числа фрагментов);
• распознавания последовательности, включающей серии квазипериодически повторяющихся эталонных фрагментов (случаи неизвестного числа фрагментов);
• обнаружения повторяющегося набора эталонных фрагментов в квазипериодической последовательности (случаи известного и неизвестного числа фрагментов);
• распознавания числовой последовательности, включающей повторяющийся набор эталонных фрагментов (случаи известного и неизвестного числа фрагментов).
Перечисленные результаты, с одной стороны, расширяют совокупность изученных задач дискретной оптимизации, а с другой, - закрывают ряд проблем вычислительного плана в области математических методов апостериорного анализа и распознавания числовых последовательностей. Полученные результаты позволили создать первую версию компьютерной системы QPSLab (Quasi-Periodic Sequences Laboratory) для апостериорного анализа и распознавания числовых последовательностей с квазипериодической структурой. Практическая ценность результатов состоит в том, что они гарантируют получение наилучших (оптимальных) решений для целого ряда типовых задач, возникающих в перечисленных приложениях.

Кельманов А. В., Хамидуллин С. А. Оптимальное обнаружение в числовой последовательности заданного числа неизвестных квазипериодических фрагментов // Сиб. журнал вычислительной математики. 2007, Т.10, N2. С. 159-175.
Kel'manov A. V., Khamidullin S. A. A Posteriori Concurrent Detection and Identification of Quasiperiodic Fragments in a Sequence from Their Pieces // Pattern Recognition and Image Analysis. 2006. Vol.16, No.4, pp. 599-613.
Кельманов А. В., Михайлова Л. В. Распознавание числовой последовательности, включающей серии квазипериодически повторяющихся эталонных фрагментов // Сибирский журнал индустриальной математики. 2007. Т.10, N4 (32).
Кельманов А. В., Михайлова Л. В. Апостериорное обнаружение квазипериодических фрагментов из эталонного набора в числовой последовательности и ее разбиение на участки, включающие серии одинаковых фрагментов // Журнал вычислительной математики и математической физики, 2007. (принята в печать).
Кельманов А. В. Полиномиально разрешимые и NP-трудные варианты задачи оптимального обнаружения в числовой последовательности повторяющегося фрагмента // Тез. докл. Всероссийской конференции "Дискретная оптимизация и исследование операций". Владивосток, 2007. (пленарный доклад).
Кельманов А. В. Проблемы оптимизации в задачах анализа и распознавания последовательностей с квазипериодической структурой // Тез. докл. Российской конференции "Математика в современном мире", посвященной 50-летию Института математики им. С. Л. Соболева СО РАН, 17-23 сентября 2007 г. - C. 268-269. (пленарный доклад).
Кельманов А. В. О некоторых полиномиально разрешимых и NP-трудных задачах анализа и распознавания последовательностей с квазипериодической структурой // 13-я Всероссийская конференция "Математические методы распознавания образов" (ММРО-13). Ленинградская обл., г. Зеленогорск, 2007 г. Сборник докладов. - М.: МАКС Пресс, 2007. - С. 261-264. (пленарный доклад).
Кельманов А. В., Михайлова Л. В. Задача распознавания числовой последовательности, включающей серии квазипериодически повторяющихся эталонных фрагментов. Случай неизвестного числа фрагментов // Тез. докл. Всероссийской конференции "Математическое программирование и приложения". Екатеринбург, 2007. С. 180-181.
Кельманов А. В., Михайлова Л. В., Хамидуллин С. А. Задача апостериорного обнаружения в числовой квазипериодической последовательности повторяющегося набора эталонных фрагментов. Случай заданного числа фрагментов // Тез. докл. Всероссийской конф. "Математическое программирование и приложения". Екатеринбург, 2007. С. 182-183.
Кельманов А. В., Михайлова Л. В., Хамидуллин С. А. Оптимальное обнаружение в квазипериодической последовательности повторяющегося набора эталонных фрагментов // Тез. докл. Всероссийской конференции "Дискретная оптимизация и исследование операций". Владивосток, 2007.
Кельманов А. В., Михайлова Л. В., Хамидуллин С. А. Распознавание числовой квазипериодической последовательности, включающей повторяющийся набор эталонных фрагментов // 13-я Всероссийская конференция "Математические методы распознавания образов" (ММРО-13). Ленинградская обл., г. Зеленогорск, 2007 г. Сборник докладов. - М.: МАКС Пресс, 2007. С. 264-267.
Кельманов А. В., Михайлова Л. В., Хамидуллин С. А. Задача распознавания квазипериодической последовательности, включающей повторяющийся набор эталонных фрагментов // Тез. докл. Всероссийской конференции "Дискретная оптимизация и исследование операций". Владивосток, 2007.
Кельманов А. В., Михайлова Л. В., Хамидуллин С. А. Система QPSLab для анализа и распознавания числовых последовательностей с квазипериодической структурой // 13-я Всероссийская конференция "Математические методы распознавания образов" (ММРО-13). Ленинградская обл., г. Зеленогорск, 2007г. Сборник докладов. - М.: МАКС Пресс, 2007. - С. 594-597.

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

Описание важнейшего результата. Разработаны методы построения гиперкубического (многомерного) представления данных, которое является основой технологии оперативной аналитической обработки данных OLAP (online analytical processing). Предложена и исследована следующая последовательность преобразования данных: RDB -> TJ -> ST -> TJ -> RDB, где RDB - реляционная модель (исходная), TJ - модель 'таблица соединений' (промежуточная), ST - модель гиперкуба 'семантическая трансформация' (целевая). Для модели TJ получены и доказаны свойства, важные для построения преобразований. Разработаны алгоритмы преобразования, переводящие представление TJ к виду, эквивалентному представлению реляционной базы данных после выполнения базисных операций: дополнение, удаление и модификация кортежа. Для этих алгоритмов доказана корректность формирования результата и получены оценки вычислительной сложности, квазилинейные относительно количества кортежей в таблице соединений. Для модели ST получены образы ограничений целостности на данные (функциональные и многозначные зависимости) при их трансформации в гиперкуб. Разработан алгоритм представления формирования ST с использованием контекстных ограничений на данные. В дополнение к традиционным операциям для гиперкуба определен набор операций по модификации данных. Разработаны полиномиальные алгоритмы, реализующие эти операции для моделей ST и RDB.

Зыкин С. В. Формирование пользовательского представления реляционной базы данных с помощью отображений // Программирование. 1999. N3. С. 70 - 80.
Зыкин С. В. Построение отображения реляционной базы данных в списковую модель данных // Управляющие системы и машины. 2001. N3. С. 42 - 63.
Zykin S. V. Formation of Hypercube Representation of Relational Database // Programming and Computer Software, 2006, Vol. 32, No.6. P. 348-354.
Зыкин С. В. Формирование гиперкубического представления реляционной базы данных // Программирование. - 2006. - N6. С. 348 - 354.
Зыкин С. В. Актуализация базы данных в OLAP-технологии // Материалы Всероссийской конференции "Знания - Онтологии - Теории" (ЗОНТ-07), Новосибирск, 2007, Т.1. - С. 73 - 79.

30. В двухдублетной модели Хиггса в электрослабых взаимодействиях найдены необходимые и достаточные условия для реализации экстремумов с разными физическими свойствами как вакуумных состояний Вселенной. Исследованы фазовые переходы в процессе охлаждения ранней Вселенной.

Обсуждаются экстремумы двухдублетной модели Хиггса, которая может описывать нарушение электрослабой симметрии элементарных взаимодействий. Найдены необходимые и достаточные условия для реализации экстремумов с разными физическими свойствами как вакуумных состояний Вселенной. Энергии экстремальных состояний выражены через параметры потенциала, если он явно сохраняет СР симметрию. Эти выражения позволяют избрать вакуумное состояние при данных параметрах потенциала и проследить за их сменой (фазовыми переходами) при эволюции этих констант в процессе охлаждения ранней Вселенной.

Работа принята к печати в Phys. Rev. D.