Original title: Duhové aritmetické posloupnosti a extremální množiny v mřížkách
Translated title: Rainbow arithmetic progressions and extremal subsets of lattices
Authors: Voborník, Jan ; Šámal, Robert (advisor) ; Pangrác, Ondřej (referee)
Document type: Bachelor's theses
Year: 2013
Language: cze
Abstract: [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)
Keywords: antiramsey; arithmetic progressions; extremal; antiramsey; aritmetické posloupnosti; extremální kombinatorika

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/56464

Permalink: http://www.nusl.cz/ntk/nusl-325738


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses