Original title: Dělení trojúhelníků a vzdálenosti grup
Translated title: Dissections of triangles and distances of groups
Authors: Szabados, Michal ; Drápal, Aleš (advisor) ; Klazar, Martin (referee)
Document type: Master’s theses
Year: 2013
Language: eng
Abstract: [eng] [cze]
Denote by gdist(p) the least number of cells that have to be changed to get a latin square from the table of addition modulo prime p. A conjecture of Drápal, Cavenagh and Wanless states that there exists c > 0 such that gdist(p) ≤ c log(p). In this work we prove the conjecture for c ≈ 7.21, and the proof is done by constructing a dissection of an equilateral triangle of side n into O(log(n)) equilateral triangles. We also show a proof of the lower bound c log(p) ≤ gdist(p) with improved constant c ≈ 2.73. At the end of the work we present computational data which suggest that gdist(p)/ log(p) ≈ 3.56 for large values of p. Označme gdist(p) najmenší možný počet políčok, ktorý je nutné zmeniť v tabuľke sčítania modulo prvočíslo p, aby vznikol latinský štvorec. Drápal, Cavenagh a Wanless formulovali hypotézu, podľa ktorej existuje c > 0 také, že gdist(p) ≤ c log(p). V tejto práci je táto hypotéza dokázaná pre c ≈ 7.21, a to pomocou konštrukcie delenia rovnostranného trojuholníka so stranou n na O(log(n)) rovnostranných trojuholníkov. Uvádzame taktiež spodný odhad c log(p) ≤ gdist(p) s vylepšenou konštanou c ≈ 2.73. V práci na záver prezentujeme výpočetné dáta, ktoré naznačujú, že pre veľké hodnoty p platí gdist(p)/ log(p) ≈ 3.56.
Keywords: Cayley table; dissection; equilateral triangle; latin bitrade; tiling; Cayleyho tabuľka; delenie; dláždenie; latinská zámena; rovnostranný trojuholník

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/55324

Permalink: http://www.nusl.cz/ntk/nusl-324616


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses