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:

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