Темы

Теория графов

Graph Theory · 49 статей

  1. Теорема о четырёх красках

    Теорема о четырёх красках: докажите, что для раскраски любой карты достаточно 4 цветов, чтобы соседние области не были одинаковыми. Первое крупное компьютерное доказательство.

    #2591 · 14 мин чтения

  2. Латинские квадраты: свойства, конструкции и приложения

    Латинский квадрат: определение, свойства и история. Математическая задача о заполнении таблицы символами без повторений в строках и столбцах. Euler, Choi Seok jeong.

    #8775 · 4 мин чтения

  3. Принцип Дирихле: Ящики и голуби

    Принцип Дирихле: если предметов больше, чем ящиков, то хотя бы в одном ящике окажется минимум два предмета. Математическая теорема и примеры применения.

    #12706 · 10 мин чтения

  4. Лемма Кёнига о бесконечных графах и деревьях

    Лемма Кёнига: теорема из теории графов о бесконечных путях в графах. Применение в математической логике, вычислимости и конструктивной математике.

    #48425 · 7 мин чтения

  5. Теорема Ван дер Вардена в теории Рамсея

    Теорема Ван дер Вардена: ключевой результат в теории Рамсея. Гарантирует существование монохромной арифметической прогрессии при раскраске чисел.

    #49106 · 1 мин чтения

  6. Вероятностный метод в математических доказательствах

    Вероятностный метод в математике: неконструктивное доказательство существования объектов через анализ вероятностей. Применяется в комбинаторике и других областях.

    #52680 · 2 мин чтения

  7. Теорема Рамсея в комбинаторике: монохроматические клики и раскраски графов.

    Теорема Рамсея в комбинаторике: существование монохромных клик в больших графах. Определение числа Рамсея R(r, s) и его значение для двух цветов.

    #55351 · 13 мин чтения

  8. Теорема Холла о сочетаниях и графах

    Теорема Холла в комбинаторике и теории графов: условия существования трансверсаля и совершенного соответствия в конечных множествах и двудольных графах.

    #55743 · 8 мин чтения

  9. Игра Сим: Стратегия, Рамсеева теория и выигрышные ходы.

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

    #67834 · 2 мин чтения

  10. Верхняя граница для семейств пересекающихся множеств.

    Теорема Эрдёша-Ко-Радо: ограничения на количество пересекающихся множеств в комбинаторике. Оптимальные семейства множеств и их размерность.

    #74058 · 9 мин чтения

  11. Гипотеза Эрдёша — Дьюрфаша о циклах длины степени двойки.

    Гипотеза Эрдёша-Дьюрфаша: графы с минимальной степенью 3 содержат цикл длиной, равной степени двойки. Приз $100 за доказательство/опровержение!

    #81438 · 1 мин чтения

  12. Граф Турана: свойства и применение в экстремальной теории графов.

    Турáнов граф: полное многодольное графическое представление. Оптимизация числа рёбер для (r+1)-свободных графов. Теорема Турана и экстремальная теория графов.

    #85374 · 4 мин чтения

  13. Граничная теорема Турана для графов без клик

    Теория графов: предел Турáна для графов без клик. Исследование максимального числа рёбер в графах, не содержащих полные подграфы. Математика, Турáн.

    #85375 · 7 мин чтения

  14. Теорема о раскрасках триангуляционных графов и лемма Спернера.

    Лемма Спернера: теорема о раскрасках триангуляций в математике. Аналог теоремы Брувера о неподвижной точке, применение в алгоритмах и теории множеств.

    #103024 · 9 мин чтения

  15. Экстремальная теория графов: основные понятия и результаты.

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

    #112683 · 4 мин чтения

  16. Ричард Радо: Жизнь и вклад в математику

    Ричард Радо: британский математик, вклад в комбинаторику и теорию графов. Доктор наук Кембриджа и Берлина, профессор Редингского университета. Полное описание.

    #124404 · 2 мин чтения

  17. Теорема Хейлза — Джеветта: Комбинаторный результат в теории Рамсея

    Теорема Хейлза-Джеветта: ключевой результат в комбинаторике и теории Рамсея. Доказывает неизбежность структуры в многомерных объектах, отсутствие полной случайности.

    #128277 · 4 мин чтения

  18. Семейства множеств с k-свойством Хелли и их обобщения.

    Семейства Хелли в комбинаторике: определение, свойства и теорема Хелли о выпуклых множествах. Порядок k и примеры с арифметическими прогрессиями.

    #132196 · 2 мин чтения

  19. Раскраска графов по спискам цветов: теория и примеры

    Раскраска графов со списками: определение, история (Визинг, Эрдёш). k-допустимость графа – возможность раскраски при заданных списках цветов для вершин.

    #134232 · 5 мин чтения

  20. Гипотеза Эрдеша — Фабера — Ловаша: раскраска графов и гиперграфов.

    Гипотеза Эрдёша-Фабера-Ловаса: раскраска графов. Доказательство для больших k. Связь с задачей о рассадке в комитетах с ограничениями на пересечение участников.

    #134366 · 4 мин чтения

  21. Теорема о совершенных графах: Запрещенные подграфы и доказательство

    Сильные совершенные графы: теорема о запрещенных графах, отсутствие нечетных циклов и антициклов. Доказательство Чудновской и др., премия Фулькерсона.

    #140574 · 6 мин чтения

  22. Спернеровы семейства и клаттеры: комбинаторные свойства и приложения.

    Спернеровы семейства в комбинаторике: определение, свойства и связь с числами Дедекинда. Антицепи, клаттеры и теорема Спернера. Оптимальный размер семейства.

    #141060 · 3 мин чтения

  23. Теорема Спернера о симплексах и обобщения

    Теорема Спернера: максимальные семейства конечных множеств без включения друг в друга. Ключевой результат в экстремальной теории множеств (1928).

    #141075 · 3 мин чтения

  24. Теорема Дилворта о ширине частично упорядоченных множеств

    Теорема Дилворта: ширина частично упорядоченных множеств, антицепи и цепи. Математика, комбинаторика, теория порядка. Минимальное разбиение на цепи.

    #141107 · 7 мин чтения

  25. Теорема Каратеодори об выпуклых оболочках

    Теорема Каратеодори о выпуклых оболочках: любая точка в выпуклой оболочке множества может быть представлена как комбинация ≤d+1 точек. Геометрия, доказательства.

    #156234 · 2 мин чтения

  26. Пересечение семейства множеств: трансверсали и системы различных представителей.

    Пересечение множеств: определение трансверсалы (системы различных представителей) в комбинаторике. Биекция, взаимно однозначное соответствие, SDR.

    #156973 · 5 мин чтения

  27. Свойство B в конечной теории групп

    Свойство B в теории групп: определение, 2-раскраска гиперграфов, связь с бипарностью. Введено Феликсом Бернштейном в 1908 году. Математика, теория множеств.

    #159337 · 2 мин чтения

  28. Ограничения на число инциденций точек и прямых на плоскости

    Теорема Семереди-Троттера: оценка числа инциденций точек и прямых на плоскости. Оптимальные границы, константы Паха и др. Дискретная геометрия.

    #175322 · 6 мин чтения

  29. Теорема Краскала — Катона об f-векторах симплициальных комплексов

    Теорема Краскала-Катона: характеристики f-векторов абстрактных симплициальных комплексов. Алгебраическая комбинаторика, гиперграфы, доказательства Эрдёша-Ко-Радо.

    #226712 · 1 мин чтения

  30. Теорема о раскраске графов на поверхностях

    Теорема о раскраске графов на поверхностях: conjecture Heawood/Ringel-Youngs, хроматическое число, доказательство, исключения (бутылка Клейна, теорема о 4 цветах).

    #231439 · 2 мин чтения

  31. Характеризация графов с совершенными паросочетаниями

    Теорема Татта о совершенных паросочетаниях в графах: обобщение теоремы Холла, характеризация графов без совершенного паросочетания, нечетное число вершин.

    #238681 · 3 мин чтения

  32. Гипотеза Хадвигера: обобщение теоремы о четырёх красках

    Гипотеза Хадвигера: обобщение теоремы о четырёх цветах в теории графов. Исследует связь между хроматическим числом и отсутствием Kₙ как минора. Остаётся нерешённой.

    #238968 · 6 мин чтения

  33. Лемма Семереди о регулярности и ее приложения в теории графов

    Лемма Семереди в экстремальной теории графов: разбиение графа на части для анализа плотности и подсчета подграфов. Приложения в математике и теории вероятностей.

    #268332 · 4 мин чтения

  34. Нижние оценки числа прямых, определяемых набором точек на плоскости.

    Теорема Бека в дискретной геометрии: нижние оценки числа прямых, определяемых точками на плоскости. Исследования конфигураций точек и их обобщения.

    #279345 · 3 мин чтения

  35. Локальная лемма Ловаша: теория, применение и алгоритмы.

    Лемма Ловаша: вероятность отсутствия событий при "частичной" независимости. Применение в теории вероятностей и доказательствах существования.

    #291003 · 3 мин чтения

  36. Задача о расположении точек на сетке без трех на одной прямой

    Макс. кол-во точек на сетке без трёх в линию: задача дискретной геометрии, предложенная Дюдени в 1900г. Ограничение – любые линии, не только по сетке.

    #294658 · 9 мин чтения

  37. Теорема о друзьях и незнакомцах: Гарантированное наличие трио

    Теорема о друзьях и незнакомцах: в любой группе из 6 человек найдутся 3 взаимных незнакомца или 3 общих знакомых. Рамсеева теория, графы.

    #310381 · 3 мин чтения

  38. Farkas' lemma

    #314515 · 2 мин чтения

  39. Combinatorial design

    #336343 · 6 мин чтения

  40. Теорема Оре о гамильтоновых графах

    Теорема Оре в теории графов: достаточное условие для существования гамильтонова цикла. Сумма степеней не смежных вершин ≥ числу вершин графа.

    #361583 · 3 мин чтения

  41. Разделы на пересекающиеся выпуклые оболочки

    Теорема Тверберга в дискретной геометрии: разбиение точек в d-мерном пространстве на подмножества с пересекающимися выпуклыми оболочками. Теорема Радона – частный случай.

    #362691 · 3 мин чтения

  42. Проблема раскраски плоскости на единичном расстоянии (Problema raskraski ploskosti na edinichnom rasstoyanii)

    Проблема Хадвигера-Нельсона: минимальное число цветов для раскраски плоскости, чтобы точки на расстоянии 1 не имели одинаковый цвет. Ответ: 5, 6 или 7?

    #363975 · 5 мин чтения

  43. Графы без больших полных двудольных подграфов

    Задача Заранкевича: поиск макс. кол-ва рёбер в двудольном графе без полных двудольных подграфов. Экстремальная теория графов, комбинаторика.

    #386789 · 4 мин чтения

  44. Гипотеза Герцого-Шёнхайма и покрытия групп подгруппами

    Гипотеза Герцого-Шёнхайма: комбинаторная задача теории групп о разбиении группы на левые классы подгрупп. Утверждается, что индексы не могут быть различными.

    #395030 · 1 мин чтения

  45. Цепи Кемпе: математический инструмент доказательства теоремы о четырёх красках

    Цепи Кемпе – математический инструмент, используемый в доказательстве теоремы о четырёх красках. Ключевой метод в современных доказательствах и теории графов.

    #396300 · 2 мин чтения

  46. Лемма Кнастера — Куратовского — Мазуркевича и её обобщения.

    Лемма Кнастера-Куратовского-Мазуркевича: фиксированные точки, выпуклые множества, обобщение Гейла (rainbow KKM lemma). Математическая теория, доказательство теорем.

    #416339 · 2 мин чтения

  47. Гипотеза о замкнутых относительно объединения множествах

    Гипотеза Франкла (1979) в комбинаторике: для любой конечной объединяемо-замкнутой семьи множеств существует элемент, содержащийся хотя бы в половине множеств.

    #435587 · 5 мин чтения

  48. Vizing's theorem

    #491767 · 5 мин чтения

  49. Pseudorandom graph

    #503502 · 3 мин чтения