О комбинаторной структуре непримитивных параллелоэдров первого типа тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

Механико-математический факультет

На правах рукописи УДК 511.9+514.174+519.17

Большакова Елена Алексеевна

О КОМБИНАТОРНОЙ СТРУКТУРЕ НЕПРИМИТИВНЫХ ПАРАЛЛЕЛОЭДРОВ ПЕРВОГО ТИПА

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертация иа соискание ученой степени кандидата физико-математических наук

г*

Москва 2006

Работа выполнена на кафедре дискретной математики Мех&нико-математичес-кого факультета Московского государственного университета имени М.В. Ломоносова,

Научный руководитель: доктор физико-математических наук,

профессор | С.С. Рышков |

Официальные оппоненты: доктор физико-математических наук

А.М. Райгородский

кандидат физико-математических наук Ф.Я. Ветухновский

Ведущая организация: Ивановский государственный университет

Защита диссертации состоится 17 ноября 2006г. в 16 часов 15 минут на заседании диссертационного совета Д.501.001.84 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, Механико-математический факультет, ауд. 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 17 октября 2006г.

Ученый секретарь диссертационного совета Д.501.001.84 в МГУ, профессор В.Н. Чубариков

Общая характеристика работы

Актуальность темы

Параллелоэдром п измерений называется n-мерный ограниченный выпуклый многогранник, параллельными копиями которого можно без пропусков и перекрытий по внутренним точкам замостить все п-мерное евклидово пространство Е™.

В XIX веке в классических работах Е.С. Федорова1 и Г. Минковского* были заложены начала теории параллелоэдров. Особо значительное продвижение в этой теории совершил в начале XX века Г.Ф, Вороной3.

Большой класс параллелоэдров составляют так называемые области Дирихле-Вороного точечных решеток. Вопрос о том, исчерпываются ли ими все парал-лелоэдры, до сих пор открыт. Вороной показал, что аффинно эквивалентны ЛЖ-областям все примитивные параллелоэдры4, O.K. Житомирский несколько расширил этот класс3, Б.Н. Делоне дал доказательство8 для всех параллелоэдров размерности п < 4 .

Одной из основных задач, связанных с параллелоэдрами, является перечисление всех их разновидностей. Полное описание трехмерных параллелоэдров дал Федоров7, все четырехмерные параллелоэдры перечислил Делоне3.

Чаще всего параллелоэдры классифицируют по ¿-типам. Первоначально это понятие определил Вороной. В дальнейшем оказалось, что удобно различать геометрический и арифметический ¿-типы параллелоэдра.

Перечисление L-типов пятимерных примитивных параллелоэдров выпол-

'Е.С. Федоров Начала jrWKtt» о фигурах // Петербург, 18S5; М.; Л.: Иад-во АН СССР. 195$. 410 е.; B.C. Федоров Правильное деление плоскости и пространства // Л., "Наука", 1979, 272 е..

'О. Minkowski Algtmeine LehrtSUe Cher die konvexen Polyeder // Nachrlchten von det K.GeseHschaft der Wlwenschaften zu Gittlngen, Mathem.-phyaikalLsche Klasse, 1S97, S.198.

*Г.Ф. Вороной Исследован ил о примитивных параллелоэдрах // Собр. соч., т. 2, Киев, Иэд-во АН УССР, 1952, с. 239-368.

''Г.Ф. Воронов Исследованил а примитивных ялраллелоэдрах // Собр. соч., т. 2, Киев, Изд-во АН УССР, 1952, с. 239-363.

"О. Zltomlrskij Verthdrfung emea SaUet von Woronoi (O.K. Житомирский Обобщение одной теоремы Вороного) // Журнал Ленинградского фнэико-матеыатнческого общества, 1929г. т. П, вьш. П, с. 131-151. (Journal de 1» Société Physico-Mathématique de Léningcade t. П, fasc. П).

*B. Delaunay [B.N. Deione] Sur la partition réguliire l'espace л 4 dimensions // Известия AH СССР, Овд. Фиэ.-Мат. Наук. - 1929. - »1 - С.79-110, - №2 - С.147-164.

ТЕ.С. Федоров Правильное деление плоскости и пространства j j Л., "Наука", 1979,272 е..

'Б.Н. Делоне Геометрия пожхмеителъмых квадратичных форм // УМН, 1937, вып. 3, С. 16-92, 1938, вып. 4, с. 102-164.

нили С.С. Рышков и Б.П. Барановский®, а также, независимо, швейцарский геометр П. Энгель10. Результаты этих двух исследований не совсем совпадали (221 и 223 типа примитивных пятимерных параллелоэдров соответственно), сравнение предпринял В.П. Гришухин11. Итогом стало уточнение: существует ровно 222 типа примитивных пятимерных параллелоэдров.

В последнее время изучение DV-областеЙ решеток сведено к изучению сумм Минковского конечного для каждого п числа так называемых коренных параллелоэдров благодаря теореме о коренных параллелоэдрах, сформулированной Рышковым11. Окончательные формулировки и подробные доказательства этой теоремы были опубликованы13 в 2005г.

Тем не менее, найти общий конструктивных подход ко всем параллелоэдрам затруднительно. Поэтому изучаются и отдельные классы параллелоэдров. В частности, интерес вызывают параллелоэдры, являющиеся зовоэдрами (эоно-эдральные параллелоэдры).

Исследованиями условий, необходимых или достаточных для того, чтобы зоноэдр был параллелоэдром, занимались H.S.M. Сохе ter14, П. Макмюллен11, G.C. Shephard18. Зоноэдральные параллелоэдры тесно связаны с дайсинтами17, кроме того, существует соответствие между стандартными системами зонных

'Барановекий Е.П., Рышков С. С. Примитивные пятимерные параллелоэдры/J Доклады АН СССР, 212(í) (1973), 532-535; Ç.C. Рышков, Б.П. Барановский С-типы п^мернхлх решеток и пятимерные примитивные параллелоэдры (с приложением к теории покрытий) ff Труды МИАН СССР, 137 (1976), 1-133.

"Р. Engel The contraction types of paraltdohedra in R5 // Acta Cryst. A., 56 (2000), 491-496.

"P. Engel, V. Grishukhin There are exactly £22 L-typu of primitive five-dimensional lattice) ff Europ. J. Combinatorics, 23 (2002), Ï75-279.

"С.С. Рышков О структуре примитивного параллелоэдра t» о последней проблеме Вороного // УМН, 1998,. Т.М, вып. 2(320}, с. 161-162; С.С. Рышков Прямое геометрическое описание произвольного n-мерного параллелоэдра второго типа Вороного ff Успехи матем. наук, -1999. - т. 54, вып. 2. - с. 13-19; С.С. Рышков Коренные параллелоэдры и вершины областей типа п-мерных параллелоздров ff Материалы VII Международного семинара "Дискретная математика и ее приложения", Издательство центра прикладных исследований при механико-математическом факультете МГУ, 2001, 279-281.

"С.С. Рышков, Е.А. Большакова К теории коренных параллелоэдров // Известия РАН сер. матем., т. 69, №6,2005, с. 187 - 210.

"H.S.M. Conectar The cioaiification of tonohedra by meant of projective diagram* // J. Math. Pures Appt., 41 (1962), 137-156.

"P. McMuUen Space tiling lonotopa ff Mathematika 22 (1975), 202-211.

"G.C. Shephard Space-filing lonatopes ff Mathematika, 21 (1974), 261-269.

"R.M. Erdahl, S.S. Ryshkov On Lattice dicing ff Europ.J.Comblnatorics, IS (1994), 459-481; R.M. Erdahl Zonotopes, and Voronoi'* conjecture on pandlelohedra // Voronoi'a impact on modem science. Book IL Eds. P. Engel and H. Sjrta. National Academy of Sciences of Ukraine. Institute of Mathematics. Kyir: Institute of Mathematics, 1998. 61-74; FUM. Erdahl Zonotopes, dicing», and Voronoi 'j conjecture on parallelohedra ff Europ. J. Combinatorics 20 (1999), 527-549.

векторов зоноэдральных параллелоэдров и регулярными матроидами18.

В настоящее время исследованиями по перечислению комбинаторных типов зоноэдральных параллелоадров занимается П. Энгель'9. Это перечисление выполняется в результате компьютерных расчетов. В настоящее время расчеты проведены вплоть до размерности S.

Научная новизна

Основные результаты, полученные в диссертации, являются новыми и состоят в следующем.

1. Построен метод установления комбинаторной структуры параллелоэдра первого типа по его символу;

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

3. установлено, что непримитивные параллелоэдры первого типа комбинаторно эквивалентны тогда н только тогда, когда соответствующие грани областей первого L-типа целочнсленно унимодулярно эквивалентны.

Методы исследования

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

Теоретическая и практическая ценность

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

"V. Daoilov, V. Criahulthln Maximal iinimodular system of vectors // Europ. J. Combinatorics

20 (1999), 507-526.

"P. EageL Mathematical problems in modem crystallography // Comput. Math. Appl., IB (1985), 425-436, P. Engel, L. Michel, M. Senechal Lattice Geometry // IHES preprint, В ures-sur-Yvette, 2003.

Апробация работы

Результаты настоящей диссертации неоднократно докладывались автором на семинарах механико-математического факультета МГУ: на семинаре академика О.Б. Лупанова "Математические вопросы кибернетики", на семинаре "Дискретная геометрия и геометрия чисел" поя руководством С.С. Рышкова, Н.П. Дол-билина и Н.Г. Мощевитика, а также на конференциях: на коллоквиуме в Венском Техническом Университете (Вена, октябрь 2004г.), на 6-й международной конференции по геометрии и топологии (Черкассы, Украина, сентябрь 2005г.), на Международная научной конференции "Современные проблемы математики, механики, информатики", посвященная 86-летию со дня рождения профессора C.B. Стечкина и 75-летию ТулГУ (Тула, ноябрь 2005г.), на международной научной конференция "Аналитические и комбинаторные методы в теории чисел н геометрии" (Москва, май 2006г.).

Публикации

Результаты диссертации опубликованы в работах (1-4], список которых приводится в конце автореферата.

Структура и объем работы

Диссертация состоит из введения, 3 глав и списка литературы, включающего 38 наименований. Общий объем диссертации 86 страниц.

Краткое содержание диссертации

Первая глава глава косит технический характер. Она посвящена сравнению различных определений DV-области и ¿-разбиения, соответствующих положительно определенной квадратичной форме (ПКФ).

Определение (Г.Ф.Вороной). Многогранник DVq„ (соответствующий положительно определенной квадратичной форме (ПКФ) /) есть множество точек а, заданных координатами (аи с*г,..., о^) в ортонормированием базисе £, удовлетворяющими неравенствам

f(x) + 2(ог, а;) > 0, х 6 Zn. (1)

ZJVgp-разбиение получается переносом многогранника DVgp на все векторы вида М, где t € Z", А ~ матрица ПКФ /.

Определение (Б.Н.Делоне). Многогранником ОУдн или областью Дирихле-Вороного некоторой тонки N решетки Г называется совокупность точек рассматриваемого п-мериого пространства, каждая из которых отстоит от точки N «г дальше, чем от любой другой точки решетки Г.

Совокупность ОУдн~оЪ ласте в всех точек решетки образует D разбиение. Это разбиение можно подучить переносом £5 Уд „-области начала координат на все векторы решетки.

Теорема 1. Разбиения DVgp, DУдневклидова пространства и измерений, отвечающие одной и той же ПКФ, аффинно эквивалентны друг другу.

Кроме того, в первой главе рассматривается определение области Дирихле* Вороного, данное Венковым20. Оказывается, что эта область не совп^ц&ет ни с DVgp-, ни с ОУдн- областью, хотя и аффинно им эквивалентна.

Далее, рассматривается взаимосвязь между определениями i-разбнения по Вороному и Делоне (они не совпадают, но аффинно эквивалентны), и £-типа ПКФ (совпадают).

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

Вторая и третья главы посвящены непримитивным параллелоэдрам первого типа.

Среди всех областей ¿-типа наиболее простое описание имеет' область первого типа, при любом п представляющая собой симплициальный конус. Ей принадлежат квадратичные формы, представимые следующей суммой, в шторой формально полагается ю = 0:

f(xi,хг,,..,хп) = ~^i)1- гДе АУ > 0, A¡y > 0. {*)

MS.A. Венков О проектировании пароляелоэЭрое // Избранные, труды, Ленинград, "Наука", Ленинградское отдаление 1981, с. 362-379.

11 С.С. Рыщков О структуре примитивного параллеаоэдра и о последней проблеме Вороного // УМН, 1998, Т.53, выл. 2{320), с. 161-162, С.С. Рытков ¡Трямое геометрическое описание произвольного n-мерном параллелоздра второго типа Вороном Ц Успехи матеы. наук, -1999, - т. 54, вып. 2. - с. 18-19, С.С. Рышков Коренные плраллелоэдры и вершины областей типа п->«p«titr параллелоэдроа // Материалы VII Международного семинара "Дискретная математика к ее приложения", Издательство центра прикладных исследований при механико-математическом факультете МГУ, 3001, 279-281.

исм. ссылку 13.

Параллелоэдры, соответствующие квадратичным формам ранга 1 от п переменных суть отрезки. Таким образом, все параллелоэдры первого типа суть суммы Минковсхого отрезков, т.е. зоноэдри.

Поскольку параллелоэдры, соответствующие точкам одной и той же открытой грани области ¿1, отличаются друг от друга только метрическими характеристиками, достаточно описать структуру одного параллелоэдра из этого множества, отвечающего "эталонной" квадратичной форме, а разложении (*) которой каждый коэффициент Ау равен либо 0, либо 1.

Такие параллелоэдры (и квадратичные формы) описываются символом Рыш-кова: для квадратичной формы / от п переменных это граф с вершинами «о, VI, ..уп, в котором ребро (и*, г^) присутствует тогда и только тогда, когда в разложении (*) формы / коэффициент Ау равен 1.

Вторая глава посвящена построению метода явного описания структуры произвольного непримитивного п-мерного параллелоэдра первого типа по его символу. &гот метод существенно опирается ка результаты о коренных парал-лелоэдрах.

Вводится естественное понятие ранга символа.

Определение. Рангом символа называется размерность соответствующего ему параллелоэдра (то есть ранг соответствующей символу "эталонной" квадратичной формы).

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

Утверждение 1. Пусть символ С? имеет £ вершин и г компонент связности. Тогда ранг символа С? равен {— г.

Далее, для изучения А-мерных граней зоноэдрального параллелоэдра, порожденного системой отрезков 3, требуется рассмотрение неисполнимых подсистем системы 5, имеющих ранг к. Для того, чтобы отыскать такие подсистемы по известному символу, вводится понятие ¿-вырезов и ¿¡-остатков графа (символа).

Определение. Множество Д(С)с£ ребер произвольного простого разреза графа С = (V, Е) будем называть 1-вырезом в графе О.

Определение. Граф Сг = (V, £'\Л(С)), получающийся удалением из графа С = (V, Е) некоторого 1-выреза Й(С), будем называть 1-остатком (от) графа С.

Определение. Назовем к-остатком графа С при 2 < к < п (где « -ранг символа б) всякий 1-остаток от какого-либо (к - 1)-остатка графа О.

Определение. Назовем к-еырезом Л* (С) в графе <2 объединение 1-вырезов Д(С), Л(£7г),.,£(£?*_!), выбранных соответственно из графов <7, <?1 = 0\И(С), вг = СЛК(С1).....= вк.М(Ск.г)-

Кроме того, ¿-вырез будем называть реалшовапным последовательно-

стью 1-вырезов Д(<7), ...,

Между (п — ^-остатками символа и ¿-зонами граней соответствующего па-раллелоэдра существует взаимно однозначное соответствие:

Теорема 2. Пусть V - параллелоэдр первого типа, соответствующий символу й, а Р - его грань размерности к £ п. Тогда определяющим параллелоэдром для грани Р (и для всякой другой грани параллелоэдра V, параллельно конгруэнтной грани Р, то есть для всей к-зоны, которой принадлежит грань Р) служит параллелоэдр, отвечающий некоторому (п — А:) -остатку графа С.

Обратно, если - (о - к)-остаток (к > символа О о ~Р(п~к) - соответствующий ему параллелоэдр, то в параллелоэдре V есть к-зона граней, определяющим параллелоэдром для которой служит *Р(п-к) •

Для нахождения всех индивидуальных граней в ¿-зоне требуется изучение различных ориентаций ребер символа, входящих в соответствующий (п — вырез.

Всякий 1-вырез Я(С) порождает разбиение множества верщин V графа С на два непересекающихся подмножества \\ и Ц (К и ^ = V), обладающих тем свойством, что множество ребер 1-выреза Я(<?) совпадает с множеством всех таких ребер графа С, что одна из вершин ребра принадлежит множеству а другая - множеству Ц: И{С) = {(«(, € Е \ 6 VI , €

Определение. Допустимой ориентацией 1-выреза Я(С?) в графе ¿7 назовем такое приписывание направлений всем ребрам, входящим в этот вырез, что все начальные вершины ребер находятся в множестве К или же все начальные вершины находятся в множестве Ц.

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

1. Выбор реализации ¿-выреза: Л*(С) = Я((?)и.Я(Сч)и... иД{С*_1).

2. Выбор последовательно для каждого 1-выреза Д(С), .. допустимой ориентации (соответственно в графах й, £?ь ...,

3. Приписывание каждому ребру х, принадлежащему ¿»вырезу того направления, которое оно получило на шаге 1 при выборе допустимой ориентации соответствующего 1-выреза.

Ориентации ¿-выреза Я* (С), которые не могут быть получены в результате выполнения шагов 1-3, допустимыми не являются.

Направленному ребру (г^, и£) будем ставить в соответствие вектор рц = - е*). Ребру (шГЙ) ставится в соответствие вектор ры = -рц = 1(е* - а).

Определение. Вектором (пространства Еп), представляющим ориентированный допустимым образом Л-вырез Д*(£?) (А; > 1) назовем сумму векторов, соответствующих ребрам этого ¿-выреза:

Отклоняющими вектором грани с центром симметрии О? параллелоэд-ра V с центром симметрии О-р будем называть вектор х — ОрО?,

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

Теорема 3. Пусть V - параллелоэдр первого типа, С - его символ, -это (п — А)-вырез в графе (7, и - соответствующий (п — к)-остаток, V, - параллелоэдр, отвечающий символу Сп-ь> Среди к-мерных граней параллелоэдра V, параллельно конгруэнтных параллелоэдру V,, тогда и только тогда есть грань с отклоняющим вектором х, когда существует такая допустимая ориентация (п — ¿)-выреза Лп_к, что х = _ е<)> где (гч,-

ребра ориентированного (п — А:)-выреза Л™-*, а еьез,...,е„ - координатные векторы.

Таким образом, чтобы перечислять все грани в А:-зоне, достаточно найти все допустимые ориентации соответствующего (п — ¿)-выреза. Для формулировки конструктивного критерия допустимости ориентации выреза вводится понятие когерентной ориентации ¿-выреза (которое выделяет некоторый класс ориентация, содержащий в себе все допустимые).

Определение. Пусть Л*(<?) - ¿-вырез в графе <7, а <?* - соответствующий ему ¿-остаток. Назовем ориентацию ребер ¿-выреза Я*((?) когерентной, если для любых двух различных компонент связности Н\ и Н% в графе справедливо одно из трех утверждений:

- ¿-вырез Д*(<?) не содержит ребер, соединяющих компоненты Я| и Н%,

— все ребра ¿-выреза соединяющие компоненты и Яг, выходят из Н\ и входят в Яг,

- все ребра. выреза Я*(С), соединяющие компоненты Н\ и Я3р выходят из #2 и входят в Н\.

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

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

Определение. Стягиванием в графе С = {V, Е) множеств вершин VI С V, VI с V, ..С V, обладающих тем свойством, что Ц П V, = 0 при г Ф у и !Х1 К — V, будем называть переход к графу & = (V, Е1), образованному следующим образом: V = {и^,....О, & = {К.«;) I € Е, 6

Уи V; 6 1$).

Бели вершины графа (7 были помечены, вершину VI графа С считаем помеченной всеми пометками вершин из множества Ц,

Определение. Символом ¿-выреза в символе £? будем называть

граф, получающийся из графа С стягиванием по множествам вершин компонент связности А-остатка = С7\Д*{<?).

Очевидно, имеет место взаимно однозначное соответствие между всеми когерентными ориентацнями выреза и всеми ориентациями символа этого выреза.

Следующая теорема дает критерий допустимости ориентации ¿-выреза в графе (символе).

Теорема 4. Пусть Як - неориентированный вырез в графе (7, а 3 - его символ. Тогда

1. всякой допустимой ориентации выреза Д* (и, тем самым, грани па-раллелоэдра "Р, соответствующего символу С) соответствует такая ориентация символа 3, что в нем нет ни одного орцикла;

2. обратно, всякой ориентации символа Збез орциклов соответствует допустимая ориентация выреза Л* (и, тем самым, отклоняющий вектор некоторой грани параллелоэдра V).

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

Определение. Будем говорить, что для ориентированного некоторым образом символа 3 = {II, £>) некоторого А-выреза в графе О допустимо ориентированное стягивание ребра (и^ и]) 6 О {его направление не существенно), если для каждой вершины и графа 3, за исключением вершин щ и щ, верно одно из трех утверждений:

1. Вершина ti соединена ребром не более чем с одной из вершин щ и Uj.

2. Оба ребра (а, щ), (u.uj*) исходят из вершины и (т.е. имеют вид {«, t^),

<=гн5».

3. Оба ребра (u, Uj), (и, Uj) входят в вершину и (т.е. имеют вид («JT^))-

Бели это условие выполнено, ориентированным стягиванием ребра (ui,uj) в графе J назовем переход к графу J' =• (U',D')> образованному следующим образом:

ГУ = Р \ {(«(.«j» \ {(ui,Ti)|ti € D) \ {(u;,u)|u 6 У,(щ,и) € D) U

{(«*,1|)|(5ГЙ) € D или (577Й) € D) U {(гм?)|{5Г35) € D или (tvÎ) € £>}.

Вершину и* получившегося графа считаем помеченной объединением тех множеств, которыми были помечены вершины щ и щ.

Будем также говорить, что граф G допускает ориентированное стягивание на граф G\ если можно из графа G последовательными ориентированными стягиваниями ребер получить граф, изоморфный G'.

Теорема 5. Пусть V - параллелоэдр, соответствующий символу G, a « Fi - его грани. Пусть грань Fi описываете* ориентированным символом J\ выреза Rk(G), а грань Fi - ориентированным символом Jj выреза ft^iG).

Грань Fi является гранью грани F\ тогда и только тогда, когда символ Jj допускает (как граф) стягивание на символ J\.

Также во второй главе рассмотрены примеры.

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

Определение. Пусть G» = (Ц, E-i) и Gt = (Ц, E-Î) - два графа. Отображение <р : Ei —.► Ei множества ребер первого графа в множество ребер второго графа сохраняет простой цикл С графа Gi, состоящий из ребер хц xt, s*, если ребра <р(х\), <p(xi), ..., <p(xk) образуют, возможно в другом порядке, простой цикл в графе Gj.

Определение. Назовем два графа Gi = (Vj, £"i) и Ga = (Vî,£s) циклически неразличимыми, если между ребрами одного н другого графа установлено взаимно однозначное соответствие <р : Е\ -+ Ез, удовлетворяющее условию: отображение <р сохраняет все простые циклы графа G\, а обратное отображение <р~г : Et —> Ei сохраняет все простые циклы графа Gj.

Теорема б (Основная). Пусть С?1 и О; - два символа первого типа, /[ и /г - соответствующие им квадратичные формы первого типа, а Т\ и Ту - соответствующие параллелоэдры, Тогда следующие три утверждения эквивалентны;

1. Параллелоэдры Т\ и Тг комбинаторно эквивалентны.

2. Символы <?1 и С?1 циклически неразличимы.

3. Квадратичные формы /х и /г целочисленно унимодулярно эквивалентны.

Импликация 3=^1 теоремы 6 практически очевидна, особенно если принять во внимание, что двум целочисленно унимодулярным квадратичным формам соответствуют конгруэнтные решетки, а значит, и конгруэнтрые параллелоэдры (в определениях Делоне).

Для доказательства импликации 1 2 важно следующее утверждение.

Утверждение 2. Пусть Сп+\ - кольцо ранга п (то есть (п + \)-вершинное), Тс - параллелоэдр, соответствующий символу Ся+1. Пусть также С? - некоторый символ первого типа, То ~ соответствующий ему параллелоэдр, и пусти параллелоэдры Рс « То комбинаторно эквивалентны. Тогда граф О также является кольцам нвп+1 вершине.

Импликации 2 3 дано два доказательства, опирающихся на теорему Уит-ни44. Первое из них проще, зато второе попутно положительно решает вопрос о возможности согласованной с отображением <р ориентации двух циклически неразличимых графов.

Пусть С? = (У,Е)~ граф, V1 и и"-две его вершины, \\ я У3 - такие множества вершин, что VI иН — УД {«Л К П Ц = 0 и в графе С? нет ни одного ребра ввда (п,где VI € Кь щ 6 Уа.

Определение. Обобщенным переключением в графе £7 = (V, Е) по паре вершин ^гг', Vй) с вариантным множеством \\ будем называть переход к графу

Теорема Уитни о циклически неразличимых графах. Один из двух циклически неразличимых графов можно превратить в другой последовательностью обобщенных переключений.

ИН. Whitney 2-iscmorphic graphs // Amer. J. Math., 55(1933), Л» 2, 245-254.

G = ('V,E), где

А именно, если £?1 и Сз - циклически неразличимые графы, то существует последовательность обобщенных переключений, преобразующая граф Да в изоморфный графу (?1, то есть

С?! Бт*^, (3«г{„ .. (**)

Импликация 2^3 следует, например, из теоремы Уитни и следующего утверждения.

Утверждение 3. Пусть символ <?з получается из символа СI переключением по паре вершин то есть (?з = ^^^(Сх).

Тогда соответствующие квадратичные формы /1 и /1 целочисленно унимоду-лярно эквивалентны.

Доказательство этого утверждения конструктивно: в явном виде указывается целочисленное унимодулярное преобразование переменных, переводящее квадратичную форму Д в /3. Композиция таких преобразований, соответствующих всем переключениям в соотношении (*»), и дает преобразование для пары циклически неразличимых символов.

Для второго доказательства импликации 2 => 3 вводится понятие согласованной ориентации циклически неразличимых символов.

Пусть С?1 и Са - циклически неразличимые графы, ребрам которых приписаны некоторые направления. Пусть С1 - простой цикл в графе (?1, а Ох -соответствующий ему простой цикл в графе (?£.

Определение. Будем называть циклы С\ и Сч сонаправленными, если для заданного направления обхода цикла С\ существует направление обхода цикла Сг, для которого выполнено следующее:

если при обходе цикла С\ ребра 11, ха,х* направлены "по обходу", а ребра у\, уг,..., у! - "против обхода" (в порядке, не обязательно совпадающим с указанным), то при обходе цикла Са ребра 9(21), <р(хз).....<р(х*) также направлены

"по обходу", а ребра • ■ ^(ш) ~ "претив обхода" {в порядке, не

обязательно совпадающим с указанным или с тем, в котором их прообразы входят в ЦИКЛ С]).

Импликация 2^-3 основной теоремы следует из двух утверждений:

Утверждение 4 (Эквивалентность согласованно ориентированных символов). Пусть = (V, Е) и Сг = ((/, I?) - циклически неразличимые, согласованно ориентированные символы.

Тогда существует целочисленное унимодулярное отображение, переводящее символ С?1 в символ бг-

Утверждение 5 (Существование согласованной ориентации). Пусть и <?з - циклически неразличимые графи. Тогда существует их согласованная ориентация.

Теорема Унтни используется для доказательства существования согласованной ориентации.

Второе доказательство во многих случаях дает более удобный способ явного указания целочисленного у ни модулярного преобразования для пары циклически неразличимых символов (?1 и С?г: согласованная ориентация часто строится просто "на глаз", а после этого достаточно выбрать каркас в символе (?ь соответствующий ему каркас в символе С?з и решить несложную систему уравнений для нахождения преобразования для этой пары каркасов.

Наконец, в третьей главе приведены аналоги теоремы 6 для случая, когда рассматриваются не только "эталонные" квадратичные формы из замкнутой области первого типа, а также для случая, когда квадратичные формы первого типа принадлежат не обязательно главной области.

Теорема 7. Пусть /> и /з - две квадратичные формы первого типа, представленные в виде разложения (*), не обязательна "эталонныеД[ и Д? -открытые грани главной области первого типа, которым принадлежат эти формы. Пусть также и Р2 - параллелоэдры, соответствующие квадратичным формам Л и Л, аС\ и Сг - символы этих граней Д[ и Д^. Тогда следующие три утверждения эквивалентны;

1. Параллелоэдры "Р\ и Рг комбинаторно эквивалентны.

2. Символы и Съ циклически неразличимы.

3. Грани Д} и А* целочисленно унимодулярно эквивалентны.

Теорема 8. Пусть Л и /з - две квадратичные формы первого типа, не обязательно из главной области, Д{ и Д? - открытые ерами областей Ь-типа, которым принадлежат эти формы. Пусть также Р£ и * параллелоэдры, соответствующие квадратичным формам и /г, Параллелоэдры *Р\ и Яг комбинаторно эквивалентны тогда и только тогда, когда гран и Д[ и Д' целочисленно унимодулярно эквивалентны.

Следует заметить, что теорема 8 положительно решает вопрос об эквивалентности понятий комбинаторного типа и ¿-типа параллелоэдров в частном случае (непримитивных параллелоэдров первого типа).

Автор глубоко благодарен Сергею Сергеевичу Рышков^, своему научному

руководителю, за постановку задач и постоянное внимание к работе, а также всему коллективу кафедры дискретной математики механико-математического факультета МГУ за внимательное отношение и доброжелательную атмосферу.

Работы по теме диссертации

[1] Е.А. Большакова ОУ-разбиение и £,-разбиение по Г.Ф. Вороному, Б.И. Делоне и Б.А. Венкову // ЧебышевскиЙ сборник 2004г. т.5 вып. 2(10), с.30-41.

[2] Е.А. Большакова Непримитивные п-мерные параллелоэдры первого типа: комбинаторика и символтк // Успехи математических наук, т. 61, вып. 3, 2006г., стр. 167-168.

(3| Е.А. Большакова О параллелоэдрах, связанных с некоторыми графами Ц Тезисы докладов 6-ой международной конференции по геометрии и топологии, Черкассы, 2005, с. 10-11.

[4] Е.А. Большакова О структуре параллелоэдров первого типа и о связанных с ними графах // Тезисы докладов международной научной конференции "Современные проблемы математики, механики, информатики", посвященной 85-летию со дня рождения профессора С.Б.Отечкина и 75-летию ТулГУ, Тула, 2005, с. 59-62.

Подписано а печать/^" /£> ££> Формат 60x84/16. Усл.нсч.л. "Пфаж {£>6 экз. Заказ Отпечшно а Отделе печати МГУ

Введение

1 Различные определения DV- области и L-разбиения: по Г.Ф. Вороному, Б.А. Венкову, Б.Н. Делоне

1.1 Основные разбиения, связанные с ПКФ.

1.2 1Ж-разбиения

1.3 L-разбиения.

1.4 Дуальность.

1.5 L-типы.

2 Установление комбинаторной структуры непримитивного параллелоэдра первого типа по его символу

2.1 Первый тип параллелоэдров и его символ.

2.2 О расположении в n-мерном пространстве параллелоэдров, соответствующих правильным квадратичным формам ранга к < п.

2.3 Суммы Минковского отрезков (зоноэдры).

2.4 Ранг символа.

2.5 Вырезы и остатки в символах.

2.6 Зоны граней.

2.7 Отдельные грани.

2.8 Инцидентность граней.

2.9 Примеры

3 Критерий комбинаторной эквивалентности параллелоэдров первого типа, заданных символами

3.1 Определения, формулировка основной теоремы.

3.2 Из комбинаторной эквивалентности парал л елоэдров следует циклическая неразличимость символов

3.3 Из циклической неразличимости символов следует целочисленная унимодулярная эквивалентность квадратичных форм.

3.4 Согласованная ориентация двух символов.

3.5 Основная теорема без ограничения рассмотрения только "эталонными" квадратичными формами.

Параллелоэдром п измерений называется n-мерный ограниченный выпуклый многогранник, параллельными копиями которого можно без пропусков и перекрытий по внутренним точкам замостить все п-мерное евклидово пространство Еп.

В XIX веке в классических работах Е.С. Федорова [1, 2] и Минков-ского [3] были заложены начала теории параллелоэдров. Особо значительное продвижение в этой теории совершил в начале XX века Г.Ф.Вороной [4].

Большой класс параллелоэдров составляют так называемые области Дирихле-Вороного точечных решеток. Вопрос о том, исчерпываются ли ими все параллелоэдры, до сих пор открыт. Вороной показал, что аффинно эквивалентны DV-областям все примитивные параллелоэдры [4], Житомирский несколько расширил этот класс [8], Делоне дал доказательство для всех n-мерных параллелоэдров при п < 4 [6].

Одной из основных задач, связанных с параллелоэдрами, является перечисление всех их разновидностей. Полное описание трехмерных параллелоэдров дал Федоров [2], все четырехмерные параллелоэдры перечислил Делоне [9].

Чаще всего параллелоэдры классифицируют по L-типам. Первоначально это понятие определил Вороной. В дальнейшем оказалось, что удобно различать геометрический и арифметический L-типы па-раллелоэдра.

Перечисление L-типов пятимерных примитивных параллелоэдров выполнили Рышков и Барановский [10,11], а также, независимо, швейцарский геометр П. Энгель [15]. Результаты этих двух исследований не совсем совпадали (221 и 223 типа примитивных пятимерных параллелоэдров соответственно), сравнение предпринял В.П. Гришухин [16]. Итогом стало уточнение: существует ровно 222 типа примитивных пятимерных параллелоэдров.

В последнее время изучение .DV-областей решеток сведено к изучению сумм Минковского конечного для каждого п числа так называемых коренных параллелоэдров благодаря теореме о коренных парал-лелоэдрах, сформулированной Рышковым [25, 26, 27]. Окончательные формулировки и подробные доказательства этой теоремы даны в [28].

Тем не менее, найти общий конструктивных подход ко всем па-рал л елоэдрам затруднительно. Поэтому изучаются и отдельные классы параллелоэдров. В частности, интерес вызывают параллелоэдры, являющиеся зоноэдрами (зоноэдральные параллелоэдры).

Исследованиями условий, необходимых или достаточных для того, чтобы зоноэдр был параллелоэдром, занимались H.S.M. Coxeter [13], П. Макмаллен [23], G.C. Shephard [22]. Зоноэдральные параллелоэдры тесно связаны с дайсингами [19, 20, 21], кроме того, существует соответствие между стандартными системами зонных векторов зоно-эдральных параллелоэдров и регулярными матроидами [24].

В настоящее время исследованиями по перечислению комбинаторных типов зоноэдральных параллелоэдров занимается Энгель [17, 18]. Это перечисление выполняется в результате компьютерных расчетов. В настоящее время расчеты проведены вплоть до размерности 8.

В настоящей диссертации изучается один класс зоноэдральных параллелоэдров, а именно, параллелоэдры (в том числе и непримитивные) первого типа. Найден конструктивный подход к таким паралле-лоэдрам любой размерности.

В дальнейшем во введении теоремы и утверждения снабжены теми номерами, которые они имеют в основном тексте.

1. Е.С. Федоров Начала учения о фигурах // Петербург, 1885; М.; Л.: Изд-во АН СССР. 1953. 410 с. (сер. "Классики науки")

2. Е.С. Федоров Правильное деление плоскости и пространства // Л., "Наука", 1979, 272 с. оригинал см. E.S.Fedorov Regulare Plan- und Raumteilung, Abhandlungen der K.Bayer, Akademie der Wissenschaften, II CL, Bd. XX, II Abt., Miinchen, 1899.

3. G. Minkowski Algemeine Lehrsatze uber die konvexen Polyeder // Nachrichten von der K.Gesellschaft der Wissenschaften zu Gottingen, Mathem.-physikalische Klasse, 1897, S.198.

4. Г.Ф. Вороной Исследования о примитивных параллелоэдрах // Собр. соч., т. 2, Киев, Изд-во АН УССР, 1952, с. 239-368; (Оригинал в J. reine und angew. Math., 1908, т. 134, с. 198-287, 1909, т. 136, с. 67-179).

5. В. Delaunay B.N. Delone] Sur la sphere vide // Proc. Internat. Congr. Math. (Toronto, 1924), Univ. of Toronto Press, 695-700 (1928).

6. B. Delaunay B.N. Delone] Sur la partition reguliere I'espace a 4 dimensions // Известия АН СССР, Отд. Физ.-Мат. Наук. 1929. - №1 - С.79-110, - №2 - С.147-164.

7. Б.А. Венков 0 проектировании параллелоэдров // Избранные труды, Ленинград, "Наука", Ленинградское отделение 1981, с. 362-379 (Оригинал в Мат. сб., 1959, т. 49, вып. 2, с. 207-224).

8. R.M. Erdahl Zonotopes, dicings, and Voronoi's conjecture on parallelohedra // Europ. J. Combinatorics 20 (1999), 527-549.

9. G.C. Shephard Space-filling zonotopes // Mathematika, 21 (1974), 261-269.

10. P. McMullen Space tiling zonotopes // Mathematika 22 (1975), 202211.

11. V. Danilov, V. Grishukhin Maximal unimodular system of vectors // Europ. J. Combinatorics 20 (1999), 507-526.

12. C.C. Рышков О структуре примитивного параллелоэдра и о последней проблеме Вороного // УМН, 1998, т.53, вып. 2(320), с. 161-162.

13. С.С. Рышков Прямое геометрическое описание произвольного п-мерного параллелоэдра второго типа Вороного // Успехи матем. наук, 1999. - т. 54, вып. 2. - с. 18-19.

14. С.С. Рышков, Е.А. Большакова К теории коренных параллелоэдров // Известия РАН сер. матем., т. 69, №6, 2005, с. 187 210.

15. Ф. Харари Теория графов 11 М. Мир, 1973.

16. С.С. Рышков К теории конуса положительности и теории совершенных полиэдров П(п) и цп(т) // Чебышевский сборник 2002г., т. 3 вып. 1(3), с. 84 96.

17. P. McMullen On zonotopes // Trans. Amer. Math. Soc., 159 (1971), 91-110.

18. A.A. Зыков Основы теории графов. М. Вузовская книга, 2004.

19. H. Whitney On the classification of graphs // Amer. J. Math., 55(1933), № 2, 236-244.

20. H. Whitney 2-isomorphic graphs // Amer. J. Math., 55(1933), № 2, 245-254.Публикации автора по теме диссертации

21. Е.А. Большакова DV-разбиение и L-разбиение по Г. Ф. Вороному, Б.Н. Делоне и В.А. Венкову // Чебышевский сборник 2004г. т.5 вып. 2(10), с.30-41.

22. Е.А. Большакова О параллелоэдрах, связанных с некоторыми графами // Тезисы докладов 6-ой международной конференции по геометрии и топологии, Черкассы, 2005, с. 10-11.

23. Е.А. Большакова Непримитивные n-мерные параллелоэдры первого типа: комбинаторика и символы // Успехи математических наук, т. 61, вып. 3, 2006г., стр. 167-168.