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

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

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

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

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

Наименьшее число множеств в коллекции множеств размера n, такое, что C не обладает свойством B, обозначается 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.

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

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

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

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

• Эрдеш, Пол (1963), «Об одной комбинаторной проблеме», Nordisk Mat. Тидскр. , 11 : 5–10
• Эрдеш, П. (1964). «Об одной комбинаторной задаче. II». Acta Mathematica Academiae Scientiarum Hungaricae . 15 (3–4): 445–447. дои : 10.1007/BF01897152 .
• Шмидт, WM (1964). «Комбинаторная задача П. Эрдеша и А. Хайнала». Acta Mathematica Academiae Scientiarum Hungaricae . 15 (3–4): 373–374. дои : 10.1007/BF01897145 .
• Сеймур, Пол (1974), «Заметка о комбинаторной задаче Эрдёша и Хайнала», Бюллетень Лондонского математического общества , 8 (4): 681–682, doi :10.1112/jlms/s2-8.4.681.
• Тофт, Бьярне (1975), «О гиперграфах, критических по цвету», в Hajnal, A .; Rado, Richard ; Sós, Vera T. (ред.), Бесконечные и конечные множества: Паулю Эрдёшу в день его 60-летия , North Holland Publishing Co., стр. 1445–1457.
• Мэннинг, GM (1995), «Некоторые результаты по проблеме m (4) Эрдёша и Хайнала», Electronic Research Announcements of the American Mathematical Society , 1 (3): 112–113, doi : 10.1090/S1079-6762-95-03004-6.
• Бек, Дж. (1978), «О 3-хроматических гиперграфах», Дискретная математика , 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.
• Миллер, Э. У. (1937), «Об одном свойстве семейств множеств», Comp. Rend. Varsovie , 30 : 31–38.
• Эрдеш, П .; Хайнал, А. (1961), «О свойстве семейств множеств», Acta Mathematica Academiae Scientiarum Hungaricae , 12 (1–2): 87–123, doi : 10.1007/BF02066676.
• Эбботт, Х. Л.; Хансон, Д. (1969), «О комбинаторной задаче Эрдёша», Канадский математический вестник , 12 (6): 823–829, doi : 10.4153/CMB-1969-107-x
• Östergård, Patric RJ (30 января 2014 г.). «О минимальном размере 4-однородных гиперграфов без свойства B». Дискретная прикладная математика . 163, Часть 2: 199–204. doi : 10.1016/j.dam.2011.11.035 .