Мінімальні вкладення повних графів та 1-занурення графів у двовимірні поверхні

Размещено на http://www.allbest.ru/

Київський національний університет імені Тараса Шевченка

УДК 519.17

Автореферат

дисертації на здобуття наукового ступеня

доктора фізико-математичних наук

Спеціальність 01.01.08 - Математична логіка, теорія алгоритмів та дискретна математика

Мінімальні вкладення повних графів та 1-занурення графів у двовимірні поверхні

Коржик Володимир Павлович

Київ - 2010

Дисертація є рукописом

Робота виконана в Інституті прикладних проблем механіки і математики імені Я.С.Підстригача НАН України.

Офіційні опоненти: доктор фізико-математичних наук, професор БАНАХ Тарас Онуфрійович, Львівський національний університет імені Івана Франка, професор кафедри геометрії і топології; доктор фізико-математичних наук, професор ПРОТАСОВ Ігор Володимирович, Київський національний університет імені Тараса Шевченка, провідний науковий співробітник кафедри дослідження операцій; доктор фізико-математичних наук, професор САПОЖЕНКО Олександр Антонович, Московський державний університет імені М.В. Ломоносова, професор кафедри математичної кібернетики.

Захист відбудеться 6 грудня 2010~року о 14 годині на засіданні спеціалізованої вченої ради Д\,26.001.18 при Київському національному університеті імені Тараса Шевченка за адресою: 03127, м. Київ, проспект акад. Глушкова,~6,

Київський національний університет імені Тараса Шевченка, механіко-математичний факультет.

З дисертацією можна ознайомитись у бібліотеці Київського національного університету імені Тараса Шевченка за адресою: 01033, м. Київ, вул.~Володимирська,~58.

Автореферат розісланий 25 жовтня 2010 року.

Вчений секретар спеціалізованої вченої ради В.М. Журавльов

Загальна характеристика роботи

Актуальність теми. Топологічна теорія графів досліджує вкладення графів у двовимірні поверхні. Ця область дослідження, де вивчається взаємодія неперервних та дискретних математичних структур, збагатила математику рядом глибоких результатів, що мають загальноматематичне значення: теорема про розфарбування карт на довільній двовимірній поверхні, відмінної від сфери; теорема про 4 фарби; теорема про скінчену кількість мінімальних заборонених підграфів для кожної поверхні Ця теорема стверджує, що для кожної поверхні існує скінчена множина графів така, що граф не вкладається у тоді і тільки тоді, коли цей граф містить як підграф деякий граф з . (ця теорема стала важливим кроком у доведенні теореми Вагнера Теорема Вагнера стверджує, що для кожної сім'ї графів, замкненою відносно операцій вилучення та стягування ребер, існує скінчена множина графів така, що граф не належить до тоді і тільки тоді, коли цей граф містить як мінор деякий граф з ., що є одним з найбільш глибоких результатів сучасної дискретної математики), і т.п. Ця проблематика має не тільки теоретичне, але і практичне значення. Зокрема, відомо, що знання того, у які поверхні вкладається даний граф, дозволяє знайти ефективні алгоритми розв'язання деяких задач стосовно цього графа.

Топологічна теорія графів, як самостійний напрямок дослідження, бере свій початок з доведення Рінгелем і Янгсом у 1968 році теореми про розфарбування карт на двовимірних орієнтовних та неорієнтовних поверхнях, відмінних від сфери. Ця теорема, для кожної з цих поверхонь, дає значення максимального хроматичного числа графів, що вкладаються у цю поверхню. Доведення цієї теореми поставило багато нових цікавих та глибоких питань.

Мінімальним орієнтовним (неорієнтовним, відповідно) вкладенням графа називається вкладення цього графа у орієнтовну (неорієнтовну, відповідно) поверхню найменшого роду. Доведення теореми про розфарбування карт на поверхнях зводиться до знаходження мінімального орієнтовного та неорієнтовного вкладення кожного повного графа. Для побудови таких вкладень був розроблений апарат графів струмів. Для деяких значень , мінімальне вкладення графа є трикутним, тобто кожна грань вкладення має точно три сторони.

Доведення теореми про розфарбування карт на поверхнях є довгим і технічно складним. Повному доведенню цієї теореми присв'ячена книга Г. Рінгеля "Теорема про розфарбування карт"\ (1974). Найбільш важкою частиною доведення цієї теореми є побудова мінімального орієнтовного і неорієнтовного вкладень кожного повного графа. Актуальним є пошук більш простого доведення цієї теореми. В даній дисертаційній роботі дано більш простий і короткий спосіб побудови мінімального неорієнтовного вкладення кожного повного графу і, як результат, отримано значно більш просте і коротке доведення теореми про розфарбування карт на неорієнтовних поверхонь.

Виникає наступне природне запитанння: якщо важко побудувати одне мінімальне вкладення повного графа, то скільки взагалі існує неізоморфних мінімальних вкладень повного графа? До 2000 р. максимальне число відомих у літературі неізоморфних мінімальних вкладень якогось повного графа не перевищувало трьох (таких повних графів було чотири). В 2000 році, застосовуючи рекурсивні конструкції, Бонінгтон, Греннел, Грігс та Ширан довели, що граф має щонайменше неізоморфних орієнтовних і неорієнтовних трикутних вкладень для , де mod 3. На жаль, ці рекурсивні конструкції дають можливість побудувати тільки неізоморфні трикутні вкладення і тільки для деяких (не всіх) графів , mod 12, так що проблема побудови неізоморфних мінімальних вкладень повних графів залишається актуальною.

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

Клітинні вкладення графів у поверхні можуть бути описані чисто комбінаторно, і тому трикутні вкладення графів можна розглядати як приклад складних дискретних математичних об'єктів. Важлива фундаментальна проблема, пов'язана з дослідженням та застосуванням складних дискретних математичних об'єктів, полягає у тому, що складність цих об'єктів зростає дуже швидко зі зростанням їх розміру, і, як наслідок, дуже важко будувати і описувати такі об'єкти великого розміру і з бажаними властивостями.

В даній дисертаційній роботі для побудови трикутних вкладень повних графів застосовуються графи струмів. Графи струмів є математичним апаратом, що дозволяє, використовуючи групи, "підносити"\ вкладення графа малого розміру до бажаного вкладення графа великого розміру; ці отримані вкладення є високосиметричними, що дозволяє їх просто описувати та застосовувати. В даній роботі за допомогою графів струмів також досліджується відстань між трикутними вкладеннями повного графа (як міра того, наскільки ці вкладення відрізняються).

Актуальним є встановлення зв'язків між задачами побудови вкладень графів та іншими комбінаторними об'єктами. В даній дисертаційній роботі вивчаються застосування систем трійок Штейнера для рішення деяких задач стосовно трикутних вкладень повних графів. Системи трійок Штейнера застосовуються для побудови неізоморфних трикутних вкладень повних графів і для побудови трикутних вкладень повних графів з деякими цікавими властивостями, що стосуються розфарбування вершин цих вкладень.

Трикутні вкладення повних графів мають усі характерні риси складних дискретно-математичних об'єктів, так що можна очікувати, що математичні методи, розроблені для дослідження трикутних вкладень повних графів, знайдуть застосування і при дослідженні інших складних дискретних математичних об'єктів.

Розміщення графів на поверхнях, коли ребра можуть перетинатися, є таким об'єктом дослідження, де на теперішній час ще дуже мало що відомо. Ми кажемо, що граф 1-занурений у поверхню, якщо цей граф зображений на цій поверхні так, що кожне ребро графа перетинається не більш ніж з одним іншим ребром. Мало що відомо стосовно 1-занурень графів у поверхні. Однією з основних відкритих проблем у цій області дослідження є проблема характеризації графів, що мають 1-занурення у дану поверхню. Такої характеризації не відомо для жодної поверхні. Стосовно площини відкритою була наступна проблема: чи є скінченною кількість мінімальних графів, що не мають 1-занурення у площину (якщо ця кількість є скінченною, то тоді графи, що мають 1-занурення у площину, можуть бути зручно охарактеризовані в термінах таких мінімальних підграфів)? В даній дисертації дається негативна відповідь на цю проблему: доводиться, що існує нескінченна кількість таких мінімальних графів.

1-хроматичним числом поверхні називається максимальне хроматичне число графів, які можуть бути 1-зануреними у цю поверхню. Рінгель (1981) отримав верхню межу для 1-хроматичного числа довільної поверхні і висунув гіпотезу, що ця межа є точною для всіх поверхонь (за виключенням, може бути, декількох поверхонь малого роду). Ця гіпотеза залишається відкритою до теперішнього часу. Довгий час прогрес у знаходженні 1-хроматичного числа поверхонь стримувався відсутністю методів побудови 1-занурень повних графів необмежено великого порядку. Все, що було зроблено раніше у літературі, це знайдено 1-хроматичне число для 14 поверхонь малого роду.

У даній роботі розроблено методи побудови 1-занурень повних графів необмежено великого порядку. Це дозволило знайти з точністю до 10 1-хроматичне число кожної поверхні, орієнтовної чи неорієнтовної, а також знайти 1-хроматичне число нескінченної кількості неорієнтовних поверхонь. Можна очікувати, що, як і у випадку теореми про розфарбування карт, спроби доведення цієї гіпотези Рінгеля збагатять математику новими цікавими та потужними методами.

Коли розглядають проблеми, пов'язані з розміщенням графів на двовимірних поверхнях, то топологічні аспекти цих проблем інколи можуть бути описані чисто комбінаторно, а комбінаторні аспекти можуть набути топологічну інтерпретацію. Такий взаємозв'язок збагачує як топологію, так і комбінаторику, даючи можливість застосувати методи, розвинуті в одній області, для розв'язання проблем в іншої області.

Зв'язок роботи з науковими програмами, планами, темами.

Тематика дисертації пов'язана з науково-дослідними роботами "Розвиток методів дослідження ультрапараболічних рівнянь і варіаційних нерівностей та некласичних крайових задач для диференціальних і диференціально-функціональних рівнянь з частинними похідними" (державний реєстраційний номер теми 0106U000595), що проводяться в Інституті прикладних проблем механіки та математики НАН України.

Мета та завдання дослідження. Метою дисертації є встановлення властивостей та розробка методів побудови мінімальних вкладень повних графів та 1-занурень графів у двовимірні поверхні.

Для досягнення поставленої мети у дисертації вирішуються наступні завдання:

(1) знаходження більш простого і короткого доведення теореми про розфарбування карт на неорієнтовних поверхнях;

(2) побудова неізоморфних мінімальних вкладень повних графів;

(3) дослідження конструкцій графів струмів, що породжують трикутні вкладення повних графів;

(4) застосування систем трійок Штейнера для побудови трикутних вкладень повних графів;

(5) дослідження відстані між трикутними вкладеннями повних графів;

(6) дослідження мінімальних не-1-планарних графів;

(7) побудова 1-занурень повних графів;

(8) знаходження нижніх меж на 1-хроматичне число поверхні.

Об'єкт дослідження. Вкладення та 1-занурення графів у двовимірні поверхні, хроматичне число графів на поверхні.

Предмет дослідження. а) Мінімальні вкладення графів у поверхні; б) неізоморфні мінімальні вкладення графів у поверхні; в) побудова і властивості трикутних вкладень графів у поверхні; г) побудова 1-занурень графів у поверхні; д) 1-хроматичне число поверхні.

Методи дослідження. В дисертації використовуються методи комбінаторного аналізу та теорії графів, методи топологічної теорії графів (зокрема метод графів струмів), методи теорії чисел.

Наукова новизна одержаних результатів. Всі результати, отримані в дисертації, є новими.

В даній дисертаційній роботі:

1. Дано більш просте і коротке доведення теореми про розфарбування карт на двовимірних неорієнтовних поверхнях.

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

3. Доведено, що є константи такі, що для кожного є щонайменше неізоморфних орієнтовних і неорієнтовних мінімальних вкладень повного графа .

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

5. Досліджено застосування систем трійок Штейнера для побудови трикутних вкладень повних графів. Як наслідок, побудовано щонайменше неізоморфних неорієнтовних трикутних вкладень графа для нескінченої кількості значень , mod 3 (це перший такий результат для цього класу графів).

6. Застосовуючи системи трійок Штейнера, побудовано неорієнтовні трикутні вкладення повних графів з необмежено великою нещільністью. Цим дано негативну відповідь на відкриту проблему Негамі.

7. Розроблено методи побудови дводольних каскадів, що породжують орієнтовні взаємні вкладення циклічних систем трійок Штейнера. Як наслідок, побудовано неізоморфних орієнтовних взаємних вкладень циклічних систем трійок Штернера порядку .

8. Доведено, що існує нескінченно багато мінімальних графів, що не мають 1-занурення у площину.

9. Знайдено з точністю до 10 1-хроматичне число кожної поверхні, орієнтовної чи неорієнтовної.

10. Знайдено 1-хроматичне число нескінченної кількості неорієнтовних поверхонь.

Практичне значення одержаних результатів. Дисертаційна робота має теоретичний характер. Її результати вже використовувались в працях М. Альбертсона (Smith College, США), Г. Беннета та М. Греннела (The Open University, Великобританія), П. Бонінгтона (University of Auckland, Нова Зеландія), Л. Годдина та Б. Мохар (Simon Fraser University, Канада), Т. Григса та Д. Ширана (The Open University, Великобританія), М. Еллінгхема та С. Стефенса (Vanderbilt University, США), Р. Джекі (Indiana State University, США), Б. Ріхтера (University of Waterloo, Канада), Т. Таккера (Colgate Univerity, США), М. Уоткінса (Syracuse Univerity, США) та інш.

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

Особистий внесок дисертанта. Всі наукові результати, що містяться в дисертаційній роботі, отримані автором самостійно. Із спільних публікацій в дисертацію включені лише ті результати, що належать автору.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідались і обговорювались на наступних міжнародних конференціях: "Вкладення графів та карти на поверхнях"\ (Словаччина, 1997, 2001, 2005), "Дискретна математика та її застосування"\ (Московський державний університет, Москва, 1993, 1998, 2001, 2004, 2007), конференція з комбінаторної математики (Брауншвіг, Німеччина, 1998), а також на наукових семінарах: семінар з теорії графів (університет Сімона Фразера, Ванкувер, Канада, 2007), семінар з дискретної математики (Відкритий університет, Мілтон-Кейнс, Великобританія, 2006), семінар з теорії графів (Науково-технологічний університет, Поханг, Південна Корея, 2005), семінар з дискретної математики (Технічний університет, Дрезден, Німеччина, 1998, 2001).

Публікації. Результати дисертаційної роботи опубліковані в 25 статтях, усі у виданнях з переліку ВАК України, а також в тезах міжнародних конференцій.

Структура та обсяг дисертації. Дисертація складається зі вступу, основної частини, яка включає в себе сім розділів, висновків і списку використаних джерел. Обсяг дисертації - 303 сторінки. Список використаних джерел обсягом 11 сторінок включає 102 найменувань.

Основний зміст

В Розділі 1 зроблено огляд літератури за темою дисертації, а також наведено деякі поняття та результати, що використовуються у наступних розділах. Розділ 1 складається з двох підрозділів.

В підрозділі 1.1 для кожного з розділів даної дисертації висвітлюється робота попередників, пов'язана з питаннями, що розглядаються у цьому розділі. Називаються ті питання, що залишилися невирішеними, та визначається те нове, що дає дисертація у розв'язанні цих проблем.

В підрозділі 1.2 наводяться основні поняття і означення, що використовуються у наступних розділах дисертації. В цьому підрозділі розглядаються базові поняття теорії графів струмів, які є одним з основних методів побудови вкладень графів, що застосовуються в даній роботі. Теорія графів струмів грунтується на можливості чисто комбінаторного опису клітинного вкладення графа у поверхню. Цей опис дається в термінах обертань вершин та типів ребер графа.

Граф струмів є клітинним вкладенням графа, дуги якого марковані елементами (струмами) групи, і задається трійкою , де - орграф, - приписування елементів групи дугам орграфа , - набір обертань вершин орграфа . Індексом графа струмів називається число граней цього вкладення. Дуальною конструкцією до графа струмів є вкладений граф напруг, дуги якого марковані елементами (напругами) тієї ж самої групи. Використовуючи ці приписування напруг, це вкладення графа напруг може бути "піднесеним" до похідного вкладення похідного графа. Це похідне вкладення називається вкладенням. породженим цим графом струмів.

Метод графів струмів є комбінаторним методом, який, використовуючи групу, дозволяє "піднести" вкладення графа малого розміру (у поверхню малого роду) до вкладення графа великого розміру (у поверхню великого роду). Це вкладення графа великого розміру має високу симетрію і, як наслідок, має відносно простий опис, що дозволяє легко модифікувати це вкладення з метою побудови якогось іншого бажаного вкладення. Графи струмів знайшли широке застосування для розв'язання багатьох задач топологічної теорії графів.

В Розділі 2 дається більш просте і коротке доведення теореми про розфарбування карт на неорієнтовних поверхнях. Розділ 2 складається з двох підрозділів.

Хроматичним числом поверхні називається максимальне хроматичне число графів, що вкладаються в цю поверхню. Теорема про розфарбування карт на поверхнях дає хроматичне число кожної поверхні, відмінної від сфери. Для неорієнтовних поверхонь ця теорема була доведена у 1954 р. Рінгелем в термінах схем обертань графів. У 1967 р. Янгс використав графи струмів для доведення теореми про розфарбування карт на неорієнтовних поверхнях у більш короткий і простий спосіб. Відтоді деякі випадки у доведенні були спрощені до деякої міри Ландесманом і Янгсом (1972), і Рінгелем - всі ці спрощення були включені в книгу Рінгеля "Теорема про розфарбування карт" (1974).

Щоб довести теорему про розфарбування карт на неорієнтовних поверхнях, достатньо для кожного побудувати вкладення графа у неорієнтовну поверхню роду 3 для та роду для і ; це вкладення графа називається мінімальним неорієнтовним вкладенням цього графа. У ході доведення теореми про розфарбування карт на неорієнтовних поверхнях мінімальні неорієнтовні вкладення повного графа були побудовані наступним чином. У випадку 0,3,4,5,7,8,11 mod 12 були використані графи струмів індексу один (каскади). Графи струмів індексу три були застосовані у випадку mod 12. У випадку 1,2,6,10 mod 12 були використані індуктивні конструкції індексу два і три.

Графи струмів, що були застосовані у доведенні теореми про розфарбування карт на неорієнтовних поверхнях, відрізняються (коли розглядати різні значення mod 12) своїми графами, індексами, і до того ж треба застосовувати індуктивні конструкції, що використовують графи струмів індексу два і три. Тут виникає природне запитання: чи існує більш просте доведення теореми про розфарбування карт на неорієнтовних поверхнях, яке не має потреби у використанні такого різноманіття конструкцій?

В підрозділі 2.1 дається більш просте і коротке доведення теореми про розфарбування карт на неорієнтовних поверхнях. Це доведення використовує тільки графи струмів індексу один (каскади) і не використовує індуктивних конструкцій. В цьому підрозділі, для кожного , , будується каскад (з групою струмів ), який дає мінімальне неорієнтовне вкладення графа . Ми даємо 12 конструкцій каскадів, залежно від значення mod 12. Тільки одна з цих конструкцій (для mod 12) співпадає з графом струмів, наведеним у літературі.

Головне, що робить наше доведення більш простим і коротким, є те, що ці 12 конструкцій каскадів утворюють таку послідовність, де кожна наступна конструкція отримується незначним перетворенням попередньої конструкції. Відкриття такої послідовності є дещо несподіваним і вказує на можливе існування якихось глибоких і ще невідомих взаємозв'язків у цій області дослідження.

Конструкції графів струмів, що застосовуються у первісному доведенні теореми про розфарбування карт на неорієнтовних поверхнях, є такими, що конструкція, яка дає мінімальне неорієнтовне вкладення графа , має мало чого спільного (якщо взагалі має) з конструкцією, що дає мінімальне неорієнтовне вкладення графа . У результаті, мінімальні неорієнтовні вкладення графів і теж мають мало чого спільного. Схожість мінімального вкладення графа і мінімального вкладення графа можна описати наступним чином. Застосуємо ті ж самі букви для позначення частини вершин графа і графа . Тоді, якщо вкладення графа і графа мають трикутну грань, інцидентну тим самим вершинам , то кажемо, що ця грань є спільною гранью цих двох вкладень. Тут виникає природне запитання: чи можливо побудувати такі мінімальні неорієнтовні вкладення всіх повних графів, що велика частка граней мінімального неорієнтовного вкладення графа є гранями мінімального неорієнтовного вкладення графа ?

В підрозділі 2.2 вивчаються властивості вкладень, породжених каскадами, побудованих в підрозділі 2.1. Каскади , побудовані в підрозділі 2.1, мають ту властивість, що каскади і не дуже відрізняються і мають спільний драбинно-подібний фрагмент великого розміру. Можна розглядати каскад як перетворений каскад такий, що для достатньо великого майже всі вершини каскаду не змінюються при цьому перетворенні. У результаті, мінімальні неорієнтовні вкладення і мають велике число спільних граней. Теорема 2.1 стверджує, що коли прямує до нескінченності, то для що не є mod 12 (відп. для mod 12) щонайменше (відп. всіх граней вкладення є також гранями вкладення $.

З того часу, як було доведено теорему про розфарбування карт на поверхнях, завжди стояло питання, чи можливо побудувати такі мінімальні вкладення повних графів, що можна знайти перетворення, за допомогою яких мінімальне вкладення графа переходить у мінімальне вкладення графа . Результати Розділу 2 дають можливу відповідь на це питання. Вкладення можна розглядати як таке перетворене вкладення , що у ході цього перетворення багато граней вкладення (щонайменше або всіх граней, коли ) не змінюються. Ці грані, що не змінюються, утворюють деякі поверхні з краями. У цьому перетворенні всі відсутні грані вкладення "приклеюються"\ до країв цих поверхонь. Зручно описувати ці перетворення в термінах графів струмів (видалення вершин і формування нових вершин, додавання нових дуг, і т.п.). Знаючи, які грані індуковані якими вершинами каскадів і , можна детально описати, як мінімальне неорієнтовне вкладення графа може бути перетвореним у мінімальне неорієнтовне вкладення графа .

Нехай - граф без петель і кратних ребер. Грань вкладення графа позначається як циклічна послідовність вершин, що отримується, коли ми проходимо границю цієї грані у деякому обраному напрямку і записуємо послідовно зустрічні вершини. Послідовності і позначають ту саму грань. Можна розрізняти вкладення графа як марковані об'єкти (у цьому випадку кажемо про різні вкладення) і як немарковані об'єкти (у цьому випадку кажемо про неізоморфні вкладення). Два вкладення і графа у поверхню називаються ізоморфними, якщо існує автоморфізм графа такий, що якщо - грань вкладення , то - грань вкладення . Цей автоморфізм називається ізоморфізмом вкладення на вкладення .

Побудова мінімального вкладення кожного повного графа є найбільш важкою частиною доведення теореми про розфарбування карт. Первісне доведення цієї теореми дає одне мінімальне орієнтовне і одне мінімальне неорієнтовне вкладення повного графа для кожного . Виникає наступне природне запитанння: якщо важко побудувати одне мінімальне вкладення повного графа, то скільки взагалі існує неізоморфних мінімальних вкладень повного графа? Барнет (1982) показав, что граф має точно одне неорієнтовне трикутне вкладення. Негамі (1983) довів, що граф має точно одне орієнтовне трикутне вкладення.

До 2000 року максимальне число відомих у літературі неізоморфних мінімальних вкладень (всі ці відомі мінімальні вкладення були трикутними) якогось повного графа (ці графи є , , та ) не перевищувало трьох. Тільки в останні роки було показано, що повні графи мають багато (точніше, дуже багато) неізоморфних мінімальних вкладень. Прямою компютерною перевіркою було знайдено, що граф має точно 59 неізоморфних орієнтовних трикутних вкладень (Альтшулер, Боковски та Шухерт (1996)), а графи та мають точно, відповідно, 182200 та 243088286 неізоморфних неорієнтовних трикутних вкладень (Елінгхем та Стефенс (2005)).

Були розроблені теоретичні (тобто відмінні від компютерного перебору) методи побудови великого числа неізоморфних мінімальних вкладень повних графів з необмеженим числом вершин. Зараз відомі два таких теоретичних методи.

Перший метод (Бонінгтон, Греннел. Грігс та Ширан (2000, 2002) використовує рекурсивні конструкції та перетворення поверхонь і дає можливість побудувати щонайменше неізоморфних орієнтовних (відп. неорієнтовних) трикутних вкладень графа тільки для деяких сімей (не для всіх) значень таких, що mod 12 (відп. mod 6). Відзначимо, що відома (Елінгхемом і Стефенсом (2005)) верхня межа на число неізоморфних трикутних вкладень графа випливає з верхньої межи на число різних двократних систем трійок порядку .

Другий метод поданий у даній дисертації. Цей метод використовує графи струмів і дає щонайменше неізоморфних орієнтовних і неорієнтовних мінімальних вкладень кожного повного графа . Крім того, цей метод дозволяє будувати таких неізоморфних вкладень повного графа , що ці вкладення не обов'язково є мінімальними, а можуть мати різні бажані властивості (наприклад, для деякого цілого , всі грані вкладення мають бути -кутними).

В Розділі 3 дисертації вивчаються такі методи побудови неізоморфних вкладень повних графів, що базуються на застосуванні графів струмів індексу один (каскадів), і далі ці методи застосовуються для побудови щонайменше мінімальних неорієнтовних вкладень графа . Розділ 3 складається з трьох підрозділів.

В підрозділі 3.1 розглядаються ті клітинні вкладення повного графа , що породжуються схемами на абелевих групах. Схемою на абелевій групі порядку називається пара , де - циклічне переставлення всіх ненульових елементів групи і - множина ненульових елементів групи така, що якщо , то і . Схема породжує клітинне вкладення графа , множина вершин якого є множиною всіх елементів групи . Це вкладення визначається обертанням кожної вершини графа і множиною ребер типу 1.

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

Теорема 3.1.1 Нехай схеми і на абелевій групі породжують вкладення і , відповідно. Припустимо, що виконується (a) або (b):

(a) - непарне;

(b) - парне і або , або .

Тоді ці вкладення ізоморфні тоді і тільки тоді, коли ці схеми еквівалентні.

Теорема 3.1.1 є внеском не тільки в топологічну теорію графів, але і в теорію карт Кейлі, що було відзначено в останньому огляді Ріхтера, Шірана, Джайкея, Таккера та Уоткінса (2005) теорії карт Кейлі.

Кожна схема на абелевій групі визначається каскадом з групою струмів . На множині всіх каскадів, що визначають схеми на , означається відношення еквівалентності і доводиться наступна теорема.

Теорема 3.1.2 Дві схеми і на еквівалентні тоді і тільки тоді, коли каскади і , відповідно, що визначають ці схеми, є ізоморфними.

Теореми 3.1.1 та 3.1.2 зводять проблему побудови неізоморфних вкладень, породжених схемами на абелевій групі, до проблеми побудови неізоморфних каскадів.

В підрозділі 3.2 вивчаються методи побудови сімей неізоморфних каскадів. Якщо трійка є каскадом, то кажемо, що обертання є один-обертанням для пари (каскад задає таке вкладення графа, дугам якого приписані струми, що це вкладення має точно одну грань. Для кожної пари на групі можна розглядати її групу автоморфізмів, яка визначається групою автоморфізмів орграфа і групою автоморфізмів групи .

Теорема 3.2.1 Припустимо, що група автоморфізмів пари має порядок . Припустимо, що існує різних один-обертань для пари . Тоді серед цих різних каскадів є щонайменше неізоморфних каскадів.

У випадку, коли група автоморфізмів пари є складною або невідомою, можна обмежитись наступною теоремою, що вимагає знання тільки групи автоморфізмів орграфа .

Теорема 3.2.2 Припустимо, що існує різних один-обертань для пари . Припустимо, що група автоморфізмів орграфа має порядок . Тоді серед цих різних каскадів є щонайменше неізоморфних каскадів.

Щоб застосовувати Теореми 3.2.1 та 3.2.2 для побудови сімей неізоморфних вкладень повного графа, необхідно вміти будувати багато різних один-обертань для пари . Дві пари суміжних вершин орграфа називаються неперетинними, якщо ці пари не мають спільних вершин.

Твердження 3.2.1 Нехай - каскад. Припустимо, що орграф має неперетинних пар суміжних тривалентних вершин. Тоді пара має щонайменше різних один-обертань.

Твердження 3.2.2 є ускладненим варіантом Твердження 3.2.1 і дає умови існування різних один-обертань для пари таких, що різних каскадів визначають різних пар таких, що для кожних двох пар і з цих пар, множини і задовольняють умові (b) Теореми 3.1.1.

Кожний каскад, побудований в даній дисертаційній роботі, має драбинно-подібний фрагмент і вершини ребер, що є "поперечинами"\ цього фрагмента, є неперетинними парами суміжних тривалентних вершин.

В підрозділі 3.3 Теореми 3.2.1 та 3.2.2 застосовуються для доведення Теорем 3.3.1-3.3.4, які стверджують, що для кожного цілого числа існують такі цілі числа і , що повний граф для має щонайменше неізоморфних неорієнтовних мінімальних вкладень. Відзначимо, що для mod 3 ці вкладення є трикутними. Числа є, відповідно, числами 2,2,6,3,2,2,2,2,2,4,3,2, а числа є, відповідно, числами 2,1,6,5,2,4,3,1,4,9,3,3.

Щоб довести ці теореми, для кожного будується каскад з групою струмів , . Для маємо і каскад породжує мінімальне неорієнтовне вкладення графа . Для маємо і каскад породжує вкладення графа , яке може бути перетвореним (додаванням нових вершин і ребер, плівок Мебіуса, і т.п.) у мінімальне неорієнтовне вкладення графа . Орграф має неперетинних пар суміжних тривалентних вершин, що дає, за Твердженням 3.2.2, різних один-обертань для пари . Показується, що пара не має нетотожних автоморфізмів, отже, за Теоремою 3.2.1, серед цих різних каскадів є щонайменше неізоморфних каскадів, які, за Теоремою 3.1.2, визначають неізоморфних схем, що породжують неізоморфних вкладень графа . Для , коли , ці вкладень графа є неізоморфними мінімальними неорієнтовними вкладеннями. Для , коли , доводиться, що ці неізоморфних вкладень графа можна перетворити у неізоморфних мінімальних неорієнтовних вкладення графа (щоб це довести, використовується поняття ланки для двох вершин вкладеного графа).

Ланкою для вершин і вкладення називається кожна пара і суміжних трикутних граней цього вкладення. В даній роботі, щоб довести, що вкладення і графа є неізоморфними, використовується знання множини ланок цих вкладень. Для довільних двох вершин і графа , якщо - ізоморфізм вкладення на , то вершини і вкладення та вершини і вкладення мають однакову кількість ланок. Отже, щоб довести, що вкладення і неізоморфні, достатньо показати, що для кожного автоморфізма графа є такі дві вершини і цього графа, що вершини і вкладення та вершини і вкладення мають різну кількість ланок.

Розділ 4 дисертації присвячено розробці методів побудови неізоморфних орієнтовних мінімальних вкладень повних графів. В цьому розділі показується, що для кожного цілого числа існують такі цілі числа і , що повний граф для має щонайменше неізоморфних орієнтовних мінімальних вкладень. Відзначимо, що для 3,4,7 mod 12 ці вкладення є трикутними. Числа є, відповідно, 2,3,11,1,2,3,1,4,1,1,1,2, а числа є, відповідно, 3,3,11,0,2,2,0,3,0,1,2. Також показується, що граф , , має щонайменше неізоморфних орієнтовних мінімальних (трикутних) вкладень. Розділ 4 складається з чотирьох підрозділів.

В першій частині підрозділу 4.1, застосовуючи результати Розділу 3, побудовано (Теореми 4.1.1 та 4.1.2} неізоморфних орієнтовних трикутних вкладень графа для 4,7.

В другій частині підрозділу 4.1 побудовано (Теореми 4.1.3 - 4.1.10) неізоморфних орієнтовних мінімальних вкладень графа для 1,2,5,6,8,9,10,11. Ці неізоморфні вкладення будуються за допомогою графів струмів індексу один або три, вибираючи різні обертання цих графів. Ці мінімальні вкладення є нетрикутними, і, як наслідок, неізоморфність цих вкладень можна довести не використовуючи результати Розділу 3, а тільки враховуючи деякі спеціальні властивості цих мінімальних вкладень.

В підрозділах 4.2 та 4.3 будуються неізоморфні орієнтовні трикутні вкладення графа для 0,3. Ці вкладення не можуть бути породженими каскадами з абелевою групою струмів, отже результати Розділу 3 не можуть бути безпосередньо застосованими для побудови цих вкладень.

Побудова орієнтовного трикутного вкладення графа була найбільш важким випадком у ході доведення теореми про розфарбування карт на поверхнях. Уперше орієнтовне трикутне вкладення графа було побудовано Террі, Велшем та Янгсом (1967) з використанням графа струмів індексу один з неабелевою групою струмів, цей граф струмів є складним. Пенгеллі та Юнгерман (1979) показали, що не існує графів струмів індексу один, два і три з групою струмів , які могли б породжувати орієнтовне трикутне вкладення графа . Граф струмів індексу чотири з групою струмів , який породжує орієнтовне трикутне вкладення графа , був запропонований Пенгеллі та Юнгерманом (1979). Цей граф струмів є складним, конструкція цього графа струмів залежить від значення mod 8 і тільки для mod 8 цей граф струмів був наведений в літературі.

В підрозділі 4.2 для і кожного будується граф струмів індексу чотири з групою струмів , цей граф струмів породжує орієнтовне трикутне вкладення графа . Конструкція цього графа струмів залежить від значення mod 4. Всі чотири випадки детально описані. Цей граф струмів будується з більш простих конструкцій (базисної драбини і чотирьох бічних блоків) і є більш простим, ніж граф струмів, запропонований Пенгеллі та Юнгерманом.

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

Для даного вкладеного графа, дві вершини і деякої підмножини множини вершин цього графа називаються -зчепленими () відносно підмножини , якщо є послідовність , () вершин підмножини така, що для вершини і мають ланок.

Лема 4.2.1 показує, що множина вершин графа розбивається на чотири підмножини порядку такі, що для деяких цілих додатних чисел у орієнтовному трикутному вкладенні графа , породженого довільним графом струмів , кожні дві вершин з різних підмножин мають щонайбільше ланок, а кожні дві вершини кожної підмножини з цих чотирьох підмножин є -зчепленими відносно . Це означає, що якщо вкладення, породжені двома різними графами струмів , є ізоморфними, то цей ізоморфізм відображає всі вершини кожної з цих чотирьох підмножин на всі вершини деякої з цих чотирьох підмножин. Для двох з цих підмножин, для кожної з цих двох підмножин грані вкладення графа , інцидентні тільки вершинам цієї підмножини, є гранями, які можна розглядати як грані вкладення, породженого каскадом, включеним у цей граф струмів індексу чотири.

Теорема 4.2.2 показує, що якщо вкладення графа , породжені двома різними графами струмів , є ізоморфними, то тоді вкладення, породжені двома каскадами, включеними в один з цих графів струмів, є ізоморфними, відповідно, до вкладень, породжених двома каскадами, включеними в інший граф струмів. Оскільки каскади, включені в графи струмів , породжують вкладення графа $K_{3s}$, то, згідно з Теоремами 3.1.1. та 3.1.2, вкладення, породжені такими двома каскадами, є ізоморфними тоді і тільки тоді, коли ці каскади ізоморфні.

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

Теорема 4.2.3 стверджує, що серед цих різних орієнтовних трикутних вкладень графа є щонайменше неізоморфних вкладень.

В підрозділі 4.3 для кожного будується граф струмів індексу три з групою струмів , цей граф струмів породжує орієнтовне трикутне вкладення графа . Граф струмів містить два підграфи (вони називаються -гребенями), які можна розглядати як каскади, включені в цей граф струмів.

-гребень є каскадом з тривалентними вершинами, решта вершин є одновалентними. Вибираючи різні обертання цих тривалентних вершин, отримаємо різних -гребенів. Кожний з цих -гребенів породжує орієнтовне трикутне вкладення графа без ребер , . Кожне з цих вкладень має ту властивість, що тривалентні вершини -гребеня індукують трикутні грані, одновалентні вершини -гребеня індукують нетрикутні грані, і, як результат, трикутні грані вкладення утворюють неперетинних кластерів, де кожні дві суміжні трикутні грані вкладення належать до того ж самого кластера. У результаті, перевірка ізоморфності двох таких вкладень графа зводиться до перевірки ізоморфності кластера одного вкладення до кластера іншого вкладення.

Теорема 4.3.1 дає умови, при виконанні яких є ізоморфними вкладення, що породжені -гребенями з різними наборами обертань цих тривалентних вершин. А саме, на множині всіх можливих наборів обертань цих тривалентних вершин означається відношення еквівалентності і Теорема 4.3.1 доводить, що якщо вкладення графа , породжені -гребенями з різними наборами обертань цих тривалентних вершин є ізоморфними, то ці набори обертань є еквівалентними.

Позначимо через граф струмів індексу три, що виходить з графа струмів , коли набори обертань тривалентних вершин двох -гребенів, включених в , є, відповідно, і .

Лема 4.3.1 показує, що орієнтовне трикутне вкладення графа , породжене довільним графом струмів , має ту властивість, що множина вершин графа розбивається на три підмножини порядку такі, що кожні дві вершини кожної з цих підмножин мають щонайменше ланки, а кожні дві вершини з різних підмножин мають менше ніж ланок. Це означає, що якщо вкладення, породжені двома різними графами струмів є ізоморфними, то цей ізоморфізм відображає всі вершини кожної з цих трьох підмножин у всі вершини деякої з цих трьох підмножин. Для двох з цих підмножин, для кожної з цих двох підмножин грані вкладення графа , інцидентні тільки вершинам цієї підмножини, є гранями, які можна розглядати як грані вкладення, породженого -гребенем, включеним у цей граф струмів індексу три.

Теорема 4.3.2 показує, що якщо вкладення графа , породжені двома різними графами струмів є ізоморфними, то тоді вкладення, породжені двома -гребенями, включеними в один з цих двох графів струмів, є ізоморфними, відповідно, вкладенням, породженими двома -гребенями, включеними в інший граф струмів.

Вибираючи різні обертання тривалентних вершин кожного з двох -гребенів, включених в граф струмів , дістанемо різних графів струмів , що породжують різні орієнтовні трикутні вкладення графа . Теорема 4.3.3 доводить, що серед цих різних орієнтовних трикутних вкладень графа , , є щонайменше неізоморфних вкладень.

Результати Розділу 3 дають можливість будувати такі неізоморфні вкладення повних графів, що мають різні бажані властивості (не тільки бути мінімальними). Підрозділ 4.4 наводить приклад такого застосування результатів Розділу 3. Теорема 4.4.1 доводить, що граф , , має щонайменше таких неізоморфних орієнтовних вкладень графа що кожна грань цих вкладень є чотирикутною. Відзначимо, що рекурсивні методи побудови неізоморфних вкладень повних графів, запропоновані Бонінгтоном, Греннелом, Грігсом та Шираном (2000, 2002), можуть бути застосованими тільки для побудови трикутних (гране 2-розфарбованих) вкладень деяких повних графів.

Дослідження структури множини всіх різних дискретних об'єктів одного і того ж класу має великий математичний інтерес. Перший крок у цьому напрямку - це дослідження відмінностей між таким дискретними об'єктами. Як міра того, наскільки ці об'єкти можуть відрізнятися друг від друга, вводиться поняття відстані між таким двома об'єктами.

Дрепал (1992, 1999, 2000) вивчав відстань між групами одного і того ж порядку. Донован, Оурс-Уильямс та Прегер (1997) дослідили відстань між латинськими квадратами. Відстань між системами трійок Штернера вивчалася Форбсом, Греннелом та Грігсом (2007). До цього часу відстань між трикутними вкладеннями графа не досліджувалася. Це, можливо, пояснюється складністю побудови трикутних вкладень повних графів.

В Розділі 5 розглядається відстань між трикутними вкладеннями повного графа. Позначимо через грань, інцидентну вершинам і вкладеного графа. Нехай і - два трикутних вкладення повного графа . Для бієкції , позначимо через множину таких граней вкладення , що не є гранью вкладення . Відстанню між вкладеннями і називається мінімальне значення величини для всіх бієкцій між вершинами графа . Інакше кажучи, відстань є таким мінімальним числом , що можна замінити граней вкладення на нові граней і отримати трикутне вкладення, ізоморфне вкладенню .

Розділ 5 складається з двох підрозділів.

В підрозділі 5.1 досліджується мінімальне ненульове значення відстані для всіх трикутних вкладень і повного графа. Основним результатом цього підрозділу є Теорема 5.1.1 яка стверджує, що 4 є мінімальною ненульовою відстанню у випадку, коли і неорієнтовні, і що 6 є мінімальною ненульовою відстанню у випадку, коли і орієнтовні, і у випадку, коли є орієнтовним і є неорієнтовним вкладенням. вкладення графа струм неізоморфний

Щоб довести Теорему 5.1.1, ми спочатку знаходимо нижню межу нп мінімальну ненульову відстань між трикутними вкладеннями повного графа, а потім, застосовуючи каскади, будуємо пари трикутних вкладень повного графа, на яких досягається ця нижня межа.

В підрозділі 5.2 вивчається питання, наскільки великою може бути відстань між двома трикутними вкладеннями повного графа. Основним результатом цього підрозділу є

Теорема 5.2.1 Для кожного цілого числа , якщо - просте число і - первісний корінь по модулю , то тоді існують такі неорієнтовні трикутні вкладення і повного графа , що , де - число граней трикутного вкладення графа .

Нагадаємо, що число 2 - первісний корінь по модулю простого числа , якщо є найменшим цілим числом таким, що mod .

Невідомо, чи існує нескінченно багато таких , що задовольняють умовам Теореми 5.2.1, але є аргументи на користь того, що таких значень нескінченно багато. Знаменита гіпотеза Артіна стверджує, що для даного цілого числа такого, що не є квадратом іншого цілого числа і , існує нескінченно багато простих чисел таких, що - первісний корінь по модулю . Ця гіпотеза є відкритою, але є багато теоретико-числових аргументів на користь цієї гіпотези. За законом квадратичної взаємності, число 2 може бути первісним коренем по модулю тільки тоді, коли число має вигляд або (тобто, , mod 2). Оскільки числа 8 і 5 - взаємно прості, то за відомою теоремою Діріхле , арифметична прогресія , містить нескінченно багато простих чисел. Отже, можна припускати, що арифметична прогресія , , містить нескінченно багато таких простих чисел вигляду , не є mod 3, що 2 - первісний корінь по модулю .

Щоб довести Теорему 5.2.1, використовуючи каскади будуємо такі трикутні вкладення і того ж самого повного графа, що у вкладенні деякі пари вершин мають велику кількість ланок, а у вкладенні кожна пара вершин має малу кількість ланок.

Майже всі каскади, побудовані в літературі, породжують такі трикутні вкладення повного графа, що деякі пари вершин мають велику кількість ланок, а переважна більшість пар вершин або не має ланок, або має мало ланок.

Щоб довести Теорему 5.2.1, побудовано каскад з групою струмів , де число є простим і 2 - первісний корінь по модулю . Приписування струмів дугам цього каскаду використовує властивості числа 2 як первісного кореня по модулю і, в результаті, цей каскад породжує таке неорієнтовне трикутне вкладення повного графа , у якому кожна пара вершин має щонайбільше 8 ланок.

Гіпотеза. Існує константа така, що якщо повний граф має трикутні вкладення, то для кожних двох трикутних вкладень і цього графа виконується

де - число граней трикутного вкладення графа .

Інакше кажучи, ця гіпотеза стверджує, що кожні два трикутних вкладення повного графа мають багато, а саме, не менше ніж

спільних граней (з точністю до перепозначення вершин цього повного графа).

Кожна відповідь до цієї гіпотези, позитивна чи негативна, буде цікавою, бо дасть нам розуміння того, наскільки різними можуть бути трикутні вкладення повного графа.

Актуальним є встановлення зв'язків між задачами побудови вкладення графів та іншими комбінаторними об'єктами. В Розділі 6 вивчаються застосування систем трійок Штейнера для рішення деяких задач стосовно трикутних вкладень повних графів.

Системою трійок Штейнера порядку називається упорядкована пара , де - -елементна множина і - множина 3-елементних підмножин множини (трійки), такі, що кожна 2-елементна підмножина множини входить точно в одну трійку. Така система трійок існує тоді і тільки тоді, коли mod 6 (такі значення називаються припустимими).

Трикутне вкладення графа називається гранє -розфарбованим, якщо - найменьше ціле число таке, що грані цього вкладення можуть бути розфарбовані фарбами так, що суміжні грани отримають різні кольори. За відомою теоремою Брукса (1941), .

До теперішнього часу, у літературі, коли розглядали зв'язок між системами трійок Штейнера та трикутними вкладеннями повних графів, то системи трійок Штейнера завжди асоціювалися з гранями одного кольору гране 2-розфарбованих трикутних вкладень повних графів.

В Розділі 6 ми застосовуємо системи трійок Штейнера у інший спосіб. Ми асоціюємо системи трійок Штейнера з тим способом, у який деякі допоміжні вкладення поєднуються, щоб утворити трикутне вкладення повного графа.

У цьому підході кожна трійка представляє "вилку"\ , що поєднує три допоміжні вкладення.

В підрозділі 6.1 будуються ці допоміжні вкладення.

Позначимо через таке клітинне вкладення повного графа , яке має грані, кожна з яких є -кутною і інцідентною всім вершинам графа , а всі інші грані є трикутними.

Розглянемо -вершинний граф, який дістанемо, якщо візьмемо три неперетинні -цикли , , і , і з'єднаємо ребром кожну пару вершин різних -циклів. -вилкою називається таке клітинне неорієнтовне вкладення цього графа, що три грані є -кутними з границями , , і , відповідно, а всі інші грані є трикутними.

Основним результатом підрозділу 6.1 є

Лема 6.1.1

(а) Вкладення існує для кожного такого цілого числа , що $12s+7$ - просте число.

(b) Для кожного цілого числа , існує різних позначених -вилок з тією ж самою множиною вершин і з тими ж самими границями -кутних граней.

В підрозділі 6.2 системи трійок Штейнера застосовуються для побудови неізоморфних неорієнтовних трикутних вкладень повних графів. Основним результатом цього підрозділу є

Теорема 6.2.1 Для кожного цілого числа такого, що - просте число, повний граф , де , має щонайменше неізоморфних гране 3-розфарбованих неорієнтовних трикутних вкладень.

Трикутні вкладення графа , стосовно яких йде мова у Теоремі 6.2.1, отримуються у наступний спосіб. Беремо неперетинних копій , вкладення .

Далі беремо систему трійок Штейнера на множині і для кожної трійки , беремо -вилку і ототожнюємо границі трьох -кутних граней цієї вилки, відповідно, з границями -кутних граней вкладень , і (внутрішності всіх цих -кутних граней видалені).

Дістаємо неорієнтовне трикутне вкладення повного графа

.

Рекурсивні конструкції, використані Бонінгтоном, Греннелом, Грігсом та Шираном (2000, 2002), зробили можливим побудову неізоморфних гране 2-розфарбованих неорієнтовних трикутних вкладень графа для mod 3. Оскільки , Теорема 6.2.1 є першим відомим прикладом побудови щонайменше , , неізоморфних неорієнтовних трикутних вкладень графа , , mod 3. Ці вкладення є гране 3-розфарбованими.

В підрозділі 6.3 системи трійок Штейнера застосовуються для побудови неорієнтовних трикутних вкладень повних графів з необмежено великою нещільністю.

Нещільністю трикутного вкладення повного граф у замкнуту поверхню називається мінимальне натуральне число таке, що для кожного приписування фарб вершинам цього вкладення (так, що кожна фарба використана) існує грань, вершини якої пофарбовані в три різні кольори.

Трикутне вкладення графа з нещільністю має "-подібну" структуру. Це означає, що таке вкладення може бути отриманим у такий спосіб: беремо вкладень повних графів , відповідно, (тут ), потім ці вкладення поєднуємо циліндрами, а потім триангулюємо кожний циліндр ребрами, які з'єднують вершини, що лежать на протилежних краях циліндра.

Мотивація розглядати нещільність трикутних вкладень з'явилася при спробах довести, що два трикутні вкладення повного графа не ізоморфні. Ароха, Брахо та Неймана-Лара (1995) побудували пари неорієнтовних трикутних вкладень повних графів з нещільністю 3 і принаймі 4, відповідно; тобто були отримані пари неізоморфних трикутних вкладень, і було підняте питання, чи існує трикутне орієнтовне вкладення повного графа із нещільністю принаймі 4. Як це не дивно, але це питання все ще залишається відкритим.