Temata bakalarskych a diplomovych praci - Pavel Valtr
Nize jsou uvedeny 4 pomerne siroce pojate tematicke okruhy,
umoznujici diplomovou ci bakarskou praci.
Je moznost se individualne dohodnout a temata upresnit
nebo se dohodnout na jinem tematu (vhodne zejmena
pro studenty Problemoveho seminare z kombinatoriky, Kombinatorickeho seminare
nebo prednasky Kombinatoricka a vypocetni geometrie I).
Seznam temat:
-
Projde ctyrsten obruci?
-
Ramseyovske vety v geometrii
-
Zobecnena Ramseyova cisla
-
Pokryvani secen ctverce
Popisy jednotlivych temat:
(Popisy jsou pomerne obecne pojate, na pozadani
rad vysvetlim podrobneji.)
Projde ctyrsten obruci?
Jak malou obruci (=kruznici) jeste projde ctyrsten (prip. krychle)?
Jak velka kruznice se vejde do ctyrstenu (prip. do krychle)?
Tyto otazky si lze obecneji polozit i v prostorech vyssi dimenze.
V nekterych pripadech neni odpoved znama, napr. pro
simplexy (vicedimenzionalni analogie ctyrstenu)
byl problem dosud uvazovan pouze ve zcela specialnich pripadech.
Ramseyovske vety v geometrii
Asi nejznamejsim problemem v teto oblasti
je otazka, zda pri libovolnem obarveni bodu
roviny pomoci 2 barev
lze libovolny nerovnostranny trojuhelnik
posunout a natocit tak, aby vsechny jeho vrcholy byly obarveny
stejnou barvou. Moznost prace na teto a cele rade podobnych
otazek.
Zobecnena Ramseyova cisla
Ramseyova veta rika, ze obarvime-li hrany
uplneho grafu pomoci 2 barev,
potom v nem existuje uplny podgraf
urcite velikosti, jehoz vsechny hrany jsou obarveny
stejnou barvou. Cilem diplomove prace je zkoumat
jak veliky uplny graf musime vzit, abychom pro kazde
obarveni jeho hran 2 barvami nasli podgraf urcite
velikosti v nemz vetsina (urcity minimalni pocet)
hran je obarvena stejnou barvou.
Pokryvani secen ctverce
Jaka je nejmensi celkova delka
takovych usecek v jednotkovem
ctverci, ze kazda
primka, ktera protina tento ctverec,
protina alespon jednu z usecek. Nejlepsi
zname reseni se sklada ze 4 usecek a prekvapive
netvori souvislou mnozinu. Soudi se, ze lepsi
reseni neexistuje, nikdo to vsak neumi dokazat.
Cilem diplomove prace je dosahnout co nejlepsiho
dolniho odhadu pro tento problem
i pro obdobny problem pro trojuhelnik.
Pavel Valtr