|
|
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)
|
|
|
Petersen coloring and variants
Bílková, Hana ; Šámal, Robert (advisor) ; Dvořák, Zdeněk (referee)
The Petersen coloring of 3-regular graph G is equivalent to the normal coloring by five colors. The normal coloring is a good coloring of edges such that every edge and its four neighbours have together three or five different colors. Jaeger conjectures that every bridgeless 3-regular graph has a Petersen coloring. If the conjecture were true, it would imply other interesting statements about 3-regular graphs. In this text we investigate normal coloring by more than five colors. Jaeger theorem about nowhere-zero Z2 3 -flow implies that every bridgeless graph has normal coloring by seven colors. Independently on the Jaeger theorem, we prove the existence of normal coloring by nine colors for graphs with a bridge, a cut of size two or with a triangle. The idea of our proof comes from Andersen's proof of existence of strong coloring by ten colors for 3-regular graphs. Finally, we sketch the idea of the proof for other classes of 3-regular graphs. 1
|
|
|
Circuits and matchings in graphs
Tesař, Karel ; Pangrác, Ondřej (advisor) ; Šámal, Robert (referee)
O grafu řekneme, že je k-linkovaný, pokud pro každých k dvojic jeho vrchol· existují navzájem disjunktní cesty, které dané dvojice spojují. Existuje vztah mezi k-linkovaností a vrcholovou souvislostí grafu. V této práci hledáme vztah mezi vrcholovou souvislostí grafu a vlastností, že každých k jeho disjunktních hran leží na společné kružnici. Tento problém se dá řešit pomocí k-linkovanosti. Naším cílem je dosáhnout lepších odhad· na souvislost, resp. jiných postačujících podmínek než těch, které jsou známe pro k-linkovanost. 1
|
|
|
Minimal counterexamples to flow conjectures
Korcsok, Peter ; Šámal, Robert (advisor) ; Goodall, Andrew (referee)
We say that a~graph admits a~nowhere-zero k-flow if we can assign a~direction and a~positive integer (<k) as a~flow to each edge so that total in-flow into $v$ and total out-flow from $v$ are equal for each vertex $v$. In 1954, Tutte conjectured that every bridgeless graph admits a~nowhere-zero 5-flow and the conjecture is still open. Kochol in his recent papers introduces a~computational method how to prove that a~minimal counterexample cannot contain short circuits (up to length 10). In this Thesis, we provide a~comprehensive view on this method. Moreover, since Kochol does not share his implementation and in order to independently verify the method, we provide our source code that validates Kochol's results and extend them: we prove that any minimal counterexample to the conjecture does not contain any circuit of length less than 12. Powered by TCPDF (www.tcpdf.org)
|
|
|
Eberhard-Like Theorems
Šimečková, Zuzana ; Šámal, Robert (advisor) ; Fiala, Jiří (referee)
Define sequence (pk) = (p3,p4, . . . ) as numbers of k-sized faces - k-gons - of an embedding of a planar graph. A corollary to Euler's formula for planar graphs states that for cubic graphs ∑ k>=3 (6 − k)pk = 12 holds. Naturally, this leads us to explore the nature of p for which a corresponding cubic planar graph exists. Eberhard proved that if p satisfies the equality above then a cubic planar graph that corresponds to p except for the number of hexagons, exists. DeVos et al. show similar theorem, but instead of hexagon, both pentagons and heptagons can be added. In this thesis, we extend their result by using their proof strategy and designing a program to find graphs needed in such proof. We were able to prove that for every pair r,s ∈ N where s < 6 < r < 14 and r,s are coprime the following theorem holds: for each sequence of nonnegative integers satisfying ∑ k>=3 (6 − k)pk = 12 there are infinitely many cubic planar graphs corresponding to p except for the number of both r-gons and s-gons. 1
|
|
|
Lipschitz mappings of discrete sets
Kaluža, Vojtěch ; Matoušek, Jiří (advisor) ; Šámal, Robert (referee)
In this thesis we consider Feige's question of whether there always exists a constantly Lipschitz bijection of an n2 -element set S ⊂ Z2 onto a regular lattice of n × n points in Z2 . We propose a solution of this problem in case the points of the set S form a long rectangle or they are arranged in the shape of a square without a part of its interior points. The main part is a summary of Burago's and Kleiner's article [2] and the article by McMullen [12] dealing with the problem of existence of separated nets in R2 that are not bi-Lipschitz equivalent to the integer lattice. This problem looks similar to Feige's problem. According to these articles we construct a separated net that is not bi-Lipschitz equivalent to the integer lattice, using a positive bounded measurable function that is not the Jacobian of a bi-Lipschitz homeomorphism almost everywhere. We present McMullen's construction of such a function and we complete his proof of its correctness. 1
|
|
|
Persistent homology and neural networks
Černý, Marek ; Šámal, Robert (advisor) ; Tancer, Martin (referee)
Deep learning has solved various computer vision problems in the last decade. We use computational topology, namely persistent homology groups, to analyze the spaces of internal feature representations of convolutional neural networks (CNNs). We observed the correspondence between the summaries of the homological persistence groups of the decision boundary and ResNet-18 CNN training error during the phenomenon of deep double descent. Furthermore, a considered specific persistence summary suggests an analogy to epoch-wise double descent so that we may better understand the internal representations during the critically parametrized regime. Mainly, we develop and compare multiple approaches to CNN models processing using the persistence homology. Our best method, the Differentiable Persistence Accuracy Es- timator (DPAE), achieves very high accuracy in predicting CNN's performance (R2 score close to 0.99). Our DPAE is a topologically optimized end-to-end architecture involving differentiable persistence computation. Moreover, DPAE overperforms the original clas- sical machine learning-based method on its native Small CNN Zoo dataset. We publicly release the complete source code of DPAE and other presented experiments. 1
|
|
|
Identification of bilinear systems
Kršková, Iveta ; Mareš, Martin (advisor) ; Šámal, Robert (referee)
Title: Identification of bilinear systems Author: Iveta Kršková Department: Department of Applied Mathematics Supervisor: Mgr. Martin Mareš, Ph.D., Department of Applied Mathematics Abstract: In this thesis, the identification of systems with bilinear structure is studied. The main focus lies in the identification of chemical reaction networks with a biological background. The identification of such systems is extremely useful. Once the model of such a system is obtained it can be used for the purposes of control of the processes in the human body. In order to properly perform such a complex process as the system identification is, the properties of linear and bilinear dynamical systems regarding the identification procedure are studied. The suitability of bilinear systems for modelling chemical reaction networks is discussed. Several approaches used for the estimation of parameters are reviewed. The identification procedure suggested by Juang is implemented and extensively studied on the example of peptide chain elongation. How to choose the parameters for the system identification procedure of a bilinear system is illustrated for the latter example. The conclusions about the gained experience with Juang's identification procedure are stated. 1
|
|
|
Structural properties of random networks with dynamics
Gajdová, Anna ; Hartman, David (advisor) ; Šámal, Robert (referee)
Real systems are often represented by so-called complex networks. These networks have a specific connectivity structure given by the specifics of the studied systems. Since often insufficient or inaccurate data are available, a common approach is to model these systems at the level of this connectivity using random networks replicating specific prop- erties such as ease of connectivity, modularity or specific sparsity. The representation of these properties in basic complex network models is a widely explored area. However, if the presence of edges is controlled by a specific distributions or if an element of the dynamics of the overall graph is added to the model, the analysis of such models be- comes more complex. This thesis aims to investigate the properties of such dynamically dependent random models. 1
|
|
|
Number of faces in a random embedding of a complete graph
Ryzák, David ; Šámal, Robert (advisor) ; Tancer, Martin (referee)
Any finite graph can be embedded on a surface with sufficiently high genus. Such an embedding can be described (up to homeomorphism) by local rotations at vertices, i.e., a cyclical order of all edges incident to a vertex. A random embedding is then just an embedding with randomly chosen local rotations at each vertex. A genus distribution of some types of graphs is well known. However, our main interest is a distribution of the number of faces of some length. We also restrict the work only on one type of a graph, i.e., a complete graph. The main result is that the number of faces of a fixed length has asymptotically Poisson distribution. We knew there is a close relation between cycles in a random permutation and faces of a random embedding. We found out that they have the same limit distribution, however, we also found differences between these two objects. Relations are described by theoretical calculations of various moments and by simulations of a random embedding and a random permutation. 1
|
guest ::
