WikiDer > Теорема Эрдеша – Посы
 | Эта статья требует внимания специалиста по математике. Конкретная проблема: Здесь могут помочь диаграммы, а не «большие страшные слова». (Июнь 2020 г.) |
В математической дисциплине теория графов, то Теорема Эрдеша – Посы, названный в честь Пол Эрдёш и Lajos Pósa, заявляет, что существует функция ж(k) так что для каждого положительное число k, каждый граф либо содержит не менее k вершинно-непересекающийся циклы или у него есть набор вершин обратной связи не более ж(k) вершины, пересекающие каждый цикл. Более того, ж(k) = Θ (k бревно k) в смысле Обозначение Big O. В силу этой теоремы говорят, что циклы имеют Erdős – Pósa недвижимость.
Теорема утверждает, что для любого конечного числа k есть подходящее (наименьшее) значение ж(k), со свойством, что в каждом графе без набора k вершинно-непересекающиеся циклы, все циклы могут быть покрыты не более чем ж(k) вершины. Это обобщило неопубликованный результат Béla Bollobás, в котором говорится, что ж(2) = 3. Эрдеш и Поса (1965) получил оценки c1k бревно k < ж(k) < c2k бревно k для общего случая. По делу k = 2, Ловас (1965) дал полную характеристику. Восс (1969) доказано ж(3) = 6 и 9 ≤ ж(4) ≤ 12.
Erdős – Pósa недвижимость
Семья F графиков или гиперграфы определяется как обладающее свойством Эрдеша – Посы, если существует функция ж: ℕ → ℕ такое, что для любого (гипер-) графа грамм и каждое целое число k верно одно из следующего:
- грамм содержит k вершинно-непересекающиеся подграфы, каждый изоморфный графу в F; или же
- грамм содержит набор вершин C размером не более ж(k) такой, что грамм − C не имеет подграфа, изоморфного графу в F.
Это определение часто формулируется следующим образом. Если обозначить через ν(грамм) максимальное количество вершинных непересекающихся подграфов грамм изоморфен графу в F и по τ(грамм) минимальное количество вершин, удаление которых из грамм оставляет граф без подграфа, изоморфного графу в F, тогда τ(грамм) ≤ ж(ν(грамм)), для некоторой функции ж: ℕ → ℕ не в зависимости от грамм.
Перефразированная в этой терминологии, теорема Эрдеша – Поса утверждает, что семейство F состоящий из всех циклов, обладает свойством Эрдеша – Посы с ограничивающей функцией ж(k) = Θ (k бревно k). Робертсон и Сеймур (1986) значительно обобщили это. Учитывая график ЧАС, позволять F(ЧАС) обозначают семейство всех графов, содержащих ЧАС как незначительный. Как следствие их малая теорема о сетке, Робертсон и Сеймур доказали, что F(ЧАС) обладает свойством Эрдеша – Посы тогда и только тогда, когда ЧАС это планарный граф. Более того, теперь известно, что соответствующая ограничивающая функция есть ж(k) = Θ (k) если ЧАС это лес (Фиорини, Джорет и Вуд 2013), пока ж(k) = Θ (k бревно k) для любого другого плоского графа ЧАС (Cames van Batenburg et al. 2019 г.). Частный случай, когда ЧАС является треугольником, что эквивалентно теореме Эрдеша – Посы.
Рекомендации
- Эрдеш, Пол; Pósa, Lajos (1965). «О независимых схемах, содержащихся в графе». Канадский математический журнал. 17: 347–352. Дои:10.4153 / CJM-1965-035-8.CS1 maint: ref = harv (связь)
- Робертсон, Нил; Сеймур, Пол (1986). «Миноры графа. V. Исключение плоского графа». Журнал комбинаторной теории, серия B. 41: 92–114. Дои:10.1016/0095-8956(86)90030-4.CS1 maint: ref = harv (связь)
- Восс, Хайнц-Юрген (1969). "Eigenschaften von Graphen, die keine k + 1 knotenfremde Kreise enthalten". Mathematische Nachrichten. 40: 19–25. Дои:10.1002 / мана.19690400104.CS1 maint: ref = harv (связь)
- Ловас, Ласло (1965). «О графах, не содержащих независимых схем». Мат. Лапок. 16: 289–299.CS1 maint: ref = harv (связь)
- Камес ван Батенбург, Воутер; Huynh, Тони; Джорет, Гвенаэль; Раймон, Жан-Флоран (2019). «Жесткая функция Эрдеша-Посы для плоских несовершеннолетних». Успехи комбинаторики. 2: 33 стр. Дои:10.19086 / aic.10807.CS1 maint: ref = harv (связь)
- Фиорини, Самуэль; Джорет, Гвенаэль; Вуд, Дэвид Р. (2013). «Исключенные малые леса и собственность Эрдёш-Поша». Комбинаторика, теория вероятностей и вычисления. 22 (5): 700–721. arXiv:1204.5192. Дои:10.1017 / S0963548313000266.CS1 maint: ref = harv (связь)