Let G be a graph. For k ≥ d ≥ 1, a k/d -coloring of G is a coloring c of vertices of G with colors 0, 1, 2, . . ., k - 1, such that d ≤ | c(x) - c(y) | ≤ k - d, whenever xy is an edge of G. We say that the circular chromatic number of G, denoted χc(G), is equal to the smallest k/d where a k/d -coloring exists. In [6], Pan and Zhu have given a function μ(g) that gives an upper bound for the circular-chromatic number for every K4-minor-free graph Gg of odd girth at least g, g ≥ 3. In [7], they have shown that their upper bound in [6] can not be improved by constructing a sequence of graphs approaching μ(g) asymptotically. We prove that for every odd integer g = 2k + 1, there exists a graph Gg ∈ G/K4 of odd girth g such that χc(Gg) = μ(g) if and only if k is not divisible by 3. In other words, for any odd g, the question of attainability of μ(g) is answered for all g by our results. Furthermore, the proofs [6] and [7] are long and tedious. We give simpler proofs for both of their results.

Computing the most specific concept (msc) is an inference task that can be used to support the 'bottom-up' construction of knowledge bases for KR systems based on description logics. For description logics that allow for number restrictions or existential restrictions, the msc need not exist, though. Previous work on this problem has concentrated on description logics that allow for universal value restrictions and number restrictions, but not for existential restrictions. The main new contribution of this paper is the treatment of description logics with existential restrictions. More precisely, we show that, for the description logic ALE (which allows for conjunction, universal value restrictions, existential restrictions, negation of atomic concepts) the msc of an ABox-individual only exists in case of acyclic ABoxes. For cyclic ABoxes, we show how to compute an approximation of the msc. Our approach for computing the (approximation of the) msc is based on representing concept descriptions by certain trees and ABoxes by certain graphs, and then characterizing instance relationships by homomorphisms from trees into graphs. The msc/approximation operation then mainly corresponds to unraveling the graphs into trees and translating them back into concept descriptions.

In the 1970’s, L. Lovász proved that two graphs G and H are isomorphic if and only if for every graph X , the number of homomorphisms from X → G equals the number of homomorphisms from X → H . He used this result to deduce cancellation properties of the direct product of graphs. We develop a result analogous to Lovász’s theorem, but in the class of graphs without loops and with weak homomorphisms. We apply it prove a general cancellation property for the strong product of graphs.

Made available in DSpace on 2014-06-11T19:26:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2010-02-26Bitstream added on 2014-06-13T19:26:01Z : No. of bitstreams: 1 benedito_cwo_me_sjrp.pdf: 1004485 bytes, checksum: fd9cc4cec014a6fbfc619f640e7f98b5 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / Neste trabalho é feito um estudo sobre famílias de reticulados algébricos e reticulados ideais. Nosso principal objetivo é a construção de reticulados que são versões rotacioanadas de reticulados já conhecidos na literatura. Deste modo, apresentamos construções obtidas via polinômios, via perturbações do homomorfismo canônico e, também, construções ciclotômicas a partir fo reticulado Zn. / This work presents a study of algebraic and families of ideal lattices. Our main goal is the construction of lattices which are rotated versions of known lattices in the literature. In this way, we present constructions obtained via polynomials, via pertubations of the canonical homomorphism, and also cyclotomic construction from the lattice Zn.

No description available.

No abstract provided. / Thesis / Doctor of Philosophy (PhD) / Scope and contents: Two topics are studied in this thesis. The first topic is concerned with the relation between the categories of complexes over two algebras when there is a unitary algebra homomorphism from one to the other. The second topic deals with differential forms. A certain finiteness theorem for the module of integral differential forms is studied.

We introduce an extension of the lightweight Description Logic EL that allows us to de_ne concepts in an approximate way. For this purpose, we use a graded membership function, which for each individual and concept yields a number in the interval [0, 1] expressing the degree to which the individual belongs to the concept. Threshold concepts C~t for ~ then collect all the individuals that belong to C with degree ~ t. We generalize a well-known characterization of membership in EL concepts to construct a specific graded membership function deg, and investigate the complexity of reasoning in the Description Logic τEL(deg), which extends EL by threshold concepts defined using deg. We also compare the instance problem for threshold concepts of the form C>t in τEL(deg) with the relaxed instance queries of Ecke et al.

Reasoning for Description logics with concrete domains and w.r.t. general TBoxes easily becomes undecidable. For particular, restricted concrete domains decidablity can be regained. We introduce a novel way to integrate a concrete domain D into the well-known description logic ALC, we call the resulting logic ALCP(D). We then identify sufficient conditions on D that guarantee decidability of the satisfiability problem, even in the presence of general TBoxes. In particular, we show decidability of ALCP(D) for several domains over the integers, for which decidability was open. More generally, this result holds for all negation-closed concrete domains with the EHD-property, which stands for the existence of a homomorphism is definable. Such technique has recently been used to show decidability of CTL with local constraints over the integers.

Les problèmes de satisfaction de contraintes, qui consistent à attribuer des valeurs à des variables en respectant un ensemble de contraintes, constituent une large classe de problèmes naturels. Pour étudier la complexité de ces problèmes, il est commode de les voir comme des problèmes d'homomorphismes vers des structures relationnelles. Un axe de recherche actuel est la caractérisation des classes de complexité auxquelles appartient le problème d'homomorphisme, ceci dans la perspective de confirmer des conjectures reliant les propriétés algébriques des structures relationelles à la complexité du problème d'homomorphisme. Cette thèse propose dans un premier temps la caractérisation des digraphes pour lesquels le problème d'homomorphisme avec listes appartient à FO. On montre également que dans le cas du problèmes d'homomorphisme avec listes sur les digraphes télescopiques, les conjectures reliant algèbre et complexité sont confirmées. Dans un deuxième temps, on caractérise les graphes pour lesquels le problème d'homomorphisme avec listes est résoluble par cohérence d'arc. On introduit la notion de polymorphisme monochromatique et on propose un algorithme simple qui résoud le problème d'homomorphisme avec listes si le graphe cible admet un polymorphisme monochromatique TSI d'arité k pour tout k ≥ 2. / Constraint satisfaction problems, consisting in assigning values to variables while respecting a set of constraints, form a large class of natural problems. In order to study the complexity of these problems, it is convenient to see them as homomorphism problems on relational structures. One current research topic is to characterise complexity classes where the homomorphism problem belongs. The ultimate goal is to confirm conjectures that bind together algebraic properties of the relationnal structure and complexity of the homomorphism problem. At first, the thesis characterizes digraphs which generate FO list-homomorphism problems. It is shown that in the particular case of telescopic digraphs, conjectures binding together algebra and complexity are confirmed. Subsequently, we characterize graphs which generate arc-consistency solvable list-homomorphism problems. We introduce the notion of monochromatic polymorphism and we propose a simple algorithm which solves the list-homomorphism problem if the target graph admits a monochromatic TSI polymorphism of arity k for every k ≥ 2.

L'objectif de cette thèse est l'étude des approximations et des vitesses de convergence pour des fonctionnelles de grands graphes discrets vers leurs limites continues. Nous envisageons deux cas de graphes discrets: des arbres (i.e. des graphes connexes et sans cycles) et des graphes finis, simples et denses. Dans le premier cas, on considère des fonctionnelles additives sur deux modèles d'arbres aléatoires: le modèle de Catalan sur les arbres binaires (où un arbre est choisi avec probabilité uniforme sur l'ensemble des arbres binaires complets ayant un nombre de nœuds donné) et les arbres simplement générés (et plus particulièrement les arbres de Galton-Watson conditionnés par leur nombre de nœuds).Les résultats asymptotiques reposent sur les limites d'échelle d'arbres de Galton-Watson conditionnés. En effet, lorsque la loi de reproduction est critique et de variance finie (ce qui est le cas des arbres binaires de Catalan), les arbres de Galton-Watson conditionnés à avoir un grand nombre de nœuds convergent vers l'arbre brownien continu qui est un arbre réel continu qui peut être codé par l'excursion brownienne normalisée. Par ailleurs, les arbres binaires sous le modèle de Catalan peuvent être construits comme des sous arbres de l'arbre brownien continu. Ce plongement permet d'obtenir des convergences presque-sûres de fonctionnelles. Plus généralement, lorsque la loi de reproduction est critique et appartient au domaine d'attraction d'une loi stable, les arbres de Galton-Watson conditionnés à avoir un grand nombre de nœuds convergent vers des arbres de Lévy stables, ce qui permet d'obtenir le comportement asymptotique des fonctionnelles additives pour certains arbres simplement générés. Dans le second cas, on s'intéresse à la convergence de la fonction de répartition empirique des degrés ainsi qu'aux densités d'homomorphismes de suites de graphes finis, simples et denses. Une suite de graphes finis, simples, denses converge si la suite réelle des densités d'homomorphismes associées converge pour tout graphe fini simple. La limite d'une telle suite de graphes peut être décrite par une fonction symétrique mesurable appelée graphon. Etant donné un graphon, on peut construire par échantillonnage, une suite de graphes qui converge vers ce graphon. Nous avons étudié le comportement asymptotique de la fonction de répartition empirique des degrés et de mesures aléatoires construites à partir des densités d'homomorphismes associées à cette suite particulière de graphes denses / The aim of this thesis is the study of approximations and rates of convergence for functionals of large dicsrete graphs towards their limits. We contemplate two cases of discrete graphs: trees (i.e. connected graphs without cycles) and dense simple finite graphs. In the first case, we consider additive functionals for two models of random trees: the Catalan model for binary trees (where a tree is chosen uniformly at random from the set of full binary trees with a given number of nodes) and the simply generated trees (and more particulary the Galton-Watson trees conditioned by their number of nodes).Asymptotic results are based on scaling limits of conditioned Galton-Watson trees. Indeed, when the offspring distribution is critical and with finite variance (that is the case of Catalan binary trees), the Galton-Watson trees conditioned to have a large number of nodes converge towards the Brownian continuum tree which is a real tree coded which can be coded by the normalized Brownian excursion. Furthermore, binary trees under the Catalan model can be built as sub-trees of the Brownian continuum tree. This embedding makes it possible to obtain almost sure convergences of functionals. More generally, when the offspring distribution is critical and belongs to the domain of attraction of a stable distribution, the Galton-Watson trees conditioned to have a large number of nodes converge to stable Levy trees giving the asymptotic behaviour of additive functionals for some simply generated trees. In the second case, we are interested in the convergence of the empirical cumulative distribution of degrees and the homomorphism densities of sequences of dense simple finite graphs. A sequence of dense simple finite graphs converges if the real sequence of associated homomorphism densities converges for all simple finite graph. The limit of such a sequence of dense graphs can be described as a symmetric measurable function called graphon.Given a graphon, we can construct by sampling, a sequence of graphs which converges towards this graphon. We have studied the asymptotic behaviour of the empirical cumulative distribution of degrees and random measures built from homomorphism densities associated to this special sequence of dense graphs