Введение
Свойство B в теории конечных групп
В математике, свойство B — это определенное теоретико-множественное свойство. Формально, для конечного множества X, коллекция C подмножеств X обладает свойством B, если можно разбить X на два непересекающихся подмножества Y и Z таким образом, чтобы каждое множество из C имело непустое пересечение как с Y, так и с Z. Свое название свойство получило от математика Феликса Бернштейна, который впервые ввел это свойство в 1908 году. Свойство B эквивалентно 2-раскраске гиперграфа, заданного коллекцией C. Гиперграф, обладающий свойством B, также называют 2-раскрашиваемым. Иногда его также называют бипарным, по аналогии с бипартитными графами. Свойство B часто изучается для равномерных гиперграфов (систем множеств, в которых все подмножества системы имеют одинаковую мощность), но оно также рассматривалось и в неравномерном случае. Задача проверки наличия у коллекции C свойства B называется задачей разбиения множества.
In mathematics, Property B is a certain set theoretic property. Formally, given a finite set X, a collection C of subsets of X has Property B if we can partition X into two disjoint subsets Y and Z such that every set in C meets both Y and Z. The property gets its name from mathematician Felix Bernstein, who first introduced the property in 1908. Property B is equivalent to 2 coloring the hypergraph described by the collection C. A hypergraph with property B is also called 2 colorable. Sometimes it is also called bipartite, by analogy to the bipartite graphs. Property B is often studied for uniform hypergraphs (set systems in which all subsets of the system have the same cardinality) but it has also been considered in the non uniform case. The problem of checking whether a collection C has Property B is called the set splitting problem.
Наименьшие семейства множеств без свойства B
Наименьшее число множеств в наборе множеств размера n, для которого C не обладает свойством B, обозначается m(n).
Асимптотики m (n)
Эрдош (1963) доказал, что для любого семейства, содержащего менее чем 2^n множеств размера n, существует 2-раскраска, в которой все множества бихроматичны. Доказательство просто: рассмотрим случайную раскраску. Вероятность того, что произвольное множество монохроматично, равна 2^(-n+1). По неравенству о союзе, вероятность того, что существует монохроматическое множество, меньше, чем 2^n * 2^(-n+1) = 2. Следовательно, существует хорошая раскраска. Эрдош (1964) показал существование n-равномерного гиперграфа с 2^n - 1 гиперребрами, который не обладает свойством B (то есть не имеет 2-раскраски, в которой все гиперребра бихроматичны), устанавливая верхнюю границу. Шмидт (1963) доказал, что любое семейство, содержащее не более 2^n - 1 множеств размера n, обладает свойством B. Эрдош и Ловас предположили, что Бек в 1978 году улучшил нижнюю границу до n/(log n)^2, где ε – произвольно малое положительное число. В 2000 году Радхакришнан и Шринивасан улучшили нижнюю границу до n/(log n)^c. Они использовали изящный вероятностный алгоритм.