Критические решетки тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат наук Перминова, Ольга Евгеньевна

• Перминова, Ольга Евгеньевна
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Перминова, Ольга Евгеньевна

Содержание

Введение

Глава 1. Мощности конечных критических решеток

1.1. Предварительные сведения

1.2. Описание конструкций п-элементных критических решеток для

п = 7 и натуральных чисел п > 9

1.3. Доказательство жесткости построенных п-элементных решеток для натуральных чисел п > 9

1.4. Доказательство критичности построенных п-элементных решеток для натуральных чисел п > 9

1.5. О существовании критической неразборной решетки

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

2.1. Ультрастепень алгебраической системы по неглавному ультрафильтру

2.2. Конструкция счетной критической решетки

2.3. Доказательство арифметической незамкнутости класса критических решеток

Глава 3. Функция роста конечных жестких решеток

3.1. Описание конструкций жестких решеток

3.2. Доказательство экспоненциальности роста числа конечных жестких решеток

3.3. Описание алгоритма нахождения конечных строго жестких разборных решеток

Литература

Введение диссертации (часть автореферата) на тему «Критические решетки»

Введение

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

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

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

фы и решетки. Жесткие в этом смысле графы впервые рассматривались Хва-талом [6], решетки — Сиклером [7].

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

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

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

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

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

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

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

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

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

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

Цели данной работы:

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

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

3) оценить функцию роста жестких решеток.

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

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

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

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

Из теоремы 2 работы [18] следует, что для 3 < п < б не существует жестких, а, следовательно, и критических решеток.

Рассмотрим случаи п — 7 и п = 8, указанные в теореме 1. Примеры жестких семиэлементной и восьмиэлементной решеток (см. рис. 1.4) можно извлечь из работы [18]. Обозначим их соответственно через Яч и Анализ диаграмм всех семиэлементных и восьмиэлементных решеток (см. приложение к работе [22]) показывает, что Я"? является единственной жесткой семиэлементной решеткой, решетка Яв — единственной жесткой восьмиэлементной решеткой. Поскольку для п = 3,..., 6 не существует жестких п-элементных ре-

шеток, решетка Я7 является критической решеткой. Решетка Я& не является критической, так как содержит в качестве собственной подрешетки решетку Д7. Следовательно, не существует критических восьмиэлементных решеток.

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

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

Дадим более удобное для нас определение разборной решетки, эквивалентное указанному выше.

Для чего опишем сначала необходимые для этого процедуры.

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

х <у <

х, у £ А и х < у на А, х Е А, х < а, у = V, х = V, у в А, у > Ь.

Будем говорить, что в решетке Ь элемент а покрывает Ь или Ь покрывается элементом а (и обозначать это так: а >- Ь или Ь -< а), если а > Ь и не существует х такого, что а > х > Ь.

Далее рассмотрим решетку С = А и {0}, получаемую процедурой присо-

единения к конечной решетке А внешнего нуля 0:

\ х, у е А и х -< у на А, х у I

I х = 0, у = а, где а — наименьший элемент решетки А.

Нам понадобится также решетка И = А и {1}, получаемая процедурой присоединения к решетке А внешней единицы 1:

{х, у € А и х -< у на А,

х = 6, у = 1, где Ь — наибольший элемент решетки А.

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

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

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

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

применяя конечное число указанных процедур.

Доказательство критичности построенных п-элементных решеток для натуральных чисел п > 9 разбито на три части, а, именно, приводятся доказательство того, что:

1) данные решетки не имеют склеивающих эндоморфизмов, отличных от постоянных, при этом склеивающим эндоморфизмом решетки Ь будем называть любой ее эндоморфизм (р такой, что (рх = ру для некоторых различных элементов х, у е Ь;

2) данные решетки не имеют автоморфизмов, отличных от тождественного;

3) каждая построенная решетка не содержит собственных нетривиальных жестких подрешеток.

Из 1) и 2) следует жесткость построенных решеток. Из 3) и из жесткости построенных решеток следует их критичность.

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

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

доказательстве того, что подрешетки не являются жесткими существенно используется достаточное условие нежесткости решетки — лемма 2 из работы [18].

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

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

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

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

Хг < Уи т > Хг+1 (г = 1, . . . , Ш - 1), Х\ < ут,

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

У1 У2 Ут-1 Ут

Х\ Х2 Хз Хт

Рис. 1. Корона порядка 2т.

Нами установлено, что существуют конечные критические неразборные решетки и построена минимальная по числу элементов неразборная критическая решетка. Эта решетка содержит десять элементов. Доказательство ее критичности излагается в параграфе 5 главы 1.

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

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

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

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

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

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

Перед изложением основных результатов главы 3 остановимся на задаче перечисления алгебраических систем. Хороший подход к исследованию этой задачи даёт нахождение функции роста, которая для заданного натурального п указывает число п-элементных конечных алгебраических систем заданного вида. В монографии Харари [26] можно найти много примеров функций роста, указывающих для каждого натурального п число п-элементных графов того или иного вида. Широко известна и функция роста другого вида, которая указывает число п-элементных подсистем или элементов данной

алгебраической системы, обладающих заданным свойством. Р. И. Григорчу-ком изучалась известная функция роста групп, определяющая количество различных элементов группы, записываемых в виде произведения порождающих элементов, В. И. Трофимовым изучались другие интересные аналоги функций роста групп, луп, полугрупп, графов (см. [27]).

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

Биркгоф в 1948 году в хорошо известной книге "Теория решеток" (см. также [28], с. 35) одним из первых сформулировал проблему перечисления всех ч.у. множеств: "Пусть <2(п) — число неизоморфных ч.у. множеств с п-элементами, (?*(п) — число различных упорядочений п-элемептного множества. Вычислить для небольших п и найти асимптотику и оценки для степени роста функций С?(п) и С?*(п)". Те же вопросы сформулированы в [28] для чисел Н*(п) и Н(п), обозначающих соответственно количество различных и количество неизоморфных решеточных упорядочений п-элементного множества. Таким образом, в случае отсутствия точной или рекурсивной формулы имеется два направления исследований. Первое направление — найти нижнюю и верхнюю границы или асимптотическую оценку роста алгебраических систем из заданного класса с п элементами. Второе направление — найти алгоритм построения алгебраических систем из заданного класса и сосчитать их число. Главным достоинством второго подхода является создание базы алгебраических систем из заданного класса. Такая база полезна для поиска

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

Основные результаты о числе n-элементных конечных ч.у. множеств можно найти в работах [29-31]. Асимптотическую оценку для числа всех помеченных n-элементных ч.у. множеств в работах [32, 33]. Поскольку число непомеченных структур асимптотически в п\ раз меньше числа помеченных структур (доказательство см. в [34]), для ч.у. множеств справедлива оценка

—> 1 для п —> оо. п\Рп

В [31] Хейтциг и Рейнгольд описали алгоритм подсчета числа непомеченных ч.у. множеств и вычислили их число до 14 элементов включительно. Скорость работы алгоритма на 450 Mhz DEC Alpha соответствует 3000 ч.у. множеств в секунду. В [30] Бринкман и МакКей описали алгоритм счета числа непомеченных ч.у. множеств и вычислили их число до 16 элементов включительно. Скорость работы алгоритма на 1 GHz Pentium III соответствует генерации 4 млн. неизоморфных ч.у. множеств в секунду. Отметим, что к настоящему времени известны (см. [30]) значения 0(п) и G*(n) для натуральных чисел п < 18 и п < 16, соответственно. Интересной также является работа Хамиза 2012 г. [13] о перечислении некоторого класса жестких ч.у. множеств.

Как и для числа ч.у. множеств, до сих пор не известно точной или рекурсивной формулы для вычисления числа всех n-элементных непомеченных (иначе, попарно неизоморфных) решеток (далее - решеток). В работах Клотца и Люхта [35] и Клейтмана и Уинстона [36] найдены экспоненциальные нижняя и верхняя оценки функции роста для класса конечных решеток, соответственно. Кюно в работе [22] описал индуктивный алгоритм построения

диаграмм Хассе для всех n-элементных решеток и нашел число решеток до п < 9, а также привел диаграммы всех решеток порядка п < 8. Кода [37] вычислил их число до п < 13. Хейтциг и Рейнгольд [38] применили алгоритм упорядочения, описанный в общем случае в работе Рида [39], для построения n-элементных решеток и вычислили число решеток до п < 18, указав на ошибку в вычислении для п = 12,13 в [37]. Приведем описание трудности определения числа решеток из статьи [38]. Например, чтобы определить число n-элементных решеток для п = 18 понадобилась 6 суток непрерывной работы суперкомпьютера Cray ТЗе " Berte" в Берлине. В работе Белохлавека и Выходила [40] представлены два других алгоритма построения конечных n-элементных решеток. Число n-элементных решеток для п < 12, указанное в [40], совпадает с числом, указанным в [38].

Также к настоящему времени известны:

1) число всех неизоморфных n-элементных дистрибутивных решеток и вертикально неразложимых дистрибутивных решеток для п < 49, также нижняя и верхняя границы их числа [41];

2) число всех неизоморфных n-элементных модулярных решёток, решёток с дополнениями, булевых решеток, решёток с относительными дополнениями, решёток с относительными псевдодополнениями, решеток с делением для п < 12 [40]. В частности построена база решеток с делением для каждого тг < 12 и имеется ссылка на эту базу;

3) рекурсивные формулы для вычисления числа слабых полумодулярных решеток и их планарных диаграмм [42], асимптотическая оценка пла-нарных диаграмм слабых полумодулярных решеток [43];

4) точная формула для вычисления числа решеток, содержащих в точности два разложимых элемента, числа решеток с n-элементами и числом ребер, меньшим или равным п+ 1, в частности дистрибутивных и модулярных решеток с n-элементами и числом ребер, меньшим или равным п + 1

Перейдем к рассмотрению жестких решеток и строго жестких решеток.

Отметим, что до сих пор неизвестна точная или рекурсивная формула для вычисления числа жестких решеток. Известно [20], что для каждого натурального п > 10 существует п — 8 жестких попарно невложимых друг в друга п-элементных решеток. Основными результатами главы 3 являются:

1) оценка функции роста жестких решеток — первое направление исследований в условиях отсутствия точной или рекурсивной формулы;

2) построение алгоритма генерации разборных решеток и анализа их на свойство "быть строго жесткими", с помощью которого найдено число строго жестких разборных решеток и создана база всех строго жестких разборных решеток для каждого п < 12 — второе направление исследований.

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

Таким образом, число жестких решеток, также как и число всех решеток, имеет экспоненциальный рост. Более точно, найдена экспоненциальная нижняя оценка числа п-элементных жестких решеток, а именно доказано, что для любого натурального числа п > 31 существует 25(п-7~г) простых жестких п-элементных решеток, где г — остаток от деления числа п — 7 на 6. В параграфе 1 главы 3 описаны конструкции решеток, используемых в доказательстве теоремы 3. В параграфе 2 главы 3 показано, что все интервалы этих решеток проективны и указанные решетки не имеют автоморфизмов, отличных от тождественного. Следовательно, рассматриваемые решетки являются простыми жесткими решетками. Данные решетки не являются критическими, так как содержат жесткие подрешетки определенного вида. Отметим также, что данные решетки являются неразборными, т. е. мы доказали в частности, что число жестких неразборных решеток растет по экспоненте.

С помощью описанного в параграфе 3.3 алгоритма и реализованной на

его основе программы для РС была создана база строго жестких разборных решеток и найдено их число для каждого п < 12. Сначала из (п — 1)-элементных разборных решеток с помощью процедур одноэлементного расширения, присоединения внешнего нуля 0 и присоединения внешней единицы 1 строятся все попарно неизоморфные разборные решетки с числом элементов п. Далее все построенные разборные решетки проверяются на свойство быть "строго жесткими". Отметим, что число и база всех строго жестких решеток для п = 9,..., 12, также как число и база всех разборных решеток для п = 9, ...,12, до сих пор приведены не были. С помощью программы нами, в частности, получены следующие результаты, указанные в третьем и четвертом столбце таблицы:

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

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

Продолжение на следующей странице

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

12 262 776 253 531 5 912

По данным программы число всех разборных n-элементных решеток для п = 8 и п = 9 равно соответственно 221 и 1070. Поскольку число всех n-элементных неразборных решеток для п = 8 и п = 9 равно соответственно 1 и 8 (доказательство см. в параграфе 1.5), общее число n-элементных решеток для указанных п совпадает с числом, приведенным в работе [38] (см. столбец 1 таблицы). Отметим также, что диаграммы разборных n-элементных решеток для п = 7,8, найденные с помощью программы (см. http : //kadm.imkn.urf и. ги/pages.phplid = perminova_papers), совпадают с точностью до изоморфизма с диаграммами решеток, представленными в работе [22].

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

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

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

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

База всех разборных и строго жестких разборных решеток дана в http : //kadm.imkn.urfu.ru/pages.php7id = perminova_papers.

Рис. 2

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

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

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

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

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

Глава 1

Мощности конечных критических решеток

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

Список литературы диссертационного исследования кандидат наук Перминова, Ольга Евгеньевна, 2014 год

Литература

[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] Белеградек О. В., Тайцлин М. А. Два замечания о многообразиях ат,п // Алгебра и логика. 1972. Т. 11, № 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., Trnkova 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] Важенин Ю.М., Перминов E.A. О жестких решетках и графах // Исслед. по соврем, алгебре/ Уральск, гос. ун-т. 1979. С. 3-21.

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

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

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

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

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

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

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

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

[27] Трофимов В. И. Функции роста алгебраических систем : автореф. дис. ... канд. физ.-мат. наук // Новосибирск : НГУ, 1982. 10 с.

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

[29] Klaska J. History of the number of finite posets // Acta Univ. M. Belii ser. Mathematics. 1997. No 5. P. 73-84.

[30] Brinkmann G., McKay B. D. Posets on up to 16 points // Order. 2002. Vol. 19, Issue 2. P. 147-179.

[31] Heitzig J., Reinhold J. The number of unlabeled orders on fourteen elements // Order. 2000. Vol. 17, Issue 4. P. 333-341.

[32] Kleitman D. J. , Rothschild B. L. Asymptotic enumeration of partial orders on a finite set // Trans. Amer. Math. Soc. 1975. Vol. 205. P. 205-220.

[33] Kim К. H., Roush F. W. Posets and finite topologies // Pure Appl. Math. Sci. 1981. Vol. 14, No 1-2. P. 9-22.

[34] Promel H. J. Counting unlabeled structures //J. Combinat. Theory, Ser. A. 1987. Vol. 44. P. 83-93.

[35] Klotz W.,Lucht L. Endliche verbände // J. Reine Angew. Math. 1971. Vol. 247. P. 58-68

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

[37] Koda Y. The numbers of finite lattices and finite topologies // Bull. Inst. Combin. Appl. 1994. Vol. 10. P. 83-89.

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

[39] 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.

[40] Belohlavek R., Vychodil V. Residuated lattices of size < 12 // Order. 2010. Vol. 27, Issue 2. P. 147-161.

[41] Erne M., Heitzig J., Reinhold J. On the number of distributive lattices // Electronic journal of combinatorics. 2002. Vol. 9, No 1. Research Paper 24. 23 pp.

[42] Cze'dli G., De'ka'ny T., Ozsva'rt L., Szaka'cs N., Udvari B.

[3ji. pecypc] On the number of slim, semimodular lattices / / http://arxiv.org/pdf/1208.6173vl (Submitted on 30 Aug 2012)

[43] Cze'dli G. [3ji. pecypc] The asymptotic number of planar, slim, semimodular lattice diagrams // http://arxiv.org/pdf/1206.3679vl (Submitted on 16 Jun 2012)

[44] Thakare N. К., Pawar M. M., Waphare B. N. A structure theorem for dismantlable lattices and enumeration // Periodica Mathematica Hungarica. 2002. Vol. 45, No 1-2. P. 147-160.

[45] Dilworth R.P. The structure of relatively complemented lattices // Annals of Math. 1950. Vol. 51. P. 348-359.

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

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

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

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

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

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

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

127

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