In this thesis we study the following dimensional parameters : boxicity, cubicity, threshold dimension and poset dimension. While the first three parameters are defined on graphs, poset dimension is defined on partially ordered sets (or posets). We only consider finite graphs and posets. In addition, we assume that the graphs are simple and undirected. Boxicity and Cubicity: A k-box (k-cube) is a Cartesian product of closed intervals(unit-intervals) [a1,b1]x…x [ak,bk]. The boxicity (cubicity) of a graph G,box (G) (cub(G)) is the minimum integer k such that every vertex in G is mapped to a k-box(k-cube) in the k-dimensional Euclidean space and two boxes(cubes) intersect if and only if their corresponding vertices are adjacent in G. Boxicity and cubicity can be considered as extensions of the concept of interval graphs and unit-interval graphs respectively. Threshold Dimension: A graph G is a threshold graph if there is a real number p and a weight function w: V→ R such that for any two vertices u,,v ε V(G),{ u, v }is an edge if and only if w(u)+w(v) ≥ p. The threshold dimension of a graph G is the minimum integer k such that there exist k threshold graphs Gi, i =1,2,...,k which satisfy E(G)= E(G1)U E(G2)U….UE(Gk). Poset Dimension: Let P = (S, P)be a poset where S is a finite non-empty set and P is a reflexive, anti-symmetric and transitive binary relation on S. P is a total order if every pair of elements in S is comparable in P. The dimension of P , denoted by dim(P )is the minimum integer k such that there exist k total orders on S, L1,...,Lk and for two distinct elements x,y ε S: x < y in P if and only if x < y in each Li,i ε ,{1. 2,...,k } All the four dimensional parameters that we have considered are very hard to compute. It is NP-complete to even determine if the boxicity of a graph is at most 2, if its cubicity is at most 3, if its threshold dimension is at most 3 and if the dimension of a poset is at most 3. Also it is hard to design an approximation algorithm within √n factor for computing the dimension of a poset. OurResults We state some of our main results: 1. Lower bounds for boxicity: We have developed two general methods based on certain vertex isoperimetric properties of graphs for deriving lower bounds. Application of these methods has led to some significant results. We mention a few of them here: ( a) Almost all graphs have boxicity Ω(n). (b) For a fixed k, boxicity of random k-regular graphs is Ω(k/log k). 2. Consider a poset P = (S,P) and let GP be its underlying comparability graph. We show that for any poset P, box(GP)/(χ(GP) - 1) ≤ dim(P) ≤ 2box (GP), where χ(GP) is the chromatic number of GP and χ(GP) = 1. Some important consequences of this result are: (a) It allows us to derive hitherto unknown upper bounds for poset dimension such as dim(P) ≤ 2tree-width (GP) + 4. (b) The boxicity of any graph with maximum degree Δ is O (Δlog2 Δ) which is an improvement over the best known upper bound of Δ2 +2. (c) There exist graphs with boxicity Ω(ΔlogΔ). This disproves a conjecture that the boxicity of a graph is O(Δ). (d)There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices within a factor of O(n0.5−ε)for any ε > 0, unless NP = ZPP. 3.We show that every poset can be associated with a split graph such that the threshold dimension of the complement of the split graph is equal to the dimension of the poset. As a consequence we show that there exists no polynomial-time algorithm to approximate the threshold dimension of a split graph on n vertices with a factor of O(n0.5−ε)for any ε > 0, unless NP= ZPP. 4.We have given an upper bound for the cubicity of interval graphs. Claw number of a graph G, ψ(G) is the largest positive integer m such that K1,m is an induced subgraph of G. If G is an interval graph, we show that [log2 ψ(G)] ≤ cub(G) ≤ min([log2 α ], [log2 ψ(G)] +2), where α is the independence number of G. 5.We have improved upper bounds for the dimension of incidence posets and interval orders which are among the well-studied classes of posets.

在這篇論文中，我們探討了最近在有界雙容忍序中的一些成果。同時， 我們提供一些標準的簡短證明，包含有界雙容忍序的等價種類， 單位有界雙容忍序與適當有界雙容忍序的關係。 我們的目標是希望能在有界雙容忍序的現今地位上，去提供新的洞悉，並給未來學習者一個方向。 / In the paper、we study recent work on some classes of bounded bitolerance orders. Also, we provide the short proofs of some of classical results on bounded bitolerance orders, including the equivalent classes of bounded bitolerance orders、the relation of unit and proper bitolerance orders. Our goal is to provide the fresh insights into the current status of research in the area while suggesting directions for the future.

On étudie une sous-classe des suites b-multiplicatives rarefiées avec un pas de raréfaction p premier, et on trouve une structure asymptotique avec un exposant alphain]0,1[ et une fonction de raréfaction continue périodique. Cette structure vaut pour les suites qui contiennent des nombres complexes du disque unité (section 1.1), et aussi pour des systèmes de numération avec b chiffres successifs positifs et négatifs (section 1.2). Ce formalisme est analogue à celui décrit (pour le cas particuler de la suite de Thue-Morse) par Gelfond; Dekking; Goldstein, Kelly, Speer; Grabner; Drmota, Skalba et autres. Dans la deuxième partie, largement indépendante, on étudie la raréfaction dans les suites composées de -1,0 et +1. On se restreint davantage au cas où b engendre le groupe multiplicatif modulo p. Cette hypothèse est conjecturée (Artin) d'être vraie pour une infinité de nombres premiers. Les constantes qui apparaissent s'expriment alors comme polynômes symétriques des P(zeta^j) où P est un polynôme à coefficients entiers, zeta est une racine primitive p-ième de l'unité, $j$ parcourt les entiers de 1 à p-1 (ce lien est explicité dans la section 1.3). On définit une méthode pour étudier les valeurs de ces polynômes symétriques, basée sur la combinatoire, notamment sur le problème de comptage des solutions des congruences et des systèmes linéaires modulo p avec deux conditions supplémentaires: les résidus modulo p utilisés doivent être non nuls et différents deux à deux. L'importance est donnée à la différence entre les nombres de soluions de deux congruences qui ne diffèrent que du terme sans variable. Le cas des congruences de la forme $x_1+x_2+...+x_n=i mod p$ équivaut à un résultat connu. Le mémoire (section 2.2) lui donne une nouvelle preuve qui en fait une application originale de la formule d'inversion de Möbius dans le p.o.set des partitions d'un ensemble fini. Si au moins deux coefficients distincts sont présents, on peut classer les réponses associées à toutes les congruences possibles qui ont un ensemble fixe de coefficients (de taille d), dans un tableau qu'on va appeler un "simplexe de Pascal fini". Ce tableau est une fonction delta:N^d->Z restreinte aux points de somme des coordonnées inférieure à p (un simplexe), avec deux propriétés: l'équation récursive de Pascal y est vérifiée partout sauf les points où la somme des coefficients est multiple de p (qui seront appelés les "sources" et forment un sous-réseau de l'ensemble des points entiers), et les valeurs en-dehors du simplexe induites par l'équation sont nulles (c'est démontré, en réutilisant la méthode précédente, dans la section 2.3 et en partie 2.4). On décrit un algorithme (section 2.4) qui consiste en applications successives de l'équation dans un ordre précis, qui permet de trouver l'unique fonction delta qui vérifie les deux conditions. On applique ces résultats aux suites b-multiplicatives (dans la section 2.5). On montre aussi que le nombre de sources ne dépend que de la dimension du simplexe d et de la longueur de son côté p. On formule la conjecture (partie 2.6) qu'il serait le plus petit possible parmi les tableaux de forme d'un simplexe de la dimention fixe et taille fixe qui vérifient les mêmes conditions. On montre un premier résultat sur les systèmes de deux congruences linéaires (section 2.5.4), et on montre (section 1.4) un lien avec une méthode de Drmota et Skalba pour prouver l'absence de phénomène de Newman (dans un sens précis), décrit initialement pour la suite de Thue-Morse et tout p tel que b engendre le groupe multiplicatif modulo p, et généralisé (section 1.4) à la suite (-1)^{nombre de chiffres 2 dans l'écriture en base 3 de n} appelée "++-". Cette problématique est riche en problèmes d'algorithmique et de programmation. Différentes sections du mémoire sont illustrées dans l'Annexe. La plupart de ces figures sont inédites. / The primary object of study is a subclass of b-multiplicative sequences, p-rarefied which means that the subsequence of terms of index multiple of a prime number p is taken. The sums of their initial terms have an asymptotic structure described by an exponent alphain]0,1[ and a contnous periodic "rarefaction function". This structure is valid for sequences with complex values in the unit disc, in both cases of the usual numerating system (section 1.1) and one with b successive digits among which there are positive and negative (section 1.2). This formalism is analogous to the formalism for the Thue-Morse sequence in texts by Gelfond; Dekking; Goldstein, Kelly, Speer; Grabner; Drmota, Skalba and others. The second, largely independent, part concerns rarefaction in sequences with terms in -1,0 or 1. Most results concern the case where b is a generator of the multiplicative group modulo p. This condition has been conjectured to be valid for infinity of primes, by Artin. The constants which are important, can be written as symmetric polynomials of P(zeta^j) where zeta is a primitive p-th root of unity, P is a polynomial with integer coefficients and j runs through the numbers from 1 to p-1 (section 1.3). The text describes a combinatorics-based method to study the values of these symmetric polynomials, where the combinatorial problem is as follows. Count the solutions of a linear congruence or a system modulo p, which satisfy a condition: the values of variables must be different from each other and from zero. Importance is attached to the difference between the numbers of solutions of two congruences that differ only in the free term. For the congruences of the form $x_1+x_2+...+x_n=i mod p$ this problem reduces to a well-known result. The text (section 2.2) gives an original proof of it, using the Möbius inversion formula in the p.o.set of partitions of a finite set. If at least two distinct coefficients are present, we can fix a set of coefficients (of size d) and put the answers corresponding to all possible linear congruences into an array that will be called "finite Pascal's triangle". It is a function delta:N^d->Z restricted to inputs with the sum of coordinates smaler than p (a simplex), and it has two properties. A recursive equation similar to the equation of Pascal holds everywhere except the points where the sum of coefficients is a multiple of p (a sublattice of Z^d the points of which are called "sources"); the values induced by this equation beyond the simplex are zeroes (section 2.3 and part of 2.4). An algorithm that finds the unique function delta satisfying these condiditions is described (section 2.4). It consists in successive applications of the equation in a precise order. These results are then applied to the b-multiplicative sequences (section 2.5). We also prove that the number of sources depends only on the dimention d and the size p of the simplex. We conjecture (section 2.6) that this number is the smallest possible for all numerical arrays of the same dimention and size that satisfy the same conditions. A first result about the systems of two linear congruences is proved (section 2.5.4). It is shown how these systems are related to a method by Drmota and Skalba of proving the absence of Newman's phenomenon (in a precise sence) initially described for the Thue-Morse sequence and for a prime p such that 2 is a generator of the multiplicative group modulo p, then extended to the sequence (-1)^{number of digits 2 in the ternary extension of n} called "++-". These questions generate many algorithmic and programming problems. Several sections link to illustration situated in the Annexe. Most of these figures are published for the first time.

No description available.

Quasi-hereditary algebras are an important class of algebras with many appli-cations in representation theory, most notably the representation theory of semi-simple complex Lie-algebras. Such algebras sometimes admit an exact Borel sub-algebra, that is a subalgebra satisfying similar formal properties to the Borel sub-algebras from Lie theory. This thesis is divided into two parts. In the first part we classify quasi-hereditary algebras with two simple modules over perfect fields up to Morita equivalence, generalizing a similar result by Membrillo-Hernandez for thealgebraically closed case. In the second part, we take a poset X, a certain set M of constants, and a finite set ρ of paths in the Hasse-diagram of X and construct analgebra A(X, M, ρ) that generalizes the twisted double incidence algebras originally introduced by Deng and Xi. We provide necessary and sufficient conditions for this algebra to be quasi-hereditary when X is a tree, and we show that A(X, M, ρ) admits an exact Borel subalgebra when these conditions are satisfied. Following this, we compute the Ext-algebra of the standard modules of A(X, M, ρ).

The thesis covers methods for image segmentation. Fuzzy segmentation is based on the thresholding method. This is generalized to accept multiple criteria. The whole process is mathematically based on the free algebra theory. Free distributive lattice is created from poset of elements based on image properties and the lattice members are represented by terms used by the threshoding. Possible segmentation results compose the equivalence classes distribution. The thesis also contains description of resulting algorithms and methods for their optimization. Also the method of area subtracting is introduced.