Název: Duhové aritmetické posloupnosti a extremální množiny v mřížkách
Překlad názvu: Rainbow arithmetic progressions and extremal subsets of lattices
Autoři: Voborník, Jan ; Šámal, Robert (vedoucí práce) ; Pangrác, Ondřej (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2013
Jazyk: cze
Abstrakt: [cze] [eng]
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) When numbers $1,\ldots,tn$ are colored with $t$ colors (each color is used $n$ times), there exists a rainbow arithmetic progression of length $k$ (rainbow progression is a progression whose terms are colored with pairwise distinct colors). This holds true for $t>k^3$. Let $T_k$ denote the smallest $t$ for which it applies. Jungic et al. conjectured $T_k=O(k^2)$. Problem relates to extremal problems in discrete hypercubes. We present a method which uses lattices (discrete hypercubes which can contain indistinguishable elements) which can lead to improving the upper bound of $T_k$ down to $O(k^2\log k)$. In this thesis, we solve several extremal problems in lattices which have corollaries in various branches of mathematics. For example, using lattices we solve edge isoperimetric inequality in Hammilton cube, we find a graph with maximal sum of squares of degrees and convex set $M\subseteq [0,b]\times[0,a]$ which maximizes function $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)
Klíčová slova: antiramsey; aritmetické posloupnosti; extremální kombinatorika; antiramsey; arithmetic progressions; extremal

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/56464

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-325738


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce