Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Property B
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== 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.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)