Показать меню

Теорема Бараньяи

03.05.2022
27

Теорема Бараньяи — теорема о разбиениях полных гиперграфов. Доказана Жолтом Бараньяи и названа его именем.

Формулировка

Если 2 ⩽ r < k {displaystyle 2leqslant r<k} являются натуральными числами и r делит k, то полный гиперграф K r k {displaystyle K_{r}^{k}} можно разложить на 1-факторы.

Замечания

  • K r k {displaystyle K_{r}^{k}} — это гиперграф с k вершинами, в котором каждое подмножество из r вершин образует гиперребро.
  • 1-фактор этого гиперграфа — это набор гиперрёбер, которые содержат каждую вершину в рёбрах ровно раз, что эквивалентно разбиению вершин на подмножества размера r.

Таким образом, теорема утверждает, что k вершин гиперграфа могут быть разбиты на подмножества r вершин ( k r ) r k = ( k − 1 r − 1 ) {displaystyle {inom {k}{r}}{frac {r}{k}}={inom {k-1}{r-1}}} различными способами таким образом, что каждое r-элементное подмножество появляется ровно раз в разбиении.

Случай r = 2 {displaystyle r=2}

В специальном случае r = 2 {displaystyle r=2} мы имеем полный граф K n {displaystyle K_{n}} с n {displaystyle n} вершинами и хотим раскрасить рёбра в ( n 2 ) 2 n = n − 1 {displaystyle {inom {n}{2}}{frac {2}{n}}=n-1} цветов так, что рёбра каждого цвета образуют совершенное паросочетание. Теорема Бараньяи утверждает, что мы можем это сделать, если n {displaystyle n} чётно.

История

Случай r = 2 можно переформулировать как утверждение, что любой полный граф с чётным числом вершин имеет рёберную раскраску, число цветов которой равно его степени, или, эквивалентно, что рёбра могут быть разбиты на совершенные паросочетания. Это можно использовать для создания круговых турниров и решение было известно в 19-м веке. Случай k = 2r также прост.

Случай r = 3 рассмотрел в 1963 году Р. Пелтесон. Общий случай доказал в 1975 году Жолт Бараньяи.

Еще по этой теме:
Теорема Миттаг-Леффлера
13:00, 18 апрель
Теорема Миттаг-Леффлера
Теорема Миттаг-Леффлера о разложении мероморфной функции — одна из основных теорем теории аналитических функций, дающая для мероморфных функций аналог разложения рациональной функции на простейшие
Теорема Гротендика о расщеплении
15:52, 18 декабрь
Теорема Гротендика о расщеплении
Теорема Гротендика о расщеплении даёт классификацию голоморфных векторных расслоений над комплексной проективной прямой. А именно, она утверждает, что каждое голоморфное векторное расслоение над
Теорема Вейерштрасса об ограниченной возрастающей последовательности
21:30, 15 декабрь
Теорема Вейерштрасса об ограниченной возрастающей последовательности
Теорема Вейерштрасса об ограниченной сверху возрастающей последовательности (или ограниченной снизу убывающей последовательности) утверждает, что любая ограниченная сверху монотонно возрастающая (или
Теорема Крылова — Боголюбова
16:07, 12 декабрь
Теорема Крылова — Боголюбова
Теорема Крылова — Боголюбова — утверждает существование инвариантных мер у «хороших» отображений, определённых на «хороших» пространствах. Существуют две вариации теоремы, для динамических систем и
Существенно особая точка
14:44, 12 декабрь
Существенно особая точка
Изолированная особая точка z 0 {displaystyle z_{0}} функции f (
Теорема Бондаревой — Шепли
20:24, 03 декабрь
Теорема Бондаревой — Шепли
В теории игр теорема Бондаревой — Шепли описывает необходимые и достаточные условия для непустоты ядра в кооперативной игре. В частности, ядро игры непусто тогда и только тогда, когда игра
Комментарии:
Добавить комментарий
Ваше Имя:
Ваш E-Mail: