|
|
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 .
|
|
|
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.
|
|
| |
|
| |
|
| |
|
|
Věty Hellyho typu a zlomkového Hellyho typu
Tancer, Martin ; Kaiser, Tomáš (referee) ; Matoušek, Jiří (advisor)
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.
|
|
| |
guest ::
