Editing Property B

{{for|the B-property in finite group theory|B-theorem}}
[[File:Property b.svg|thumb|A [[Hypergraph#Hypergraph coloring|2-coloring]] of a hypergraph, equivalent to a collection C with Property B.]]
In [[mathematics]], '''Property B''' is a certain [[set theory|set theoretic]] property. Formally, given a [[finite set]] ''X'', a collection ''C'' of [[subset]]s 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 (mathematician)|Felix Bernstein]], who first introduced the property in 1908.<ref>{{citation|last=Bernstein|first=F.|title=Zur theorie der trigonometrische Reihen|journal=Leipz. Ber.|volume=60|year=1908|pages=325–328}}.</ref>

Property B is equivalent to [[Hypergraph#Hypergraph coloring|2-coloring]] the [[hypergraph]] described by the collection ''C''. A hypergraph with property B is also called '''2-colorable'''.<ref name="lp">{{Cite Lovasz Plummer}}</ref>{{rp|468}} Sometimes it is also called '''bipartite''', by analogy to the [[bipartite graph]]s.
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.<ref>{{citation
 | last = Beck | first = J. | authorlink = József Beck
 | doi = 10.1016/0012-365X(78)90191-7
 | issue = 2
 | journal = Discrete Mathematics
 | mr = 522920
 | pages = 127–137
 | title = On 3-chromatic hypergraphs
 | volume = 24
 | year = 1978| doi-access = free
 }}</ref>

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

== Smallest set-families without property B ==
[[File:Not property b.svg|thumb|300px|The [[Steiner triple system]] ''S''<sub>7</sub>, 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'').

=== Known 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)
: For ''n'' = 1, set ''X'' = {1}, and ''C'' = <nowiki>{{1}}</nowiki>. Then C does not have Property B.

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

; ''m''(3)
: 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''<sub>7</sub>); ''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''<nowiki>'</nowiki> 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)
: Östergård (2014) through an exhaustive search found ''m''(4) = 23. Seymour (1974) constructed a hypergraph on 11 vertices with 23 edges without Property B, which shows that ''m''(4) <= 23. Manning (1995) narrowed the floor such that ''m''(4) >= 21.

=== Asymptotics of ''m''(''n'') ===
Erdős (1963) proved that for any collection of fewer than <math>2^{n-1}</math> 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 <math>2^{-n+1}</math>. By a [[union bound]], the probability that there exist a monochromatic set is less than <math>2^{n-1}2^{-n+1} = 1</math>. Therefore, there exists a good coloring.

Erdős (1964) showed the existence of an ''n''-uniform hypergraph with <math>O(2^n \cdot n^2)</math> 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 <math>n/(n+4)\cdot 2^n</math> sets of size ''n'' has property B. Erdős and Lovász conjectured that <math>m(n) = \theta(2^n \cdot n)</math>. Beck in 1978 improved the lower bound to <math>m(n) = \Omega(n^{1/3 - \epsilon}2^n)</math>, where <math>\epsilon</math> is an arbitrary small positive number. In 2000, Radhakrishnan and Srinivasan improved the lower bound to <math>m(n) = \Omega(2^n \cdot \sqrt{n / \log n})</math>. They used a clever probabilistic algorithm.

==See also==
*{{slink|Sylvester–Gallai theorem|Colored points}}
*[[Set splitting problem]]

== References ==
{{reflist}}

==Further reading==
*{{citation|last=Erdős|first=Paul|title=On a combinatorial problem|journal=Nordisk Mat. Tidskr.|year=1963|pages=5–10|volume=11|ref=none}}
*{{Cite journal| first1 = P.|author1-link=Paul Erdős| title = On a combinatorial problem. II| journal = [[Acta Mathematica Hungarica|Acta Mathematica Academiae Scientiarum Hungaricae]]| last1 = Erdős| volume = 15| issue = 3–4| pages = 445–447| year = 1964| doi = 10.1007/BF01897152|doi-access=free|ref=none}}
*{{Cite journal|ref=none| first1 = W. M.| title = Ein kombinatorisches Problem von P. Erdős und A. Hajnal| journal = [[Acta Mathematica Hungarica|Acta Mathematica Academiae Scientiarum Hungaricae]]| last1 = Schmidt| volume = 15| issue = 3–4| pages = 373–374| year = 1964| doi = 10.1007/BF01897145| doi-access=free}}
*{{citation|ref=none|doi=10.1112/jlms/s2-8.4.681|last=Seymour|first=Paul|authorlink=Paul Seymour (mathematician)|title=A note on a combinatorial problem of Erdős and Hajnal|journal=Bulletin of the London Mathematical Society|volume=8|issue=4|year=1974|pages=681–682}}.
*{{citation|ref=none|last=Toft|first=Bjarne|contribution=On colour-critical hypergraphs|title=Infinite and Finite Sets: To Paul Erdös on His 60th Birthday|editor1-first=A.|editor1-last=Hajnal|editor1-link=András Hajnal|editor2-first=Richard|editor2-last=Rado|editor2-link=Richard Rado|editor3-first=Vera T.|editor3-last=Sós|publisher=North Holland Publishing Co.|year=1975|pages=1445–1457}}.
*{{citation|ref=none|doi=10.1090/S1079-6762-95-03004-6|first=G. M.|last=Manning|title=Some results on the ''m''(4) problem of Erdős and Hajnal|journal=[[Electronic Research Announcements of the American Mathematical Society]]|volume=1|issue=3|year=1995|pages=112–113|doi-access=free}}.
*{{citation|ref=none|first=J.|last=Beck|title=On 3-chromatic hypergraphs|journal=Discrete Mathematics|volume=24|issue=2|pages=127–137|year=1978|doi=10.1016/0012-365X(78)90191-7|doi-access=free}}.
*{{citation|ref=none|doi=10.1002/(SICI)1098-2418(200001)16:1<4::AID-RSA2>3.0.CO;2-2|first1=J.|last1=Radhakrishnan|first2=A.|last2=Srinivasan|title=Improved bounds and algorithms for hypergraph 2-coloring|url=https://ieeexplore.ieee.org/document/743519|journal=Random Structures and Algorithms|volume=16|issue=1|pages=4–32|year=2000}}.
*{{citation|ref=none|first=E. W.|last=Miller|title=On a property of families of sets|journal=Comp. Rend. Varsovie|volume=30|year=1937|pages=31–38}}.
*{{citation|ref=none|doi=10.1007/BF02066676|doi-access=free|first1=P.|last1=Erdős|author1-link=Paul Erdős|first2=A.|last2=Hajnal|author2-link=András Hajnal|title=On a property of families of sets|journal=[[Acta Mathematica Hungarica|Acta Mathematica Academiae Scientiarum Hungaricae]]|volume=12|issue=1–2|year=1961|pages=87–123}}.
*{{citation|ref=none|doi=10.4153/CMB-1969-107-x|doi-access=free|first1=H. L.|last1=Abbott|first2=D.|last2=Hanson|title=On a combinatorial problem of Erdös|journal=[[Canadian Mathematical Bulletin]]|volume=12|issue=6|year=1969|pages=823–829}}
*{{cite journal|ref=none|last1=Östergård|first1=Patric R. J.|title=On the minimum size of 4-uniform hypergraphs without property B|journal=Discrete Applied Mathematics|date=30 January 2014|volume=163, Part 2|pages=199–204|doi=10.1016/j.dam.2011.11.035|doi-access=free}}

[[Category:Families of sets]]
[[Category:Hypergraphs]]