|
Rainbow arithmetic progressions and extremal subsets of lattices
Voborník, Jan ; Šámal, Robert (advisor) ; Pangrác, Ondřej (referee)
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)
|
|
Rainbow arithmetic progressions and extremal subsets of lattices
Voborník, Jan ; Šámal, Robert (advisor) ; Pangrác, Ondřej (referee)
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)
|