Problém s výsadbou sadů - Orchard-planting problem

Uspořádání devíti bodů (vztahující se k Konfigurace Pappus ) tvořící deset tříbodových čar.

v diskrétní geometrie, originál problém s výsadbou sadů žádá o maximální počet 3bodových čar dosažitelných konfigurací konkrétního počtu bodů v rovině. Také se tomu říká problém s výsadbou stromů nebo jednoduše problém sadů. Také se zkoumá, kolik čar k-bodu může být. Hallard T. Croft a Paul Erdős dokázal t_k > C n² / k³, kde n je počet bodů a t_k je počet k-bodové čáry.^[1] Jejich konstrukce obsahuje několik čar m-bodu, kde m> k. Lze také položit otázku, pokud nejsou povoleny.

Celá sekvence

Definovat t₃^{ovocný sad}(n) je maximální počet 3bodových čar dosažitelných při konfiguraci n bodů. Pro libovolný počet bodů n, t₃^{ovocný sad}(n) se ukázalo být (1/6)n² - O (n) v roce 1974.

Prvních několik hodnot t₃^{ovocný sad}(n) jsou uvedeny v následující tabulce (sekvence A003035 v OEIS ).

Horní a dolní mez

Protože žádné dvě čáry nesmějí sdílet dva odlišné body, a triviální horní hranice pro počet 3bodových čar určený n body jsou

${ displaystyle left lfloor { binom {n} {2}} { Big /} { binom {3} {2}} right rfloor = left lfloor { frac {n ^ {2} -n} {6}} doprava rfloor.}$

S využitím toho, že počet 2bodových čar je alespoň 6n/13 (Csima & Sawyer 1993 ), lze tuto horní hranici snížit na

${ displaystyle left lfloor { frac {{ binom {n} {2}} - 6n / 13} {3}} right rfloor = left lfloor { frac {n ^ {2}} { 6}} - { frac {25n} {78}} doprava rfloor.}$

Dolní hranice pro t₃^{ovocný sad}(n) jsou dány konstrukcemi pro množiny bodů s mnoha tříbodovými čarami. Nejdříve kvadratická dolní mez ~ (1/8)n² byl dán Sylvester, který umístil n body na kubické křivce y = X³. To bylo vylepšeno na [(1/6)n² − (1/2)n] + 1 v roce 1974 Burr, Grünbaum, a Sloane  (1974 ), pomocí konstrukce založené na Weierstrassovy eliptické funkce. Elementární konstrukce pomocí hypocykloidy byl nalezen uživatelem Füredi a Palásti (1984) dosažení stejné dolní meze.

V září 2013 Ben Green a Terence Tao zveřejnili dokument, ve kterém dokazují, že pro všechny bodové sady dostatečné velikosti n > n₀, existuje maximálně ([n(n - 3)/6]  + 1) = [(1/6)n² − (1/2)n + 1] 3bodové čáry, které odpovídají spodní hranici stanovené Burr, Grünbaum a Sloane.^[2] To je o něco lepší než vazba, která by přímo vyplývala z jejich těsné spodní hranice n/ 2 pro počet 2bodové čáry: [n(n - 2) / 6], prokázané ve stejné práci a řešení problému z roku 1951, který položil samostatně Gabriel Andrew Dirac a Theodore Motzkin.

Poznámky

Reference

• Brass, P .; Moser, W. O. J .; Pach, J. (2005), Výzkumné problémy v diskrétní geometrii, Springer-Verlag, ISBN  0-387-23815-8.
• Burr, S.A.; Grünbaum, B.; Sloane, N. J. A. (1974), "The Orchard problem", Geometriae Dedicata, 2 (4): 397–424, doi:10.1007 / BF00147569.
• Csima, J .; Sawyer, E. (1993), „Existuje 6n/ 13 běžných bodů ", Diskrétní a výpočetní geometrie, 9: 187–202, doi:10.1007 / BF02189318.
• Füredi, Z.; Palásti, I. (1984), "Uspořádání čar s velkým počtem trojúhelníků", Proceedings of the American Mathematical Society, 92 (4): 561–566, doi:10.2307/2045427, JSTOR  2045427.
• Zelená, Ben; Tao, Terence (2013), „Na množinách definujících několik běžných řádků“, Diskrétní a výpočetní geometrie, 50 (2): 409–468, arXiv:1208.4714, doi:10.1007 / s00454-013-9518-9

externí odkazy

• Weisstein, Eric W. „Problém s výsadbou sadů“. MathWorld.