|
|
Duhové aritmetické posloupnosti a extremální množiny v mřížkách
Voborník, Jan ; Šámal, Robert (vedoucí práce) ; Pangrác, Ondřej (oponent)
Když jsou čísla $1,\ldots,tn$ obarvena $t$ barvami (každá je užita $n$-krát), existuje mezi nimi duhová aritmetická posloupnost délky $k$. (Duhová aritmetická posloupnost je taková, která nemá žádné dva členy stejné barvy.) Toto platí pro $t>k^3$. Označme $T_k$ nejmenší takové $t$, pro které to platí. Hypotéza Jungiće a spol. říká, $T_k=O(k^2)$. Problém souvisí s extremálními problémy diskrétních hyperkrychlí. Představujeme metodu s mřížkami (diskrétní hyperkrychle, které mohou obsahovat nerozlišitelné prvky), která může vést k vylepšení odhadu $T_k$ až na $O(k^2\log k)$. V práci vyřešíme několik extremálních problémů v mřížkách, které mají důsledky v různých partiích matematiky. Například pomocí mřížek dokážeme hranovou isoperimetrickou nerovnost pro Hammingovu krychli, nalezneme bipartitní graf s maximálním součtem druhých mocnin stupňů a konvexní množinu $M\subseteq [0,b]\times[0,a]$ maximalizující funkci $G(M)=\int_{x=0}^a \lambda_1(M_x)^2+\int_{y=0}^b \lambda_1(M_y)^2$. Powered by TCPDF (www.tcpdf.org)
|
|
|
Rothova věta o aritmetických posloupnostech
Krkavec, Michal ; Klazar, Martin (vedoucí práce) ; Kráľ, Daniel (oponent)
Název práce: Rothova věta o aritmetických posloupnostech Autor: Michal Krkavec Katedra: Katedra aplikované matematiky Vedoucí bakalářské práce: doc. RNDr. Martin Klazar, Dr., Katedra aplikované matematiky Abstrakt: V předložené práci se zabýváme vlastnostmi množin přirozených čí- sel neobsahujících aritmetické posloupnosti. Cílem této práce je podat přehled a srovnání analytických a kombinatorických důkazů Rothovy věty, která tvrdí, že každá množina s kladnou horní asymptotickou hustotou obsahuje aritmetic- kou posloupnost délky tři. Zaměříme se také na vývoj poznatků od Erd˝osovy- Turánovy domněnky přes Rothovu větu až ke slavné Szemerédiho větě, která podala odpověď pro aritmetické posloupnosti libovolné délky k. V závěru práce se seznámíme s odhady čísla r3(n), které odpovídá největší velikosti podmnožiny A ⊆ [n], jež neobsahuje žádné aritmetické posloupnosti délky tři. Ukážeme dvě konstrukce, jak takové množiny A ⊆ [n] vybrat. Klíčová slova: Aditivní teorie čísel, Aritmetická posloupnost, Rothova věta, Elki- nova konstrukce
|
|
|
Duhové aritmetické posloupnosti a extremální množiny v mřížkách
Voborník, Jan ; Šámal, Robert (vedoucí práce) ; Pangrác, Ondřej (oponent)
Když jsou čísla $1,\ldots,tn$ obarvena $t$ barvami (každá je užita $n$-krát), existuje mezi nimi duhová aritmetická posloupnost délky $k$. (Duhová aritmetická posloupnost je taková, která nemá žádné dva členy stejné barvy.) Toto platí pro $t>k^3$. Označme $T_k$ nejmenší takové $t$, pro které to platí. Hypotéza Jungiće a spol. říká, $T_k=O(k^2)$. Problém souvisí s extremálními problémy diskrétních hyperkrychlí. Představujeme metodu s mřížkami (diskrétní hyperkrychle, které mohou obsahovat nerozlišitelné prvky), která může vést k vylepšení odhadu $T_k$ až na $O(k^2\log k)$. V práci vyřešíme několik extremálních problémů v mřížkách, které mají důsledky v různých partiích matematiky. Například pomocí mřížek dokážeme hranovou isoperimetrickou nerovnost pro Hammingovu krychli, nalezneme bipartitní graf s maximálním součtem druhých mocnin stupňů a konvexní množinu $M\subseteq [0,b]\times[0,a]$ maximalizující funkci $G(M)=\int_{x=0}^a \lambda_1(M_x)^2+\int_{y=0}^b \lambda_1(M_y)^2$. Powered by TCPDF (www.tcpdf.org)
|
|
|
Rothova věta o aritmetických posloupnostech
Krkavec, Michal ; Klazar, Martin (vedoucí práce) ; Kráľ, Daniel (oponent)
Název práce: Rothova věta o aritmetických posloupnostech Autor: Michal Krkavec Katedra: Katedra aplikované matematiky Vedoucí bakalářské práce: doc. RNDr. Martin Klazar, Dr., Katedra aplikované matematiky Abstrakt: V předložené práci se zabýváme vlastnostmi množin přirozených čí- sel neobsahujících aritmetické posloupnosti. Cílem této práce je podat přehled a srovnání analytických a kombinatorických důkazů Rothovy věty, která tvrdí, že každá množina s kladnou horní asymptotickou hustotou obsahuje aritmetic- kou posloupnost délky tři. Zaměříme se také na vývoj poznatků od Erd˝osovy- Turánovy domněnky přes Rothovu větu až ke slavné Szemerédiho větě, která podala odpověď pro aritmetické posloupnosti libovolné délky k. V závěru práce se seznámíme s odhady čísla r3(n), které odpovídá největší velikosti podmnožiny A ⊆ [n], jež neobsahuje žádné aritmetické posloupnosti délky tři. Ukážeme dvě konstrukce, jak takové množiny A ⊆ [n] vybrat. Klíčová slova: Aditivní teorie čísel, Aritmetická posloupnost, Rothova věta, Elki- nova konstrukce
|
host ::
RSS.