<p>Denote by $k_t(G)$ the number of cliques of order $t$ in a graph $G$ having $n$ vertices. Let $k_t(n) = \min\{k_t(G)+k_t(\overline{G}) \}$ where $\overline{G}$ denotes the complement of $G$. Let $c_t(n) = {k_t(n)}/{\tbinom{n}{t}}$ and $c_t$ be the limit of $c_t(n)$ for $n$ going to infinity. A 1962 conjecture of Erd\H{o}s stating that $c_t = 2^{1-\tbinom{t}{2}}$ was disproved by Thomason in 1989 for all $t\geq 4$. Tighter counterexamples have been constructed by Jagger, {\v S}{\v t}ov{\' \i}{\v c}ek and Thomason in 1996, by Thomason for $t\leq 6$ in 1997, and by Franek for $t=6$ in 2002. Further tightenings $t=6,7$ and $8$ was recently obtained by Deza, Franek, and Liu.</p> <p>We investigate the computational framework used by Deza, Franek, and Liu. In particular, we present the benefits and limitations of different parallel computer memory architectures and parallel programming models. We propose a functional decomposition approach which is implemented in C++ with POSIX thread (Pthread) libraries for multi-threading. Computational benchmarking on the parallelized framework and a performance analysis including a comparison with the original computational framework are presented.</p> / Master of Science (MSc)

Dans cette thèse, nous étudions quelques problèmes géométriques liés aux domaines bornés symétriques réels. Ces espaces sont des espaces D=G/K riemanniens symétriques non compacts, obtenus à partir de domaines bornés hermitiens symétriques. Lorsque le domaine D=G/K est de type Cr ou Dr, G opère transitivement sur chaque composante connexe de l'ensemble [sigma] des tripotents maximaux du système triple de Jordan réel positif T0D. Dans le cas complexe, cet ensemble est connexe et est appelé frontière de Shilov du domaine. Dans le cas réel, [sigma] n'est en général pas connexe. Nous fixons donc une composante connexe S de [sigma]. Alors l'action de G sur S x S possède un nombre fini d'orbites et nous donnons un système explicite de représentants. Si le domaine est de type Cs ou D2s, alors parmi ces orbites, il y a celle des couples d'éléments transverses. Sous ces hypothèses, nous pouvons alors définir l'ensemble des triplets d'éléments de S transverses deux à deux, sur lequel G opère. Là encore, nous déterminons les orbites de cette action. Enfin, nous nous intéressons à un problème analytique concernant un système de Hua. Nous montrons que pour toute fonction continue [phi] sur S, la transformée de poisson f=P[sigma phi]:=[intégrale]SP(.,u)[sigma phi](u)du est solution du système de Hua Hf(x)=(2n-/r)2[sigma]([sigma]-1)f(x)Id, où P(.,.) est le noyau de Poisson sur D x S et où n- désigne la dimension de V-. / In this thesis, we are interested in geometric problems related with \emph{real bounded symmetric domains}. These spaces are Riemannian symmetric spaces $\mathcal{D}=G/K$ of noncompact type, constructed from \emph{hermitian bounded symmetric domains}. When $\mathcal{D}=G/K$ is of type $C_r$ or $D_r$, we prove that $G$ acts transitively on each connected component of the set $\Sigma$ of \emph{maximal tripotents} in the \emph{compact Jordan triple system} $T_0\mathcal{D}$. In the hermitian case, this set is connected and is called \emph{the Shilov boundary}. In the real case, $\Sigma$ is not necessarily connected, thus we choose a connected component $\mathcal{S}$ of $\Sigma$. Then the action of $G$ in $\mathcal{S}\times\mathcal{S}$ as a finite number of orbits for wich we give representative elements. If $\mathcal{D}$ is of type $C_s$ or $D_{2s}$, then the set of couples of transversal elements of $\mathcal{S}$ is a $G$-orbit in $\mathcal{S}\times\mathcal{S}$. Under these assumptions, $G$ acts on the set of transversal triples in $\mathcal{S}\times\mathcal{S}\times\mathcal{S}$ and we determine the orbits for this action. Finally, we are interested in Hua differential systems. We prove that for any continuous function $\varphi$ on $\mathcal{S}$, the Poisson transform $f=\mathcal{P}_\sigma\varphi:=\int_\mathcal{S}\mathcal{P}(\cdot,u)^\sigma\varphi(u)du$ is a solution of the Hua system $\mathcal{H}f(x)=(\frac{2n^-}{r})^2\sigma(\sigma-1)f(x)\textnormal{Id}$, where $\mathcal{P}(\cdot,\cdot)$ is the Poisson kernel on $\mathcal{D}\times\mathcal{S}$ and $n^-$ is the dimension of $V^-$.

Cette thèse se place dans le cadre du vaste domaine s'intitulant géométrie non commutative, domaine dont l'étude est motivée par l'opinion courante des mathématiciens et physiciens selon laquelle les méthodes de la géométrie non commutative peuvent être utiles pour décrire certains processus dynamiques à l'échelle de Planck. Aussi l'objectif principal de cette thèse est de généraliser quelques modèles dynamiques définis sur l'espace de Minkowski sur son q-analogue. Des tentatives d'introduire des modèles dynamiques qui seraient covariants par rapport à l'action de groupes quantiques ont été entrepris juste après la création de la théorie sur les groupes quantiques par Drinfeld. Les modèles les plus intéressants sont ceux qui sont liés au q-analogue de l'espace de Minkowski. C'est P. Kulish qui définit cette algèbre comme étant un cas particulier d'une algèbre appelée modified Reflection Equation Algebra (mREA) elle-même liée à un opérateur appelé symétrie de Hecke. Nous définissons donc certains modèles dynamiques qui sont des déformations de modèles classiques, l'espace des phases de nos modèles déformés n'est autre alors que notre espace de q-Minkowski. Nous recherchons par la suite des intégrales de mouvement de ces dynamiques, ce qui nous amène à définir des analogues de l'énergie et du vecteur de Runge-Lenz. Nous généralisons pour terminer les équations aux dérivées partielles de la théorie des champs et en particulier l'opérateur de Maxwell.

Un théorème dû à Zak montre un lien pour le moins mystérieux entre des objets algébriques, les algèbres de Jordan, et des objets apparaissant naturellement dans le cadre de la géométrie projective complexe, les variétés de Scorza. La première partie de cette thèse essaie d'expliquer ce lien. Tout d'abord, la variété des éléments de rang de Jordan 1 dans une algèbre de Jordan est définie puis étudiée en détail: c'est une variété de Scorza et elle est l'image d'une généralisation de l'application de Veronese de degré deux. Ensuite, je donne des variantes de la preuve du théorème de Zak qui expliquent directement le lien avec les algèbres de Jordan, mais aussi l'homogénéité des variétés de Scorza et le rapport avec les espaces préhomogènes symétriques. Une technique omniprésente pour cette étude consiste à définir une algèbre par des constructions de géométrie projective: celle-ci permet de définir l'algèbre de Jordan dans laquelle vivent toutes les variétés de Scorza, mais s'applique plus généralement à un grand nombre d'autres algèbres. Par exemple, je donne une définition géométrique des algèbres de matrices, des algèbres de Lie et des algèbres de composition. De nombreux résultats de nature algébrique peuvent ainsi être retrouvés par des raisonnements géométriques particulièrement simples. J'étudie ainsi le groupe d'automorphismes d'une algèbre de Jordan et prouve une description des groupes spinoriels d'ordre pair. L'autre partie de cette thèse montre des théorèmes d'annulation pour les fibrés vectoriels amples. Je propose une généralisation d'un théorème dû à Laytimi et Nahm pour les puissances de Schur d'un fibré vectoriel correspondant à un produit tensoriel de crochets. Je démontre aussi des résultats pour les fibrés vectoriels de petit rang: ceux-ci impliquent une petite partie de la conjecture de Fulton et Lazarsfeld concernant la connexité de lieux de dégénérescence d'un morphisme de fibrés vectoriels. Par ailleurs, j'obtiens aussi des résultats plus forts dans le cas où le fibré est muni d'une forme quadratique non dégénérée ou symplectique à valeurs dans un fibré en droites. Ces résultats sont conséquence de théorèmes sur la cohomologie de Dolbeault des fibrés en droites homogènes sur les grassmanniennes, isotropes ou non. Je donne plusieurs résultats nouveaux concernant cette cohomologie.

Les motivations initiales de ce travail proviennent de l'étalonnage de caméras en vision artificielle. Nous nous sommes surtout intéressés aux manières d'exploiter des mesures dans les images (détection d'objets) et des considérations géométriques formelles. Nous avons élargi nos recherches à la problématique suivante :"l'interaction entre symbolique et numérique ". Ce travail se divise en trois parties. La première partie traite de la résolution d'équations polynomiales avec des coefficients approchés. Nous étudions des méthodes matricielles qui transforment la résolution en la recherche des valeurs et des vecteurs propres d'une matrice. Ces transformations et et les calculs de valeurs et vecteurs propres sont continues par rapport aux coefficients et permettent donc de résoudre des équations à coefficients approchés. La deuxième partie présente un cadre algébrique permettant d'exprimer simplement des contraintes géométriques. Ce formalisme nous a permis de modéliser de manière fine l'étalonnage d'une ou plusieurs caméras avec l'aide d'un plan. L'étalonnage ne peut être effectué pratiquement qu'avec des résolutions numériques de systèmes linéaires. La troisième partie est consacrée à l'étude et surtout à l'utilisation des outils de démonstration automatique en géométrie pour la construction de modèles 3D articulés. Par des optimisations numériques, nous déterminons les paramètres des modèles articulés qui permettent aux images de ces modèles de coïncider avec les données extraites des photographies

Cette thèse est divisée en deux parties. La première partie concerne la commutation rapide des informations dans les réseaux ATM. Dans le chapitre 2, nous décrivons la technologie ATM. Dans le chapitre 3, nous modélisons le problème du positionnement des chemins virtuels et définissons les deux paramètres étudiés, charge et nombre de sauts d'un VPL. Nous discutons l'orientation du modèle, la complexité du problème, puis proposons une synthèse des résultats de la littérature. Les démonstrations des résultats originaux se trouvent dans les chapitres 4 et 5. La seconde partie concerne l'échange total dans les réseaux d'interconnexion entre processeurs. Dans le chapitre 6, nous introduisons les notions de théorie des groupes nécessaires ainsi que la motivation du problème. L'objet du chapitre 7 est de caractériser les graphes de Cayley admettant un certain automorphisme de graphe (appelé rotation complète) permettant de construire d'une manière simple un protocole d'échange total optimal. Nous mettons en évidence des conditions nécessaires sur le groupe pour que le graphe admette une rotation complète. Nous donnons la liste exhaustive des graphes de Cayley admettant une rotation complète parmi les graphes de Cayley engendrés par des transpositions.

Every knapsack problem may be relaxed to a cyclic group problem. In 1969, Gomory found the subadditive characterization of facets of the master cyclic group problem. We simplify the subadditive relations by the substitution of complementarities and discover a minimal representation of the subadditive polytope for the master cyclic group problem. By using the minimal representation, we characterize the vertices of cardinality length 3 and implement the shooting experiment from the natural interior point. The shooting from the natural interior point is a shooting from the inside of the plus level set of the subadditive polytope. It induces the shooting for the knapsack problem. From the shooting experiment for the knapsack problem we conclude that the most hit facet is the knapsack mixed integer cut which is the 2-fold lifting of a mixed integer cut. We develop a cutting plane algorithm augmenting cutting planes generated by shooting, and implement it on Wong-Coppersmith digraphs observing that only small number of cutting planes are enough to produce the optimal solution. We discuss a relaxation of shooting as a clue to quick shooting. A max flow model on covering space is shown to be equivalent to the dual of shooting linear programming problem.

La robotique chirurgicale vise à rendre les gestes du chirurgien plus précis et moins invasifs. La complexité d'une salle d'opération conduit à rechercher des dispositifs robotiques aussi compacts que possible et pouvant être facilement stérilisés. Une conception robotique basée sur l'emploi de mécanismes compliants à structures monolithiques et d'actionneurs piézoélectriques est particulièrement intéressante sur ce point. Des travaux précédents conduits au laboratoire ont permis de proposer un dispositif robotique pour le pontage coronarien qui facilite la réalisation des gestes minimalement invasifs sur cœur battant. Ce dispositif répond au besoin médical mais manque aujourd'hui de la compacité souhaitée pour une intégration optimale. À partir du cas d'application où nous cherchons à réduire la taille du dispositif de compensation, nous nous intéressons, dans cette thèse, aux problématiques de conception de mécanismes compliants à fortes contraintes d'intégration. Nous étudions d'abord la possibilité d'intégrer le dispositif de compensation directement dans la tige du stabilisateur cardiaque passif. Puis, nous étudions la possibilité de réduire la taille du dispositif de compensation en amont, en explorant les possibilités de réaliser des mécanismes dans un plan. Nous avons notamment proposé une méthode originale de conception de mécanismes compliants plans à partir de l'analyse des singularités de mécanismes à architectures parallèles en configuration plane. Afin d'optimiser les différents mécanismes très contraints par les volumes imposés, une méthode originale d'optimisation à base d'un algorithme de colonie de fourmis est employée.

La robotique chirurgicale vise à rendre les gestes du chirurgien plus précis et moins invasifs. La complexité d’une salle d’opération conduit à rechercher des dispositifs robotiques aussi compacts que possible et pouvant être facilement stérilisés. Une conception robotique basée sur l’emploi de mécanismes compliants à structures monolithiques et d’actionneurs piézoélectriques est particulièrement intéressante sur ce point. Des travaux précédents conduits au laboratoire ont permis de proposer un dispositif robotique pour le pontage coronarien qui facilite la réalisation des gestes minimalement invasifs sur cœur battant. Ce dispositif répond au besoin médical mais manque aujourd’hui de la compacité souhaitée pour une intégration optimale. À partir du cas d’application où nous cherchons à réduire la taille du dispositif de compensation, nous nous intéressons, dans cette thèse, aux problématiques de conception de mécanismes compliants à fortes contraintes d’intégration. Nous étudions d’abord la possibilité d’intégrer le dispositif de compensation directement dans la tige du stabilisateur cardiaque passif. Puis, nous étudions la possibilité de réduire la taille du dispositif de compensation en amont, en explorant les possibilités de réaliser des mécanismes dans un plan. Nous avons notamment proposé une méthode originale de conception de mécanismes compliants plans à partir de l‘analyse des singularités de mécanismes à architectures parallèles en configuration plane. Afin d’optimiser les différents mécanismes très contraints par les volumes imposés, une méthode originale d’optimisation à base d’un algorithme de colonie de fourmis est employée. / Surgical robotics helps to increase the surgeon’s accuracy and limits the invasiveness of the surgery. The complexity of an operation room implies to design surgical devices that are as compact as possible and that can be easily sterilized. One interesting design approach is to combine compliant mechanisms, which have a monolithic structure, and piezoelectric actuators. Based on this approach, a robotic device for minimally invasive coronary artery bypass grafting has been proposed previously in our laboratory. This device successfully helps to increase the stabilization of the heart surface during the surgery but its compactness needs to be increased for an optimal integration in the operation room. Based on the need to reduce the compensation mechanism of this device, the problem of the design of compliant mechanisms with strong integration constrains is studied in this PhD thesis. First, the possibility to integrate the compensation mechanism directly in the shaft is considered. Then, the possibility to reduce the compensation mechanism at the end of the shaft by considering an assembly of planar manufactured structures is considered. Among the contributions, we propose an original design method based on the analysis of singularities of parallel manipulators in planar configuration. We also propose an original optimization method based on ant colony optimization in order to optimize the compliant architectures proposed in this work.

In this thesis we address the analytic and numerical aspects of isospectral flows. Such flows occur in mathematical physics and numerical linear algebra. Their main structural feature is to retain the eigenvalues in the solution space. We explore the solution of Isospectral flows and their stochastic counterpart using explicit generalisation of Magnus expansion. \par In the first part of the thesis we expand the solution of Bloch--Iserles equations, the matrix ordinary differential system of the form $ X'=[N,X^{2}],\ \ t\geq0, \ \ X(0)=X_0\in \textrm{Sym}(n),\ N\in \mathfrak{so}(n), $ where $\textrm{Sym}(n)$ denotes the space of real $n\times n$ symmetric matrices and $\mathfrak{so}(n)$ denotes the Lie algebra of real $n\times n$ skew-symmetric matrices. This system is endowed with Poisson structure and is integrable. Various important properties of the flow are discussed. The flow is solved using explicit Magnus expansion and the terms of expansion are represented as binary rooted trees deducing an explicit formalism to construct the trees recursively. Unlike classical numerical methods, e.g.\ Runge--Kutta and multistep methods, Magnus expansion respects the isospectrality of the system, and the shorthand of binary rooted trees reduces the computational cost of the exponentially growing terms. The desired structure of the solution (also with large time steps) has been displayed. \par Having seen the promising results in the first part of the thesis, the technique has been extended to the generalised double bracket flow $ X^{'}=[[N,X]+M,X], \ \ t\geq0, \ \ X(0)=X_0\in \textrm{Sym}(n),$ where $N\in \textrm{diag}(n)$ and $M\in \mathfrak{so}(n)$, which is also a form of an Isospectral flow. In the second part of the thesis we define the generalised double bracket flow and discuss its dynamics. It is noted that $N=0$ reduces it to an integrable flow, while for $M=0$ it results in a gradient flow. We analyse the flow for various non-zero values of $N$ and $M$ by assigning different weights and observe Hopf bifurcation in the system. The discretisation is done using Magnus series and the expansion terms have been portrayed using binary rooted trees. Although this matrix system appears more complex and leads to the tri-colour leaves; it has been possible to formulate the explicit recursive rule. The desired structure of the solution is obtained that leaves the eigenvalues invariant in the solution space.