Property B

For the B-property in finite group theory, see B-theorem.

A 2-coloring of a hypergraph, equivalent to a collection C with Property 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. ^[1]

Property B is equivalent to 2-coloring the hypergraph described by the collection C. A hypergraph with property B is also called 2-colorable. ^{[2] : 468} 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. ^[3]

The problem of checking whether a collection C has Property B is called the set splitting problem.

Smallest set-families without property B

The Steiner triple system S₇, the smallest 3-uniform set that doesn't have property B.

The smallest number of sets in a collection of sets of size n such that C does not have Property B is denoted by m(n).

Small values of m(n)

It is known that m(1) = 1, m(2) = 3, m(3) = 7 (as can by seen by the following examples), and m(4) = 23 (Östergård), although finding this result was the result of an exhaustive search. An upper bound of 23 (Seymour, Toft) and a lower bound of 21 (Manning) have been proven. At the time of this writing (March 2017), there is no OEIS entry for the sequence m(n) yet, due to the lack of terms known.

m(1) = 1

For n = 1, set X = {1}, and C = {{1}}. Then C does not have Property B.

m(2) = 3

For n = 2, set X = {1, 2, 3} and C = {{1, 2}, {1, 3}, {2, 3}} (a triangle). Then C does not have Property B, so m(2) <= 3. However, C' = {{1, 2}, {1, 3}} does (set Y = {1} and Z = {2, 3}), so m(2) >= 3.

m(3) = 7

For n = 3, set X = {1, 2, 3, 4, 5, 6, 7}, and C = {{1, 2, 4}, {2, 3, 5}, {3, 4, 6}, {4, 5, 7}, {5, 6, 1}, {6, 7, 2}, {7, 1, 3}} (the Steiner triple system S₇); C does not have Property B (so m(3) <= 7), but if any element of C is omitted, then that element can be taken as Y, and the set of remaining elements C' will have Property B (so for this particular case, m(3) >= 7). One may check all other collections of 6 3-sets to see that all have Property B.

m(4) = 23

Östergård (2014) through an exhaustive search found m(4) = 23. Before, Seymour (1974) constructed a hypergraph on 11 vertices with 23 edges without Property B, showing that m(4) <= 23, and Manning (1995) had narrowed the floor such that m(4) >= 21.

29 <= m(5) <= 51

The bounds for even the next unknown value are quite far apart. On the lower end, only collections with certain numbers of unique elements could potentially not have Property B, but this range grows larger further from the lower bound. The lower bound was improved from 28 to 29 in 2020. ^[4]

Asymptotics of m(n)

Erdős (1963) proved that for any collection of fewer than ${\displaystyle 2^{n-1}}$ sets of size n, there exists a 2-coloring in which all set are bichromatic. The proof is simple: Consider a random coloring. The probability that an arbitrary set is monochromatic is ${\displaystyle 2^{-n+1}}$. By a union bound, the probability that there exist a monochromatic set is less than ${\displaystyle 2^{n-1}2^{-n+1}=1}$. Therefore, there exists a good coloring.

Erdős (1964) showed the existence of an n-uniform hypergraph with ${\displaystyle O(2^{n}\cdot n^{2})}$ hyperedges which does not have property B (i.e., does not have a 2-coloring in which all hyperedges are bichromatic), establishing an upper bound.

Schmidt (1963) proved that every collection of at most ${\displaystyle n/(n+4)\cdot 2^{n}}$ sets of size n has property B. Erdős and Lovász conjectured that ${\displaystyle m(n)=\theta (2^{n}\cdot n)}$. Beck in 1978 improved the lower bound to ${\displaystyle m(n)=\Omega (n^{1/3-\epsilon }2^{n})}$, where ${\displaystyle \epsilon }$ is an arbitrary small positive number. In 2000, Radhakrishnan and Srinivasan improved the lower bound to ${\displaystyle m(n)=\Omega (2^{n}\cdot {\sqrt {n/\log n}})}$. They used a clever probabilistic algorithm.

See also

• Sylvester–Gallai theorem § Colored points
• Set splitting problem

References

1. Bernstein, F. (1908), "Zur theorie der trigonometrische Reihen", Leipz. Ber., 60: 325–328.
2. Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN   0-444-87916-1, MR   0859549
3. Beck, J. (1978), "On 3-chromatic hypergraphs", Discrete Mathematics, 24 (2): 127–137, doi: 10.1016/0012-365X(78)90191-7 , MR   0522920
4. Aglave, Sachin; Amarnath, V. A.; Shannigrahi, Saswata; Singh, Shwetank (2020). "Improved bounds for uniform hypergraphs without property B" (PDF). Australasian Journal of Combinatorics. 76 (1): 73–86. ISSN   2202-3518.

Further reading

• Erdős, Paul (1963), "On a combinatorial problem", Nordisk Mat. Tidskr., 11: 5–10
• Erdős, P. (1964). "On a combinatorial problem. II". Acta Mathematica Academiae Scientiarum Hungaricae . 15 (3–4): 445–447. doi: 10.1007/BF01897152 .
• Schmidt, W. M. (1964). "Ein kombinatorisches Problem von P. Erdős und A. Hajnal". Acta Mathematica Academiae Scientiarum Hungaricae . 15 (3–4): 373–374. doi: 10.1007/BF01897145 .
• Seymour, Paul (1974), "A note on a combinatorial problem of Erdős and Hajnal", Bulletin of the London Mathematical Society, 8 (4): 681–682, doi:10.1112/jlms/s2-8.4.681 .
• Toft, Bjarne (1975), "On colour-critical hypergraphs", in Hajnal, A.; Rado, Richard; Sós, Vera T. (eds.), Infinite and Finite Sets: To Paul Erdös on His 60th Birthday, North Holland Publishing Co., pp. 1445–1457.
• Manning, G. M. (1995), "Some results on the m(4) problem of Erdős and Hajnal", Electronic Research Announcements of the American Mathematical Society , 1 (3): 112–113, doi: 10.1090/S1079-6762-95-03004-6 .
• Beck, J. (1978), "On 3-chromatic hypergraphs", Discrete Mathematics, 24 (2): 127–137, doi: 10.1016/0012-365X(78)90191-7 .
• Radhakrishnan, J.; Srinivasan, A. (2000), "Improved bounds and algorithms for hypergraph 2-coloring", Random Structures and Algorithms, 16 (1): 4–32, doi:10.1002/(SICI)1098-2418(200001)16:1<4::AID-RSA2>3.0.CO;2-2 .
• Miller, E. W. (1937), "On a property of families of sets", Comp. Rend. Varsovie, 30: 31–38.
• Erdős, P.; Hajnal, A. (1961), "On a property of families of sets", Acta Mathematica Academiae Scientiarum Hungaricae , 12 (1–2): 87–123, doi: 10.1007/BF02066676 .
• Abbott, H. L.; Hanson, D. (1969), "On a combinatorial problem of Erdös", Canadian Mathematical Bulletin , 12 (6): 823–829, doi: 10.4153/CMB-1969-107-x
• Östergård, Patric R. J. (30 January 2014). "On the minimum size of 4-uniform hypergraphs without property B". Discrete Applied Mathematics. 163, Part 2: 199–204. doi: 10.1016/j.dam.2011.11.035 .