Критические решетки тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

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

УДК 512.562

Перминова Ольга Евгеньевна КРИТИЧЕСКИЕ РЕШЕТКИ

01.01.06 - математическая логика, алгебра и теория чисел

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

2 3 ОКГ 2014

Екатеринбург - 2014

005553627

005553627

Работа выполнена на кафедре алгебры и дискретной математики Института математики и компьютерных наук ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н. Ельцина».

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

доктор физико-математических наук, профессор В.А. Баранский

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

доктор физико-математических наук, профессор Ю.Д. Корольков

доктор физико-математических наук, профессор С.С. Титов

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

Южно-Уральский государственный университет

Защита состоится 18 ноября 2014 года в 12°° часов на заседании диссертационного совета Д 004.006.03 в Институте математики и механики УрО РАН по адресу: 620219, г. Екатеринбург, ул. С. Ковалевской, 16.

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

Автореферат разослан /3 октября 2014 года

Ученый секретарь диссертационного совета, кандидат физ.-мат. наук

И.Н. Белоусов

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

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

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

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

Для некоторых классов алгебраических систем указанное понятие жесткости естественно модифицировать, объявив тривиальными эндоморфизмами, кроме тождественного и постоянные эндоморфизмы, преобразующие все элементы в какой-либо один элемент. Типичный пример — рефлексивные графы и решетки. Жесткие в этом смысле графы впервые рассматривались Хваталом [6], решетки — Сиклером

И-

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

К настоящему времени вышло более восьмидесяти работ, в кото-

рых в явном виде изучались или использовались жесткие в том или ином смысле системы, см. обзор по состоянию до 1985 года в [9] и более поздние работы [10, 11] (жесткие бинарные отношения), [12] (жесткие топологические пространства и графы), [13| (жесткие частично упорядоченные множества), [14-16] (жесткие решетки и графы), [17] (жесткие универсальные алгебры) и многие другие. В соответствующей проблематике возникло несколько аспектов, которые были сформулированы в виде проблем, относящихся к одному фиксированному типу жесткости. Среди них отметим наиболее интересные проблемы.

Проблема 1 (о мощностях). Описание мощностей жестких систем из заданного класса.

Проблема 2 (об элементарной характеризации). Будет ли класс жестких систем из заданного класса аксиоматизируем.

Проблема 3 (алгоритмическая). Нахождение алгоритма перечисления всех конечных жестких систем из заданного класса.

Продолжая изучение свойства жесткости, естественно заинтересоваться минимальными (критичными) в этом смысле системами. А именно, под такой системой следует понимать жесткую систему, не обладающую собственными нетривиальными жесткими подсистемами. Например, в монографии Пультра и Трнковой [8] критическим (ко-кри-тическим) назван жесткий граф, удаление (добавление) любого ребра которого превращает его в нежесткий граф. Заметим, что интересуются также и максимальными жесткими системами, т. е. жесткими системами, все подсистемы которых являются жесткими. Например, в работе [17] такие системы названы наследственно жесткими. Как следует из изложенного, для класса критических и наследственных систем является актуальным решение аналогичных перечисленным ранее общим проблемам для жестких алгебраических систем.

В данной работе мы рассматриваем жесткие и критические решетки. Решетка называется жесткой, если любой её эндоморфизм является постоянным эндоморфизмом (т. е. преобразует все элементы в какой-либо один элемент) или тождественным эндоморфизмом. Критической назовем жесткую решетку, у которой нет собственных жестких подрешеток, исключая тривиальные — одно- и двухэлементные подрешетки. Определения эндоморфизма и автоморфизма решетки см. в [18].

В работах [19, 20] получены важные для нас решения проблем 1 и 2 для класса жестких решеток. А именно, доказано, что для любого кардинала а тогда и только тогда существует жесткая решетка мощно-

сти а, когда а > 7; класс жестких решеток арифметически незамкнут и, следовательно, неаксиоматизнруем.

Естественно, основная проблема описания всех алгебраических систем заданного вида, в том числе и всех жестких систем, является очень трудной и в настоящее время (алгоритмически) нерешенной для многих классов ранее изучавшихся систем. Не решена она и для случая жестких решеток. О трудности описания жестких решеток свидетельствует результат о том, что каждая (конечная) решетка вложима в жесткую (конечную) решетку [20].

Цель диссертационной работы — описать все натуральные числа п, для каждого из которых существует п-элементпая критическая решетка (решение проблемы 1 для класса конечных критических решеток); дать ответ на вопрос о том, является ли класс критических решеток аксиоматизируемым (решение проблемы 2 об элементарной характеризации класса критических решеток); оценить функцию роста жестких решеток.

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

В доказательстве критичности решеток определяющую роль играют свойства проективных и слабо проективных интервалов, автоморфизмов и эндоморфизмов решеток, лемма 2 из работы [19] о достаточном условии нежесткости решеток. Наряду с этим используются некоторые вспомогательные решеточные конструкции.

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

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

1. Найдены все мощности конечных критических решеток.

2. Установлена неаксиоматизируемость класса всех критических решеток.

3. Найдена нижняя экспоненциальная оценка для функции роста жестких п-элементных решеток при п > 31.

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

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

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

Изложенные в диссертации результаты были представлены на VI

Межвузовской научно-практической конференции студентов, аспирантов и молодых ученых " Безопасность информационного пространства" (Тюмень, 2007), на 42-й Всероссийской молодежной школе-конференции "Современные проблемы математики" (Екатеринбург, 2011), на Международной конференции по алгебре и геометрии, посвященной 80-летию со дня рождения А.И. Старостина (Екатеринбург, 2011), на семинаре "Алгебраические системы" (Екатеринбург, 2014).

Публикации

Основные результаты диссертации опубликованы в 7 работах [3238), из них 4 статьи [33, 35, 37, 38] в изданиях, входящих в перечень, утвержденный ВАК, и 3 тезисов докладов [32, 34, 36].

Структура и объем диссертации

Текст диссертации состоит из введения, трех глав, списка литературы, включающего 52 наименования. Общий объем диссертации составляет 128 страниц.

Содержание диссертации

Во введении обсуждена предыстория и актуальность темы диссертации, определены цели работы, введены основные понятия, кратко изложено содержание диссертации.

В первой главе излагается решение проблемы 1 для класса конечных критических решеток. Основным результатом первой главы является следующая

Теорема 1. Пусть п - натуральное число, п > 3. Тогда п-элементная критическая решетка существует в том и только в том случае, когда п = 7 или п > 9.

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

Во втором параграфе описываются конструкции некоторых п-элементных критических решеток для п = 7 и натуральных чисел п > 9 (далее - класс Сг).

Рассмотрим сначала случаи п = 3,8, указанные в теореме 1. Из теоремы 2 работы [19] следует, что для 3 < п < С не существует жестких, а, следовательно, и критических решеток. Отсюда непосредственно следует, что жесткая семиэлементная решетка Щ из работы [19] (см. рис. 1) является критической. Пример жесткой восьмиэле-

ментной решетки Д8 (см. рис. 1) также можно извлечь из работы (19]. Отметим, что анализ диаграмм всех семиэлементных и восьми-элементных решеток (см. приложение к работе [21]) ) показывает, что Д7 является единственной жесткой семиэлементной решеткой, решетка Д8 — единственной жесткой восьмиэлементной решеткой. Решетка Ла не является критической, так как содержит в качестве собственной подрешетки решетку Я7. Следовательно, не существует критических восьмиэлементных решеток.

Диаграммы решеток из класса С г для п = 9,10,11,12,13,14,16,17, 20 см. на рис. 2.

Пусть п — число элементов решеточной конструкции Я(к, т), диаграмма которой представлена на рис. 2. Очевидно,

п = 0 + 3к + 2т + 2(т - 1) = Зк + 4т + 4 (к>1,т> 2).

Из этой формулы в результате варьирования чисел кит получаются значения п = 15,18,19 и п > 21.

1

1

о

о

Рис. 1. Решетки П7,

Решетка Ли

Решетка Д13

Решетка Яц

Решетка Лза

Решетка Л30

Решетка Я(Дг,т)

Рис. 2. Критические решетки класса Ст

Для доказательства того, что конструкции на рис. 2 являются решетками, используется понятие разборной решетки, введенное Ри-валом [22]. Конечная решетка Ь порядка п называется разборной, если она содержит цепь Ь\ С ¿2 С ... С Ьп = Ь её подрешеток таких, что |1/г| = г для всех г = 1,..., п.

Дадим более удобное для нас определение разборной решетки, эквивалентное указанному выше. Для чего опишем сначала необходимую для этого процедуру одноэлементного расширения решетки. Рассмотрим произвольную решетку А и одноэлементную решетку {и} такие, что АП {и} = 0. Возьмем в решетке А произвольные различные сравнимые элементы а и Ь, где а < Ь. На множестве В = А и {г>} определим следующий частичный порядок < :

Легко проверить, что указанное частично упорядоченное множество В является решеткой.

Итак, разборной является решетка, полученная из одноэлементной решетки с помощью конечного числа процедур одноэлементного расширения решетки, присоединения к решетке внешнего нуля 0 или единицы 1 [23, предложение 2.1]. Таким образом, понятие разборности имеет алгоритмическую природу, что облегчает описание конечных разборных решеток.

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

Нами была написана программа для РС, которая порождает из (п — 1)-элементных разборных решеток все попарно неизоморфные п-элементиые разборные решетки и выделяет среди них некоторый естественный подкласс класса жестких решеток. Описание программы дано в параграфе 3 главы 3. Результаты работы этой программы были использованы для нахождения критических п-элементных решеток для п = 9,10,11,12 и конструкции га-элементных критических решеток для п > 13.

В третьем параграфе излагается доказательство того, что решетки из класса Сг являются жесткими. Доказательство разбито на две части.

1. Доказывается, что данные решетки не имеют склеивающих эндоморфизмов, отличных от постоянных, при этом склеивающим эндоморфизмом решетки Ь будем называть любой ее эндоморфизм <р такой, что Iрх = '-ру для некоторых различных элементов х,у € Ь. В доказательстве основную роль играют понятия простой решетки [24] и отношения проективности и слабой проективности интервалов [18]. Простой называется решетка, обладающая только тривиальными кон-груэнциями.

2. Доказывается, что данные решетки не имеют автоморфизмов, отличных от тождественного. Будем говорить, что в решетке элемент а покрывает Ь или Ь покрывается элементом а (и писать Ъ -< а), если а > Ь и не существует х такого, что а > х > Ь. Пусть у — произвольный элемент решетки, отличный от 0 и 1. Через 1(0, у) обозначим длину наибольшей по числу элементов цепи между элементами 0 и у (далее, высота элемента у), через 1(у, 1) — длину наибольшей по числу элементов цепи между элементами у и 1, через у) — число попарно несравнимых элементов, покрываемых элементом V, через д(у -<) — число попарно несравнимых элементов, покрывающих элемент V. Четверку чисел (1(0, у), 1(у, 1), q(-< и), <7(1; -<)) назовем типом элелгепта и. В доказательстве части 2) ведущую роль играет сохранение типов элементов при автоморфизмах.

В четвертом параграфе излагается доказательство того, что каждая построенная решетка из класса СУ не содержит собственных нетривиальных жестких подрешеток. Отсюда и из жесткости решеток следует их критичность. Доказательство основано на переборе всех возможных нетривиальных подрешеток и доказательстве их нежесткости. Для упрощения перебора используются несколько вспомогательных решеточных конструкций, описанных в начале параграфа 4 и решеточная конструкция, описанная в конце параграфа 1. При доказательстве того, что подрешетки не являются жесткими существенно используется достаточное условие нежесткости решеток, сформулированное в работе [19] в виде следующей леммы.

Лемма. Если решетку Ь можно разбить в объединение двух подрешеток Ь\ и Ь'1 так, что хотя бы одна из них неодноэлементна, и для любых х € Ь\, у € Ь'2, либо х меньше у, либо х и у несравнимы, то Ь обладает нетривиальным эндоморфизмом, т. е. не является жесткой.

Поскольку все построенные нами критические решетки являются разборными, возникает вопрос:

Существуют ли конечные неразборные критические решетки?

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

Отметим сначала одно важное свойство неразборных решеток. Известно [23], что любая конечная решетка либо является разборной, либо содержит корону. Таким образом, неразборные решетки и только они содержат короны.

Короной (см. рис. За)) называется частично-упорядоченное множество {х\, уг, х2, У2, ■ ■ ■, Ут} (т > 3) со следующим отношением частичного порядка <:

< У и У* > (г = 1, • • •, т - 1), XI < ут,

при этом множества {хь Хг,..., хт} и {у\, у2. • • •, Ут} являются антицепями, т. е. состоят из попарно несравнимых элементов.

Известно, что любая решетка, содержащая не более семи элементов, является разборной (см. [22]). Нами установлено, что существуют конечные критические неразборные решетки и построена минимальная по числу элементов неразборная критическая решетка (см. рис. Зс)). Эта решетка содержит десять элементов. Доказательство ее минимальности основано на том, что не существует жестких вось-миэлементных и девятиэлементных неразборных решеток. А именно, имеется одна восьмиэлементная (см. рис. ЗЬ)) и восемь девятиэлементных попарно неизоморфных неразборных решеток. В начале пятого параграфа построены их диаграммы и доказана нежесткость каждой девятиэлементной неразборной решетки.

а) Ь) с)

Рис. 3.

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

Известно [25], что алгебраическая система элементарно эквивалентна своей ультрастепени по любому ультрафильтру. Поэтому для доказательства арифметической незамкнутости класса К критических решеток достаточно показать, что найдется бесконечная решетка Ь из К, для которой существует некритическая решетка Ь*, являющаяся ее ультрастепенью по некоторому ультрафильтру.

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

Во втором параграфе построена счетная решетка Ь и показано, что она является критической. В доказательстве того, что решетка Ь не содержит жестких подрешеток, кроме одно- и двухэлементных, существенно используется решеточная конструкция из параграфа 1 главы 1.

В третьем параграфе сначала изучается строение ультрастепени Ь* решетки Ь по некоторому неглавному ультрафильтру над 2 и затем доказывается, что ультрастепень 1/ можно разбить в объединение двух подрешеток, удовлетворяющих требованиям указанной ранее леммы о достаточном условии нежесткости решеток. Поэтому Ь" — нежесткая, и, следовательно, — некритическая решетка. Отсюда вытекает

Теорема 2. Класс всех критических решеток неаксиоматизируем.

Перед изложением основных результатов третьей главы остановимся на задаче перечисления алгебраических систем. Хороший подход к исследованию этой задачи даёт нахождение функции роста, которая для фиксированного натурального п указывает число п-элементных конечных алгебраических систем заданного вида. В монографии Ха-рари [26] можно найти много примеров функций роста, указывающих для каждого натурального п число п-элементных графов того или иного вида. Для многих классов алгебраических систем задача нахождения функций роста оказалась очень трудной и нерешенной до сих пор, в частности, не известно точной или рекурсивной формулы для вычисления числа всех п-элементных попарно неизоморфных решеток (далее - решеток). В случае отсутствия точной или рекурсивной формулы имеется два направления исследований, которые для решеток впервые сформулировал Биркгоф в хорошо известной книге "Теория решеток" (см. [27], с. 35). Первое направление — найти нижнюю и

верхнюю границы или асимптотическую оценку роста п-элементных алгебраических систем из заданного класса. Второе направление — найти алгоритм построения n-элементных алгебраических систем из заданного класса и сосчитать их число. Главным достоинством второго подхода является создание базы алгебраических систем из заданного класса. Такая база полезна для поиска примеров и контрпримеров. Главный недостаток данного подхода — время работы алгоритма обычно растет очень быстро даже при небольшом порядке систем.

В работах Клотца и Люхта [28] и Клейтмана и Уинстона (29] найдены экспоненциальные нижняя и верхняя оценки функции роста для класса конечных решеток, соответственно. Кюно в работе [21] описал индуктивный алгоритм построения диаграмм Хассе для всех n-элементных решеток и нашел число решеток до п < 9, а также привел диаграммы всех решеток порядка п < 8. Хейтциг и Рейнгольд [30] применили алгоритм упорядочения, описанный в общем случае в работе Рида [31], для построения n-элементных решеток и вычислили число решеток до п < 18, как указано в статье [30], для определения числа n-элементных решеток при п = 18 понадобилось б суток непрерывной работы суперкомпьютера Cray ТЗе "Berte" в Берлине.

Перейдем к рассмотрению жестких решеток и строго жестких решеток. Под строго жесткой решеткой мы понимаем решетку, не имеющую автоморфизмов, кроме тождественного, все интервалы которой проективны [18]. Очевидно, любая строго жесткая решетка является жесткой решеткой. Отметим, что до сих пор неизвестна точная или рекурсивная формула для вычисления числа жестких решеток.

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

Теорема 3. Функция роста конечных жестких решеток экспоненциальна.

Таким образом, число жестких решеток, также как и число всех решеток, имеет экспоненциальный рост. Более точно, найдена экспоненциальная нижняя оценка числа n-элементных жестких решеток, а именно доказано, что для любого натурального числа п > 31 существует 2з("-7_г' попарно неизоморфных простых жестких n-элементных решеток, где г — остаток от деления числа п —7 на 6. Отметим здесь, что из работы [20] известно, что для каждого натурального п > 10 существует п — 8 попарно неизоморфных жестких n-элементных решеток. Таким образом, результат теоремы 3 существенно усилил результат, полученный в работе [20], для п > 31.

В первом параграфе описаны конструкции решеток, используемых в доказательстве теоремы 3. Все используемые решетки являются подрешетками решетки общего вида Я (см. рис. 4). Через Я; на рис. 4 обозначена разборная решетка вида /?5+2Р+1 или её подрешетка Д5+2Р = Й5+2р+1\{-г£+1}. Здесь и далее нижний индекс в обозначении решетки - это порядок (число элементов) решетки.

Пусть X = = 1,..., т}, У = {и|г = 1,..., т}, Ех = {/*, /¡+1\{ = 1,..., т- 1}и{/1т}и{с7<|г = 1,...,т}и{7ц|г = 1,..., т}и{д}. Обозначим через Я-/т+2 подрешетку {0,1} и А" и У решетки Я.

Расширениями решетки назовем решетки, полученные из данной решетки с помощью применения конечного числа процедур одноэлементного расширения. Поскольку \Ех\ = 4т, число расширений решетки Дгт+2 всеми /с-элементными подмножествами множества Ех равно \{В^т+2+кМ = !> -> С4т>к = •••> 4т)1 = 24т- Для фиксированных к и j интервал [хт, у,п] решетки Щт+2+к расширим 5 + 4т-к + г элементами до решетки вида Я;. Обозначим полученное расширение через ^¡¡т+7+г- Итак, для каждого фиксированного п = 6т + 7 + г мы получим попарно неизоморфных п-элементных решеток

7+г' являющихся подрешетками решетки общего вида Я.

Решетка Л

Рис. 4.

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

В третьем параграфе описан алгоритм генерации разборных решеток и анализа их на свойство "быть строго жесткими". Для реализации алгоритма нами была написана программа для РС.

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

Число элементов в решетке, п Число негооморфных решеток, Ь(п) [30] Число неизоморфных разборных решеток Число неизоморфных разборных строго жестких решеток

1 1 1 1

2 1 1 1

3 1 1 0

4 2 2 0

5 5 5 0

6 15 15 0

7 53 53 1

8 222 221 1

9 1 078 1 070 15

10 5 994 5 913 98

11 37 622 36 774 748

12 262 776 253 531 5 912

По данным программы число всех разборных п-элементных решеток для п = 8 и п = 9 равно соответственно 221 и 1070. Поскольку число всех п-элементных неразборных решеток для п = 8 и и = 9 равно соответственно 1 и 8, общее число п-элементных решеток для указанных п совпадает с числом, приведенным в работе [30] (см. стол-бед 2 таблицы).

На рис. 5 показана зависимость между числом элементов п и

1) числом всех попарно неизоморфных п-элементных разборных решеток (верхняя линия),

2) числом всех попарно неизоморфных п-элементных строго жестких разборных решеток (нижняя линия).

Рис. 5.

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

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

Список литературы

[1| Vopenka P., Pultr A., Hedrlin Z. A rigid relation exists on any set // Comment. Math. Univ. Carol. 1965. Vol. 6, № 2. P. 149-155.

[2] Dlab V., Neumann В. H. Semigroups with few endomorphisms // J. Austral. Math. Soc. 1969. Vol. 10, № 1-2. P. 162-168.

[3] Смирнов Д. M. Канторовы алгебры с одним порождающим // Алгебра и логика. 1971. Т. 10, № 6. Р. 658-667.

[4] Белеградек О. В., Тайцлин М. А. Два замечания о многообразиях am>n / Алгебра и логика. 1972. Т. И, № 5. Р. 501-508.

[5] Байрамов Р. А. Об эндоморфизмах некоторых алгебраических систем // Доклады АН АзССР. 1968. Т. 24, № 11. Р. 3-7.

[6] Chvatal V. On finite and countable rigid graphs and tournaments // Comment. Math. Univ. Carol. 1965. Vol. 6, № 4. P. 429-438.

[7] Sichler J. Non-constant endomorphisms of lattices // Proc. Amer. Math. Soc. 1972. Vol. 34. P. 67-70.

[8] Pultr A., TYnkova V. Combinatorial, algebraic and topological representations of groups, semigroups and categories. — Prague: Academia Praha, 1980. 372 p.

[9] Перминов E. А. Жесткие графы и решетки: дис. ... канд. физ.-мат. наук. — Свердловск: УрГУ, 1985. 100 с.

[10] Tyszka A. A stronger form of the theorem on the existence of a rigid binary relation on any set // Aequationes Math. 2003. Vol. 66, Issue 3. P. 257-260.

[11] Hamkins J. D., Palumbo J. [Эл. ресурс] The rigid relation principle, a new weak choice principle // http://arxiv.org/pdf/1106.4635vl (Submitted on 23 Jun 2011)

[12] Hrusak M. Automorphism groups of complements of points // Acta Universitatis Carolinae. Mathematica et Physica. 1994. Vol. 35, № 2. P. 23-31.

[13] Khamis S. M. Exact counting of unlabeled rigid interval posets regarding or disregarding height // Order. 2012. Vol. 29. P. 443-461.

[14] Koubek V., Sichler J. Quotients of rigid (0, l)-lattices // Arch. Math. 1985. Vol. 44. P. 403-412.

[15] Gibson P., Zaguia I. Endomorphism classes of ordered sets, graphs and lattices // Order. 1998. Vol. 15. P. 21-34.

[16] Nesetril J. A rigid graph for every set // Journal of Graph Theory. 2002. Vol. 39, Issue 2. P. 108-110.

[17] Koubek V., Rodl V. On hereditarily rigid algebras // Algebra Universalis. 1986. Vol. 22. P. 120-141.

[18] Гретцер Г. Общая теория решеток. — М.: Мир, 1982. 456 с.

[19] Важешш Ю.М., Перминов Е.А. О жестких решетках и графах // Исслед. по соврем, алгебре/ Уральск, гос. ун-т. 1979. С. 3-21.

[20] Перминов Е.А. О жестких решетках // Депонир. в ВИНИТИ. 27.01.1984. № 847-84. 22 с.

[21] Kyuno S. An inductive algorithm to construct finite lattices // Math. Сотр. 1979. Vol. 33. P. 409-421.

[22] Rival I. Lattices with doubly irreducible elements // Can. Math. Bull. 1974. Vol. 17. P. 91-95.

[23] Kelly D., Rival I. Crowns, fences, and dismantlable lattices // Canad. J. Math. 1974. Vol. XXVI, № 5. P. 1257-1271.

[24] Crawley P., Dilworth R.P. Algebraic theory of lattices. — New Jersey: Prentice-Hall, Inc., Englewood Cliffs, 1973. 193 p.

[25] Мальцев А.И. Алгебраические системы. — M.: Наука, 1970. 392 с.

[26] Харари Ф. Перечисление графов. — М.: Мир, 1977. 324 с.

[27] Биркгоф Г. Теория решеток. — М.: Наука, 1984. 568 с.

[28] Klotz W.,Lucht L. Endliche verbande // J. Reine Angew. Math. 1971. Vol. 247. P. 58-68

[29] Kleitman D. J., Winston K. J. The asymptotic number of lattices // Ann. Discrete Math. 1980. Vol. 6. P. 243-249.

[30] Heitzig J., Reinhold J. Counting finite lattices // Algebra univers. 2002. Vol. 48. P. 43-53.

[31] Read R. C. Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations // Ann. Discrete Math. 1978. Vol. 2. P. 107-120.

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

[32] Перминова О. Е. О жестких критических решетках // Безопасность информационного пространства VI: сб. тр. Межвузовской научно-практической конференции студентов, аспирантов и молодых ученых. Тюмень, 22-23 ноября 2007 г. С. 180-183.

[33] Перминова О. Е. О конечных критических решетках // Тр. Инта математики и механики УрО РАН. 2009. Т. 15, № 2. С. 185-193.

[34] Перминова О. Е. О мощностях конечных критических решеток // Современные проблемы математики. Тезисы 42-й Всероссийской молодежной школы-конференции. Ин-т математики и механики УрО РАН, Екатеринбург. 2011. С. 235-237.

[35] Перминова О. Е. О функции роста конечных жестких решеток // Изв. Иркут. гос. ун-та. Сер. Математика. 2011. Т. 4, № 2. С. 124-133.

[36] Перминова О. Е. О функции роста конечных жестких решеток // Тезисы Международной конференции по алгебре и геометрии, посвященной 80-летию со дня рождения А.И. Старостина. Ин-т математики и механики УрО РАН, Екатеринбург. 2011. С. 136-138.

[37] Перминова О. Е. О конечных критических решетках. II // Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, № 4. С. 278-292.

[38] Перминова О. Е. Неаксиоматизируемость класса критических решеток // Изв. Иркут. гос. ун-та. Сер. Математика. 2012. Т. 5, № 4. С. 66-78.

Подписано в печать 09.10.2014. Формат 60x84 1/16 Бумага офсетная. Усл. печ. л. 1,2 Тираж 100 экз. Заказ № 1647

Отпечатано в типографии ИПЦ УрФУ 620000, Екатеринбург, ул. Тургенева, 4