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

• Název práce v češtině: Duhové aritmetické posloupnosti a extremální množiny v mřížkách
• Název v anglickém jazyce: Rainbow arithmetic progressions and extremal subsets of lattices
• Klíčová slova: antiramsey, aritmetické posloupnosti, extremální kombinatorika
• Klíčová slova anglicky: antiramsey, arithmetic progressions, extremal
• Akademický rok vypsání: 2012/2013
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: doc. Mgr. Robert Šámal, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 06.11.2012
• Datum zadání: 22.05.2013
• Datum potvrzení stud. oddělením: 29.05.2013
• Datum a čas obhajoby: 02.09.2013 00:00
• Datum odevzdání elektronické podoby: 02.08.2013
• Datum odevzdání tištěné podoby: 02.08.2013
• Datum proběhlé obhajoby: 02.09.2013
• Oponenti: RNDr. Ondřej Pangrác, Ph.D.

Zásady pro vypracování

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.

Seznam odborné literatury

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.