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. |