|
|
Using gadget construction in structural convergence
Hons, Tomáš ; Hartman, David (advisor) ; Ossona de Mendez, Patrice (referee) ; Pultr, Aleš (referee)
Structural convergence is a framework for convergence of graphs and relational struc- tures based on the probability of satisfaction of first-order formulas. We consider gadget construction, which is a ubiquitous tool in many areas of mathematics, as a method for constructing convergent sequences of structures. Both for elementary and local conver- gence, we investigate the behavior of a sequence created by gadget construction from convergent sequences of base structures and gadgets. We show that elementary conver- gence is always preserved while additional assumptions are necessary for local convergence as witnessed by several examples. We give various different conditions that ensure local convergence. One of them states that the resulting sequence is local convergent if the replaced edges are dense in the sequence of base structures. The sufficient conditions are partially complemented by inverse theorems. 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...
|
|
|
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.
|
|
|
Specialni bezbodove prostory
Novák, Jan ; Pultr, Aleš (advisor) ; Klazar, Martin (referee)
1 This thesis concerns separation axioms in point-free topology. We introduce a notion of weak inclusion, which is a relation on a frame that is weaker than the relation ≤. Weak inclusions provide a uniform way to work with standard separation axioms such as subfitness, fitness, and regularity. Proofs using weak inclusions often bring new insight into the nature of the axioms. We focus on results related to the axiom of subfitness. We study a sublocale which is defined as the intersection of all the codense sublocales of a frame. We show that it need not be subfit. For spacial frames, it need not be spacial.
|
|
|
Some point-free aspects of connectedness
Jakl, Tomáš ; Pultr, Aleš (advisor)
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
|
|
|
Semigroup-valued metric spaces
Konečný, Matěj ; Hubička, Jan (advisor) ; Pultr, Aleš (referee)
The structural Ramsey theory is a field on the boundary of combinatorics and model theory with deep connections to topological dynamics. Most of the known Ramsey classes in finite binary symmetric relational language can be shown to be Ramsey by utilizing a variant of the shortest path completion (e.g. Sauer's S-metric spaces, Conant's generalised metric spaces, Braunfeld's Λ-ultrametric spaces or Cherlin's metrically homogeneous graphs). In this thesis we explore the limits of the shortest path completion. We offer a unifying framework - semigroup-valued metric spaces - for all the aforementioned Ramsey classes and study their Ramsey expansions and EPPA (the extension property for partial automorphisms). Our results can be seen as evidence for the importance of studying the completion problem for amalgamation classes and have some further applications (such as the stationary independence relation). As a corollary of our general theorems, we reprove results of Hubička and Nešetřil on Sauer's S-metric spaces, results of Hubička, Nešetřil and the author on Conant's generalised metric spaces, Braunfeld's results on Λ-ultrametric spaces and the results of Aranda et al. on Cherlin's primitive 3-constrained metrically homogeneous graphs. We also solve several open problems such as EPPA for Λ-ultrametric...
|
|
|
d-Frames as algebraic duals of bitopological spaces
Jakl, Tomáš ; Pultr, Aleš (advisor) ; Picado, Jorge (referee) ; Cintula, Petr (referee)
Achim Jung and Drew Moshier developed a Stone-type duality theory for bitopological spaces, amongst others, as a practical tool for solving a particular problem in the theory of stably compact spaces. By doing so they discovered that the duality of bitopological spaces and their algebraic counterparts, called d-frames, covers several of the known dualities. In this thesis we aim to take Jung's and Moshier's work as a starting point and fill in some of the missing aspects of the theory. In particular, we investigate basic categorical properties of d-frames, we give a Vietoris construction for d-frames which generalises the corresponding known Vietoris constructions for other categories, and we investigate the connection between bispaces and a paraconsistent logic and then develop a suitable (geometric) logic for d-frames.
|
|
|
Some point-free aspects of connectedness
Jakl, Tomáš ; Pultr, Aleš (advisor)
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
|
|
|
Extension property of structures
Hartman, David ; Nešetřil, Jaroslav (advisor) ; Pultr, Aleš (referee) ; Woodrow, Robert (referee)
This work analyses properties of relational structures that imply a high degree of symmetry. A structure is called homogeneous if every mapping from any finite substructure can be extended to a mapping over the whole structure. The various types of these mappings determine corresponding types of homogeneity. A prominent position belongs to ultrahomogeneity, for which every local isomorphism can be extended to an automorphism. In contrast to graphs, the classification of ultrahomogeneous relational struc- tures is still an open problem. The task of this work is to characterize "the distance" to homogeneity using two approaches. Firstly, the classification of homogeneous structures is studied when the "complexity" of a structure is increased by introducing more relations. This leads to various classifications of homomorphism-homogeneous L-colored graphs for different L, where L- colored graphs are graphs having sets of colors from a partially ordered set L assigned to vertices and edges. Moreover a hierarchy of classes of ho- mogeneous structures defined via types of homogeneity is studied from the viewpoint of classes coincidence. The second approach analyses for fixed classes of structures the least way to extend their language so as to achieve homogeneity. We obtain results about relational complexity for finite...
|
guest ::
