Original title:
Maximální množiny bodů na diskrétní torické mřížce bez trojic bodů ležících na stejné přímce
Translated title:
Maximal point sets on discrete toric grid with no three colinear points
Authors:
Skotnica, Michael ; Tancer, Martin (advisor) ; Kala, Vítězslav (referee) Document type: Bachelor's theses
Year:
2016
Language:
cze Abstract:
[cze][eng] Označme τ(Tm×n) maximální počet bodů na diskrétní torické mřížce o roz- měrech m × n bez trojic bodů ležících na jedné přímce. Práce se zabývá otázkou, jaká je hodnota τ(Tm×n) pro různá m, n. Jedná se o variantu problému, který je znám jako no-three-in-line-problem. Nejdříve uvádíme některé poznatky z článků, které se touto otázkou již zabývaly. Některé z nich jsou zde zobecněny. Dále nově vylepšujeme horní a dolní odhady pro případy, které v předchozích článcích ne- byly vyřešeny, zejména pro případy, kdy rozměry mřížky jsou mocniny prvočísla. Nakonec definujeme posloupnost (τ(Tm×n))n∈N, o které dokážeme, že je periodická pro libovolné pevné m. 1Let τ(Tm×n) denote maximal number of points on a discrete toric grid of the sizes m×n with no three colinear points. This thesis examines τ(Tm×n) for various m, n. It is a variant of the well-known no-three-in-line-problem. First, we present some previously known results. Then we generalize them in various directions. In particular we improve upper and lower bounds for cases which have not been solved in previous papers especially for cases when the sizes of the grid are prime powers. At the end we define the sequence (τ(Tm×n))n∈N and we prove that it is periodic for all fixed m. 1
Keywords:
combinatorics of points on lines; discrete toric grid; prime numbers and divisibility; diskrétní torická mřížka; kombinatorika bodů na přímkách; prvočísla a dělitelnost
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/83781