|
|
Comonads (not only) for programmers
Šefl, Vít ; Hric, Jan (advisor) ; Pultr, Aleš (referee)
Monads (and their categorical dual - comonads) are important concepts in category theory and while monads enjoy their popularity in functional languages (mainly due to the programming language Haskell), comonads are often forgotten. In this work we present a definition of comonads suitable for programming and give examples of their use. One of the more important examples is zipper - a structure used to represent position. We show that zipper can be automatically derived for any regular type and show that this operation is very reminiscent of derivative from mathematical analysis. We also show worked examples of various problems that comonads can help solve in the language Haskell. All relevant proofs for the theoretical part of this work are machine checked in the language Agda. Powered by TCPDF (www.tcpdf.org)
|
|
|
Some point-free aspects of connectedness
Jakl, Tomáš ; Pultr, Aleš (advisor) ; Fiala, Jiří (referee)
In this thesis we present the Stone representation theorem, generally known as Stone duality in the point-free context. The proof is choice-free and, since we do not have to be concerned with points, it is by far simpler than the original. For each infinite cardinal κ we show that the counter- part of the κ-complete Boolean algebras is constituted by the κ-basically disconnected Stone frames. We also present a precise characterization of the morphisms which correspond to the κ-complete Boolean homomorphisms. Although Booleanization is not functorial in general, in the part of the dual- ity for extremally disconnected Stone frames it is, and constitutes an equiv- alence of categories. We finish the thesis by focusing on the De Morgan (or extremally disconnected) frames and present a new characterization of these by their superdense sublocales. We also show that in contrast with this phenomenon, a metrizable frame has no non-trivial superdense sublocale; in other words, a non-trivial Čech-Stone compactification of a metrizable frame is never metrizable. 1
|
|
|
Computational Homotopy Theory
Krčál, Marek ; Matoušek, Jiří (advisor) ; Pultr, Aleš (referee) ; Romero Ibáñez, Ana (referee)
of doctoral thesis "Computational Homotopy Theory": We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of compu- tational complexity. The extension problem asks, given topological spaces X, Y , a subspace A ⊆ X, and a (continuous) map f : A → Y , whether f can be extended to a map X → Y . For computational purposes, we assume that A, X, Y are represented as finite simplicial complexes and f as a simplicial map. We study the problem under the assumption that, for some d ≥ 1, Y is d- connected, otherwise the problem is undecidable by uncomputability of the fundamental group; We prove that, this problem is still undecidable for dim X = 2d + 2. On the other hand, for every fixed dim X ≤ 2d + 1, we obtain an algorithm that solves the extension problem in polynomial time. We obtain analogous complexity results for the problem of determining the set of homotopy classes of maps X → Y . We also consider the computation of the homotopy groups πk(Y ), k ≥ 2, for a 1-connected Y . Their computability was established by Brown in 1957; we show that πk(Y ) can be computed in polynomial time for every fixed k ≥ 2. On the other hand, we prove that computing πk(Y ) is #P-hard if k is a part of input. It is a strengthening of...
|
|
|
Separation axioms
Ha, Karel ; Pultr, Aleš (advisor) ; Loebl, Martin (referee)
The classical (point-set) topology concerns points and relationships between points and subsets. Omitting points and considering only the structure of open sets leads to the notion of frames, that is, a complete lattice satisfying the dis- tributive law b ∧ A = {b ∧ a | a ∈ A}, the crucial concept of point-free topology. This pointless approach-while losing hardly any information-provides us with deeper insights on topology. One such example is the study of separation axioms. This thesis focuses on the Ti-axioms (for i = 0, 1, 2, 3, 31 2 , 4): properties of topological spaces which regard the separation of points, points from closed sets, and closed sets from one another. In this text we discuss their point-free counterparts and how they relate to each other. 1
|
|
|
Topological and geometrical combinatorics
Tancer, Martin ; Matoušek, Jiří (advisor) ; Pultr, Aleš (referee) ; Kaiser, Tomáš (referee) ; Meshulam, Roy (referee)
1 Topological and Geometrical Combinatorics Martin Tancer Abstract The task of the thesis is to present several new results on topological methods in combinatorics. The results can be split into two main streams. The first stream regards intersection patterns of convex sets. It is shown in the thesis that finite projective planes cannot be intersection patterns of convex sets of fixed dimension which answers a question of Alon, Kalai, Matoušek and Meshulam. Another result shows that d-collapsibility (a necessary condition on properties of in- tersection patterns of convex sets in dimension d) is NP-complete for recognition if d ≥ 4. In addition it is shown that d-collapsibility is not a necessary condition on properties of intersection patterns of good covers, which disproves a conjecture of G. Wegner from 1975. The second stream considers algorithmic hardness of recognition of simplicial com- plexes embeddable into Rd . The following results are proved: It is algorithmically un- decidable whether a k-dimensional simplicial complex piecewise-linearly embeds into Rd for d ≥ 5 and k ∈ {d−1, d}; and this problem is NP-hard if d ≥ 4 and d ≥ k ≥ 2d−2 3 .
|
|
| |
|
|
Combinatorial Properties of Finite Models
Hubička, Jan ; Nešetřil, Jaroslav (advisor) ; Pultr, Aleš (referee) ; Cameron, P. (referee)
We study countable embedding-universal and homomorphism-universal structures and unify results related to both of these notions. We show that many universal and ultrahomogeneous structures allow a concise description (called here a finite presentation). Extending classical work of Rado (for the random graph), we find a finite presentation for each of the following classes: homogeneous undirected graphs, homogeneous tournaments and homogeneous partially ordered sets. We also give a finite presentation of the rational Urysohn metric space and some homogeneous directed graphs. We survey well known structures that are finitely presented. We focus on structures endowed with natural partial orders and prove their universality. These partial orders include partial orders on sets of words, partial orders formed by geometric objects, grammars, polynomials and homomorphism orders for various combinatorial objects. We give a new combinatorial proof of the existence of embedding-universal objects for homomorphism-defined classes of structures. This relates countable embedding-universal structures to homomorphism dualities (finite homomorphism-universal structures) and Urysohn metric spaces. Our explicit construction also allows us to show several properties of these structures.
|
|
| |
guest ::
