|
Симметричные системы представителей в графах и других структурах
Наталья Михайловна Лунева 7 мая 2018, понедельник, 1645
Я докажу одну общую теорему о системах представителей, из которой
вытекает, например, следующий факт:
если в графе можно уничтожить все стоугольники путём
удаления
2018-ти рёбер, то
в этом графе можно уничтожить все стоугольники
путём удаления
не
более 201800 рёбер так, чтобы множество удаляемых рёбер было
инвариантно относительно всех автоморфизмов исходного графа.
Аналогичное утверждение верно для любого «запрещённого» подграфа
(а не только для стоугольника), причём полученная оценка во многих случаях
оказывается неулучшаемой.
|