Понеділок, 14 жовтня 2013 Автор Опубліковано в Cтатті & Публікації

Твердження в забороненому мінорі

(13 голосів)
Перегляди: 48485 разів
Джан-Карло Рота - американський математик і філософ Джан-Карло Рота - американський математик і філософ

В середині серпня 2013 року троє математиків - Джоф Уіттл (Geoff Whittle), Джім Джилін (Jim Geelen) і Берт Гегардз (Bert Gerards) - оголосили, що їм вдалося довести гіпотезу Роти. Ця гіпотеза (яку сформулював Жан-Карло Рота в 1970-му році) відноситься до матроїдів - об'єктів, вкрай популярних в комбінаториці та геометрії. Робота математиків ще не опублікована, однак, схоже, немає сумнівів у тому, що гіпотезу доведено.

«Ми більше не в Матриці»

Сам термін «матроїд» виник у роботі «Абстрактні властивості лінійної залежності» (.pdf ) Хасслера Уітні в 1935 році. Ми розпочнемо з абстрактного визначення цього об'єкта, а потім покажемо, як він природним чином виникає в різних задачах - від геометрії до програмування.

Отже, нехай задано деяку скінченну множину E. Вона називається носієм матроїда. Серед всіх підмножин цієї множини виділено деякий набір підмножин I, що задовольняє трьом умовам :

  1. Набір містить порожню множину.
  2. Якщо набір містить підмножину H, то він містить і всі підмножини H.
  3. Якщо і K  - дві різні підмножини E, що містяться в I, причому в H елементів менше, ніж в K , то в K можна вибрати такий елемент a, що, додавши його до H , ми отримаємо підмножину H', яка також лежить в I.

Підмножини, які потрапили в набір I, називають незалежними. В протилежному випадку - залежними.

Наведемо декілька прикладів. Розглянемо носій E, що складається з одного елемента {x}. Множина усіх підмножин такого носія складається рівно з двох підмножин - порожньої підмножини і усієї підмножини {x}. Враховуючи, що за першою умовою у визначенні матроїда порожня множина мусить завжди потрапляти в набір I, варіантів цього набору залишається рівно два - порожня множина і порожня підмножина разом з усією множиною. Для обох наборів решта властивостей з означення матроїда, очевидно, виконуються.

Якщо в носії E  два елементи {x, y}, то, з врахуванням порожньої підмножини, у такої множини рівно 4 підмножини. Всього можна придумати 15 наборів підмножин. Матроїдів буде набагато менше. Справді, візьмемо підмножину з максимальним числом елементів, що входять в матроїд. Якщо в такій множині 0 елементів, то матроїд складається тільки з порожньої множини; якщо це число дорівнює 1, то матроїдів три - ті, які окрім порожньої множини містять або {x}, або {y}, або обидві з цих підмножин; якщо ж число дорівнює 2, то за третім пунктом означення такий матроїд єдиний і містить всі підмножини E. Тобто загалом ми отримали п'ять матроїдів на двохелементному носії.

Нехай тепер множина E складається з n елементів. Універсальним матроїдом Uk,n  називається матроїд, що складається з усіх підмножин множини E, в яких не більше k елементів. Побудовані вище для одноелементного носія матроїди є універсальними і позначаються U0,1  і  U1,1 .  З п'яти матроїдів для двохелементної множини три є універсальними - це U0,2 , U1,2  і  U2,2 .

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

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

Обмеження працює таким чином - ми беремо і викидаємо з E деяку кількість елементів. Залишається множина, яку ми позначимо S. Якщо на E був заданий матроїд M, то залишаємо тільки ті незалежні підмножини, які цілком потрапили в S. Результат такого викидання виявляється матроїдом вже на S і називається результатом обмеження матроїда на S.

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

Розглянемо роботу цієї операції на прикладі. Візьмемо вже знайомий нам двохелементний носій E і викинемо з нього один елемент. В результаті отримаємо одноелементний носій S. Легко перевіряється, що при обмеженні на S матроід U2,2 перетворюється на U1,1. При цьому, обмеження на S U1,2 також дає U1,1. Загалом, операція не найпростіша.

Стиснення матроїда влаштовано трохи складніше. З E знову викидаються деякі елементи, щоб залишилася множина S. При цьому носієм стиснення будуть викинуті елементи. Підмножина H такого носія називається незалежною, якщо після додавання до нього будь-якої незалежної множини з S отримується незалежна множина у вихідному матроїді. Стиснення матроїда U2,2 на одноелементну підмножину знову дає U1,1.

Потрібно триматися коренів

Тепер, коли з мотивацією завершено, можна перейти до змістовних з точки зору теорії прикладів матроїдів. Отож, нехай задано звичайну матрицю - прямокутну таблицю з m рядками і n стовпцями. Стовпці матриці можна додавати (покомпонентно), множити на числа (також покомпонентно). Набір стовпців s1, ... , sk називається лінійно залежним, якщо існують такі числа ai (серед них має бути хоча б одне ненульове), що, перемноживши стовпці на ці числа і додавши, тобто a1s1 + ... + aksk, ми отримаємо нульовий стовпчик.

Розглянемо кілька прикладів. Якщо k=1, то стовпець повинен бути нульовим, оскільки a1 має бути ненульовим. Якщо k=2, то два стовпці залежні тоді і тільки тоді, коли вони пропорційні з деяким коефіцієнтом. Коли k>2, то ситуація дещо ускладнюється. Наприклад, якщо задано матрицю 3 на 3, то її стовпці залежні, якщо всі три вектори, які відповідають стовпцям, лежать в одній площині.

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

Матроід Фано

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

Графові матроїди

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

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

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

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

Граф називають плоским, якщо його можна зобразити на площині так, що його ребра не перетинатимуться. Розглянемо тепер матроїд графів. Будемо називати матроїд забороненим мінором, якщо граф, за яким він побудований, не плоский , однак, будь-який його підграф - уже плоский. Легко зрозуміти, що граф не плоский, якщо і тільки якщо в якості одного зі своїх мінорів він містить заборонений мінор. Теорема Вагнера стверджує, що таких заборонених мінорів всього два. Вони відповідають так званим графам K5 і K3,3.

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

Деякі заборонені графи на торі

Гіпотеза Роти

Полем в математиці називається множина з набором операцій (зазвичай їх позначають додаванням і множенням), що володіють певними властивостями. Найпростіший приклад поля - це множина дійсних чисел. По-перше, елементи цієї множини можна додавати, причому додавання асоціативне (тобто p+(q+r)=(p+q)+r); комутативне (від зміни місць доданків сума не змінюється); існує нейтральний елемент, який називають нулем (нейтральний, тобто його сума з будь-яким числом дає це ж число), і для кожного елемента q визначено зворотний -q, сума з яким дає нейтральний елемент. По-друге, елементи цієї множини можна множити, причому множення також асоціативне, комутативне, володіє нейтральним елементом (одиниця) і для кожного ненульового q визначено зворотний елемент 1/q, добуток з яким дає нейтральний елемент, тобто одиницю. Додавання і множення пов'язані так званим дистрибутивним законом p(q+r)=pq+pr.

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

Тепер розглянемо матроїди і задамося питанням, які з них матричні? Виявляється, властивість матроїда не бути матричним якраз підходить для визначення заборонених мінорів. У результаті, якщо в матриці стоять дійсні числа, то заборонених мінорів нескінченно багато (матроїд Фано - лише один з них). Як зміниться ситуація, якщо перейти від поля дійсних чисел до скінченних полів?

Вільям Татт в 1958 році довів, що над полем, яке складається з двох елементів Z2 існує рівно один заборонений мінор - це U2,4. У 1979 році було доведено, що над полем з трьох елементів забороненими є U2,5 і U3,5, а в 2000 році було показано, що над полем з чотирьох елементів існує 7 заборонених мінорів.

У 1978 році Жан-Карло Рота сформулював гіпотезу: множина заборонених мінорів над кожним скінченним полем скінченна. Через майже 40 років троє математиків - Джоф Уїттл, Джим Джилін і Бера Гегардз - заявили про доведення цієї гіпотези. Відповідна доповідь прозвучала ще в липні 2013 року. Поки їх робота не опублікована в рецензованому журналі (та й самої роботи поки немає) і нічого не відомо про саме доведення. Чи дозволяє воно будувати заборонені мінори або хоча б оцінювати їх кількість? Невідомо.

Фахівці, однак, сходяться на думці, що, якщо хтось і міг довести цю гіпотезу, то це Уїттл, Джилін і Гегардз. Загалом вони витратили на роботу над цією гіпотезою 15 років.

Переклад Lenta.ru

yaneya

Якщо не можеш вітер змалювати, прозорий вітер на ясному тлі, -
Змалюй дуби, могутні і крислаті, котрі од вітру гнуться до землі!

Додати коментар

Захисний код
Оновити

Наші контакти

Ідея, дизайн, верстка і т.д.:
Олег Романів