Problema de l'hort

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 tk > c n2 / k3, on n és el nombre de punts i tk és el nombre de línies 'k.[1] La seva construcció conté algunes línies de m punts, on m> k. També es pot fer la pregunta si aquests no estan permesos.

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

Seqüència de nombre enterModifica

Definiu t3hort(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, t3hort(n) va ser (1/6)n2 − O(n) el 1974.

Els primers valors de t3hort(n) es donen a la taula següent (successió A003035 a l'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 inferiorsModifica

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

 

Utilitzant el fet que el nombre de línies de 2 punts és com a mínim 6n/13 (Csima & Sawyer 1993), aquest superior lligat pot ser abaixat a

 

Els límits inferiors per a t3hort(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)n2 va ser donat per Sylvester, que va col·locar n punts a la corba cúbica y = x3. Això va ser millorat per [(1/6)n2 − (1/2)n] + 1 el 1974 per (txt), emprant una construcció basada en les funcions el·líptiques de Weierstrass.

Al setembre de 2013, Ben GreenTerence Tao van publicar un document en el qual demostren que per a tots els conjunts de punts de mida suficient, n > n0, hi ha com a màxim ([n(n - 3)/6]  + 1) = [(1/6)n2 − (1/2)n + 1] línies de 3 punts que aparella el més baix va lligar establert per Burr, Grünbaum i Sloane.[2] 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.

NotesModifica

  1. The Handbook of Combinatorics, edited by László Lovász, Ron Graham, et al, in the chapter titled Extremal Problems in Combinatorial Geometry by Paul Erdős and George B. Purdy.
  2. Green & Tao (2013)

ReferènciesModifica

Enllaços externsModifica