|
|
Structure and complexity of homomorphisms
Bok, Jan ; Nešetřil, Jaroslav (advisor)
This thesis is concerned with computational complexity aspects of graph homomorph- isms and related concepts. We are mainly interested in various polynomial time versus NP-complete dichotomies. These results are especially popular thanks to the seminal result of Hell and Nešetřil providing the complexity dichotomy for graph homomorph- ism problems and the recent breakthrough result proving the complexity dichotomy for constraint satisfaction problems. The thesis is divided into three parts, all unified by the common goal to provide complexity classifications of various graph homomorphism problems. The first part is about list homomorphism problems for signed graphs. We study the complexity of such problems and obtain a structural description and dichotomy first for the case of targets being signed trees and then for the so-called separable graphs. The second part focuses on graph covering projections, also known as locally bijective homomorphisms. To the best of our knowledge, we are the first to initiate cataloguing the complexity of the corresponding problems for (mutli)graphs with semi-edges. We have three larger goals here. (1) Providing the complete dichotomy for one- and two- vertex target graphs. (2) Discuss and propose the right definition of graph cover in the case of disconnected targets. (3)...
|
|
|
Structure and complexity of homomorphisms
Bok, Jan ; Nešetřil, Jaroslav (advisor) ; Golovach, Petr (referee) ; Proskurowski, Andrzej (referee)
This thesis is concerned with computational complexity aspects of graph homomorph- isms and related concepts. We are mainly interested in various polynomial time versus NP-complete dichotomies. These results are especially popular thanks to the seminal result of Hell and Nešetřil providing the complexity dichotomy for graph homomorph- ism problems and the recent breakthrough result proving the complexity dichotomy for constraint satisfaction problems. The thesis is divided into three parts, all unified by the common goal to provide complexity classifications of various graph homomorphism problems. The first part is about list homomorphism problems for signed graphs. We study the complexity of such problems and obtain a structural description and dichotomy first for the case of targets being signed trees and then for the so-called separable graphs. The second part focuses on graph covering projections, also known as locally bijective homomorphisms. To the best of our knowledge, we are the first to initiate cataloguing the complexity of the corresponding problems for (mutli)graphs with semi-edges. We have three larger goals here. (1) Providing the complete dichotomy for one- and two- vertex target graphs. (2) Discuss and propose the right definition of graph cover in the case of disconnected targets. (3)...
|
|
|
Structural aspects of aesthetic visualinformation processing
Douchová, Veronika ; Nešetřil, Jaroslav (advisor) ; Klazar, Martin (referee) ; Vlček, Tomáš (referee)
Univerzita Karlova Filozofická fakulta Katedra logiky Obor: Logika Strukturální aspekty zpracování vizuální informace s estetickou složkou Structural aspects of aesthetic visual information processing Abstract Mgr. Veronika Douchová vedoucí (supervisor): prof. RNDr. Jaroslav Nešetřil, DrSc., 2022 Abstract In the thesis, we investigate and formulate a framework for analyzing certain aspects of aesthetics from a structural and mathematical perspective. We build on the results of neuroaesthetics-a (relatively new) field in neurol- ogy introduced by S. Zeki in 1990's-which links the process of seeing, and evaluating information with an aesthetic component, with the structure of the human brain. Several principles influencing aesthetic judgements were identified by neuroaesthetics and connected with the structure of the human brain, such as the notions of modularity, symmetry, harmony, or balance. We argue that these results provide an objective interpretative framework for an- alyzing certain aspects of visual information with an aesthetic component by means of mathematical methods. We apply these results to Birkhoff's aes- thetic measure, providing objective foundations for his theoretical methods, based on algebraic invariants for aesthetics. We follow up with a discussion of the theory of J. Nešetřil-which...
|
|
| |
|
|
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.
|
|
|
Freiman's theorem in additive combinatorics
Hančl, Jaroslav ; Klazar, Martin (advisor) ; Nešetřil, Jaroslav (referee)
In the presented summary work we study the inverse problem in additive number theory. More speci cally, we try to characterize sets A of positive integers if we know some information about their sumsets 2A = A + A. At the beginning we devote some time to nite sets with the property |2A| = 2|Aj| - 1, then we solve a generalized problem for such abelian groups G in whose order of all elements is bounded by a constant rand their subsets A satisfying j2Aj cjAj. At the end we present the famous Freiman theorem, which describes sets of positive integers A small in the sense |2A| - c|A|. We prove this theorem and give some corollaries and applications.
|
|
|
Algebraic, Structural, and Complexity Aspects of Geometric Representations of Graphs
Zeman, Peter ; Klavík, Pavel (advisor) ; Nešetřil, Jaroslav (referee)
Title: Algebraic, Structural and Complexity Aspects of Geometric Representations of Graphs Author: Peter Zeman Department: Computer Science Institute Supervisor: RNDr. Pavel Klavík Supervisor's e-mail: klavik@iuuk.mff.cuni.cz Keywords: automorphism groups, interval graphs, circle graphs, comparability graphs, H-graphs, recognition, dominating set, graph isomorphism, maximum clique, coloring Abstract: We study symmetries of geometrically represented graphs. We describe a tech- nique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representations. We prove that interval graphs have the same automorphism groups as trees, and for a given interval graph, we construct a tree with the same automorphism group which answers a question of Hanlon [Trans. Amer. Math. Soc 272(2), 1982]. For permutation and circle graphs, we give an inductive characterization by semidirect and wreath prod- ucts. We also prove that every abstract group can be realized by the automorphism group of a comparability graph/poset of the dimension at most four. We also study H-graphs, introduced by Biró, Hujter, and Tuza in 1992. Those are intersection graphs of connected subgraphs of a subdivision of a graph H. This thesis is the first comprehensive...
|
|
| |
|
|
Ramseyova teorie a kombinatorické hry
Valla, Tomáš ; Nešetřil, Jaroslav (advisor) ; Valtr, Pavel (referee)
Ramsey theory studies the internal homogenity of mathematical structures (graphs, number sets), parts of which (subgraphs, number subsets) are arbitrarily coloured. Often, the sufficient object size implies the existence of a monochromatic sub-object. Combinatorial games are 2-player games of skill with perfect information. The theory of combinatorial games studies mostly the questions of existence of winning or drawing strategies. Let us consider an object that is studied by a particular Ramsey-type theorem. Assume two players alternately colour parts of this object by two colours and their goal is to create certain monochromatic sub-object. Then this is a combinatorial game. We focus on the minimum object size such that the appropriate Ramsey-type theorem holds, called Ramsey number, and on the minimum object size such that the rst player has a winning strategy in the corresponding combinatorial game, called game number. In this thesis, we describe such Ramsey-type theorems where the Ramsey number is substantially greater than the game number. This means, we show the existence of rst player's winning strategies, zogether with Ramsey and game numbers upper bounds, and we compare both numbers.
|
|
|
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 ::
