Решетки конгруэнций графов тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

л

V Л

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ

ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ ОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

КУЛИКОВ НИКИТА АЛЕКСАНДРОВИЧ

УДК 512.57 .

РЕШЕТКИ КОНГРУЭНЦИЙ ГРАФОВ

01.01.06 — математическая логика, алгебра и теория чисел Автореферат

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

Омск — 1995

Работа выполнена в Новосибирском государственном университете.

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

доцент ГОРБУНОВ В.А.

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

профессор МАРТЫНОВ Л.М. кандидат физико-математических наук, допент БОЛЬБОТ А.Л.

Ведущее учреждение — Новосибирский государственный педагогический универ*

Защита состоится_¿.¿•¿/Я/Л.Ц._]

в_' && часов на заседании Диссертадионного Совета К 064.36.02. при О:

государственном университете по адресу 644077, Омск, пр. Мира, 55-а.

С диссертацией можно ознакомиться в библиотеке Омского государственного верситета.

Автореферат разослан_£ Я СУ-У^/Ь_1

Ученый секретарь Диссертадионного Совета

доктор физико-математических наук /Йу . ' РОМАНЬКОЕ

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

Заметим, что определение конгруэшши па алгебраической системе, предложенное в [5], не дает хорошего соответствия между конгруэтдаями и гомоморфными образами системы и поэтому не получило широкого распространения. Заметим также, что вопрос о конгруэнщшх на алгебраических системах привлекает внимание многих авторов (см. [6, 7, 8, 9]), поскольку он тесно связан с некоторыми областями логического программирования, например, абстрактными типами данных и базами данных.

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

Как правило (кроме §4 главы 1), в диссертации рассматриваются обыкновенные графы, т. е. неориентированные графы без петель. Этот класс графов, дополненный единичным графом, образует квазимногообразие алгебраических систем с одним бинарным предикатом г, определяемое системой квазитождеств:

Ух,у{г(х,у) т(у,х)),

\/х,у(г(х,х) —> X = у).

Лля произвольного графа (7 6 <!> пусть Соп$0 обозначает решетку 5-копгруэншй графа О, т. е. таких конгруэнций 0, что С/в € 5.

В диссертации получены следующие основные результаты:

1) Конечный граф О однозначно, с точностью до изоморфизма, определяется своим порядком |С| и решеткой конгруэнций Соп^О.

2) Если О — конечный граф, то Соп$в — простая решетка тогда и только тогда, когда дополнение <? не является двойной звездой.

3) Дается описание решеток конгруэнции конечных графов.

4) Лается характсризашм хроматических многочленов графов в терминах специальных подполурешеток решеток разбиений и доказывается, что полные г-дольные графы, г < 4, являются хроматически единственными.

Результаты диссертагош являются новыми и имеют теоретическое значение. Они докладывались на 7-ой Всесоюзной конференции по математической логике, посвященной 75-летию академика А.И. Мальцева (Новосибирск, 1984), 19-ой Всесоюзной алгебраической конференции (Львов, 1987), научно-практической конференции, посвященной пятидесятилетию Новокузнецкого государственного педагогического института (Новокузнецк, 1994), а также на заседаниях семинаров "Алгебраические системы", "Теория решеток" и "Алгебра, и логика" при Новосибирского государственного университета.

По теме диссертации опубликовано 6 работ.

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

Перейдем к Солее подробному изложению диссертации.

Первая глава состоит из четырех параграфов и посвящена изучению общих свойств решеток коетруэнний графов.

В §1.1 в терминах теории графов дается определение делителя графа, равносильное определению ^-конгруэнции. Обозначим через 0 дополнение графа &', через Е(0) — множество ребер графа б.

Определение. Пусть й — неединичный граф. Пару г = (т°, т1), где г°,т1 С Е(0), назовем делителем графа й, если г = (Е(С1),Е(С!)), либо выполнены следующие условия:

1) г0Пг' =0;

2) если — ребра одного треугольника графа Сиг ,у£ г", то с 6 7"°;

3) если х, у, г — ребра одного треугольника графа С? и х С г°, у е т1, то г € г1;

4) если я, у — смежные ребра графа С, не принадлежащие никакому треугольнику, и

х 6 т°, то у £ г1.

Заметим, что дапное определение оказалось полезным при исследовании цветосе-мейств и других каазимпогообразий графов (см. [23, 24]).

Во § 1.2 доказываются утверждения, необходимые для доказательства первого основного результата. Эти утверждения имеют также самостоятельное значение, так как в них даются некоторые свойства решетки Соп^С.

Лемма 1.5 Идеал, порожденный коатомом (г?0,!?1) решетки С0И5&, является булевым идеалом тогда и только тогда, когда либо = 0, либо {Р — некоторое множество попарно несмежных ребер, каждое из которьи несмежно ни с одним ребром из тЯ.

Пусть {¡?°, i?1) — делитель графа О и г?°. Обозначим через подмножество

множества г?1, для которого х € тогда и только тогда, когда существует ребро

у 6 К такое, что х, у — смежные ребра в б, не лежащие в одном треугольнике.

Лемма 1.6 Конгруэнция & 6 Со^С? неразложима в сумму тогда и только тогда, когда д = ({.-с},ч?1 (х)) или $ = (0, {я}) для некоторого х 6 Е(й),

С введением решетки Соп^й возникает естественный вопрос: какую информацию о графе б несет решетка С<уп$0 ? Заметим, что вопрос об определимости алгебраической системы сопутствующей структурой не является новым (см., например, [10,11, 12, 13)).

В §1.3 доказывается, что произвольный конечный граф О € <5 определяется своим порядком |Ст'| и решеткой 5-конгруэшшй СопдО.

Для произвольного графа <7 пусть 6" обозначает граф, получающийся из С удалением всех вершин, смежных со всеми остальными вершинами С.

Теорема 1.10 Если С? г/ Сг — неполные конечные графы, то СопзСг = ConsG^ тогда и только тогда, когда С = Граф является полным то/да V только

тогда, когда он не имеет нетривиальных ¿-конгруэнции.

Теорема 1.10 является основным результатом главы 1.

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

В §2.1 второй главы вводится понятие замкнутого подмножества графа — одно из основных понятий диссертации.

Определение. Замкнутым подмножеством графа G называется такое множество М ребер дополнения G, что

М = IJ Е(Л'Л) и V(G)= U V(Kr.) i<¡<¡ i<¡<<

для некоторых попарно непересекающихся подграфов Кр,, i = 1,2,..., í, графа G.

Множество H{G) всех замкнутых подмножеств графа G является полной полурешеткой относительно пересечения. На H(G) рассматривается также частичная операция сложения. Полурешетка H{G) обладает рядом важных свойств, с использованием которых в §2.1 доказывается

Теорема 2.2 II(G) = H(Gi) тогда и только тогда, когда G" = G\. В §2.2 вводится понятие специальной полурешетки.

Определение. Полурешетка называется специальной, если она получается из некоторой решетки разбиений Part(p), 2 < р < и, удалением некоторого числа максимальных фильтров.

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

Теорема 2.3 Специальные полурсшапки и только они являются полурешетками замкнутых подмножеств графов.

С

Из теорем 1.10 и 2.2 следует, что решетка Соп$0 определяется специальной полурешеткой //(й). В §2.3 дается представление решетки СопзО в терминах специальной полу решетки Н(О).

Пусть А1{Н) — множество всех атомов специальной полурешетки Я, Р(Л<(//)) — булева решетка подмножеств множества А1{Н), Н* — множество таких пар (I, Т) € Н х Р(АЦН)), что

а) а г для любого а £ Г;

б) если а + 6 = а + с= Ь-(-с для некоторых атомов а, Ъ, с, а < 2 и 6 € Т, то с е Г;

в) если атомы а, Ь не имеют верхней гралицы в Н и а < I, то Ь 6 Т.

Множество Н" является подполурешеткой в Н X Р(А1{Н)). Пусть Н — класс всех решеток вида Н' @ 1, где Я*ф 1 — решетка, полученная из Н' присоединением наибольшего элемента.

Теорема 2.5 Решетки из класса 7{ и только они являются ргшетками гсопгруэм-ций конечных графов.

С использованием этого представления доказывается

Теорема 2.7 Решетка конгруэщий конечного графа проста тогда и только тогда, когда его дополнение не является двойной звездой.

Теорема 2.7 является вторым основным результатом настоящей работы. В §2.4 лается ответ на вопрос: какой класс решеток порождают решетки конгруэнпий графов данного квазимногообразия ?

Пусть СопК — квазимпогообразие, порожденной решетками конгруэнпий систем из квалимногообразия /С, £ ■— единичное квазимногообразие в решетке подквазимцого-образий квазимногообразия неориентированных графов без петель, [.г = у] —■ квазимногообразие одноэлементных графов, являющееся единственным покрытием для £.

Рис. 2.1: М(к,1,т) — двойная звезда, к > О, I > 0, т > 0.

Теорема 2.12 Лля любого квазимногообразия графов /С, отличного от [х = у] и Е, СопК, совпадает с классол1 всех решеток, а Соп[х = у] совпадает с классом дистрибутивных решеток.

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

Глава 3 посвящена приложению методов, полученных в главе 2, к хроматическим многочленам графов (см. Харари [22]).

Графы йи С?1 называются хроматически эквивалентнъшг1% если их хроматические многочлены /((7, А) и /((?!, А) совпадают.

Пусть а, — число элементов высоты г в полурешетке замкнутых подмножеств Н. Последовательность чисел (ао>«ь-..,^), где к — высота Н, назовем спектром полурешетки II.

Пусть р — число вершин наименьшего графа, определяемого специальной полурешеткой II и (а0,а1,... ,а/,) — спектр II. Многочлен

н

1=0

где [А]* = А(А —1)... (А — к + 1), назовем многочленом, ассоциированным со специальной полу решеткой Н.

В г. Рид [15] (см. также [14]) поднял проблемы об описании хроматических многочленов графов и об описании хроматически эквивалентных графов.

В §-3.1 эти проблемы сводятся к чисто решеточпым задачам.

Теорема 3.3 Многочлены, ассоциированные со спечилльны-ми полурететпками, и только они являются хроматическими многочленами графов.

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

Одним из частных случаев проблемы Рида является вопрос об описании классов хроматически единственных графов.

Граф О называется хроматически единственным, если из равенства хроматических многочленов /(йь Л) и /(С», А) следует, что Сп = С.

В работах [16,17, 18, 19] частично или полностью решается вопрос о хроматической единственности полных двудольных графов А'т,„, т > п > 2. Основным результатом главы 3 является следующая теорема.

Теорема 3.4 Для любых > п2 > ... > пг > 2, где г < 4, полный г-долъный граф 71'пьп2,...,пг является хроматически единственным.

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

Теорема 3.8 Если полурешетка замкнутых подмножеств графа С? имеет высоту I либо изоморфна булевой решетке, то граф б является хроматически единственным.

Следствие 3.9 (Гьюдичи [20]) Лля любого тп > 1 граф Кт,\ является хроматически единственным.

Следствие 3.10 (Лоринс, Уайтхед [21]) Для любых ч > 0, ¿>0сп + г>0 граф пК2и И\'\ является хроматически единственным.

Автор благодарит В. А. Горбунова за внимание к работе и всестороннюю поддержку.

Литература

[1] Горбунов В.А., Туманов В.И. Строение решеток квазимногообразий // Тр, / Ин-т математики СО АН СССР.— 1982,— г. 2,— с. 12-44.

[2] Горбунов В.А. Мощности подпрямо неразложимых систем в квазимногообразиях // Алгебра и логика. 19SS.— т. 25, №2,— с. 3-50

[3] Gorbunov V.A., The structure of the lattices of quasivarieties // Algebra Universalis.— 1994,— v. 32, N«4.— p. 493-530.

[4] Adaricheva K.V., Dziobiak W., Gorbunov V.A., Finite atomistic lattices that can be presented as lattices of quasivarieties // Fundamenta Mathematicae. — 1993.— v. 142, №1.— p. 19-43

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

[6] Plonka Т., On lattices of congruences of relational systems and universal algebras // Algebra Universalis.— 1991 — v, 13, №1,— p. 82-8S.

[7] Adamek Т., Theory of mathematical structures / D. Reidcl Publishing Company.— Dordrecht, 1983.

[S] Rosenberg I.G.,. Sturan Т., Congruence relations of fmitary models / Reprint University of Nutal.— Durban, 19S9.

[9] Slivveigert D., Congruence relations of multialgebras // Discrete Matli..— 1985.— v. 53.— p. 249-253.

[10] Садовский Jl.Б. Некоторые вопросы теории групп // Успехи математических паук — 1968.— т. 23, вып. 3,— с. 123-137.

¡11] Лршинов М.Н., Садовский J1.E. Некоторые теоретико-структурные свойства групп и полугрупп // Успехи математичаских наук.— 1972.— т. 26, вып. 6.— с. 1:39-181.

[12] Molchanov V.A., Semigroups of mappings on graphs // Semigroup Forum.— 1983.— v. 27 — p. 155-199.

[13] Яковлев В.В. О строгой решеточной определимости смешанных нильпотентпых групп // Алгебра и логика.— 1988.—■ т. 27, №5.— с. 604-616.

[14] BirkhofF G.D., Lewis D.C., Chromatic polynomials // Trans. Amer. Math. Soc..— 1946,— v. 60, №3.— p. 355-451.

[15] Read R.C., An introduction to chromatic polynomials // J. of combin. theory.— 1968.— v. 4, M.— p. 52-71.

[16] Saltzberg P.M., Lopez M.A., Guidici R.E., On the chromatic uniqueness of bipartite graphs // Discrete Math..— 1986.— v. 58, №3,— p. 2S5-294.

[17] Koh K.M., Goh D.M., Two classes of chromatically unique graphs // Discrete Math..— 1990,— v. 82, Ji«l.— p. 13-24.

[18] Тео C.P., Koh K.M., The number of shortest cycles and the chromatic uniqueness of .a graph // J. graph theory.— 1992,— v. 16, №1 — p. 7-16.

[19] Feng-Ming Dong, On chromatic uniqueness of two infinite families of graphs // J. graph theory.— 1993,— v. 17, №3.— p. 387-392.

[20] Guidici R.E., Some, new families of chromatically unique graphs // Lecture Notes, Pure and Appl. Math..—1985.— v. 96.— p. 147-158.

[21] Loerinc В., Whitehead E.G., Chromatic polinomials for regular graphs and modified wheels // J. combin. theory.— 1981.— v. В 31, №1.— p. 54-61.

[22] Харари Ф. Теория графов: Пер. с англ.— М.: Мир, 1973.— 300 с.

[23] Кравченко A.B. О квазимногообразиях G-раскрашиваемых графов. // Тезисы докладов Международной конферершдаи по математической логике, посвященной 85-летию академика А.И. Мальцева, ноябрь 1994 г., Новосибирск.— 1994.— с. 56-57.

[24] Кравченко A.B. О сложности решетки квазимногообразий ориентированных графов. // Тезисы докладов Международной конферерядии по математической логике, посвяшенпой 85-летию академика А.И. Мальцева, ноябрь 1994 г., Новосибирск.— 1994,— с. 101-102.

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

[25] Куликов H.A. О решетках конгруэнций графов // Тезисы докладов 7-ой Всесоюзной конферернпии по математической логике, посвященной 75-летию академика А.И. Мальцева, 5-7 сент. 1984 г., Новосибирск.— 1984.— с. 87.

[26] Куликов H.A. Об определимости графов решетками конгруэнций // Алгебра и логика.— 1985.— т. 24, №1.— с. 13-25.

[27] Куликов H.A. Строение решеток конгруэнций конечных графов // Тезисы сообщений 19-ой Всесоюзной алгебраической конференции, 9-11 сент. 1987 г., Львов.— 1987,— ч. 2,— с. 156.

[28] Куликов H.A. Простые решетки конгруэнций конечных графов // Алгебра и логика,— 1990.— т. 29, №1,— с. 3-14.

[29] Куликов H.A. О хроматической единственности графов // Тезисы докладов научно-практической конференции (ноябрь 1994).— Новокузнецк, 1994.— с. 5.

[30] Куликов H.A. О хроматических многочленах графов //Препринт №12.— НИИ Мат. -инф. основ обучения НГУ, 1995.