Недвижимость Б

О B-свойстве в теории конечных групп см. B-теорему .

В математике теоретико - свойство B — это определенное множественное свойство. Формально, учитывая конечное множество X , совокупность C подмножеств X так X обладает свойством B, если мы можем разделить два непересекающихся подмножества Y и Z так, что каждое множество в C соответствует как Y, и Z. на

Свойство получило свое название в честь математика Феликса Бернштейна , который впервые представил это свойство в 1908 году.

Свойство B эквивалентно раскраске в 2 цвета , гиперграфа набором C. описываемого Гиперграф со свойством B также называется 2-раскрашиваемым . Иногда его еще называют двудольным графом , по аналогии с двудольным графом .Свойство B часто изучается для однородных гиперграфов (систем множеств, в которых все подмножества системы имеют одинаковую мощность), но оно также рассматривалось и в неоднородном случае.

Проблема проверки того, обладает ли коллекция C свойством B, называется проблемой разделения множества .

Наименьшие множества-семейства без свойства B

Наименьшее количество множеств в наборе множеств размера n, такое что C не обладает свойством B, обозначается m ( n ).

Известные значения m(n)

Известно, что m (1) = 1, m (2) = 3 и m (3) = 7 (как видно из следующих примеров); значение m (4) = 23 (Остергорд), хотя нахождение этого результата было результатом перебора. Были доказаны верхняя граница 23 (Сеймур, Тофт) и нижняя граница 21 (Мэннинг). На момент написания этой статьи (март 2017 г.) еще не было записи OEIS для последовательности m ( n ) из-за отсутствия известных терминов.

м (1)

Для n = 1 установите X = {1} и C = {{1}}. Тогда C не обладает свойством B.

м (2)

Для n = 2 положим X = {1, 2, 3} и C = {{1, 2}, {1, 3}, {2, 3}} (треугольник). Тогда C не обладает свойством B, поэтому m (2) <= 3. Однако C ' = {{1, 2}, {1, 3}} оно имеет (установите Y = {1} и Z = {2, 3 }), поэтому m (2) >= 3.

м (3)

Для n = 3 положим X = {1, 2, 3, 4, 5, 6, 7} и C = {{1, 2, 4}, {2, 3, 5}, {3, 4, 6. }, {4, 5, 7}, {5, 6, 1}, {6, 7, 2}, {7, 1, 3}} ( система троек Штейнера S ₇ ); C не обладает свойством B (поэтому m (3) <= 7), но если какой-либо элемент C опущен, то этот элемент можно принять за Y , а набор оставшихся элементов C ' будет обладать свойством B (так для в данном конкретном случае m (3) >= 7). Можно проверить все остальные коллекции из 6 3-множеств и убедиться, что все они обладают свойством B.

м (4)

Остергорд (2014) в результате исчерпывающего поиска нашел m (4) = 23. Сеймур (1974) построил гиперграф на 11 вершинах с 23 ребрами без свойства B, который показывает, что m (4) <= 23. Мэннинг (1995) сузил диапазон этаж такой, что m (4) >= 21.

Асимптотика m ( n )

Эрдеш (1963) доказал, что для любого набора размером менее $2^{n-1}$ множеств размера n существует 2-раскраска, в которой все множество бихроматично. Доказательство простое: рассмотрим случайную раскраску. Вероятность того, что произвольное множество является одноцветным, равна $2^{-n+1}$. По границе объединения вероятность существования монохроматического набора меньше, чем $2^{n-1}2^{-n+1}=1$. Поэтому существует хорошая раскраска.

Эрдеш (1964) показал существование n -однородного гиперграфа с $O(2^{n}\cdot n^{2})$ гиперребра, не обладающие свойством B (т. е. не имеющие 2-раскраски, в которой все гиперребра бихроматические), устанавливающие верхнюю границу.

Шмидт (1963) доказал, что каждая совокупность не более $n/(n+4)\cdot 2^{n}$ множества размера n обладают свойством Б. Эрдеш и Ловаш предположили, что $m(n)=\theta (2^{n}\cdot n)$. Бек в 1978 году улучшил нижнюю границу до $m(n)=\Omega (n^{1/3-\epsilon }2^{n})$, где $\epsilon$ — произвольное малое положительное число. В 2000 году Радхакришнан и Шринивасан улучшили нижнюю границу до $m(n)=\Omega (2^{n}\cdot {\sqrt {n/\log n}})$. Они использовали умный вероятностный алгоритм.

См. также

• Теорема Сильвестра – Галлаи § Цветные точки
• Установить задачу разделения

Дальнейшее чтение

• Эрдеш, Пауль (1963), «Об одной комбинаторной проблеме», Nordic Mat. Эра , 11 : 5–10
• Эрдеш, П. (1964). «Об одной комбинаторной задаче. II» . Математический журнал Венгерской академии наук . 15 (3–4): 445–447. дои : 10.1007/BF01897152 .
• Шмидт, WM (1964). «Комбинаторная задача П. Эрдеша и А. Хайнала» . Математический журнал Венгерской академии наук . 15 (3–4): 373–374. дои : 10.1007/BF01897145 .
• Сеймур, Пол (1974), «Заметка о комбинаторной проблеме Эрдеша и Хайнала», Бюллетень Лондонского математического общества , 8 (4): 681–682, doi : 10.1112/jlms/s2-8.4.681 .
• Тофт, Бьярн (1975), «О цветокритических гиперграфах», Хайнал, А .; Радо, Ричард ; Сос, Вера Т. (ред.), Бесконечные и конечные множества: Полу Эрдешу в день его 60-летия , North Holland Publishing Co., стр. 1445–1457 .
• Мэннинг, GM (1995), «Некоторые результаты по проблеме m (4) Эрдеша и Хайнала», Электронные объявления об исследованиях Американского математического общества , 1 (3): 112–113, doi : 10.1090/S1079-6762-95 -03004-6 .
• Бек, Дж. (1978), «О 3-хроматических гиперграфах», Discrete Mathematics , 24 (2): 127–137, doi : 10.1016/0012-365X(78)90191-7 .
• Радхакришнан, Дж.; Сринивасан, А. (2000), «Улучшенные границы и алгоритмы 2-раскраски гиперграфов» , Случайные структуры и алгоритмы , 16 (1): 4–32, doi : 10.1002/(SICI)1098-2418(200001)16:1 <4::AID-RSA2>3.0.CO;2-2 .
• Миллер, EW (1937), "О свойстве семейств множеств", Comp. Ренд. Варшавье , 30 : 31–38 .
• Эрдеш, П .; Хайнал, А. (1961), «О свойстве семейств множеств», Математический журнал Венгерской академии наук , 12 (1–2): 87–123, doi : 10.1007/BF02066676 .
• Эбботт, Х.Л.; Хэнсон, Д. (1969), «Об одной комбинаторной задаче Эрдеша», Canadian Mathematical Bulletin , 12 (6): 823–829, doi : 10.4153/CMB-1969-107-x
• Остергорд, Патрик Р.Дж. (30 января 2014 г.). «О минимальном размере 4-однородных гиперграфов без свойства B» . Дискретная прикладная математика . 163, Часть 2: 199–204. дои : 10.1016/j.dam.2011.11.035 .