|
|
Structure of flow-continuous mappings in algebraic context
Hušek, Radek ; Šámal, Robert (advisor) ; Bonamy, Marthe (referee) ; Kaiser, Tomáš (referee)
We explore the structure of the cycle space of the graphs - most notably questions about nowhere-zero flows and cycle double covers. We touch several facets of this field. First we show that there are edge 2-connected graphs which distinguish Z2 2- and Z4- connectivity (group connectivity which is a strengthening of nowhere-zero flows). Then we examine a conjecture of Matt DeVos which asserts existence of group flows given existence of a graph homomorphism between suitable Cayley graphs. We introduce a strengthening of this conjecture called strong homomorphism property (SHP for short) which allows splitting vertices (and hence a reduction to cubic graphs). We conjecture that SHP holds for every graph and the smallest group in which the graph has a nowhere- zero flow and we prove that both SHP and the original conjecture imply existence of cycle double covers with few cycles. The question we discuss the most is counting objects on graphs - especially counting circuit double covers. We shows an almost exponential lower bound for graphs on surfaces with nice embeddings and we also show that this bound does not apply to Flower snarks. Then we shows quite precise bound for flower snarks and we also improve the lower bound for planar graphs to an exponential one. Along the way we build a framework for counting...
|
|
|
Graph Drawing: Visualisation and Geometric Representations of Graphs and Networks
Vyskočil, Tomáš ; Kratochvíl, Jan (advisor) ; Felsner, Stefan (referee) ; Kaiser, Tomáš (referee)
Title: Graph Drawing: Visualization and Geometric Representations of Graphs and Networks Author: Tomáš Vyskočil Department: Department of applied mathematics Supervisor: Prof. RNDr. Jan Kratochvíl, CSc., KAM Abstract: This thesis is devoted to studying of representations of graphs. In Chapters 2-4 we study intersection graphs in the plane. In Chapter 5 we consider problems of modifications of graphs. Regarding intersection graphs, we prove that all complements of partial 2- trees are intersection graphs of segments. We show complexity of recognition of intersection graphs of path in the grid with bounded number of bends and intersection graphs of connected regions (we call them islands) in the extended grids. In the part devoted to modification problems we present a fixed-parameter tractable (FPT) algorithm which answers the question whether a given graph can be made planar with at most k contractions and we also provide gener- alization of this problem. Keywords: graph theory, graph representations, combinatorics
|
|
| |
|
|
Věty Hellyho typu a zlomkového Hellyho typu
Tancer, Martin ; Matoušek, Jiří (advisor) ; Kaiser, Tomáš (referee)
A simplicial complex is d-representable if it is the nerve of a collection of convex sets in Rd. Classical Helly's Theorem states that if a d-representable complex contains all the possible faces of dimension d then it is already a full simplex. Helly's Theorem has many extensions and we give a brief survey of some of them. The class of d-representable complexes is a subclass of d-collapsible complexes, and the latter is a subclass of d-Leray complexes. For d 1 we give an example of complexes that are 2d-Leray but not (3d 1)-collapsible. For d 2 we give an example of complexes that are d-Leray but not (2d 2)-representable. We show that for d 3 the complexes from the last example are also d-collapsible. We also give a simple proof of the Combinatorial Alexander Duality, which is a useful topological tool for combinatorics, e.g., for topological versions of Helly's Theorem.
|
|
| |
|
|
Information model of society
Kaiser, Tomáš ; Souček, Martin (advisor) ; Smetáček, Vladimír (referee)
The first part of this paper refers to main streams in defining the term information for the purpose of information science and states its own definition flowing from the aspect of informativness. Information is understood in its relationship to meaning, as something which points or refer to something else. Also the terms data and meaning are discussed. The second part of this paper presents the philosophical view of society and world based on the terms defined above. The view corresponds to the thoughts of some famous personalities of information science and philosophy and displays some threats of the culture held by media.
|
|
|
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...
|
|
|
Graph Drawing: Visualisation and Geometric Representations of Graphs and Networks
Vyskočil, Tomáš ; Kratochvíl, Jan (advisor) ; Felsner, Stefan (referee) ; Kaiser, Tomáš (referee)
Title: Graph Drawing: Visualization and Geometric Representations of Graphs and Networks Author: Tomáš Vyskočil Department: Department of applied mathematics Supervisor: Prof. RNDr. Jan Kratochvíl, CSc., KAM Abstract: This thesis is devoted to studying of representations of graphs. In Chapters 2-4 we study intersection graphs in the plane. In Chapter 5 we consider problems of modifications of graphs. Regarding intersection graphs, we prove that all complements of partial 2- trees are intersection graphs of segments. We show complexity of recognition of intersection graphs of path in the grid with bounded number of bends and intersection graphs of connected regions (we call them islands) in the extended grids. In the part devoted to modification problems we present a fixed-parameter tractable (FPT) algorithm which answers the question whether a given graph can be made planar with at most k contractions and we also provide gener- alization of this problem. Keywords: graph theory, graph representations, combinatorics
|
|
|
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...
|
|
|
Extremální vlastnosti hypergrafů
Mach, Lukáš ; Kráľ, Daniel (advisor) ; Kaiser, Tomáš (referee)
We give an overview of recent progress in the research of hypergraph jumps -- a problem from extremal combinatorics. The number $\alpha \in [0, 1)$ is a jump for $r$ if for any $\epsilon > 0$ and any integer $m \ge r$ any $r$-graph with $N > N(\epsilon, m)$ vertices and at least $(\alpha + \epsilon) {N \choose r}$ edges contains a subgraph with $m$ vertices and at least $(\alpha + c) {m \choose r}$ edges, where $c := c(\alpha)$ does depend only on $\alpha$. Baber and Talbot \cite{Baber} recently gave first examples of jumps for $r = 3$ in the interval $[2/9, 1)$. Their result uses the framework of flag algebras \cite{Raz07} and involves solving a semidefinite optimization problem. A software implementation of their method is a part of this work.
|
guest ::
