Majetek B - Property B

v matematika, Majetek B je jisté teoretická množina vlastnictví. Formálně, vzhledem k konečná množina X, sbírka C z podmnožiny z X, má vlastnost B, pokud můžeme rozdělit X do dvou disjunktních podmnožin Y a Z tak, že každý vstup C splňuje obojí Y a Z.

Název nemovitosti získává od matematika Felix Bernstein, který tuto nemovitost poprvé představil v roce 1908.^[1]

Vlastnost B je ekvivalentní k 2-zbarvení the hypergraf popsáno ve sbírce C. Také se nazývá hypergraf s vlastností B. 2-barevný.^[2]:468 Někdy se také nazývá bipartitní, analogicky k bipartitní grafy. Vlastnost B je často studována pro uniformní hypergrafy (soustavy systémů, ve kterých mají všechny podmnožiny systému stejnou mohutnost), ale byla také zvažována v nejednotném případě.^[3]

Nejmenší set-rodiny bez majetku B

Nejmenší počet sad v kolekci velikostí n takhle C nemá vlastnost B je označen m(n).

Známé hodnoty m (n)

Je známo že m(1) = 1, m(2) = 3 a m(3) = 7 (jak je patrné z následujících příkladů); hodnota m(4) = 23 (Östergård), ačkoli zjištění tohoto výsledku bylo výsledkem vyčerpávajícího hledání. Byla prokázána horní hranice 23 (Seymour, Toft) a dolní hranice 21 (Manning). V době psaní tohoto článku (březen 2017) neexistuje žádné OEIS položka pro sekvenci m(n) zatím kvůli nedostatku známých termínů.

m(1)

Pro n = 1, nastaveno X = {1} a C = {{1}}. Pak C nemá vlastnost B.

m(2)

Pro n = 2, sada X = {1, 2, 3} a C = {{1, 2}, {1, 3}, {2, 3}} (trojúhelník). Pak C nemá vlastnost B, takže m(2) <= 3. Nicméně, C'= {{1, 2}, {1, 3}} dělá (nastaveno Y = {1} a Z = {2, 3}), takže m(2) >= 3.

m(3)

Pro n = 3, nastaveno X = {1, 2, 3, 4, 5, 6, 7} a C = {{1, 2, 4}, {2, 3, 5}, {3, 4, 6}, {4, 5, 7}, {5, 6, 1}, {6, 7, 2}, {7, 1, 3}} ( Trojitý systém Steiner S₇); C nemá vlastnost B (takže m(3) <= 7), ale pokud existuje nějaký prvek C je vynechán, pak lze tento prvek brát jako Ya sada zbývajících prvků C'bude mít vlastnost B (takže pro tento konkrétní případ, m(3)> = 7). Jeden může zkontrolovat všechny ostatní sbírky 6 3 sad, aby zjistil, že všechny mají vlastnost B.

m(4)

Östergård (2014) prostřednictvím vyčerpávajícího hledání nalezen m(4) = 23. Seymour (1974) zkonstruoval hypergraf na 11 vrcholech s 23 hranami bez vlastnosti B, což ukazuje, že m(4) <= 23. Manning (1995) zúžil podlahu tak, že m(4) >= 21.

Asymptotika m(n)

Erdős (1963) prokázal, že u jakékoli sbírky menší než ${ displaystyle 2 ^ {n-1}}$ sady velikostí n, existuje 2 zbarvení, ve kterém jsou všechny sady bichromatické. Důkaz je jednoduchý: Zvažte náhodné vybarvení. Pravděpodobnost, že je libovolná množina jednobarevná, je ${ displaystyle 2 ^ {- n + 1}}$. Podle a odborově vázán, pravděpodobnost, že existuje monochromatická množina, je menší než ${ displaystyle 2 ^ {n-1} 2 ^ {- n + 1} = 1}$. Proto existuje dobré zbarvení.

Erdős (1964) ukázal existenci n-jednotný hypergraf s ${ displaystyle O (2 ^ {n} cdot n ^ {2})}$ hyperedges, který nemá vlastnost B (tj. nemá 2-zbarvení, ve kterém jsou všechny hyperedges bichromatické), kterým se stanoví horní mez.

Schmidt (1963) dokázal, že každá kolekce je nanejvýš ${ displaystyle n / (n + 4) cdot 2 ^ {n}}$ sady velikostí n má majetek B. Erdős a Lovász se domnívali, že ${ displaystyle m (n) = theta (2 ^ {n} cdot n)}$. Beck v roce 1978 zlepšil dolní hranici ${ displaystyle m (n) = Omega (n ^ {1 / 3- epsilon} 2 ^ {n})}$, kde ${ displaystyle epsilon}$ je libovolné malé kladné číslo. V roce 2000 Radhakrishnan a Srinivasan zlepšili dolní hranici ${ displaystyle m (n) = Omega (2 ^ {n} cdot { sqrt {n / log n}})}$. Použili chytrý pravděpodobnostní algoritmus.

Viz také

• Věta Sylvester – Gallai § Barevné body
• Nastavit problém rozdělení

Reference

• Erdős, Paul (1963), „O kombinatorickém problému“, Nordisk Mat. Tidskr., 11: 5–10
• Erdős, P. (1964). „Na kombinatorický problém. 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, Paule (1974), „Poznámka k kombinatorickému problému Erdőse a Hajnala“, Bulletin of London Mathematical Society, 8 (4): 681–682, doi:10.1112 / jlms / s2-8.4.681.
• Toft, Bjarne (1975), „On color-critical hypergraphs“, in Hajnal, A.; Rado, Richarde; Sós, Vera T. (eds.), Nekonečné a konečné sady: Paulovi Erdösovi k jeho 60. narozeninám, North Holland Publishing Co., str. 1445–1457.
• Manning, G. M. (1995), „Některé výsledky na m(4) problém Erdőse a Hajnala “, Oznámení American Mathematical Society o elektronickém výzkumu, 1 (3): 112–113, doi:10.1090 / S1079-6762-95-03004-6.
• Beck, J. (1978), „On 3-chromatic hypergraphs“, Diskrétní matematika, 24 (2): 127–137, doi:10.1016 / 0012-365X (78) 90191-7.
• Radhakrishnan, J .; Srinivasan, A. (2000), „Vylepšené hranice a algoritmy pro 2barvení hypergrafu“, Náhodné struktury a algoritmy, 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), „O majetku rodin souprav“, Comp. Vykreslit. Varsovie, 30: 31–38.
• Erdős, P.; Hajnal, A. (1961), „O majetku rodin setů“, Acta Math. Acad. Sci. Visel., 12 (1–2): 87–123, doi:10.1007 / BF02066676.
• Abbott, H.L .; Hanson, D. (1969), „O kombinatorickém problému Erdöse“, Kanadský matematický bulletin, 12 (6): 823–829, doi:10.4153 / CMB-1969-107-x
• Östergård, Patric R. J. (30. ledna 2014). "Na minimální velikosti 4 uniformních hypergrafů bez vlastnosti B". Diskrétní aplikovaná matematika. 163, část 2: 199–204. doi:10.1016 / j.dam.2011.11.035.

.