Duhové aritmetické posloupnosti a extremální množiny v mřížkách

• Thesis title in Czech: Duhové aritmetické posloupnosti a extremální množiny v mřížkách
• Thesis title in English: Rainbow arithmetic progressions and extremal subsets of lattices
• Key words: antiramsey, aritmetické posloupnosti, extremální kombinatorika
• English key words: antiramsey, arithmetic progressions, extremal
• Academic year of topic announcement: 2012/2013
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: doc. Mgr. Robert Šámal, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 06.11.2012
• Date of assignment: 22.05.2013
• Confirmed by Study dept. on: 29.05.2013
• Date and time of defence: 02.09.2013 00:00
• Date of electronic submission: 02.08.2013
• Date of submission of printed version: 02.08.2013
• Date of proceeded defence: 02.09.2013
• Opponents: RNDr. Ondřej Pangrác, Ph.D.

Guidelines

Pokud jsou čísla 1, ..., tn obarvena t barvami (každá je užita n-krát), tak existuje duhová aritmetická posloupnost délky k. (Duhová posloupnost je taková, která nemá žádné dva členy stejné barvy.) Toto je pravda pro t>k^3/2, hypotéza Jungiče a spol. říká, že to je pravda už pro t=O(k^2).

Problém souvisí se zajímavými extremálními problémy pro podmnožiny diskrétních hyperkrychlí. Těm bude věnována pozornost v první fázi práce. Dále se student pokusí tyto výsledky rozšířit na podmnožiny přirozených čísel a tak dospět k řešení původního problému.

References

V.Jungic: Long rainbow arithmetic progressions, Open Problem Garden
http://openproblemgarden.org/op/long_rainbow_arithemtic_progressions

V.Jungic, J.Licht (Fox), M. Mahdian, J.Nesetril, R.Radoicic: Rainbow arithmetic progressions and anti-Ramsey results, Combinatorics, Probability, and Computing - Special Issue on Ramsey Theory, 12, (2003), 599-620.

Další literatura podle doporučení školitele.