Property B

<h2 id="smallest-set-families-without-property-b">Smallest set-families without property B</h2>

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).

<h3>Known values of m(n)</h3>
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 <a href="/facts/OEIS/yow6cVsU">OEIS</a> entry for the sequence m(n) yet, due to the lack of terms known.

m(1)
For n = 1, set X = {1}, and C = {{1}}. Then C does not have Property B.
m(2)
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)
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 <a href="/facts/Steiner_triple_system/DdakpJpm">Steiner triple system</a> S7); 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)
Ö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.
<h3>Asymptotics of m(n)</h3>
Erdős (1963) proved that for any collection of fewer than 
 
 
 
 
 2
 
 n
 −
 1
 
 
 
 
 {\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 
 
 
 
 
 2
 
 −
 n
 +
 1
 
 
 
 
 {\displaystyle 2^{-n+1}}
 
. By a <a href="/facts/Union_bound/HDRr2yUH">union bound</a>, the probability that there exist a monochromatic set is less than 
 
 
 
 
 2
 
 n
 −
 1
 
 
 
 2
 
 −
 n
 +
 1
 
 
 =
 1
 
 
 {\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 
 
 
 
 O
 (
 
 2
 
 n
 
 
 ⋅
 
 n
 
 2
 
 
 )
 
 
 {\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 
 
 
 
 n
 
 /
 
 (
 n
 +
 4
 )
 ⋅
 
 2
 
 n
 
 
 
 
 {\displaystyle n/(n+4)\cdot 2^{n}}
 
 sets of size n has property B. Erdős and Lovász conjectured that 
 
 
 
 m
 (
 n
 )
 =
 θ
 (
 
 2
 
 n
 
 
 ⋅
 n
 )
 
 
 {\displaystyle m(n)=\theta (2^{n}\cdot n)}
 
. Beck in 1978 improved the lower bound to 
 
 
 
 m
 (
 n
 )
 =
 Ω
 (
 
 n
 
 1
 
 /
 
 3
 −
 ϵ
 
 
 
 2
 
 n
 
 
 )
 
 
 {\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 
 
 
 
 m
 (
 n
 )
 =
 Ω
 (
 
 2
 
 n
 
 
 ⋅
 
 
 n
 
 /
 
 log
 ⁡
 n
 
 
 )
 
 
 {\displaystyle m(n)=\Omega (2^{n}\cdot {\sqrt {n/\log n}})}
 
. They used a clever probabilistic algorithm.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Sylvester%25E2%2580%2593Gallai_theorem/ASXbwNmj">Sylvester–Gallai theorem § Colored points</a></li>
<li><a href="/facts/Set_splitting_problem/V9sBhlho">Set splitting problem</a></li></ul>

<h2 id="further-reading">Further reading</h2>
<ul><li>Erdős, Paul (1963), "On a combinatorial problem", Nordisk Mat. Tidskr., 11: 5–10</li>
<li><a href="/facts/Paul_Erd%25C5%2591s/63LoUTe1">Erdős, P.</a> (1964). <a href="https://doi.org/10.1007%2FBF01897152">"On a combinatorial problem. II"</a>. <a href="/facts/Acta_Mathematica_Hungarica/G1Y5GSxQ">Acta Mathematica Academiae Scientiarum Hungaricae</a>. 15 (3–4): 445–447. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01897152">10.1007/BF01897152</a>.</li>
<li>Schmidt, W. M. (1964). <a href="https://doi.org/10.1007%2FBF01897145">"Ein kombinatorisches Problem von P. Erdős und A. Hajnal"</a>. <a href="/facts/Acta_Mathematica_Hungarica/G1Y5GSxQ">Acta Mathematica Academiae Scientiarum Hungaricae</a>. 15 (3–4): 373–374. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01897145">10.1007/BF01897145</a>.</li>
<li><a href="/facts/Paul_Seymour_(mathematician)/AJp2GgAC">Seymour, Paul</a> (1974), "A note on a combinatorial problem of Erdős and Hajnal", Bulletin of the London Mathematical Society, 8 (4): 681–682, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1112%2Fjlms%2Fs2-8.4.681">10.1112/jlms/s2-8.4.681</a>.</li>
<li>Toft, Bjarne (1975), "On colour-critical hypergraphs", in <a href="/facts/Andr%25C3%25A1s_Hajnal/4gDj0N1Q">Hajnal, A.</a>; <a href="/facts/Richard_Rado/QXBFIwBd">Rado, Richard</a>; Sós, Vera T. (eds.), Infinite and Finite Sets: To Paul Erdös on His 60th Birthday, North Holland Publishing Co., pp. 1445–1457.</li>
<li>Manning, G. M. (1995), "Some results on the m(4) problem of Erdős and Hajnal", <a href="/facts/Electronic_Research_Announcements_of_the_American_Mathematical_Society/fr5gotCt">Electronic Research Announcements of the American Mathematical Society</a>, 1 (3): 112–113, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1090%2FS1079-6762-95-03004-6">10.1090/S1079-6762-95-03004-6</a>.</li>
<li>Beck, J. (1978), "On 3-chromatic hypergraphs", Discrete Mathematics, 24 (2): 127–137, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0012-365X%2878%2990191-7">10.1016/0012-365X(78)90191-7</a>.</li>
<li>Radhakrishnan, J.; Srinivasan, A. (2000), <a href="https://ieeexplore.ieee.org/document/743519">"Improved bounds and algorithms for hypergraph 2-coloring"</a>, Random Structures and Algorithms, 16 (1): 4–32, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2F%28SICI%291098-2418%28200001%2916%3A1%3C4%3A%3AAID-RSA2%3E3.0.CO%3B2-2">10.1002/(SICI)1098-2418(200001)16:1<4::AID-RSA2>3.0.CO;2-2</a>.</li>
<li>Miller, E. W. (1937), "On a property of families of sets", Comp. Rend. Varsovie, 30: 31–38.</li>
<li><a href="/facts/Paul_Erd%25C5%2591s/63LoUTe1">Erdős, P.</a>; <a href="/facts/Andr%25C3%25A1s_Hajnal/4gDj0N1Q">Hajnal, A.</a> (1961), "On a property of families of sets", <a href="/facts/Acta_Mathematica_Hungarica/G1Y5GSxQ">Acta Mathematica Academiae Scientiarum Hungaricae</a>, 12 (1–2): 87–123, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02066676">10.1007/BF02066676</a>.</li>
<li>Abbott, H. L.; Hanson, D. (1969), "On a combinatorial problem of Erdös", <a href="/facts/Canadian_Mathematical_Bulletin/BQ9Y16hL">Canadian Mathematical Bulletin</a>, 12 (6): 823–829, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.4153%2FCMB-1969-107-x">10.4153/CMB-1969-107-x</a></li>
<li>Östergård, Patric R. J. (30 January 2014). <a href="https://doi.org/10.1016%2Fj.dam.2011.11.035">"On the minimum size of 4-uniform hypergraphs without property B"</a>. Discrete Applied Mathematics. 163, Part 2: 199–204. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.dam.2011.11.035">10.1016/j.dam.2011.11.035</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Bernstein, F. (1908), "Zur theorie der trigonometrische Reihen", Leipz. Ber., 60: 325–328. <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn: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 <a href="0-444-87916-1" target="_blank">0-444-87916-1</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Beck, J. (1978), "On 3-chromatic hypergraphs", Discrete Mathematics, 24 (2): 127–137, doi:10.1016/0012-365X(78)90191-7, MR 0522920 <a href="/wiki/J%C3%B3zsef_Beck" target="_blank">/wiki/J%C3%B3zsef_Beck</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
</ol>

Property B open-in-new

Property B