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", all of size "n", has Property B iff we can partition "X" into two disjoint subsets "Y" and "Z" such that every set in "C" meets both "Y" and "Z". The smallest number of sets of size "n" that do not have Property B is denoted by "m"("n").

The property gets its name from mathematician Felix Bernstein, who first introduced the property in 1908.

Values of "m"("n")

It is known that "m"(1) = 1, "m"(2) = 3, and "m"(3) = 7 (as can by seen by the following examples); the value of "m"(4) is not known, although an upper bound of 23 (Seymour, Toft) and a lower bound of 21 (Manning) have been proven. At the time of this writing (August 2004), 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" = 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. 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 Steiner triple system "S"7); "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.

Asymptotics of "m"("n")

Erds proved that for any collection of fewer than 2^{n-1} sets of size "n", there exists a 2-coloring in which no set is monochromatic. The proof is simple: Consider a random coloring. The probability that any one set is monochromatic is 2^{-n+1}. By a union bound, the probability that any set is monochromatic is less than 2^{n-1}2^{-n+1} = 1. Therefore, there exists a good coloring.

Erds constructed an "n"-uniform graph with O(2^n cdot n^2) edges which does not have property B, establishing an upper bound. Erds and Lovász conjectured that m(n) = heta(2^n cdot n). Beck in 1978 improved the lower bound to m(n) = Omega(n^{1/3}2^n). In 2000, Radhakrishnan and Srinivasan improved the lower bound to m(n) = Omega(2^n cdot sqrt{n / log n}). They used a clever probabilistic algorithm.

References

* Bernstein, F. "Zur theorie der trigonometrische Reihen." Leipz. Ber. 60 (1908): 325-328.
* Seymour, "A note on a combinatorial problem of Erdős and Hajnal", Bull. London Math. Soc. 2:8 (1974), 681-682
* Toft, "On colour-critical hypergraphs", in "Infinite and Finite Sets", ed. A. Hajnal et al, North Holland Publishing Co., 1975, 1445-1457
* G. M. Manning, "Some results on the "m"(4) problem of Erdős and Hajnal", Electron. Research Announcements of the American Mathematical Society, 1(1995) 112-113
* J. Beck, "On 3-chromatic hypergraphs." Discrete Math., 24(2):127-137, 1978.
* J. Radhakrishnan and A. Srinivasan, "Improved bounds and algorithms for hypergraph 2-coloring." Random Structures and Algorithms, 16(1):4-32, 2000.
* E. W. Miller, ``On a property of families of sets", Comp. Rend. Varsovie (1937), 31-38.
* P. Erdös and A. Hajnal, ``On a property of families of sets", Acta Math. Acad. Sci. Hung., 12 (1961), 87-123.
* H. L. Abbott and D. Hanson, ``On a çombinatorial problem of Erdös", Canad. Math. Bull., 12 (1969), 823-829.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Property — is any physical or virtual entity that is owned by an individual. An owner of property has the right to consume, sell, mortgage, transfer and exchange his or her property.cite web|url=http://www.businessdictionary.com/definition/property.html|titl… …   Wikipedia

  • Property — • The person who enjoys the full right to dispose of it insofar as is not forbidden by law Catholic Encyclopedia. Kevin Knight. 2006. Property     Property      …   Catholic encyclopedia

  • property — prop·er·ty n pl ties [Anglo French propreté proprieté, from Latin proprietat proprietas, from proprius own, particular] 1: something (as an interest, money, or land) that is owned or possessed see also asset, estate, interest …   Law dictionary

  • property — prop‧er‧ty [ˈprɒpəti ǁ ˈprɑːpər ] noun properties PLURALFORM 1. [uncountable] LAW all the things that someone owns: • Some of the stolen property was found in Mason s house. • The President supports a tax cut on profits from sales of property… …   Financial and business terms

  • property — and property rights are central to capitalist societies. Perhaps because they are largely taken for granted in this context they have received relatively little attention from sociologists. By comparison, political philosophers and economists… …   Dictionary of sociology

  • Property — Prop er*ty, n.; pl. {Properties}. [OE. proprete, OF. propret[ e] property, F. propret[ e] neatness, cleanliness, propri[ e]t[ e] property, fr. L. proprietas. See {Proper}, a., and cf. {Propriety}.] [1913 Webster] 1. That which is proper to… …   The Collaborative International Dictionary of English

  • property — c.1300, nature, quality, later possession (a sense rare before 17c.), from an Anglo Fr. modification of O.Fr. propriete (12c., Fr. propreté), from L. proprietatem (nom. proprietas) ownership, property, propriety, lit. special character (a loan… …   Etymology dictionary

  • property — Includes money, goods, things in action, land and every description of property, whether real or personal, legal or equitable, and whether situated in Canada or elsewhere, and includes obligations, easements and every description of estate,… …   Glossary of Bankruptcy

  • property — [präp′ər tē] n. pl. properties [ME proprete < OFr proprieté < L proprietas < proprius, one s own] 1. a) the right to possess, use, and dispose of something; ownership [property in land] b) something, as a piece of writing, in which… …   English World dictionary

  • Property — Prop er*ty, v. t. [1913 Webster] 1. To invest which properties, or qualities. [Obs.] Shak. [1913 Webster] 2. To make a property of; to appropriate. [Obs.] [1913 Webster] They have here propertied me. Shak. [1913 Webster] …   The Collaborative International Dictionary of English

  • property — [n1] possessions, real estate acreage, acres, assets, belongings, buildings, capital, chattels, claim, dominion, effects, equity, estate, farm, freehold, goods, holdings, home, house, inheritance, land, means, ownership, plot, possessorship,… …   New thesaurus

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.