|
|
Probabilistic Methods in Discrete Applied Mathematics
Fink, Jiří ; Loebl, Martin (advisor) ; Koubek, Václav (referee) ; Sereni, Jean-Sébastein (referee)
One of the basic streams of modern statistical physics is an effort to understand the frustration and chaos. The basic model to study these phenomena is the finite dimensional Edwards-Anderson Ising model. We present a generalization of this model. We study set systems which are closed under symmetric differences. We show that the important question whether a groundstate in Ising model is unique can be studied in these set systems. Kreweras' conjecture asserts that any perfect matching of the $n$-dimensional hypercube $Q_n$ can be extended to a Hamiltonian cycle. We prove this conjecture. The {\it matching graph} $\mg{G}$ of a graph $G$ has a vertex set of all perfect matchings of $G$, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle. We prove that the matching graph $\mg{Q_n}$ is bipartite and connected for $n \ge 4$. This proves Kreweras' conjecture that the graph $M_n$ is connected, where $M_n$ is obtained from $\mg{Q_n}$ by contracting all vertices of $\mg{Q_n}$ which correspond to isomorphic perfect matchings. A fault-free path in $Q_n$ with $f$ faulty vertices is said to be \emph{long} if it has length at least $2^n-2f-2$. Similarly, a fault-free cycle in $Q_n$ is long if it has length at least $2^n-2f$. If all faulty vertices are...
|
|
|
Nekonečné matroidy
Böhm, Martin ; Pangrác, Ondřej (advisor) ; Loebl, Martin (referee)
We summarize and present recent results in the field of infinite matroid theory. We define and prove basic properties of infinite matroids and we discuss known classes of examples of these structures. We focus on the topic of connectivity of infinite matroids and we link some matroid properties to connectivity. The main result of this work is the proof of existence of infinite matroids with arbitrary finite connectivity, but without finite circuits or cocircuits. Powered by TCPDF (www.tcpdf.org)
|
|
|
Representation of special classes of combinatorial objects
Scholleová, Barbora ; Nešetřil, Jaroslav (advisor) ; Loebl, Martin (referee)
The aim of this thesis is to bring together two areas of the graph theory. We first give a brief exposition of graph homomorphisms and related notions that directs to the definition of the replacement operation by using an appropriate replacement graph. The tree-depth is investigated as one of considerable chara- cteristics of each graph. Finally we focus on category representations in the category Graph of all finite graphs and Graphk of all finite graphs with tree-depth at most k.
|
|
|
Structural Graph Theory
Zamora, José ; Loebl, Martin (advisor) ; Sereni, Jean Sébastien (referee) ; Fiala, Jiří (referee)
In this thesis we consider four different problems in structural graph theory: We start studying the structure of graphs having a nowhere-zero 5-flow. We give a cha- racterization of the graphs that have a nowhere-zero 5-flow in terms of the existence of a (1, 2)-factor. For the second problem we introduce a new type of labeling of graphs that we call additive coloring. This coloring is a variation of the injective coloring. Indeed, it is an injective colo- ring with arithmetic restrictions determined by the graph. We study the properties and the structure of graphs admitting this type of labeling. Moreover, we study the computational complexity of the problem of computing this labeling for a graph with a fixed number of colors. In the third problem we study how the structure of caterpillars is encoded by the chromatic symmetric function or, equivalently, the U-polynomial. Stanley conjectured that the symme- tric chromatic polynomial distinguishes non-isomorphic trees. In this thesis we prove that the conjecture is true for proper caterpillars (caterpillars without vertices of degree 2). Finally, we study the structure of infinite graphs having a complete graph as a minor or as a topological minor. It is known that bounds on the degree of the vertices is not enough to ensure the existence of a complete...
|
|
| |
|
|
Transport optimization
Šimora, Peter ; Kučera, Luděk (advisor) ; Loebl, Martin (referee)
Considering decreasing reserves of oil and increasing population is necessary to talk about the question of logistics. We have chosen the railway transport. The advantages of railway transport are built railway system and the existing fleet of vehicles. The optimization and measuring are made at the railway network of Czech Republic. Packages are generated with the information of population of town, in which stations lie. For every package is chosen the optimal route. Packages are assigned to trains regard to decreasing the total number of traveled kilometers. Packages are placed to wagons regard to placing the most packages. We have found out that the total number of traveled kilometers in our algorithm is less by 36% than in the simple algorithm, at the optimal number of generated packages per hour.
|
|
| |
|
|
Geometric and algebraic properties of discrete structures
Rytíř, Pavel ; Loebl, Martin (advisor) ; Serra, Oriol (referee) ; Kaiser, Tomáš (referee)
In the thesis we study two dimensional simplicial complexes and linear codes. We say that a linear code C over a field F is triangular representable if there exists a two dimensional simplicial complex ∆ such that C is a punctured code of the kernel ker ∆ of the incidence matrix of ∆ over F and dim C = dim ker ∆. We call this simplicial complex a geometric representation of C. We show that every linear code C over a primefield is triangular representable. In the case of finite primefields we construct a geometric representation such that the weight enumerator of C is obtained by a simple formula from the weight enumerator of the cycle space of ∆. Thus the geometric representation of C carries its weight enumerator. Our motivation comes from the theory of Pfaffian orientations of graphs which provides a polynomial algorithm for weight enumerator of the cut space of a graph of bounded genus. This algorithm uses geometric properties of an embedding of the graph into an orientable Riemann surface. Viewing the cut space of a graph as a linear code, the graph is thus a useful geometric representation of this linear code. We study embeddability of the geometric representations into Euclidean spaces. We show that every binary linear code has a geometric representation that can be embed- ded into R4 . We characterize...
|
|
|
Decompositions of directed and undirected graphs
Pelikánová, Petra ; Loebl, Martin (advisor) ; Klimošová, Tereza (referee)
Eulerian graphs have a closed walk traversing each edge exactly once. Finding such a walk is a basic arc routing problem based on a road network. Most of the problems with applications in operational research are NP-hard. We describe a formal model of a road network and vehicle routes and formulate several arc routing problems motivated by winter road maintenance in the Czech Republic. The main part is focused on single vehicle routing problems on trees. We propose a new unfairness minimization problem for finding a vehicle route with properties that lead to a minimal number of resident complaints against unfair maintenance. Residents feel like they are skipped when the vehicle route has multiple trips and passes nearby without providing maintenance to their street. By reduction of the necklace splitting problem to the unfairness minimization problem we prove it is PPA-complete. Further, we define a restricted arc routing problem on trees which formalize condi- tions given by Czech legislation. We proved the existence of a polynomial algorithm for deciding whether a single vehicle route exists when there is a single priority for roads. If multiple priorities are used, we express conditions and conjectures when the problem has polynomial complexity. Finally, a utilization of the model is illustrated by an...
|
|
|
Optimization and Statistics
Fink, Jiří ; Loebl, Martin (advisor)
CONTENTS Nazev prace: Autor: Katedra (ustav-): Vedouci diplomove prace: E-mail vedouciho: Kh'cova slova; Abstrakt: Optimization and Statistics Jifi Fink Katedra aplikovane matematiky Doc. RNDr. Martin Loebl, CSc. loebl@kam.mff, cuni.cz Edwards-Anderson Ising model, Teorie grafu, T-join, Gaussovska distribuce Jedni'm ze zakladnich problemu moderni statisticke fyzikj' je'snada porozumet frus- traci a chaosu. Zakladnfm modelem je konecne dimenzionalni Edwards-Anderson Ising model. V optimalizaci to odpovida zkoumam minimalni'ch T-joinu v konecnych mnzkach s nahodnymi vahami na hranach. V teto praci studujeme "random join", coz je nahodna cesta mezi dvema pevne danj^mi \Tcholy. Puvodni definice je pfilis slozita; a tak jsme ukazali jednodussi. Tato defmice je pouzita k pfesnernu vypoctu "random join" na kruznici. Take jsme ukazali specialm algoritmus, ktery hleda cestu v mrfzce s danymi hranami. Tento algoritmus muze byt pouzit k experimentalnimu studovani "random join". Title: Author: Department: Supervisor: Supervisor's e-mail address: Keywords: Abstract: Optimization and Statistics Jin Fink Department of Applied Mathematics Doc. RNDr. Martin Loebl, CSc. loebl@kam.mff.cuni.cz Edwards-Anderson Ising model, Graph theory, T-join, the Gaussian distribution One of the basic streams of modern statistics physics is...
|
guest ::
