Problema de l'hort

Una disposició de nou punts (relacionada amb la configuració de Pappus) formant deu línies de 3 punts.

En geometria discreta, el problema de l'hort demana el màxim nombre de línies de 3 punts assolibles per una configuració de punts en el pla. També s'anomena problema de plantar arbres o simplement el problema de l'hort. També hi ha investigacions sobre quantes línies de punts k hi pot haver. Hallard T. Croft and Paul Erdős han demostrat t_k > c n² / k³, on n és el nombre de punts i t_k és el nombre de línies 'k. La seva construcció conté algunes línies de m punts, on m> k. També es pot fer la pregunta si aquests no estan permesos.

Seqüència de nombre enter

Definiu t₃^hort(n) com el nombre màxim de línies de 3 punts assolibles amb una configuració de n punts. Per a un nombre arbitrari de punts, n, t₃^hort(n) va ser (1/6)n² − O(n) el 1974.

Els primers valors de t₃^hort(n) es donen a la taula següent Plantilla:OEIS.

n	4	5	6	7	8	9	10	11	12	13	14
t3hort(n)	1	2	4	6	7	10	12	16	19	22	26

Límits superiors i inferiors

Atès que cap de les dues línies pot compartir dos punts diferents, un límit superior trivial per al nombre de línies de 3 punts determinades per n punts és

$\lfloor (\genfrac{}{}{0ex}{}{n}{2})/(\genfrac{}{}{0ex}{}{3}{2})\rfloor =\lfloor \frac{n^2-n}{6}\rfloor .$

Utilitzant el fet que el nombre de línies de 2 punts és com a mínim 6n/13 Plantilla:Harv, aquest superior lligat pot ser abaixat a

$\lfloor \frac{(\genfrac{}{}{0ex}{}{n}{2})-6n/13}{3}\rfloor =\lfloor \frac{n^2}{6}-\frac{25n}{78}\rfloor .$

Els límits inferiors per a t₃^hort(n) veuen construccions per a conjunts de punts amb moltes línies de 3 punts. El límit quadràtic més primerenc de ~ (1/8)n² va ser donat per Sylvester, que va col·locar n punts a la corba cúbica y = x³. Això va ser millorat per [(1/6)n² − (1/2)n] + 1 el 1974 per Plantilla:Harv, emprant una construcció basada en les funcions el·líptiques de Weierstrass.

Al setembre de 2013, Ben Green i Terence Tao van publicar un document en el qual demostren que per a tots els conjunts de punts de mida suficient, n > n₀, hi ha com a màxim ([n(n - 3)/6]  + 1) = [(1/6)n² − (1/2)n + 1] línies de 3 punts que aparella el més baix va lligar establert per Burr, Grünbaum i Sloane. Això és lleugerament més ben que el lligat que directament seguiria del seu estanc més baix lligat de n/2 pel nombre de línies de 2 punts: [n(n − 2)/6], es va demostrar en el mateix document i es va resoldre un problema de 1951 plantejat de forma independent per Gabriel Andrew Dirac i Theodore Motzkin.

Referències

• Plantilla:Citar ref.
• Plantilla:Citar ref.
• Plantilla:Citar ref.
• Plantilla:Citar ref.
• Plantilla:Citar ref

Enllaços externs

• Plantilla:MathWorld