Keywords: théorie des graphes, nombre d'indépendance, nombre chromatique, SDP, codes projectifs, hiérarchies graph theory, stable number, chromatic number, SDP, projective codes, hierarchies. vi

Une nouvelle borne supérieure sur le cardinal des codes de sous-espaces d'un espace vectoriel fini est établie grâce à la méthode de la programmation semidéfinie positive. Ces codes sont d'intérêt dans le cadre du codage de réseau (network coding). Ensuite, par la même méthode, l'on démontre une borne sur le cardinal des ensembles qui évitent une distance donnée dans l'espace de Johnson et qui est obtenue par une variante d'un programme de Schrijver. Les résultats numeriques permettent d'améliorer les bornes existantes sur le nombre chromatique mesurable de l'espace Euclidien. Une hiérarchie de programmes semidéfinis positifs est construite à partir de certaines matrices issues des complexes simpliciaux. Ces programmes permettent d'obtenir une borne supérieure sur le nombre d'indépendance d'un graphe. Aussi, cette hiérarchie partage certaines propriétés importantes avec d'autres hiérarchies classiques. A titre d'exemple, le problème de déterminer le nombre d'indépendance des graphes de Paley est analysé.

Beaucoup de personnes ont contribué à la réalisation de cette thèse. En essayant de n'en oublier aucune, je remonte le long des souvenirs de ces années.

Tout commença le jour où je rencontrai celle qui allait devenir, sous peu, ma directrice de thèse. Je venais de débarquer à l'université de Bordeaux afin d'entamer ma deuxième année de Master dans le cadre du projet ALGANT. Aussi attiré qu'effrayé par le titre du cours "Empilement de sphères, symétries et optimisation" que Christine allait donner cette année là, je lui demandai donc de plus amples informations. Nous nous assîmes face à une feuille blanche et, de façon gentille et directe, Christine m'expliqua en quelques lignes de crayon les liens entre sphères, réseaux et codes, me faisant ainsi entrevoir un monde de mathématiques qui m'était resté inconnu jusquelà. Un an et un mémoire de M2 plus tard, nous commençâmes cette aventure qui se termine aujourd'hui. J'ai eu de la chance d'être dirigé dans mes recherches par une personne aussi disponible et patiente, toujours prête à m'encourager, à trouver de nouvelles idées quand je n'en avais pas, à mettre de la rigueur dans mes intuitions farfelues.

Ensuite, je tiens à exprimer ma reconnaissance à Dion Gijswijt, Didier Henrion, Arnaud Pêcher, Jean-Pierre Tillich et Gilles Zémor pour avoir accepté de former le jury de cette soutenance. Je remercie également Didier Henrion et Eiichi Bannai d'avoir accepté d'être les rapporteurs de cette thèse.

Pendant ces années j'ai eu la chance de voyager et de rencontrer des chercheurs experts qui se trouvent également être des personnes très sympathiques et disponibles, dont je garde beaucoup de bons souvenirs. Il s'agit principalement de Frank Vallentin, Monique Laurent, Cordian Riener, Elisa Gorla et Joachim Rosenthal. Ici à Bordeaux j'ai eu le plaisir de travailler avec Alain Thiery, ce qui fut particulièrement enrichissant.

Comment pourrais-je ne pas penser aussi aux amis avec qui j'ai partagé le bureau 153... Damiano, qui était toujours là le matin quand j'arrivais et qui restait après moi le soir, infatigable, toujours prêt à répondre à mes questions telles que : « Damiano, excuse-moi, quelle est la commande pour copier un fichier avec le terminal ? » Johana, rayonnante de chaleur et pourtant toujours frileuse, qui m'a fait découvrir la Colombie et progresser en espagnol. Rohit et Siddarth, qui m'ont côtoyé ce dernier été, pendant la rédaction de cette thèse.

iii Parmi tous les doctorants et étudiants de l'IMB, qu'une place soit faite à mes compagnons de route, mes chers camarades italiens. Durant ces années, Nicola, Giovanni et Andrea ont été une présence constante et d'une aide précieuse. Nous avons parcouru le même chemin, duquel je me détournais si souvent et si volontiers, mais sans jamais les perdre de vue.

Mes pensées s'envolent aussi vers mes autres collègues et amis et particulièrement vers Pierre, Nicolas, Soline, Stephanie, Sophie, Nastaran. Qu'ils le sachent ou non, ils ont tous été très importants pour moi.

Il faut aussi remarquer que l'IMB ne serait pas ce qu'il est sans le support de tous les secrétaires, informaticiens et bibliothécaires. Souvent, sans en avoir l'intention, je m'employais à rendre leur travail plus difficile en leur confiant la tâche de remédier à mes manques d'attention. En revanche, cela m'a permis de vérifier qu'ils forment une équipe bien qualifiée et compétente.

Une moindre mais importante partie de mon doctorat m'a vu côtoyer les enseignants et le personnel administratif du département d'informatique de l'IUT Bordeaux 1, en particulier Brigitte Carles, Pierre Moreau et Michel Hickel. Qu'ils soient ici remerciés d'avoir accueilli le néophyte que j'étais en m'accordant leur confiance et cela dans une ambiance respectueuse et amicale.

Je pense également à tous mes amis de Bordeaux et d'Italie, trop nombreux pour être listés ici, dont la plupart seraient par ailleurs gênés de voir leur nom apparaître dans une thèse de maths.

Le remerciement le plus important va sans doute à ma famille, sans laquelle je n'en serais jamais arrivé là. Mon frère, que chaque été je me réjouissais de rejoindre pour pouvoir mesurer l'ampleur de notre intersection. Ma mère, qui me guide avec son infinie sagesse silencieuse et dont je porte l'amour où que j'aille. Mon père, l'exemple le plus important, qui m'a appris et transmis tout ce qu'il y a de bon en moi. Ils ont su, ces années durant, supporter mon absence sans jamais arrêter de me supporter. Merci.

Introduction en français

Depuis son essor, dans les années 1950, la programmation linéaire est devenue un outil fondamental pour modéliser, et souvent résoudre, beaucoup de problèmes dans le domaine de l'optimisation combinatoire. Dès lors, le sujet n'a pas cessé d'attirer un fort intérêt, grâce aussi aux progrès réalisés en algorithmique et au développement de la puissance des moyens de calcul. C'est là que la plupart des problèmes d'optimisation plongent leurs racines. Outre la programmation linéaire, citons aussi la programmation entière et la programmation quadratique. Dans ce travail nous nous intéresserons notamment à la programmation semidéfinie positive (SDP).

Rappelons ici une des formulations possibles pour un programme linéaire : il s'agit de trouver un vecteur réel aux entrées non négatives qui maximise une fonction linéaire, le vecteur étant soumis à des contraintes qui sont des inégalités linéaires. Dans un programme semidéfini positif, les vecteurs sont remplacés par des matrices réelles symétriques. Une matrice admissible doit alors être semidéfinie positive, c'està-dire que ses valeurs propres doivent être non négatives. Il s'agit d'une généralisation : en effet, si l'on impose la condition que la matrice soit diagonale, l'on se retrouve avec un programme linéaire.

Dans les années 1980, des algorithmes basés sur la méthode des points intérieurs ont vu le jour, d'abord pour les programmes linéaires ( [START_REF] Karmarkar | A new polynomial-time algorithm for linear programming[END_REF]) et ensuite pour les programmes semidéfinis positifs ( [START_REF] Alizadeh | Interior point methods in semidefinite programming with applications to combinatorial optimization[END_REF], [START_REF] Yu | Conic formulation of a convex programming problem and duality[END_REF], [START_REF] Yu | Interior point polynomial algorithms in convex programming[END_REF]). Ceux-ci permettent de résoudre les programmes semidéfinis positifs d'une façon efficace et avec une très bonne approximation. Entretemps, la programmation semidéfinie positive a été appliquée à une multitude de problèmes, venant d'un vaste éventail de branches des mathématiques. Aujourd'hui encore, la programmation semidéfinie positive semble être loin d'avoir épuisé ses champs d'application, notamment en ce qui concerne l'approximation de problèmes durs à résoudre.

Cette thèse s'inscrit dans une ligne de recherche qui a peut-être son origine dans le travail de Philippe Delsarte sur les schémas d'association ( [START_REF] Delsarte | An algebraic approach to the association schemes of coding theory[END_REF]), où l'on trouve un programme linéaire dont la valeur optimale donne une borne supérieure sur la taille maximale d'un code avec distance minimale donnée. Quand ce programme est appliqué aux codes dans l'espace de Hamming, l'on obtient une borne qui a donné pendant longtemps les meilleurs résultats numériques et asymptotiques. xiii Les inégalités présentes dans le programme linéaire de Delsarte pour l'espace de Hamming H n peuvent être obtenues en considérant la distribution des distances d'un code. La même distribution résulte en prenant les orbites des paires de points sous l'action du groupe G d'automorphismes de H n . Les polynômes de Krawtchouk, reliés à la décomposition en composantes irréductibles sous l'action de G de l'espace de fonctions à valeurs complexes de H n , apparaissent dans les inégalités du programme de Delsarte.

Par ailleurs, la borne de Delsarte peut s'appliquer aux codes d'autres espaces, comme l'espace de Johnson binaire ou la sphère unité de l'espace Euclidien réel. Plus généralement, elle s'applique à tous les espaces 2-points homogènes. La quête de généralisations de cette méthode a conduit à l'utilisation de la programmation semidéfinie positive. En 2005, Schrijver a établi une borne supérieure pour la taille des codes dans l'espace de Hamming en utilisant la programmation semidéfine positive. Dans beaucoup de cas, sa borne donne des résultats meilleurs que celle de Delsarte ([41]). Ensuite, la méthode de Schrijver a été étendue aux codes non-binaires ( [START_REF] Gijswijt | New upper bounds for nonbinary codes[END_REF]) et améliorée davantage dans le cas binaire ( [START_REF] Gijswijt | Semidefinite code bounds based on quadruple distances[END_REF]).

L'idée sous-jacente est de prendre en compte les triplets de points, au lieu des paires. Avec ceci l'on peut obtenir la borne de Schrijver par une démarche similaire à celle rappelée ci-dessus pour le programme de Delsarte. Juste, dans ce cas on considère l'action d'un sous-groupe G ≤ G, notamment le sous-groupe stabilisateur d'un point. L'espace H n muni de cette action n'est pas 2-points homogène. Par conséquent, la décomposition en composantes irréductibles de l'espace de fonctions à valeurs complexes de H n a des multiplicités plus grandes que 1 et celle-ci est la raison pour laquelle des matrices apparaissent.

Cette idée a déjà été appliquée, avec succès, à d'autres espaces de la théorie des codes, comme la sphère unité de l'espace Euclidien réel. Avec ceci, des nouveaux résultats ont été obtenus pour le problème géométrique du "kissing number" ( [START_REF] Bachoc | New upper bounds for kissing numbers from semidefinite programming[END_REF]).

Un point de vue uniforme nous est donné par la théorie des graphes. En effet, un espace métrique peut être vu comme l'ensemble des sommets d'un graphe, où les arêtes correspondent aux distances interdites. Les problèmes cités ci-dessus peuvent alors être abordés en termes d'ensembles indépendants du graphe donné. Ceci nous permet d'utiliser le nombre ϑ de Lovász. En 1979, Lovász définit le nombre ϑ d'un graphe comme la valeur optimale d'un certain programme semidéfini positif associé au graphe ( [START_REF] Lovász | On the Shannon capacity of a graph[END_REF]). Ce nombre possède des propriétés remarquables : entre autres, il donne une borne supérieure sur le nombre d'indépendance du graphe. Aussi, quand une petite modification du programme, nommée ϑ , est appliquée à un certain graphe dans l'espace de Hamming, l'on retrouve la borne de Delsarte ( [START_REF] Mceliece | The Lovász bound and some generalizations[END_REF], [START_REF] Schrijver | A comparison of the Delsarte and Lovász bound[END_REF]).

Par ailleurs, les travaux de recherche plus récents se concentrent sur les hiérarchies de programmes semidéfinis positifs ( [START_REF] Gvozdenovic | Block-diagonal semidefinite programming hierarchies for 0/1 programming[END_REF], [START_REF] Lasserre | An explicit equivalent positive semidefinite program for nonlinear 0 -1 programs[END_REF], [START_REF] Lovász | Cones of matrices and set-functions and 0 -1 optimization[END_REF]). En ce qui concerne la détermination du nombre d'indépendance α d'un graphe, le premier degré d'une telle hiérarchie donne d'habitude le nombre ϑ de Lovász et les degrés suivants donnent des bornes supérieures de plus en plus strictes pour α. C'est dans ce contexte qu'on peut voir les bornes pour les codes dans l'espace de Hamming basées sur les triplets ( [START_REF] Schrijver | New code upper bounds from the Terwilliger algebra and semidefinite programming[END_REF]) ou les quadruplets ( [START_REF] Gijswijt | Semidefinite code bounds based on quadruple distances[END_REF]) de points.

Le point de départ de ce travail était l'application de ces méthodes dans le cadre du codage des réseaux (network coding). Il s'agit d'un domaine récent et dynamique de la théorie de l'information, qui capture à la fois l'intérêt des informaticiens et des mathématiciens. Koetter et Kschischang ont formulé le problème d'une communication fiable dans un tel contexte en utilisant des codes de sous-espaces. Cette formulation établit un lien remarquable avec le cadre classique des codes dans l'espace de Hamming. Néanmoins, des différences importantes existent entre ces deux cas, ce qui empêche de réitérer naïvement la même méthode.

Plus précisément, les codes définis par Koetter et Kschischang sont des familles de sous-espaces vectoriels d'un espace vectoriel fixé sur un corps fini. Ces codes sont nommés codes projectifs et, dans le cas où tous les sous-espaces ont la même dimension, codes à dimension constante. Ils sont les analogues q-aires des codes de Hamming et de Johnson. Ici, q denote le cardinal du corps de base et l'analogie q-aire consiste à remplacer (sous-)ensembles avec (sous-)espaces vectoriels et, par conséquent, le cardinal avec la dimension. Au niveau de l'action de groupe, le groupe symétrique est remplacé par le groupe général linéaire. Il est important, ici, de remarquer une première différence : l'espace de Hamming H n est muni d'une action transitive, tandis que ce n'est pas le cas dans l'espace projectif. Nous voyons par là que la borne de la programmation linéaire de Delsarte ne peut pas s'appliquer aux codes projectifs. En revanche, nous allons établir une borne de la programmation semidéfinie positive en utilisant le nombre ϑ de Lovász. Afin de calculer cette borne dans des cas non-triviaux, il est nécessaire de symétriser le programme définissant ϑ sous l'action du groupe général linéaire. En ce qui concerne les codes à dimension constante, il y a une meilleure analogie avec les codes à poids constant, ce qui a permis de retrouver la plupart des bornes classiques dans ce cas.

Après cela, nous nous sommes intéressés au nombre chromatique de l'espace Euclidien, dont la détermination est un problème ancien et toujours très ouvert. A ce propos, Frankl et Wilson ont remarqué le rôle joué par les ensembles qui évitent une distance donnée dans l'espace de Johnson. Dans [START_REF] Frankl | Intersection theorems with geometric consequences[END_REF] ils établissent une borne supérieure pour le cardinal de tels ensembles, cette borne n'étant valide que pour un choix limité de paramètres. Par là ils arrivent aussi à un résultat asymptotique sur le nombre chromatique Euclidien. Leur borne peut être améliorée et élargie à tout choix de paramètres en utilisant la borne de Delsarte pour les ensembles qui évitent une distance et aussi une borne du type Schrijver sur les triplets de points. Nous allons nous concentrer sur cette dernière en donnant la formulation générale en termes d'un programme semidéfini positif, ainsi que les détails de sa symétrisation. En raison de l'analogie existante entre l'espace de Hamming et l'espace projectif, cette symétrisation a plusieurs points en commun avec celle développée pour les codes projectifs. Plus précisément, les deux peuvent être vues comme des variantes de la diagonalisation par blocs de l'algèbre de Terwilliger de l'espace de Hamming.

Comme l'on peut le voir par ces applications de la méthode SDP, nous avons un bon cadre théorique que nous pouvons appliquer aux problèmes extrémaux de la théorie des graphes mais il est souvent difficile d'obtenir des résultats explicites. En effet, la plupart du travail nécessaire consiste à réduire le programme général selon les symétries de l'espace donné. Des travaux récents sur les hiérarchies de programmes semidéfinis positifs ( [START_REF] Gvozdenovic | Block-diagonal semidefinite programming hierarchies for 0/1 programming[END_REF], [START_REF] Lasserre | An explicit equivalent positive semidefinite program for nonlinear 0 -1 programs[END_REF], [START_REF] Lovász | Cones of matrices and set-functions and 0 -1 optimization[END_REF]) peuvent aussi être utilisés pour améliorer certaines bornes, mais ces programmes ont également besoin d'être réduits avant de pouvoir en calculer les solutions. En revanche, chaque programme semidéfini positif peut s'écrire en termes de la plus grande valeur propre de certaines matrices. Pour exemple, dans le cas de ϑ l'on trouve une relaxation classique que, pour les graphes réguliers, donne la borne de Hoffman, borne explicite qui s'écrit par moyen des valeurs propres de la matrice d'adjacence. Notre but est de définir une hiérarchie de programmes semidéfinis positifs qui, tout en améliorant ϑ, se prêtent facilement à l'analyse en termes de valeurs propres, voire qui donnent des généralisations de la borne de Hoffman. A notre avis, le contenu du cinquième chapitre est un premier pas dans cette direction.

Nous y définissons une nouvelle hiérarchie de programmes semidéfinis positifs, dont la valeur optimale donne une borne supérieure sur le nombre d'indépendance d'un graphe. Pour la définir, nous utilisons le langage des complexes simpliciaux, lesquels peuvent s'interpréter comme une généralisation des graphes. Par moyen des opérateurs de bord nous construisons des analogues de deux matrices reliées à ϑ et à la relaxation de Hoffman, notamment la matrice dont toutes les entrées sont 1 et le Laplacian du graphe. Avec ceci, nous définissons la hiérarchie et en analysons les propriétés. Il est naturel qu'une hiérarchie de ce type donne ϑ au premier degré et qu'elle atteigne le nombre d'indépendance à un certain degré fini. Nous montrons cette propriété et d'autres aussi qui généralisent des propriétés du nombre ϑ. Nous ne sommes pas capables de prouver la décroissance de notre hiérarchie, mais nous montrons comment l'obtenir par le moyen d'une légère modification.

A titre d'exemple, nous calculons les valeurs du deuxième degré de notre hiérarchie pour les graphes de Paley. Cette famille de graphes est intéressante en raison de son comportement quasi-aléatoire et de ses applications en théorie des nombres. Il est très difficile d'estimer la taille de la plus grande clique des graphes de Paley. Comme ces graphes sont auto-complémentaires, cela revient à en estimer le nombre d'indépendance. Aussi, en étant fortement réguliers, leur nombre ϑ est donné par la borne de Hoffman. Au moment où cette thèse se termine, nous ne sommes pas en mesure d'améliorer les bornes existantes et le problème reste ouvert.

Structure et résultats de la thèse

Le troisième chapitre 1 est dédié à l'étude du problème de la détermination de bornes supérieures pour le cardinal des codes projectifs et des codes à dimension constante (aussi dits codes de Grassmann). Nous en donnons l'état de l'art et introduisons une borne SDP qui améliore certains résultats existants. La borne est obtenue en symétrisant le programme définissant ϑ sous l'action du groupe général linéaire. En outre, nous montrons que les bornes déjà existantes pour les codes de Grassmann peuvent s'obtenir comme cas particuliers de la borne de Delsarte, laquelle est à la fois un cas particulier du nombre ϑ, tout en montrant ainsi l'intérêt de cette méthode.

Le quatrième chapitre est consacré au nombre chromatique de l'espace Euclidien. Nous y rappelons la définition des graphes de Frankl et Wilson et le rôle qu'ils jouent dans ce contexte. Nous prouvons une borne SDP sur le cardinal des ensembles qui évitent une distance donnée dans l'espace de Johnson. Ce programme semidéfini positif est une variante de celui introduit par Schrijver pour les codes à poids constant ( [START_REF] Schrijver | New code upper bounds from the Terwilliger algebra and semidefinite programming[END_REF]). Le programme est ensuite symétrisé afin de pouvoir en calculer des valeurs explicites. Les résultats ainsi obtenus améliorent les bornes inférieures pour le nombre chromatique Euclidien mesurable.

Dans le cinquième chapitre nous définissons une nouvelle séquence, nommée ϑ k , de programmes semidéfinis positifs qui donnent une borne supérieure pour le nombre d'indépendance d'un graphe. Cette séquence est liée à des matrices venant des complexes simpliciaux. Quelques propriétés de ϑ k y sont analysées. En particulier, nous prouvons le théorème du sandwich pour tout degré k, ainsi qu'un résultat concernant les homomorphismes de graphes qui généralise une propriété bien connue de ϑ. Ensuite, nous modifions légèrement notre définition de ϑ k pour assurer la décroissance de la valeur optimale à chaque degré. Nous donnons quelques résultats numériques pour des cycles et des graphes de Paley de petite taille.

Chapter 1 Introduction

Since its development in the 1950's, linear programming has become a fundamental tool in combinatorial optimization, as it gives a general formulation in which a multitude of problems can be expressed and often solved. Research in algorithmic issues and increased computational power have supported the development of the field and this approach gained more and more interest, giving rise to several related optimization problems, like integer programming and quadratic programming. One succesfull generalization is that of semidefinite programming (SDP).

A linear programming problem can be formulated as: finding a real vector with non negative entries which maximizes (or minimizes) a linear function, subject to some given linear inequalities. In a semidefinite programming problem we no longer consider vectors but symmetric matrices. Then the required condition is that the matrix is positive semidefinite, which means that all its eigenvalues are non negative. This is clearly a more general problem: indeed, requiring the matrix to be diagonal, we go back to a linear program.

In the 1980's, interior point method algorithms were developed for linear programs ( [START_REF] Karmarkar | A new polynomial-time algorithm for linear programming[END_REF]) and generalized to semidefinite programs ( [START_REF] Alizadeh | Interior point methods in semidefinite programming with applications to combinatorial optimization[END_REF], [START_REF] Yu | Conic formulation of a convex programming problem and duality[END_REF], [START_REF] Yu | Interior point polynomial algorithms in convex programming[END_REF]), thus allowing semidefinite programs to be approximately solved by efficient algorithms. Meanwhile, SDP was applied to model problems arising in a very wide range of areas. Still nowadays, it plays an important role in the development of approximation algorithms for "hard" optimization problems.

Let us move more specifically to the motivation which is behind this work. In coding theory, a linear program was established by Delsarte's work on association schemes ( [START_REF] Delsarte | An algebraic approach to the association schemes of coding theory[END_REF]). Its optimal value gives an upper bound on the maximal size of a code with prescribed minimum distance. In particular, it has longtime remained one of the best numerical bounds on the size of codes in the Hamming space, leading also to the best known asymptotics.

The inequalities involved in Delsarte linear program for the Hamming space H n can be derived by considering the distance distribution of a code. This distance distribution coincides with the orbit decomposition of pairs of words under the group G of automorphisms of H n . Then the so-called Krawtchouk polynomials are strictly related to the G-irreducible decomposition of the space of complex valued functions on H n and they are exactly the polynomials occurring in the inequalities of Delsarte linear program.

On the other hand, Delsarte bound equally applies to codes in other spaces, as the binary Johnson space or the real Euclidean unit sphere and, more generally, to all 2-point homogeneous spaces. The quest for generalizations of this method led to use semidefinite programming. In 2005, Schrijver established an SDP upper bound for the size of codes in the Hamming space which strictly improves over Delsarte's one for several parameters ( [START_REF] Schrijver | New code upper bounds from the Terwilliger algebra and semidefinite programming[END_REF]). Next, Schrijver's method was extended to non binary codes ( [START_REF] Gijswijt | New upper bounds for nonbinary codes[END_REF]) and it was further improved in the binary case ( [START_REF] Gijswijt | Semidefinite code bounds based on quadruple distances[END_REF]).

The underlying idea is to consider triples of words instead of pairs. Then it is possible to obtain Schrijver's bound using a similar approach to the one recalled above for Delsarte linear program. The difference is that in this case we consider the action of a subgroup G ≤ G, namely the stabilizer of one point. As H n is not 2-point homogeneous for this action, the irreducible decomposition of the space of complex valued functions on H n involves multiplicities greater than 1 and, roughly speaking, this is the reason for which one has to deal with matrices.

This idea has already been successfully applied to other spaces occurring in coding theory, like the unit sphere of the Euclidean space, providing new results in an old and still open geometrical problem, namely the kissing number problem ( [START_REF] Bachoc | New upper bounds for kissing numbers from semidefinite programming[END_REF]).

One unifying approach is to see all the metric spaces involved as graphs where edges coincide with forbidden distances. Then these problems can often be formulated in terms of stable sets in the given graph. This is where Lovász ϑ number comes into play. In 1979, Lovász associated to each graph a semidefinite program, whose optimal value he called the ϑ number of the graph ( [START_REF] Lovász | On the Shannon capacity of a graph[END_REF]). Among other remarkable properties, it yields an upper bound on the cardinality of every stable set in the graph. It was early recognized that when a minor modification, called ϑ , is applied to a well chosen graph in the Hamming space, the Delsarte bound is recovered ( [START_REF] Mceliece | The Lovász bound and some generalizations[END_REF], [START_REF] Schrijver | A comparison of the Delsarte and Lovász bound[END_REF]).

On the other hand, recent research tend to focus on hierarchies of semidefinite programs ( [START_REF] Gvozdenovic | Block-diagonal semidefinite programming hierarchies for 0/1 programming[END_REF], [START_REF] Lasserre | An explicit equivalent positive semidefinite program for nonlinear 0 -1 programs[END_REF], [START_REF] Lovász | Cones of matrices and set-functions and 0 -1 optimization[END_REF]). When applied to the problem of determining the independence number α of a graph, the first step of a hierarchy usually coincides with the Lovász ϑ number and successive steps give tighter upper bounds on α. Bounds for Hamming codes based on triples ( [START_REF] Schrijver | New code upper bounds from the Terwilliger algebra and semidefinite programming[END_REF]) or quadruples ([21]) of words can be interpreted in this context.

The initial motivation and starting point for this thesis was to understand how this framework could be applied to network coding. Indeed, network coding is a recent and dynamical field in coding theory which is capturing interest from both computer scientists and mathematicians. The coding theoretical formulation of the communication problem in terms of codes of subspaces by Koetter and Kschischang ([29]) establish a parallel with the classical Hamming codes. Nevertheless, important differences exist between the two cases, so a straightforward application of the same method is not possible and one needs to be more careful.

More precisely, codes for network coding are given by collections of linear subspaces of a given vector space over a finite field. Such codes are called projective codes or, if all the subspaces have the same dimension, constant dimension codes. They are the q-analog of Hamming codes and Johnson codes, respectively. Here, q is the cardinality of the base field and q-analogy is a combinatorial point of view replacing sets with subspaces and cardinality with dimension. Also, if we look at the group action, the symmetric group is replaced with the general linear group. Here we remark a first important difference: the Hamming space H n has a transitive group action while in the projective space this does not happen. This already tells us that the Delsarte linear programming bound cannot be applied to projective codes. However, a semidefinite programming bound coming from Lovász ϑ number can be established. In order to compute the explicit bound in non trivial cases, the program defining ϑ needs to be symmetrized using the action of the general linear group. About constant dimension codes, the analogy with constant weight codes holds in a better way, so all classical bounds can be generalized and indeed they have already been established.

Next, we remarked that distance avoiding sets in the Johnson space play a role in determining the chromatic number of the Euclidean space, an old and open geometrical problem. Indeed, this was already recognized by Frankl and Wilson in [START_REF] Frankl | Intersection theorems with geometric consequences[END_REF], where they give an upper bound on the cardinality of such sets for a limited choice of parameters. With this they obtained an asymptotic result on the chromatic number of the Euclidean space. Their bound can be improved and extended to all parameters by using the Delsarte bound applied to distance avoiding sets and a Schrijver-like bound on triples of words. We mainly focus on this last one, giving its general SDP formulation and the details of the symmetrization of the program. In view of the analogy between Hamming space and projective space, the group theoretical setting that we use in the symmetrization has several common points with the one we developed for projective codes. Actually, both can be seen as variations of the block diagonalization of the Terwilliger algebra of the Hamming space.

As it can be seen from these applications of the SDP method, there is a good theoretical setting that we can apply to extremal problems in graph theory, but it is often hard to obtain explicit results. Indeed, most of the work needed to come up with explicit values of this kind of bounds consists of reducing the general program according to the symmetries of the space in which we are working. Also, recent research on SDP hierarchies ( [START_REF] Gvozdenovic | Block-diagonal semidefinite programming hierarchies for 0/1 programming[END_REF], [START_REF] Lasserre | An explicit equivalent positive semidefinite program for nonlinear 0 -1 programs[END_REF], [START_REF] Lovász | Cones of matrices and set-functions and 0 -1 optimization[END_REF]) can be used to improve results in this kind of problems, but such SDPs are not ready to be computed. On the other hand, every semidefinite program has a formulation in terms of the largest eigenvalue of matrices. Looking at ϑ, it is a classical result to get a relaxation which, for regular graphs, yields the more explicit Hoffman bound, involving eigenvalues of the adjacency matrix. Our hope is to derive a hierarchy of semidefinite programs which strengthen ϑ but which remains easy to analyse in terms of eigenvalues and, possibly, which leads to high-order generalizations of the Hoffman bound. We believe that our work in chapter 5 is a first step in this direction.

We build a new hierarchy of semidefinite programs whose optimal value upper bounds the independence number of a graph. To define it, we adopt the framework of simplicial complexes. Indeed, simplicial complexes can be seen as a generalization of graphs. By mean of the boundary maps, we can build high order analogs of two matrices occurring in ϑ and its classical Hoffman relaxation, namely the all one's matrix and the Laplacian of the graph. With this, we define the hierarchy and we discuss its properties. It is natural to ask that a hierarchy of this kind starts from ϑ and reaches the independence number in finitely many steps. We show that this is the case, along with other properties that generalize some properties of ϑ. We are not able to show that our hierarchy is decreasing at any step but we show how this can be insured with a minor modification.

As an application we focus on Paley graphs, computing some values of the second step of our hierarchy. Paley graphs are interesting because of their random like behaviour and their number theoretical meaning. Determine or even estimate their clique number is a very hard open question. As these graphs are self complementary, the clique number coincides with the independence number. Moreover, being strongly regulars, they reach equality in the Hoffman bound so their ϑ number is explicitely known. At this moment, we are not able to give improvements over the existing bounds and the problem remains open.

Overview of the thesis and results

In the third chapter1 we deal with the problem of determining upper bounds on the cardinality of codes for network coding, namely the class of projective codes and the subclass of Grassmann codes. We give the state of the art of this problem and we introduce an SDP bound that, for certain parameters, gives better results than the existing ones. This SDP is obtained by symmetrizing the ϑ program under the action of the general linear group. Moreover we show that the existing general bounds for Grassmann codes can be obtained as particular instances of the Delsarte LP bound, which is itself a special case of the SDP defining the ϑ number, thus showing the interest of this approach.

In the fourth chapter we deal with the Euclidean chromatic number. We recall the definition of Frankl-Wilson graphs and the role that they play in this problem. We prove a more general SDP upper bound on the independence number of sets avoiding one distance in the Johnson space. This SDP is a variation of the one introduced by Schrijver for constant weight codes ( [START_REF] Schrijver | New code upper bounds from the Terwilliger algebra and semidefinite programming[END_REF]). The program is symmetrized in order to compute explicit values. The results obtained in this way give improvements on lower bounds for the measurable Euclidean chromatic number.

In the fifth chapter we define a new sequence ϑ k of semidefinite programs which upper bound the independence number of a graph. It is related to matrices arising from abstract simplicial complexes. Some properties of ϑ k are discussed. In particular, we prove that the sandwich theorem holds for any step of the new sequence, along with a result involving graph homomorphisms which generalizes one well known property of ϑ. Also, we slightly modify the formulation of ϑ k to insure that the optimal value decreases at each step. We give some numerical results for small cycles and Paley graphs.

In the sixth chapter we analyse in a deeper way the independence number of Paley graphs. Our program ϑ 2 is symmetrized, thus allowing its explicit computation for a wider range of parameters. Then these values are compared to the ones of the program L 2 given in [START_REF] Gvozdenovic | Block-diagonal semidefinite programming hierarchies for 0/1 programming[END_REF] and recalled in chapter 2. We end the chapter by sketching some further considerations on the structure of Paley graphs.

Notation

• for a natural number n, [n] denotes the set {1, 2, . . . , n}.

• for 0 -1 vectors, 0 m or 1 m means that m consecutive coordinates are 0 or 1 respectively. So, for example, 0 2 1 3 01 = (0, 0, 1, 1, 1, 0, 1).

• I denotes the identity matrix, whose size will be clear from the context.

• J denotes the square (sometimes rectangular) matrix with all 1's entries.

• , denotes the scalar product of matrices: given A, B matrices of the same size, A, B := Tr(AB T ).

• given a finite set X, we denote R X the real vector space of dimension |X| whose basis elements are indexed by the set X; the space R X×X is then identified with the vector space of real square matrices with rows and columns indexed by

X. Of course, R n×n = R [n]×[n] .
• a symmetric matrix A ∈ R n×n is positive semidefinite, noted A 0, if one of the following equivalent conditions holds:

(i) v T Av ≥ 0 for all vectors v ∈ R n ,
(ii) all eigenvalues of A are non negative, (iii) A = BB T for some B ∈ R n×m with m ≤ n.

We mention that semidefinite matrices form a self-dual cone. We write A B to signify A -B 0.

• for X a finite set, we will often identify functions F : X × X → R with matrices F ∈ R X×X , by F (x, y) = F x,y . Positive semidefiniteness remains valid in both notations.

• when considering complex matrices, all works the same replacing symmetric with hermitian and transpose with conjugate transpose.

Chapter 2

Background

In this chapter we give the necessary background material. The first part is nothing else that basic representation theory. The results that we recall there will be used in chapter 3, 4 and 6 to decompose certain group representations. The second part sets up some basic vocabulary of graph theory. The third part is about semidefinite programming and it is at the core of what is done in this thesis. The classic Lovász ϑ number is introduced. Although all definitions and results are commonly known in the literature, they are reproduced here, along with some proofs, as they will serve as a model for the work that we present further on in chapter 5. In particular, we briefly sketch the Lasserre hierarchy for the independence number ( [START_REF] Lasserre | An explicit equivalent positive semidefinite program for nonlinear 0 -1 programs[END_REF]), along with a variant given by Gvozdenović, Laurent and Vallentin ([23]). We then outline, following [START_REF] Bachoc | Invariant semidefinite programs[END_REF], a general strategy to symmetrize the ϑ program under a group action, using tools of representation theory. A section on coding theory will serve to introduce some basic vocabulary and to give the first example of symmetrization of an SDP, showing that in the Hamming space the ϑ program coincides with Delsarte program. Finally, the block diagonalization of the Terwilliger algebra of the Hamming scheme ( [START_REF] Schrijver | New code upper bounds from the Terwilliger algebra and semidefinite programming[END_REF], [START_REF] Vallentin | Symmetry in semidefinite programs[END_REF]) is explained, as it will serve to establish some results in chapter 4.

Representation theory of finite groups

We will consider here the representation theory of finite groups in characteristic zero, in particular over the complex field C. A classic reference is given by the book of Jean-Pierre Serre, [START_REF] Serre | Linear representations of finite groups[END_REF], which we will essentially follow for this introductory part. The goal is to understand how a given representation decomposes into irreducible subrepresentations and how to find such decomposition in an explicit way.

First definitions

Definition 2.1.1. Let k be a field and G a finite group. A representation of G over k is a homomorphism ρ : G → GL(V ), where V is a vector space over k.

If V has finite dimension n over k, we say that the representation has degree n. The choice of a basis of V allows us to express ρ(g) as an invertible matrix and to define a matrix representation ρ : G → GL n (k). Different choices of basis result in representations which are isomorphic in the sense of the following definition.

Definition 2.1.2. Two representations of the same group G, ρ : G → GL(V ) and ρ : G → GL(V ), are said to be isomorphic if there exists an isomorphism τ : V → V , such that, for every g ∈ G the following diagram is commutative:

V τ ρ(g) / / V τ V ρ (g) / / V
Clearly, isomorphic representations have the same degree. From the matrix point of view, ρ(g) and ρ (g) are conjugated by an invertible matrix.

Examples :

• The trivial representation of G of degree n is defined by ρ(g) := Id(V ) for every g ∈ G, where dim(V ) = n. Of course, this definition is given modulo isomorphism, as it depends on the choice of V .

• Let V be the vector space over k whose basis vectors are indexed by elements of G: V := e h : h ∈ G . The regular representation of G is defined by ρ(g)(e h ) := e gh extended by linearity. Its degree is |G|.

Definition 2.1.3. Given two representations of the same group G, ρ : G → GL(V ) and ρ : G → GL(V ), we define their sum

(ρ ⊕ ρ ) : G → GL(V ⊕ V ) by (ρ ⊕ ρ )(g) = (ρ(g), ρ (g)).
The degree of the sum is the sum of the degrees. If ρ and ρ are given in matrix representation, then a corresponding matrix for (ρ ⊕ ρ )(g) is ρ(g) 0 0 ρ (g) Definition 2.1.4. Let ρ : G → GL(V ) be a representation of G and W a linear subspace of V . If W is stable with respect to the action of G, that is, if for every g ∈ G, ρ(g)(W ) ⊂ W then the restriction ρ |W : G → GL(W ) is a subrepresentation of ρ, of degree dim(W ).

Every representation has two trivial subrepresentations: the ones defined by the trivial subspaces {0} and V . Definition 2.1.5. A representation is irreducible if it doesn't have non trivial subrepresentations.

Examples :

• Every representation of degree 1 is irreducible.

The following lemma is a basic result which plays a central role in the development of representation theory.

Lemma 2.1.6 (Schur). Let ρ : G → GL(V ) and ρ : G → GL(V ) be two irreducible representations and let f : V → V be a linear homomorphism which commutes with the action of G, that is, f •ρ(g) = ρ (g)•f for every g ∈ G. Then f = 0 unless ρ ρ , in which case f is an isomorphism. If moreover the ground field is algebraically closed and V = V , then f is a scalar multiple of the identity.

For the rest of the chapter we will consider only finite dimensional representations over the complex field C, which is enough for the purpose of this thesis.

Decomposition of a representation

Theorem 2.1.7. Let ρ : G → GL(V ) be a reducible representation and ρ |W : G → GL(W ) one of its non trivial subrepresentations. There exists a linear subspace W which is a complement of W in V and which is stable with respect to the action of G. In other words, V = W ⊕ W and ρ = (ρ |W ⊕ ρ |W ).

Proof. Let , be a scalar product on V . We define a G-invariant scalar product , G by setting

v, v G := 1 |G| g∈G ρ(g)(v), ρ(g)(v )
Then the orthogonal complement of W with respect to , G has the desired properties.

Iterating the theorem above yields the following classical result.

V = V 1 ⊕ • • • ⊕ V m be
a decomposition of V in irreducible subrepresentations and let {W 1 , W 2 , . . . W r } be the collection of irreducible subrepresentations of V , modulo isomorphism. The isotypic components of V are defined by

I j := ⊕ i:V i W j V i . So I j m j W j where m j := card{i : V i W j } is the multiplicity of W j in V . We obtain that V = ⊕ j I j ⊕ j m j W j (2.1.1)
This decomposition is unique in the sense that each I j is uniquely determined and does not depend on the original decomposition of V into irreducibles. In general, every isotypic component I j has several irreducible decompositions but clearly all of them are isomorphic. In particular, the multiplicity and the dimension of every W j are uniquely determined.

Characters

As we will see, characters encode a lot of properties of representations and they are a fundamental tool for performing calculations. We list here the main results.

Definition 2.1.12. The character of a representation ρ : G → GL(V ) is the function χ ρ : G → C defined by χ ρ (g) := Tr(ρ(g)).

From a well known property of the trace, it follows that characters are class functions, that is, they are invariant on conjugacy classes of G. Moreover, Theorem 2.1.13. The characters of irreducible pairwise non isomorphic representations of G form a basis of the space of class functions on G.

Corollary 2.1.14. The number of irreducible pairwise non isomorphic representations of G equals the number of conjugacy classes of G.

Given two characters χ ρ , χ ρ we consider their scalar product, given by

χ ρ , χ ρ = 1 |G| g∈G χ ρ (g)χ ρ (g)
where • means the complex conjugate.

Then the next result says that the basis of theorem 2.1.13 is an orthonormal one.

Theorem 2.1.15. If ρ is an irreducible representation, then χ ρ , χ ρ = 1. If ρ ρ , then χ ρ , χ ρ = 0.

Corollary 2.1.16. Consider the decomposition (2.1.1). For every j, we have that χ V , χ W j = m j .

Corollary 2.1.17. A representation ρ is irreducible if and only if χ ρ , χ ρ = 1.

By computing the character of the regular representation of a group G, we see that every irreducible representation W j of G is contained in the regular representation with multiplicity equal to its degree n j . This yields the sum of squares formula:

Proposition 2.1.18. Let {W 1 , W 2 , . . . W r } be the collection of irreducible represen- tations of a group G, modulo isomorphism. Set n j := deg(W j ). Then |G| = r j=1 n 2 j
The next theorem reveals the importance of characters in the study of representations.

Theorem 2.1.19. Two representations are isomorphic if and only if they have the same character.

Restriction and induction

Here we see how representations of a group can be constructed from those of its subgroups or from those of larger groups. Let H ≤ G be two finite groups.

Definition 2.1.20. If ρ : G → GL(V ) is a representation of G, then the restriction ρ |H : H → GL(V ) is a representation of H, denoted Res G H (ρ) or ρ ↓ G H . Definition 2.1.21. If µ : H → GL(V ) is a representation of H,
then the induced representation is built as follows. Consider the space V := ⊕ m i=1 x i V , where {x 1 , . . . , x m } is a system of representatives of G/H. For g ∈ G and for every i, there exists an index j and an element h ∈ H such that

gx i = x j h. Then we obtain a representation of G, µ : G → GL(V ) by setting µ (g)(x i v) := x j (µ(h)v). The induced representation is denoted Ind G H (µ) or µ ↑ G H .
Using an analog notation for characters, we can mention the following result which shows the duality between restriction and induction.

Theorem 2.1.22 (Frobenius reciprocity). Let χ be a character of G and ψ be a character of H. We have

χ, Ind G H (ψ) = Res G H (χ), ψ

Notations and basic definitions of graph theory

A graph consists of a set V of vertices together with a set E ⊂ V 2 of edges. The notation is G = (V, E). If not explicitely stated, all graphs which appear in this thesis will be finite graphs, i.e. with a finite number of vertices. Moreover, the definition implies that all graphs appearing here will be undirected, without loops and multiple edges. In chapter 3 we will define a network as a directed graph, where E is taken to be a collection of ordered pairs of vertices.

We will usually simplify the notation, writing edges as vv instead of {v, v }. Given two vertices v, v ∈ V , we say that v is adjacent to v if vv ∈ E. This is a symmetric relation and it can be encoded in the adjacency matrix A(G) of G, defined as the matrix whose rows and columns are indexed by V and whose entries are

A(G) v,v := 1 if vv ∈ E 0 otherwise.
Thus, A(G) is a real symmetric matrix and we mention that its spectrum encodes some important properties of the graph. An adjacent vertex is called a neighbour. The number of neighbours of a vertex v is called the degree of v, noted deg(v). A graph is called regular if all of its vertices have the same degree d, which in this case is also the largest eigenvalue of the adjacency matrix. Some easy examples of regular graphs are complete graphs K n = ([n], [n] 2 ), null (or empty) graphs ([n], ∅) and cycles

C n = ([n], {ij : j -i = 1}).
A graph is called strongly regular if it is regular and moreover the number of common neighbours of a pair of vertices v, v depends only on whether vv is an edge or not, hence taking only two values λ, µ, respectively. In that case, the graph is said to be (n, d, λ, µ)-strongly regular, where n is the number of vertices and d the degree.

A subgraph of G is a graph H whose vertex and edge sets are subsets of those of G. The subgraph

H = (V , E ) is called an induced subgraph of G = (V, E) if E = E ∩ V 2 . If V = V , then H is called a spanning subgraph of G.
Two graphs G, G are isomorphic if there exists a bijection between their vertex sets which preserves the adjacency relation. Such a map is called an isomorphism and we write G G . When G = G , we talk about automorphisms of G.

Given a graph G = (V, E), the complement graph is defined as G = (V, E) where E is the complement of E in V 2 . A set of pairwise non adjacent vertices of G is called a stable set (or independent set) of G. The cardinality of the largest independent set is called the independence number of G, noted α(G). The dual concept is that of a clique. A set of pairwise adjacent vertices of G is called a clique of G. So a clique is an induced subgraph which Figure 2.a: The cycle of length 5 is isomorphic to its complement is isomorphic to a complete graph. The cardinality of the largest clique is called the clique number of G, noted ω(G). We note that an independent set of G is a clique of

G, so that α(G) = ω(G). A k-colouring of G is a map c : V → [k] such that c(v) = c(v ) for all vv ∈ E.
In other words, it is a partition of the vertex set into k independent sets. The least integer k such that a k-colouring exists is called the chromatic number of G and denoted χ(G).

Determining α and χ is a fundamental problem in theoretical computer science, which is known to be NP-hard ([27]).

Semidefinite programming and Lovász ϑ number

In this third part we introduce some of the main tools that we will use in this thesis, namely linear programs (LPs) and semidefinite programs (SDPs). We mention that they are particular convex programs and thus can be analyzed in the general setting of convex optimization problems ( [START_REF] Vandenberghe | Convex optimization[END_REF]), although this point of view is more general and not needed for our work. A link between graphs and SDPs is provided by the ϑ number, introduced by Lovász in 1979. This number have several interesting properties. What will be more interesting here is that, for any graph, the optimal value of the program defining ϑ gives an upper bound on its independence number.

Stronger upper bounds are provided by some hierarchies of SDPs and we recall two of them.

LPs and SDPs

A linear program (LP) is an optimization problem in which we ask for maximizing (or minimizing) a linear function under some constraints given by linear inequalities.

A linear program can be given in its classical primal form:

sup c T x subject to : x ≥ 0 Ax ≤ b (2.3.1)
where c, x, b ∈ R n and A ∈ R m×n , x 1 , . . . , x n being the variables. The dual of the above program is the following:

inf y T b subject to : y ≥ 0 y T A ≥ c T
A vector x satisfying all constraints in 2.3.1 is called a feasible solution. The program is called feasible or unfeasible according to the existence of such a vector. The scalar product c T x is called the objective function and, for x feasible, c T x is called the objective value of x. A vector x is optimal if its objective value is maximal amongst all objective values of feasible solutions. In such case, c T x is called the optimal value of 2.3.1. A feasible problem is said to be unbounded if the objective function can assume arbitrarily large positive objective values. Otherwise, it is said to be bounded. The same vocabulary (with the obvious variations) is used for the dual program.

A pair of primal and dual linear programs are moreover related by two duality theorems called weak duality and strong duality. The weak duality theorem says that any objective value of the dual is larger than any objective value of the primal. The strong duality theorem states that if one of the programs is bounded feasible, then the other is also bounded feasible and their optimal values coincide.

A real semidefinite program (SDP) is an optimization problem of the following form:

sup C, X subject to: X 0, A i , X = b i for i = 1, . . . , m (2.3.2)
where

• C, A 1 , . . . , A m are given symmetric matrices, • b 1 , . . . , b m are given real values,
• X is a variable matrix,

• A, B = trace(AB) is the usual scalar product between matrices,

• X 0 means that X is symmetric positive semidefinite.

This formulation includes linear programming as the special case when all matrices involved are diagonal matrices. A program like (2.3.2) is called in primal form. A semidefinite program can also be expressed in its dual form: inf b T y subject to:

m i=1 y i A i C (2.3.3) So, given (C, A 1 , . . . , A m , b 1 , . . . , b m )
we will talk about the two programs above as the pair of primal and dual SDP's associated to such data. The definitions of feasibility and optimality for semidefinite programs are the same as for linear programs. We refer to the vaste literature on SDP (e.g. [START_REF] Todd | Semidefinite optimization[END_REF], [START_REF] Vandenberghe | Semidefinite programming[END_REF]) for further details on this topic.

Let us just mention that semidefinite programs can be approximated in polynomial time within any specified accuracy by the ellipsoid algorithm or by practically efficient interior point methods.

The duality theory holds as well in this case.

Proposition 2.3.1 (Weak duality). For every X primal feasible and for every y dual feasible, we have

C, X ≤ b T y (2.3.4)
In particular, the optimal value of the primal program is less or equal than the optimal value of the dual program. Moreover, whenever we have feasible solutions X and y such that equality holds in 2.3.4, then they are optimal solutions for their respective programs.

The quantity b T y-C, X is called duality gap between the primal feasible solution X and the dual feasible solution y. To announce the strong duality theorem for SDP, we need one last definition: we say that (a solution of) the program 2.3.2 or 2.3.3 is strictly feasible if the matrix is positive definite, i.e. positive semidefinite and non singular.

Proposition 2.3.2 (Strong duality). If one of the primal or of the dual program is bounded and strictly feasible, then the other one is bounded feasible, it has an optimal

solution and the two optimal values coincide.

Lovász ϑ number 2.3.2.1 Shannon capacity

Given two graphs G = (V, E) and H = (V , E ), their strong product G H is defined as the graph with vertex set the cartesian product V × V and with edges {

Θ(G) = sup k k α(G k ) = lim k→+∞ k α(G k )
The number Θ(G) was introduced by Shannon in 1956 ( [START_REF] Shannon | The zero-error capacity of a noisy channel[END_REF]) with the following interpretation. Suppose that vertices of the graph G represent letters of an alphabet and that the adjacency relation means that one letter can be confused with the other. Then α(G k ) is the maximum number of messages of length k such that no two of them can be confused and Θ(G) can be seen as an information theoretical parameter representing the effective size of an alphabet in a communication model represented by G.

We have that α(G) ≤ Θ(G) and equality does not hold in general. For instance, consider C 5 , the cycle of length 5. Clearly α(C 5 ) = 2 and Lovász showed that Θ(C 5 ) = √ 5 ( [START_REF] Lovász | On the Shannon capacity of a graph[END_REF]). He obtained this result by introducing a general upper bound on Θ, for any graph. This upper bound is called the Lovász ϑ function.

Definition and properties of ϑ

There are several equivalent definitions for Lovász ϑ function. Here we list only the two that are more suitable to handle and which we will consider all along this thesis.

Definition 2.3.4 ([34], theorem 4). Let G = (V, E) be a graph, then ϑ(G) := max{ x,y∈V F (x, y) : F ∈ R V ×V , F 0 x∈V F (x, x) = 1 F (x, y) = 0 if xy ∈ E } (2.3.5)
Equivalently, by duality, Lemma 2.3.5 ([34], theorem 3). Let G = (V, E) be a graph, then

ϑ(G) = min{ λ max (Z) : Z ∈ R V ×V , Z symmetric Z x,y = 1 if x = y or xy ∈ E } (2.3.6)
where λ max (Z) denotes the largest eigenvalue of Z.

Remark 2.3.6. Taking F = (1/|V |)I, we see that a strictly feasible solution exists for the primal program defining ϑ(G), hence strong duality holds and the definition of ϑ(G) carries no ambiguity. This function is interesting as it can be used to approximate numbers which are hard to compute, like the independence number or the chromatic number of a graph, as we will see next. Moreover, being formulated as the optimal value of a semidefinite program, an approximation is computable in polynomial time in the size of the graph. Finally, we notice that every feasible solution of the primal or of the dual gives respectively a lower or an upper bound of the optimal value.

Proposition 2.3.7 ([34], lemma 3). For any graph G, α(G) ≤ ϑ(G).

Proof. Let S ⊂ V be an independent set. Let 1 S ∈ R V be its characteristic vector (with 1 in entries indexed by elements of S and 0 elsewhere). Define the matrix

X S := 1 |S| 1 S 1 T S ∈ R V ×V .
By construction, this matrix is positive semidefinite of trace 1 and its entries are 0 when at least one of the indices lies outside S. So it fulfils the condition of the program (2.3.5) and it has objective value |S|. The optimal value being the maximum among all feasible values, we have |S| ≤ ϑ(G) for any independent set S, from which we derive the announced inequality.

Remark 2.3.8. The program given in 2.3.5 is one of the equivalent formulations of Lovász original ϑ(G). If the additional constraint that F takes non negative values is added, the optimal value gives a sharper bound for α(G) denoted ϑ (G).

Proposition 2.3.9 ([34], theorem 1). For any graph G, Θ(G) ≤ ϑ(G).

Proof. By previous proposition and the inequality

ϑ(G H) ≤ ϑ(G)ϑ(H) proved in [34] (lemma 2), we have α(G k ) ≤ ϑ(G k ) ≤ ϑ(G) k .
Now we recall and prove another famous result, known as the sandwich theorem.

Proposition 2.3.10 ([34], corollary 3). For any graph G, α(G) ≤ ϑ(G) ≤ χ(G).

Proof. The first inequality has already been established. We prove the second one. A coloring of G of size c := χ(G) is a partition (C 1 , . . . , C c ) of the vertex set in cliques of G. We can reorder the vertex set according to such partition. Then the block matrix

Z :=     I J J . . . J I J . . . J J I . . .    
where blocks correspond to sets of the partition, is feasible for the program (2.3.6).

Here we abuse a little of the notation of J, as the non diagonal blocks need not be square blocks. Consider the matrix cI -Z which has diagonal blocks of the form (c -1)I and non diagonal blocks of the form -J. As all of its minors are positive, cI -Z is positive semidefinite and thus the largest eigenvalue of Z is less than or equal to c. As Z is feasible for (2.3.6), we have

ϑ(G) ≤ λ max (Z) ≤ c = χ(G).
Now we show how ϑ behaves when two graphs are related by homomorphism in the sense of the following definition. Definition 2.3.11. Let G = (V, E) and H = (V , E ) be two graphs. A graph homomorphism ϕ : G → H, is an application ϕ from V to V , which preserves edges, that is (i, j) ∈ E ⇒ (ϕ(i), ϕ(j)) ∈ E . Proposition 2.3.12. If there exists a homomorphism ϕ : G → H, then ϑ(G) ≤ ϑ(H).

Proof. Take any feasible solution F of the program defining ϑ(G). In particular

F i,j = 0 whenever i = j, ij ∈ E. Define F ∈ R V ×V by (F ) u,v := i : ϕ(i)=u j : ϕ(j)=v F i,j
Then, using the fact that (u, v) ∈ E ⇒ (i, j) ∈ E for all i, j such that ϕ(i) = u, ϕ(j) = v we see that F is a feasible solution of the program defining ϑ(H) and that its objective value is the same as the one of F . The announced inequality follows.

We conclude this overview of classical facts about the ϑ function recalling two more results from the original paper of Lovász.

Proposition 2.3.13 ([34, corollary 2 and theorem 8]). For all graphs G = (V, E), ϑ(G)ϑ(G) ≥ |V |. If moreover the graph is vertex transitive, equality holds.

There are few families of graphs for which the ϑ number is established. One of these is the family of cycles C n . If n = 2m is even, then C 2m is a bipartite graph and it is easy to see that α(C 2m ) = ϑ(C 2m ) = m. Proposition 2.3.14 ([34], corollary 5). For n odd,

ϑ(C n ) = n cos(π/n) 1 + cos(π/n)

Hierarchies of SDPs for the independence number

In many combinatorial problems it is helpful to obtain an efficient description of an approximation P (1) of a certain polytope P . For example, P can be given as the convex hull of the solution vectors of a linear 0 -1 program, and P (1) ⊇ P can be obtained by mean of linear (or semidefinite) constraints. In this case, P (1) is called a linear (or semidefinite) relaxation of P . More generally, given an optimization problem written in the form of a (linear, semidefinite, ...) program P, a relaxation of P is another program P (1) with the properties that the feasible region of P (1) contains the feasible region of P. A sequence of the kind

P (1) ⊇ P (2) ⊇ • • • ⊇ P (α) = P
is called a hierarchy of relaxations of the polytope P . Analogously, if dealing with programs, we will talk about hierarchies of relaxations of a program P. This is a large domain in optimization theory, but for the purpose of this thesis, we restrict ourselves to hierarchies of semidefinite programs. Lovász and Schrijver ([35]) and Lasserre ( [START_REF] Lasserre | An explicit equivalent positive semidefinite program for nonlinear 0 -1 programs[END_REF]) have defined hierarchies of semidefinite programs, as relaxations of (linear or non linear) 0 -1 programs. The hierarchy of Lasserre refines the one of Lovász and Schrijver, as it is shown in [START_REF] Laurent | A comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre relaxations for 0 -1 programming[END_REF]. In [START_REF] Gvozdenovic | Block-diagonal semidefinite programming hierarchies for 0/1 programming[END_REF], the authors introduced a new hierarchy. They then applied the second and third steps of their hierarchy to the problem of calculating the independence number of Paley graphs. Here we sketch the details of the Lasserre hierarchy for the independence number ( [START_REF] Lasserre | An explicit equivalent positive semidefinite program for nonlinear 0 -1 programs[END_REF]), along with the variant of Gvozdenović, Laurent and Vallentin ([23]).

The Lasserre hierarchy for the independence number

Given a graph G = (V, E), the stable set problem is: find a stable subset S ⊂ V of maximal cardinality |S| = α(G). The stable set polytope is defined as the convex hull of the characteristic vectors of all stable subsets of V :

STAB(G) := conv{1 S ∈ {0, 1} V : (S × S) ∩ E = ∅} Then we have α(G) = max{ i∈V x i : x ∈ STAB(G)} (2.3.7)
Lasserre hierarchy applies to the stable set problem, giving approximations of STAB(G). As a consequence of 2.3.7, it applies to bound the independence number. We are going to describe this last formulation. Given a finite set V , let V t denote the collection of subsets of V with cardinality t and V ≤t the collection of subsets of V with cardinality less or equal than t. The Lasserre hierarchy is based on moment matrices:

Definition 2.3.15. The moment matrix of a vector y ∈ R ( V ≤2t ) is the matrix M t (y) ∈ R ( V ≤t )×( V ≤t ) defined by: M t (y) I,J := y I∪J Definition 2.3.16. Given a graph G = (V, E), for any t ∈ N we define (t) (G) := sup i∈V y i : y ∈ R ( V ≤2t ) M t (y) 0 y ∅ = 1 y {i,j} = 0 if ij ∈ E (2.3.8)
The program 2.3.8 is called the t-th iterate (or step) of the Lasserre hierarchy for the stable set problem. It can be verified that (1) (G) = ϑ(G), so we can see (t) as a generalization of Lovász ϑ number. It is worth to notice that, for a feasible solution y, the second and fourth constraints imply that y I = 0 whenever I contains an edge. The next results show the interest of this hierarchy.

Lemma 2.3.17. For any t, α(G) ≤ (t) (G), with equality for t ≥ α(G).

Proof. For the first statement, it suffices to show that |S| ≤ (t) (G) whenever S ⊂ V is a stable set. For this, we fix S stable and we define a vector y S ∈ R ( V ≤2t ) by

(y S ) A := 1 if A ⊂ S 0 if not
Then M t (y S ) is positive semidefinite as it is a submatrix of y T S y S . The two last constraints are obviously verified. So y S is a feasible solution and i∈V (y S ) i = |S|. The second statement follows from the fact that the Lasserre hierarchy refines the Sherali-Adams hierarchy (see [START_REF] Laurent | A comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre relaxations for 0 -1 programming[END_REF] for details).

The following proposition is easy to establish. Proposition 2.3.18. For any t, (t+1) (G) ≤ (t) (G).

Remark 2.3.19. If in 2.3.8 we add the constraint that the entries of M t (y) are non negatives, then the new program

(t)
≥0 gives a stronger upper bound on the independence number of graphs. Moreover,

(1) ≥0 coincides with ϑ as defined in remark 2.3.8.

The hierarchy L t for the independence number

Note that the computation of 2.3.8 involves a matrix of size O(|V | t ) and O(|V | 2t ) variables. In [START_REF] Gvozdenovic | Block-diagonal semidefinite programming hierarchies for 0/1 programming[END_REF], the authors considered a less costly variation of the Lasserre hierarchy, denoted L t . Let us sketch their construction. As before, we restrict to the case of upper bounds on the independence number. We need to consider the following principal submatrices of moment matrices:

Definition 2.3.20. Given a vector y ∈ R ( V ≤2t
) and a subset T ⊂ V of cardinality |T | = t -1 we define the matrix M (T, y) as the principal submatrix of M t (y) whose rows and columns are indexed by the following set: S⊂T {S, S ∪ {i}} i∈V Note that to define M (T, y) for a set T of cardinality t -1, we use only the entries of y indexed by V ≤t+1 . Then we can define the new hierarchy:

Definition 2.3.21. Given a graph G = (V, E), for any t ∈ N we define

L t (G) := sup i∈V y i : y ∈ R ( V ≤t+1 ) M (T, y) 0 ∀ T ∈ V t-1 y ∅ = 1 y {i,j} = 0 if ij ∈ E (2.3.9)
The following properties are easily verified:

Proposition 2.3.22. For any graph G, for any t ∈ N, the number L t (G) has the following properties:

• for t = 1, L 1 (G) = (1) (G) = ϑ(G); • (t) (G) ≤ L t (G); • α(G) ≤ L t (G), with equality for t ≥ α(G); • L t+1 (G) ≤ L t (G).
So the bound on the independence number provided by this hierarchy is not as good as the one of Lasserre (t) but we note that the complexity has decreased. Indeed, the program 2.3.9 involves |V | t+1 (t+1)! + O(|V | t ) variables and (with some further manipulation)

2 t-1 |V | t-1 (t-1)! + O(|V | t-2
) matrices of size n + 1 (see [START_REF] Gvozdenovic | Block-diagonal semidefinite programming hierarchies for 0/1 programming[END_REF] for details).

Symmetrization and examples

To symmetrize a semidefinite program means to exploit its symmetries (coming from some group action) in order to obtain another program which is easier to compute and equivalent to the original one, in the sense that the symmetrization transforms feasible solutions in feasible solutions and leaves the objective value invariant. As a consequence, the symmetrized program will have the same optimal value as the original one. Consider the ϑ program (2.3.5). In order to be calculated explicitely for "big" graphs, ϑ needs to be defined by a less costly program. This can be done thanks to automorphisms of the graph and using tools from representation theory. We explain how in this final part of chapter 2, giving the link to one of the fundamental problems in coding theory. We follow [START_REF] Bachoc | Invariant semidefinite programs[END_REF], to which we refer for a more complete treatment of the subject. At the end, we sketch the block diagonalization of the Terwilliger algebra of the Hamming scheme, because we will need it in chapter 4. It was first obtained by Schrijver ([41]) in order to derive a bound for codes in the Hamming space which improves over Delsarte's one. Here we follow the equivalent reformulation in terms of group representations given in [START_REF] Vallentin | Symmetry in semidefinite programs[END_REF].

Symmetrization of the SDP defining ϑ

Fix a graph G = (V, E) and a subgroup G of its automorphism group. The group G acts on R V ×V by (g.F )(x, y) = F (g -1 .x, g -1 .y). The program 2.3.5 is invariant under this action: this means that for all g ∈ G and for all feasible solution F , g.F is still feasible and it has the same objective value as F . It follows that 2.3.5 has an optimal solution which is G-invariant. In order to prove this, remark that starting from a feasible F , we can build its average over G,

1 |G| g∈G g.F ,
which is feasible, G-invariant and with the same objective value as F . It follows that the original program is equivalent to the one where the constraint that F is

G-invariant is added. A G-invariant function satisfies F (x, y) = F (g.x, g.y) for every g ∈ G and so it takes constant values f 1 , . . . , f m on the orbits V 1 , . . . , V m of G on pairs of elements of V . Assume that V 1 ∪ • • • ∪ V = {(x, x) : x ∈ V }.
Then the program 2.3.5 is equivalent to the following one:

max{ m i=1 |V i |f i : F ∈ (R V ×V ) G , F 0 i=1 |V i |f i = 1 f i = 0 if V i ⊂ E } (2.4.1)
where (R V ×V ) G denotes the G-invariant real matrices. The space of G-invariant complex matrices (C V ×V ) G is a matrix * -algebra, i.e. a vector space which is closed under taking conjugate transpose and under multiplication. Note that I ∈ (C V ×V ) G . Then the Artin-Wedderburn theorem says that (C V ×V ) G is isomorphic to a direct sum of matrix algebras

ϕ : (C V ×V ) G -→ d k=1 C m k ×m k F -→ (F k ) d k=1
The isomorphism ϕ preserves eigenvalues and hence positive semidefiniteness. The matrix ϕ(F ) is in block diagonal form, so

F 0 ⇔ ϕ(F ) 0 ⇔ F k 0 ∀ k = 1, . . . , d .
The advantage of considering the matrices F k is that it is computationally easier to solve a SDP program involving several smaller blocks than a SDP program involving one large matrix. Now we sketch a general method to construct such an isomorphism. Consider the space C V with the action of G given by (g.f )(x) = f (g -1 .x) and the G-invariant

inner product f, f := 1 |V | x∈V f (x)f (x)
. This gives a representation of G which we can decompose in irreducibles

C V = H 1,1 ⊥ • • • ⊥ H 1,m 1 ⊥ • • • ⊥ H d,1 ⊥ • • • ⊥ H d,
× m k matrices E k (x, y) with coefficients E k,i,j (x, y): E k,i,j (x, y) := d k s=1 e k,i,s (x)e k,j,s (y) (2.4.2)
These matrices are sometimes called zonal matrices to say that they are G-invariant. Moreover, it can be proven that the matrices E k,i,j form a basis of the algebra of G-invariant matrices, hence

F ∈ (C V ×V ) G ⇔ F (x, y) = k F k , E k (x, y)
and sending F to (F k ) d k=1 gives the announced isomorphism. The theorem which characterizes positive definite G-invariant functions is known as Bochner theorem: Theorem 2.4.1 ([11]). A function F ∈ C V ×V is G-invariant and positive semidefinite if and only if it can be written as

F (x, y) = d k=1 F k , E k (x, y) (2.4.3)
where

F k ∈ C m k ×m k is hermitian positive semidefinite.
Note that the entries of each F k can be written as the scalar product of F and E k,i,j , so that they can be expressed as a function of the variables

y i := |V i |f i . Once this description is obtained, program 2.3.5 becomes max{ m i=1 y i : F k 0 ∀ k = 1, . . . , d i=1 y i = 1 y i = 0 if V i ⊂ E } (2.4.4)
The size of the program has been reduced from |V | 2 variables to m = d k=1 (m k ) 2 . Remark 2.4.2. Of course, in 2.4.4 we consider only the F k such that the corresponding F has real entries. Whenever the group G has only real representations, we can start from decomposing R V and work only in the real case.

Application to coding theory

A code C is a subset of a metric space (X, d). The minimum distance of C, denoted d(C) is the least value of pairwise distances of elements of C. The classic framework is that of the (binary) Hamming space H n = {0, 1} n , i.e. the n-tuples of 0 -1 words, together with the Hamming distance

d(x, y) := |{1 ≤ i ≤ n : x i = y i }|
The Hamming weight of a word x is defined as |x| := d(x, 0 n ). A scalar product is defined on H n by x.y := n i=1 x i y i mod 2. The cardinality of the intersection of the support of x and the support of y is denoted |x ∩ y|.

Intuitively, as the cardinality of a code grows, its minimum distance decreases. So it is interesting to study the number A(X, d) := max{|C| : C ⊂ X, d(C) = d}, the maximal cardinality of a code of X with prescribed minimum distance d. The determination of this number is hard, so the goal is usually to find lower and upper bounds on it. While lower bounds mainly come from explicit constructions, upper bounds need to be set up by theoretical arguments. One of the best upper bounds for binary Hamming codes was established by Delsarte and it is obtained as the optimal value of a linear program.

Theorem 2.4.3. (Delsarte linear programming upper bound, [START_REF] Delsarte | An algebraic approach to the association schemes of coding theory[END_REF])

A(H n , d) ≤ sup 1 + n i=1 x i : x i ≥ 0 x 1 = • • • = x d-1 = 0 1 + n i=1 x i K k (i) ≥ 0 ∀ k = 0, . . . , n (2.4.5)
where K k are the Krawtchouk polynomials defined by

K k (i) = k j=0 (-1) j i j n -i k -j
Lovász ϑ program applies to bound the maximal cardinality A(X, d) of codes in a metric space X with prescribed minimal distance d. Indeed A(X, d) = α(G) where G is the graph with vertex set X and edges set {xy : 0 < d(x, y) < d}. So, we obtain Theorem 2.4.4. (The semidefinite programming bound for codes)

A(X, d) ≤ sup X 2 F (x, y) : F ∈ R X×X , F 0, F ≥ 0, X F (x, x) = 1 F (x, y) = 0 if 0 < d(x, y) < d (2.4.6) A(X, d) ≤ inf t/λ : F ∈ R X×X , F -λ 0 F (x, x) ≤ t for all x ∈ X F (x, y) ≤ 0 if d(x, y) ≥ d (2.4.7)
The second inequality (2.4.7) is obtained with the dual formulation of the semidefinite program (2.4.6). It should be noted that any feasible solution of the semidefinite program in (2.4.7) leads to an upper bound for A(X, d).

Most of the spaces occurring in coding theory are of exponential size but they are endowed with group actions which allow to reduce the size of the SDP above. The Hamming space is endowed with the Aut(H n ) = T S n action, where T (H n , +) acts by translations and S n by permuting the coordinates. It was first recognized in [START_REF] Mceliece | The Lovász bound and some generalizations[END_REF] and [START_REF] Schrijver | A comparison of the Delsarte and Lovász bound[END_REF] that in the Hamming space, the program 2.4.6 symmetrized by the T S n action coincides with the Delsarte linear program 2.4.5. As an application of the method introduced in section 2.4.1, we sketch the symmetrization process.

Let X denote H n . The program 2.4.6 is invariant for the action of G := T S n and thus we can restrict to G-invariant functions F . As the G-orbits of pairs are characterized by the pairwise distance, such F satisfies

F (x, y) = F (d(x, y))
and takes n + 1 values f 0 , f 1 , . . . , f n on the respective orbits. Then we can immediately translate the program 2.4.6, except for the semidefiniteness constraint which we analyse separately. Indeed, the values of the function verify:

f 0 = 1 |X| f 1 = • • • = f d-1 = 0 f d , . . . , f n ≥ 0
and the objective function writes as

|X|f 0 + n i=1 |V i |f i = 1 + n i=1 |V i |f i
where

V i := {(x, y) ∈ X × X : d(x, y) = i}.
The set of irreducible characters {χ z : z ∈ H n } is an orthonormal basis of C X . Remember that these characters are given by χ z (x) := (-1) z.x . Putting together characters where z has the same weight, we obtain

C X = P 0 ⊕ P 1 ⊕ • • • ⊕ P n (2.4.8)
where

P k := |z|=k Cχ z is G-irreducible of dimension n k .
Next, we build the zonal functions. As the decomposition 2.4.8 is multiplicity free, the zonal functions are 1 × 1-matrices. They are given by:

E k (x, y) := |z|=k χ z (x)χ z (y) Denote K k (d(x, y)) := E k (x, y).
The function K k is well defined and it can be proved that it is a polynomial of degree k. Explicitely:

K k (i) = k j=0 (-1) j i j n -i k -j
Then we know, by theorem 2.4.1, that F is positive semidefinite if and only if it writes as a linear combination of the functions K k with positive coefficients. These coefficients are given by

1 |X| 2 (x,y)∈X F (x, y)K k (d(x, y)) = 1 |X| 2 n i=0 |V i |f i K k (i) Now, calling x i = |V i |f i we find exactly program 2.4.5.
Indeed, it is a general fact that for 2-point homogeneous spaces, the program ϑ after symmetrization, reduces to a linear program where different families of orthogonal polynomials come into play. Here, a 2-point homogeneous space is a metric space (X, d) on which a group G acts transitively and such that the orbits on pairs are parametrized by the distance, i.e. (x, y) ∼ G (x , y ) ⇔ d(x, y) = d(x , y ).

Apart from the Hamming space, another example of 2-point homogeneous space is given by the binary Johnson space J w n , defined as the set of 0 -1 words with Hamming weight w, together with the action of the symmetric group S n .

Block diagonalization of the Terwilliger algebra of H n

The reduction of the ϑ program for the Hamming space amounts to block diagonalize the algebra (C Hn×Hn ) Aut(Hn) . In this section we replace Aut(H n ) with one of its stabilizer subgroups, namely S n = Stab Aut(Hn) (0 n ). The algebra (R Hn×Hn ) Sn coincides with the so called Terwilliger algebra of H n . Its block diagonalization is originally contained in the paper of Schrijver, [START_REF] Schrijver | New code upper bounds from the Terwilliger algebra and semidefinite programming[END_REF], where it is applied in order to obtain improvements on Delsarte LP bound. Here we adopt an equivalent point of view, but different from Schrijver's original one, which allows us to use the framework introduced in section 2.4.1. For notations and main results we follow [START_REF] Vallentin | Symmetry in semidefinite programs[END_REF] and the references therein. The decomposition 2.4.9 and the link with Hahn polynomials were proven by Delsarte in [START_REF] Delsarte | Hahn polynomials, discrete harmonics and t-designs[END_REF]. Take the notation X := H n . The space X splits into the S n -orbits X 0 , . . . , X n , where X w = J w n is the Johnson space. Hence

R X = R X 0 ⊕ R X 1 ⊕ • • • ⊕ R Xn
The irreducible modules for the action of the symmetric group on n elements are the Specht modules S λ . They are indexed by partitions λ of n. The following decomposition is a classical fact:

R Xw = H 0,w ⊕ • • • ⊕ H w,w if 0 ≤ w ≤ n/2 H 0,w ⊕ • • • ⊕ H n-w,w else (2.4.9)
where

H k,w := S (n-k,k) is of dimension d k := n k -n k-1 . The isotypic components of R X are I k := H k,k ⊕ • • • ⊕ H k,n-k H m k k,k
for k = 0, . . . , n/2 . Here the multiplicity is given by m k := n -2k + 1. Now, let {e kk1 , . . . , e kkd k } be an orthonormal basis of H k,k . Applying the valuation operator

ψ k,i : R X k -→ R X i f -→ [ x → {f (y) : |y| = k, y ⊂ x} ]
we obtain an orthogonal basis {e ki1 , . . . , e kid k } of H k,i , whenever i > k (see [START_REF] Delsarte | Hahn polynomials, discrete harmonics and t-designs[END_REF]).

To each isotypic component we associate the zonal matrix E k ∈ R m k ×m k as explained in 2.4.2:

E k,i,j (x, y) := 1 |X| d k =1
e ki (x)e kj (y)

The zonal matrices have an explicit description in terms of Hahn polynomials.

Definition 2.4.5. The Hahn polynomials associated to the parameters n, i, j with 0 ≤ i ≤ j ≤ n are the polynomials Q k (n, i, j; z) with 0 ≤ k ≤ min(i, n -j) uniquely determined by the properties:

• Q k has degree k in the variable z

• They are orthogonal polynomials for the weights

0 ≤ h ≤ i w(n, i, j; h) = i h n -i j -i + h • Q k (0) = 1. Theorem 2.4.6. If k ≤ i ≤ j ≤ n -k, |x| = i, |y| = j, we have E k,i,j (x, y) = |X| j-k i-k n-2k j-k n j j i Q k (n, i, j; i -|x ∩ y|) If |x| = i or |y| = j then E k,i,j (x, y) = 0.
This explicit description along with Bochner theorem 2.4.1 gives a block diagonalization of the algebra of S n -invariant matrices, together with a description of those who are positive semidefinite.

Chapter 3

Bounds for projective codes from semidefinite programming

Introduction

In network coding theory, as introduced in [3], some information is transmitted through a network (i.e. a directed graph), possibly having several sources and several receivers, and a certain number of intermediate nodes. Such information is modeled as vectors of fixed length over a finite field F q , called packets. To improve the performance of the communication, intermediate nodes should forward random linear F q -combinations of the packets they receive. This is the approach taken in the non-coherent communication case, that is, when the structure of the network is not known a priori [START_REF] Ho | The benefits of coding over routing in a randomized setting[END_REF]. Hence, if no errors occur, what is globally preserved all along the network is the vector space spanned by the packets injected at the sources. This observation led Koetter and Kschischang [START_REF] Koetter | Coding for errors and erasures in random network coding[END_REF] to model network codes as subsets of the projective space P(F n q ), the set of linear subspaces of F n q , or of the Grassmann space G q (n, k), the subset of those subspaces of F n q having dimension k. Subsets of P(F n q ) are called projective codes while subsets of the Grassmann space will be referred to as constant-dimension codes or Grassmann codes.

As usual in coding theory, in order to protect the system from errors, it is desirable to select the elements of the code so that they are pairwise as far as possible with respect to a suitable distance. The subspace distance defined by

d S (U, V ) = dim(U + V ) -dim(U ∩ V ) = dim U + dim V -2 dim(U ∩ V )
was introduced in [START_REF] Koetter | Coding for errors and erasures in random network coding[END_REF] for this purpose. It is then natural to ask how large a code with a given minimal distance can be. Formally, we define

   A q (n, d) := max{|C| : C ⊂ P(F n q ), d S (C) ≥ d} A q (n, k, 2δ) := max{|C| : C ⊂ G q (n, k), d S (C) ≥ 2δ} 29
where d S (C) denotes the minimal subspace distance among distinct elements of a code C. In this chapter we will discuss upper estimates for these numbers.

The Grassmann space G q (n, k) is a homogeneous space under the action of the linear group GL n (F q ). Moreover, this group acts distance transitively when this space is endowed with the subspace distance. We mean here that the orbits of GL n (F q ) acting on pairs of elements of G q (n, k) are characterized by the value that this distance takes on them; in other words the Grassmann space is 2-point homogeneous under this action. Due to this property, codes and designs in this space can be analysed in the framework of Delsarte theory, in the same way as for other classical spaces in coding theory such as the Hamming space and the binary Johnson space. In fact, G q (n, k) turns out to be a q-analog in the sense of combinatorics of the binary Johnson space as shown in [START_REF] Delsarte | Hahn polynomials, discrete harmonics and t-designs[END_REF]. The linear group plays the role of the symmetric group for the Johnson space, while the dimension replaces the weight function.

Unsurprisingly, the classical bounds (anticode, Hamming, Johnson, Singleton) have been derived for the Grassmann codes [START_REF] Koetter | Coding for errors and erasures in random network coding[END_REF][START_REF] Wang | Linear authentication codes: bounds and constructions[END_REF][START_REF] Xia | Johnson type bounds on constant dimension codes[END_REF]. The more sophisticated Delsarte linear programming bound was already obtained in [START_REF] Delsarte | Hahn polynomials, discrete harmonics and t-designs[END_REF]; however numerical computations indicate that it is not better than the anticode bound. Moreover, the Singleton and anticode bounds have the same asymptotic which is attained by a family of Reed-Solomon like codes built in [START_REF] Koetter | Coding for errors and erasures in random network coding[END_REF] and closely connected to the rankmetric Gabidulin codes.

In contrast, the projective space has a much nastier behaviour, essentially because it is not 2-point homogeneous, in fact not even homogeneous under the action of a group. For example, the balls in this space have a size that depends not only on their radius, but also on the dimension of their center. Consequently, bounds for projective codes are much harder to settle. Etzion and Vardy in [START_REF] Etzion | Error-correcting codes in projective space[END_REF] provide a bound in the form of the optimal value of a linear program, which is derived by elementary reasoning involving packing issues. The Etzion-Vardy bound is the only successful generalization of the classical bounds to the projective space.

In this chapter we settle semidefinite programming bounds for projective codes and we compare them with the above mentioned bounds. For the projective space, the symmetrization was announced in [START_REF] Bachoc | More semidefinite programming bounds[END_REF] (see also [START_REF] Bachoc | Applications of semidefinite programming to coding theory[END_REF]). The program remains a semidefinite program but fortunately with polynomial size.

This chapter is organized as follows. In Section 2 we review the classical bounds for constant dimension codes and the Etzion-Vardy bound for projective codes. In Section 3 we show that most of the bounds for Grassmann codes can be derived from the semidefinite programming method. In Section 4 we reduce the ϑ program by the action of the group GL n (F q ). In Section 5 we present some numerical results obtained with this method and we compare them with the Etzion-Vardy method for q = 2 and n ≤ 16. Another distance of interest on the projective space, the so-called injection distance was introduced in [START_REF] Kschischang | On metrics for error correction in network coding[END_REF]. We show how to adapt the Etzion-Vardy bound as well as the semidefinite programming bound to this case.

Elementary bounds for Grassmann and projective codes

Bounds for Grassmann codes

In this section we review the classical bounds for A q (n, k, 2δ). We note that the subspace distance takes only even values on the Grassmann space and that one can restrict to k ≤ n/2 by the relation A q (n, k, 2δ) = A q (n, n -k, 2δ), which follows by considering orthogonal subspaces.

We recall the definition of the q-analog of the binomial coefficient that counts the number of k-dimensional subspaces of a fixed n-dimensional space over F q , i.e. the number of elements of G q (n, k). Definition 3.2.1. The q-ary binomial coefficient is defined by

n k q = (q n -1) . . . (q n-k+1 -1) (q k -1) . . . (q -1)
The sphere-packing bound [29]

A q (n, k, 2δ) ≤ |G q (n, k)| |B k (δ -1)| = n k q (δ-1)/2 m=0 k m q n-k m q q m 2 .
(3.2.1)

It follows as usual from the observation that the balls of radius δ -1 centered at the elements of a code C ⊂ G q (n, k) with minimal distance 2δ, are pairwise disjoint, and have the same cardinality

(δ-1)/2 m=0 k m q n-k m q q m 2 .

The Singleton bound [29]

A q (n, k, 2δ) ≤ n -δ + 1 k -δ + 1 q . (3.2.2)
It is obtained by the introduction of a "puncturing" operation on the code.

The anticode bound [48]

An anticode of diameter e is a subset of a metric space whose pairwise distinct elements are at distance less or equal than e. The general anticode bound ( [START_REF] Delsarte | An algebraic approach to the association schemes of coding theory[END_REF]) states that, given a metric space X which is homogeneous under the action of a group G, for every code C ⊂ X with minimal distance d and for every anticode A ∈ X of diameter d -1, we have

|C| ≤ |X| |A| .
Spheres of given radius r are one example of anticodes of diameter 2r: indeed if we take A to be a sphere of radius δ -1 in G q (n, k), we recover the sphere-packing bound.

Obviously, to obtain the strongest bound, we have to choose the largest anticodes of given diameter, which in our case are not the spheres. The largest anticode A of diameter 2δ -2 in the finite Grassmannian was described in [START_REF] Frankl | The Erdos-Ko-Rado theorem for vector spaces[END_REF]: it consists of all elements of G q (n, k) which contain a fixed (δ -1)-dimensional subspace. Taking such A in the general anticode bound, we recover the (best) anticode bound for G q (n, k):

A q (n, k, 2δ) ≤ n k -δ + 1 q k k -δ + 1 q = (q n -1)(q n-1 -1) . . . (q n-k+δ -1) (q k -1)(q k-1 -1) . . . (q δ -1) (3.2.3)
It follows from the previous discussion that the anticode bound improves the spherepacking bound. Moreover, the anticode bound is usually stronger than the Singleton bound, with equality only in the cases n = k or δ = 1 ( [START_REF] Xia | Johnson type bounds on constant dimension codes[END_REF]).

The first and second Johnson-type bound [49]

A q (n, k, 2δ) ≤ (q n -1)(q k -q k-δ ) (q k -1) 2 -(q n -1)(q k-δ -1) (3.2.4) as long as (q k -1) 2 -(q n -1)(q k-δ -1) > 0, and

A q (n, k, 2δ) ≤ q n -1 q k -1 A q (n -1, k -1, 2δ) . (3.2.5)
These bounds were obtained in [START_REF] Xia | Johnson type bounds on constant dimension codes[END_REF] through the construction of a binary constantweight code associated to every constant-dimension code. Iterating the latter, one obtains

A q (n, k, 2δ) ≤ q n -1 q k -1 q n-1 -1 q k-1 -1 . . . q n-k+δ -1 q δ -1 . . . . (3.2.6)
If the floors are removed from the right hand side of (3.2.6), the anticode bound is recovered, so (3.2.6) is stronger. In the particular case of δ = k and if n ≡ 0 mod k, (3.2.6) was sharpened in [START_REF] Etzion | Error-correcting codes in projective space[END_REF] to:

A q (n, k, 2k) ≤ q n -1 q k -1 -1 (3.2.7)
In contrast, for δ = k and if k divides n, we have equality in (3.2.6), because of the existence of spreads (see [START_REF] Etzion | Error-correcting codes in projective space[END_REF]):

A q (n, k, 2k) = q n -1 q k -1
Summing up, the strongest upper bound for constant dimension codes reviewed so far comes by putting together (3.2.6) and (3.2.7):

Theorem 3.2.2. If n -k ≡ 0 mod δ, then A q (n, k, 2δ) ≤ q n -1 q k -1 . . . q n-k+δ+1 -1 q δ+1 -1 q n-k+δ -1 q δ -1 -1 . . . otherwise A q (n, k, 2δ) ≤ q n -1 q k -1 . . . q n-k+δ+1 -1 q δ+1 -1 q n-k+δ -1 q δ -1 . . . .

A bound for projective codes

Here we turn our attention to codes whose codewords have not necessarily the same dimension, and we review the bound obtained by Etzion and Vardy in [START_REF] Etzion | Error-correcting codes in projective space[END_REF] for these codes. The idea is to split a code C into subcodes C k = C ∩ G q (n, k) of constant dimension, and then to design linear constraints on the cardinality D k of each C k , coming from packing constraints. Let B(V, e) := {U ∈ P(F n q ) : d S (U, V ) ≤ e} denote the ball of center V and radius e. If dim V = i, we have that

|B(V, e)| = e k=0 k j=0 i j q n -i k -j q q j(k-j)
We define c(i, k, e)

:= |B(V, e) ∩ G q (n, k)| for V of dimension i. It is not difficult to prove that c(i, k, e) = min{k,i} j= i+k-e 2 i j q n -i k -j q q (i-j)(k-j) . (3.2.8)
Theorem 3.2.3 (Linear programming upper bound for codes in P(F n q ), [START_REF] Etzion | Error-correcting codes in projective space[END_REF]).

A q (n, 2e + 1) ≤ sup n k=0

x k :

x k ≤ A q (n, k, 2e + 2) ∀ k = 0, . . . , n n i=0 c(i, k, e)x i ≤ n k q ∀ k = 0, . . . , n
Proof. For C ⊂ P(F n q ) of minimal distance 2e + 1, define D 0 , . . . , D n by D k = |C ∩ G q (n, k)|. Then n k=0 D k = |C| and each D k represents the cardinality of a subcode of C of constant dimension k, so it is upper bounded by A q (n, k, 2e + 2). Moreover, balls of radius e centered at the codewords are pairwise disjoint, so the sets B(V, e) ∩ G q (n, k) for V ∈ C are pairwise disjoint subsets of G q (n, k). So

V ∈C |B(V, e) ∩ G q (n, k)| ≤ |G q (n, k)|.
Because the number of elements of B(V, e) ∩ G q (n, k) only depends on i = dim(V ), k and e and equals c(i, k, e) by definition, we obtain the second constraint

n i=0 c(i, k, e)D i ≤ n k q .
So |C| is upper bounded by the optimal value of the announced linear program in real variables x i .

Remark 3.2.4. Of course, in view of explicit computations, if the exact value of A q (n, k, 2e + 2) is not available, it can be replaced in the linear program of Theorem 3.2.3 by an upper bound.

The semidefinite programming method on the Grassmannian

The Grassmann space G q (n, k) is 2-point homogeneous for the action of G = GL n (q) and its associated zonal polynomials are computed in [START_REF] Delsarte | Hahn polynomials, discrete harmonics and t-designs[END_REF]. They belong to the family of q-Hahn polynomials, which are q-analogs of the Hahn polynomials related to the binary Johnson space and introduced in definition 2.4.5.

Definition 3.3.1. The q-Hahn polynomials associated to the parameters n, s, t with 0 ≤ s ≤ t ≤ n are the polynomials Q k (n, s, t; u) with 0 ≤ k ≤ min(s, n -t) uniquely determined by the properties:

• Q k has degree k in the variable [u] = q 1-u u 1 q
• They are orthogonal polynomials for the weights

0 ≤ i ≤ s w(n, s, t; i) = s i q n -s t -s + i q q i(t-s+i) • Q k (0) = 1.
To be more precise, in the Grassmann space G q (n, k), the zonal polynomials are associated to the parameters s = t = k. The other parameters will come into play when we will analyse the full projective space in Section 4. The resulting linear programming bound is explicitly stated in [START_REF] Delsarte | Hahn polynomials, discrete harmonics and t-designs[END_REF]: Theorem 3.3.2. (Delsarte's linear programming bound [START_REF] Delsarte | Hahn polynomials, discrete harmonics and t-designs[END_REF]).

A q (n, k, 2δ) ≤ inf 1 + f 1 + • • • + f k : f i ≥ 0 ∀ i = 1, . . . , k F (u) ≤ 0 ∀ u = δ, . . . , k where F (u) = 1 + k i=1 f i Q i (u) and Q i (u) = Q i (n, k, k; u) as in Definition 3.3.1.

Bounds for Grassmann codes

In order to show the power of the semidefinite programming bound, we will verify that most of the bounds recalled in section 3.2 for Grassmann codes can be obtained from Corollary 2.4.4 or Theorem 3.3.2. To that end, in each case we construct a suitable feasible solution of (2.4.7).

The Singleton bound.

The function

F (x, y) = dim(z)=n-δ+1 w⊂z, dim(w)=k-δ+1 1(z ∩ x = w)1(z ∩ y = w)
where x → 1(z ∩ x = w) denotes the characteristic function of the set {x ∈ G q (n, k) : z ∩ x = w}, is obviously positive semidefinite. One can verify that F is a feasible solution of (2.4.7) and leads to the Singleton bound (3.2.2).

The sphere-packing and anticode bounds.

The sphere-packing bound and the anticode bound in G q (n, k) can also be obtained directly, with the functions

F (x, y) = dim(z)=k 1 B(z,δ-1) (x)1 B(z,δ-1) (y) and F (x, y) = dim(z)=k-δ+1 1(z ⊂ x)1(z ⊂ y) .
In general, the anticode bound |C| ≤ |X|/|A| can be derived from (2.4.7), using the function F (x, y) = g∈G 1 A (g.x)1 A (g.y).

Remark 3.3.3. An interesting open point is to prove whether or not the anticode bound coincides with the Delsarte bound for constant dimension codes. We already proved one inequality and in our numerical computations the two bounds give the same value for several different parameters.

The first Johnson-type bound.

We want to apply Delsarte's linear programming bound of Theorem 3.3.2 with a function F of degree 1, i.e.

F (u) = f 0 Q 0 (u) + f 1 Q 1 (u).
According to [START_REF] Delsarte | Hahn polynomials, discrete harmonics and t-designs[END_REF] the first q-Hahn polynomials are

Q 0 (u) = 1 , Q 1 (u) = 1 - (q n -1)(1 -q -u ) (q k -1)(q n-k -1) .
In order to construct a feasible solution of the linear program, we need a pair (f 0 , f 1 ) of positive numbers for which

F (u) = f 0 + f 1 Q 1 (u) is non-positive for u = δ, . . . , k.
Then 1 + f 1 /f 0 will be an upper bound for A q (n, k, 2δ). As Q 1 (u) is decreasing, the optimal choice of (f 0 , f 1 ) satisfies F (δ) = 0. So f 1 /f 0 = -1/Q 1 (δ) and we need Q 1 (δ) < 0. We obtain (3.2.4):

A q (n, k, 2δ) ≤ 1 + f 1 f 0 = 1 - 1 Q 1 (δ) = (q n -1)(q k -q k-δ ) (q k -1) 2 -(q n -1)(q k-δ -1)
.

The second Johnson-type bound.

Here we recover an inequality on the optimal value B q (n, k, 2δ) of (2.4.7) in the case X = G q (n, k) (with the subspace distance) which is similar to (3.2.5):

B q (n, k, 2δ) ≤ q n -1 q k -1 B q (n -1, k -1, 2δ).
Let (F, t, λ) be an optimal solution for the program (2.4.7) in G q (n -1, k -1) relative to the minimal distance 2δ, i.e. F satisfies the conditions: F λ, F (x, x) ≤ t, F (x, y) ≤ 0 if d(x, y) ≥ 2δ, and moreover t/λ = B q (n -1, k -1, 2δ).

We consider the function G on G q (n, k) × G q (n, k) given by

G(x, y) = |D|=1 1(D ⊂ x)1(D ⊂ y)F (x ∩ H D , y ∩ H D )
where, for every one-dimensional space D, H D is an arbitrary hyperplane such that D ⊕ H D = F n q . It can be verified that the function G is a feasible solution of the program (2.4.7) in G q (n, k) for the minimal distance 2δ, and we obtain that

B q (n, k, 2δ) ≤ t λ q n -1 q k -1 = q n -1 q k -1 B q (n -1, k -1, 2δ) .
Remark 3.3.4. in [START_REF] Etzion | Error-correcting codes in projective space[END_REF], another Johnson-type bound is given:

A q (n, k, 2δ) ≤ q n -1 q n-k -1 A q (n -1, k, 2δ) .
which follows easily from the second Johnson-type bound combined with the equality A q (n, k, 2δ) = A q (n, n -k, 2δ). Similarly as above, one can show that an analogous inequality holds for the semidefinite programming bounds.

Semidefinite programming bounds for projective codes

In this section we reduce the semidefinite programs (2.4.6), (2.4.7) for the entire projective space, using the action of the group G = GL n (F q ). We follow the general method described in section 2.4.1. As we saw, the semidefinite program can be restricted to G-invariant functions F . It remains to obtain an explicit description of the G-invariant positive semidefinite functions on the projective space. The projective space endowed with the G action is the q-analog of the Hamming space where the action is restricted to S n . So the symmetrization process is analog to the one given in section 2.4.3. Indeed, in [START_REF] Delsarte | Hahn polynomials, discrete harmonics and t-designs[END_REF], Delsarte treats the two cases in a common framework.

The G-invariant positive semidefinite functions on the projective space

In order to obtain a suitable expression for these functions, we exploit the decomposition of the space of real-valued functions under the action of G. We take the following notations: let X = P(F n q ), X k = G q (n, k) and let R X = {f : X → R}. In the paper [START_REF] Delsarte | Hahn polynomials, discrete harmonics and t-designs[END_REF], Delsarte showed that the irreducible decomposition of the R X k under the action of G is given by the harmonic subspaces H k,i :

R X k = H 0,k ⊕ H 1,k ⊕ • • • ⊕ H min{k,n-k},k (3.4.1)
Here, H k,k is the kernel of the differentiation operator

δ k : R X k -→ R X k-1 f -→ [ x → {f (y) : |y| = k, x ⊂ y} ]
and H k,i is the image of H k,k under the valuation operator

ψ ki : R X k -→ R X i f -→ [ x → {f (y) : |y| = k, y ⊂ x} ] for k ≤ i ≤ n -k. Because δ k is surjective, we have h k := dim(H k,k ) = n k q -n k-1 q
. Moreover, ψ ki commutes with the action of G so H k,i is isomorphic to H k,k . Putting together the spaces R X k one gets the global picture:

R X = R X 0 ⊕ R X 1 ⊕ . . . ⊕ R X n 2 ⊕ . . . ⊕ R X n-1 ⊕ R Xn I 0 = H 0,0 ⊕ H 0,1 ⊕ . . . . . . . . . ⊕ H 0,(n-1) ⊕ H 0,n I 1 = H 1,
I n 2 = H n 2 , n 2
Here, the columns give the irreducible decomposition (3.4.1) of the spaces R X k . The irreducible components which lie in the same row are all isomorphic, and together they form the isotypic components

I k := H k,k ⊕ H k,k+1 ⊕ • • • ⊕ H k,n-k H n-2k+1 k,k
.

Starting from this decomposition, we build the zonal matrices E k (x, y) [6, section 3.3] in the following way. We take an isotypic component I k and we fix an orthonormal basis (e kk1 , . . . , e kkh k ) of H k,k . Applying the valuation operator ψ ki , we get an orthogonal basis (e ki1 , . . . , e kih k ) of H k,i . Then we define

E kst (x, y) = 1 h k h k i=1
e ksi (x)e kti (y) .

Theorem 2.4.1 gives the expression of the G-invariant positive semidefinite functions in terms of the matrices E k (x, y):

Theorem 3.4.1. The function F ∈ R X×X is

positive semidefinite and G-invariant if and only if it can be written as

F (x, y) = n/2 k=0 F k , E k (x, y) (3.4.2)
where F k ∈ R (n-2k+1)×(n-2k+1) and F k is positive semidefinite.

Now we need to compute the E k 's. They are zonal matrices: in other words, for all k ≤ s, t ≤ n -k, for all g ∈ G, E kst (x, y) = E kst (gx, gy). This means that E kst is actually a function of the variables which parametrize the orbits of G on X × X. It is easy to see that the orbit of the pair (x, y) is characterized by the triple (dim(x), dim(y), dim(x ∩ y)).

The next theorem gives an explicit expression of E kst , in terms of the polynomials

Q k of Definition 3.3.1. Theorem 3.4.2. If k ≤ s ≤ t ≤ n -k, dim(x) = s, dim(y) = t, E kst (x, y) = |X| t-k s-k q n-2k t-k q n t q t s q q k(t-k) Q k (n, s, t; s -dim(x ∩ y)) If dim(x) = s or dim(y) = t, E kst (x, y) = 0.
We note that the weights involved in the orthogonality relations of the polynomials Q k have a combinatorial meaning: Lemma 3.4.3. [START_REF] Dunkl | An addition theorem for some q-Hahn polynomials[END_REF] Given x ∈ X s , the number of elements y ∈ X t such that dim(x ∩ y) = s -i is equal to w(n, s, t; i).

Proof. (of Theorem 3.4.2) By construction, E kst (x, y) = 0 only if dim(x) = s and dim(y) = t, so in this case E kst is a function of (sdim(x ∩ y)). Accordingly, for k ≤ s ≤ t ≤ n -k, we introduce P k,s,t such that E k,s,t (x, y) = P k,s,t (sdim(x ∩ y)). Now we want to relate P k,s,t to the q-Hahn polynomials. We start with two lemmas: one obtains the orthogonality relations satisfied by P k,s,t and the other computes P k,s,t (0).

Lemma 3.4.4. With the above notations,

P k,s,t (0) = dim(x) t-k s-k q n-2k t-k q n t q t s q q k(t-k) .
(3.4.3)

Proof. We have P k,s,t (0) = E k,s,t (x, y) for all x, y with dim(x) = s, dim(y) = t, x ⊂ y.

Hence

P k,s,t (0) = 1 n t q t s q dim(x)=s dim(y)=t x⊂y E k,s,t (x, y) = 1 n t q t s q dim(x)=s dim(y)=t x⊂y 1 h k h k i=1 e k,s,i (x)e k,t,i (y) = 1 n t q t s q 1 h k h k i=1 dim(y)=t dim(x)=s x⊂y e k,s,i (x) e k,t,i (y) = 1 n t q t s q 1 h k h k i=1 dim(y)=t ψ s,t (e k,s,i )(y)e k,t,i (y) With the relation ψ s,t • ψ k,s = t-k s-k q ψ k,t , ψ s,t (e k,s,i ) = ψ s,t • ψ k,s (e k,k,i ) = t -k s -k q ψ k,t (e k,k,i ) = t -k s -k q e k,t,i ,
and we obtain

P k,s,t (0) = 1 n t q t s q 1 h k h k i=1 dim(y)=t t -k s -k q e k,t,i (y)e k,t,i (y) = t-k s-k q n t q t s q 1 h k h k i=1 |X|(e k,t,i , e k,t,i ) = |X| t-k s-k q n-2k t-k q n t q t s q q k(t-k)
where the last equality follows from [15, Theorem 3].

Lemma 3.4.5. With the above notations,

s i=0 w(n, s, t; i)P k,s,t (i)P l,s,t (i) = δ k,l |X| 2 n-2k s-k q n-2k t-k q q k(s+t-2k) n s q h k . (3.4.4)
Proof. We compute Σ := y∈X E k,s,t (x, y)E l,s ,t (y, z).

Σ = y∈X 1 h k h k i=1 1 h l h l j=1 e k,s,i (x)e k,t,i (y)e l,s ,j (y)e l,t ,j (z) = 1 h k h k i=1 1 h l h l j=1 e k,s,i (x)e l,t ,j (z) y∈X e k,t,i (y)e l,s ,j (y) = 1 h k h k i=1 1 h l h l j=1 e k,s,i (x)e l,t ,j (z)|X|(e k,t,i , e l,s ,j ) = 1 h k h k i=1 1 h l h l j=1 e k,s,i (x)e l,t ,j (z)|X| n -2k t -k q q k(t-k) δ k,l δ t,s δ i,j = δ k,l δ t,s |X| n-2k t-k q q k(t-k) h 2 k h k i=1 e k,s,i (x)e l,t ,i (z) = δ k,l δ t,s |X| n-2k t-k q q k(t-k) h k E k,s,t (x, z).
We obtain, with

t = s , t = s, x = z ∈ X s , taking account of E l,t,s (y, x) = E l,s,t (x, y), y∈Xt E k,s,t (x, y)E l,s,t (x, y) = δ k,l |X| n-2k t-k q q k(t-k) h k E k,s,s (x, x).
The above identity becomes in terms of P k,s,t y∈Xt

P k,s,t (s -dim(x ∩ y))P l,s,t (s -dim(x ∩ y)) = δ k,l |X| n-2k t-k q q k(t-k) h k P k,s,s (0).
Taking account of (3.4.3) and Lemma 3.4.3, we obtain (3.4.4).

We have proved that the functions P k,s,t satisfy the same orthogonality relations as the q-Hahn polynomials. So we are done if P k,s,t is a polynomial of degree at most k in the variable [u] = [dim(x ∩ y)]. This property is proved in the case s = t in [15, Theorem 5] and extends to s ≤ t with a similar line of reasoning. The multiplicative factor between P k,s,t (u) and Q k (n, s, t; u) is then given by P k,s,t (0) and the proof of Theorem 3.4.2 is completed.

The reduction of the program (2.4.6) for projective codes

A function F ∈ R X×X is G-invariant if it can be written as F (x, y) = F (dim(x), dim(y), dim(x ∩ y))
So we introduce a function F with the property that F (s, t, i) = F (x, y) for x, y ∈ X with dim(x) = s, dim(y) = t, dim(x ∩ y) = i. Let

N sti := |{(x, y) ∈ X × X : dim(x) = s, dim(y) = t, dim(x ∩ y) = i}| and Ω(d) := {(s, t, i) : 0 ≤ s, t ≤ n, i ≤ min(s, t), s + t ≤ n + i, (3.4.5) either s = t = i or s + t -2i ≥ d}.
Then, (2.4.6) becomes:

A q (n, d) ≤ sup s,t,i N sti F (s, t, i) : F ∈ R [n] 3 , F 0, F ≥ 0, n s=0 N sss F (s, s, s) = 1, F (s, t, i) = 0 if (s, t, i) / ∈ Ω(d)
where, of course, F 0 means that the corresponding F is positive semidefinite. Then, we introduce the variables x sti := N sti F (s, t, i). It is straightforward to rewrite the program in terms of these variables, except for the condition F 0. From Theorem 4.1, this is equivalent to the semidefinite conditions F k 0, where the matrices F k are given by the scalar product of F and E k :

(F k ) lj = 1 |X| 2 X 2 F (x, y)E k (x, y) lj = 1 |X| 2 s,t,i
x sti Ẽk (s, t, i) lj .

We can substitute the value of Ẽk (s, t, i) lj using Theorem 4.2; in particular it is 0 when (l, j) = (s, t), and, when (l, j) = (s, t):

(F k ) st = 1 |X| i x sti t-k s-k q n-2k t-k q n t q t s q q k(t-k) Q k (n, s, t; s -i). (3.4.6)
Finally we obtain: Theorem 3.4.6.

A q (n, d) ≤ sup (s,t,i)∈Ω(d) x sti : (x sti ) (s,t,i)∈Ω(d) , x sti ≥ 0, n s=0
x sss = 1,

F k 0 for all k = 0, . . . , n/2
where Ω(d) is defined in (3.4.5) and the matrices F k are given in (3.4.6).

Remark 3.4.7. A projective code C with minimal distance d provides a feasible solution of the above program, given by:

x sti = 1 |C| |{(x, y) ∈ C : dim(x) = s, dim(y) = t, dim(x ∩ y) = i}.
In particular, we have

t,i x sti = |C ∩ G q (n, s)|,
so, if A q (n, s, d) (or an upper bound) is known, the additional inequality

t,i x sti ≤ A q (n, s, d)
can be added to the semidefinite program of Theorem 3.4.6 in order to tighten the upper bound for A q (n, d).

Numerical results

Here we give the explicit results obtained for the upper bounds on A 2 (n, d), hence for q = 2. In Table 1, we consider the subspace distance d S while Table 2 is related to the injection distance d i recently introduced in [START_REF] Kschischang | On metrics for error correction in network coding[END_REF].

The subspace distance

The first column of Table 3 x sti ≤ A 2 (n, s, 2 d/2 ) for all s = 0, . . . , n.

In both programs, A 2 (n, k, 2δ) is replaced by its upper bound in Theorem 3.2.2.

Some additional inequalities

In [START_REF] Etzion | Error-correcting codes in projective space[END_REF], Etzion and Vardy have found additional inequalities on the unknowns of their linear program in the specific case of n = 5 and d = 3. With this, they could improve their bound to the exact value A 2 (5, 3) = 18. In this section we establish analogous inequalities for other values of the parameters (n, d).

E-V LP SDP

:= |C ∩ G q (n, k)|. Then, if d + 2 d/2 + 2 < 2n < 2d + 2 d/2 + 2,
we have:

• D 2n-d-d/2 -1 ≤ 1; • if D 2n-d-d/2 -1 = 1 then D d/2 ≤ q n -q 2n-d-d/2 -1 q d/2 -q n-d-1 . Proof. It is clear that D i ≤ 1 for 0 ≤ i < d/2 . Moreover, for all x, y ∈ C ∩ G(n, d/2 ), dim(x ∩ y) = 0. We want to show that D 2n-d-d/2 -1 ≤ 1. Indeed assume by contradiction x = y ∈ C ∩ G(n, 2n -d -d/2 -1), we have 4n -2d -2 d/2 -2 ≤ n + dim(x ∩ y) d ≤ 4n -2d -2 d/2 -2 -2 dim(x ∩ y) leading to 2 dim(x ∩ y) ≥ 6n -4d -4 d/2 -4 ( * ) 2 dim(x ∩ y) ≤ 4n -3d -2 d/2 -2 ( * * )
To obtain a contradiction, we must have ( * ) > ( * * ) which is equivalent to the hypothesis 2n

> d + 2 d/2 + 2.
With a similar reasoning, we prove that, for all

x ∈ C ∩ G(n, d/2 ) and w ∈ C ∩ G(n, 2n -d -d/2 -1), dim(x ∩ w) = n -d -1. Indeed, 2n -d -1 ≤ n + dim(x ∩ w) d ≤ 2n -d -1 -2 dim(x ∩ w) so dim(x ∩ w) ≥ n -d -1 dim(x ∩ w) ≤ n -d -1/2
which yields the result. Now we assume

D 2n-d-d/2 -1 = 1. Let w ∈ C ∩ G(n, 2n -d -d/2 -1
). Let U denote the union of the subspaces x belonging to C ∩ G(n, d/2 ). We have |U| = 1 + D d/2 (q d/2 -1) and |U ∩ w| = 1 + D d/2 (q n-d-1 -1). On the other hand, |U\(U ∩ w))| ≤ |F n q \w|, leading to

D d/2 (q d/2 -q n-d-1 ) ≤ q n -q 2n-d-d/2 -1 .
In several cases, adding the inequalities proved in the above theorem to the programs lead to a lower optimal value, however we found that only in one case other than (n, d) = (5, 3), the final result, after rounding to the previous integer, is improved. It is the case (n, d) = ( 7 A 2 (7, 5) ≤ 34.

This bound can be obtained with both the linear program of Theorem 3.2.3 and the semidefinite program of Theorem 3.4.6.

The injection distance

Recently, a new metric has been considered in the framework of projective codes, the so-called injection metric, introduced in [START_REF] Kschischang | On metrics for error correction in network coding[END_REF]. The injection distance between two subspaces U, V ∈ P(F n q ) is defined by

d i (U, V ) = max{dim(U ), dim(V )} -dim(U ∩ V )
When restricted to the Grassmann space, i.e. when U, V have the same dimension, the new distance coincides with the subspace distance (up to multiplication by 2) so nothing new comes from considering one distance instead of the other. But in general we have the relation ( [START_REF] Kschischang | On metrics for error correction in network coding[END_REF])

d i (U, V ) = 1 2 d S (U, V ) + 1 2 | dim(U ) -dim(V )|
where d S denotes the subspace distance.

It is straightforward to modify the programs in order to produce bounds for codes on the new metric space (P(

F n q ), d i ). Let A inj q (n, d) = max{|C| : C ⊂ P(F n q ), d i (C) ≥ d}. For constant dimension codes, we have A inj q (n, k, d) = A q (n, k, 2d
). To modify the linear program of Etzion and Vardy for this new distance, we need to write down the "sphere-packing" like constraint. The cardinality of balls in P(F n q ) for the injection distance can be found in [START_REF] Khaleghi | Projective space codes for the injection metric[END_REF]. Let B inj (V, e) denotes the ball of center V and radius e. If dim(V ) = i, we have

|B inj (V, e)| = e r=0 q r 2 i r q n -i r q + e r=0 r α=1 q r(r-α)   i r q n -i r -α q + i r -α q n -i r q   . We define c inj (i, k, e) := |B inj (V, e) ∩ G q (n, k)| where dim(V ) = i. We set α := |i -k|. c inj (i, k, e) =      e r=0 q r(r-α) i r q n-i r-α q if i ≥ k e r=0 q r(r-α) i r-α q n-i r q if i ≤ k
We obtain:

Theorem 3.5.3 (Linear programming upper bound for codes in P(F n q ) for the injection distance).

A inj q (n, d) ≤ sup n k=0 x k : x k ≤ A inj q (n, k, d) ∀ k = 0, . . . , n n i=0 c inj (i, k, e)x i ≤ n k q ∀ k = 0, . . . , n
For the semidefinite programming bound, we only need to change the definition of Ω(d); let

Ω inj (d) := {(s, t, i) : 0 ≤ s, t ≤ n, i ≤ min(s, t), s + t ≤ n + i, (3.5.1) either s = t = i or max(s, t) -i ≥ d}.
Then, we have: Theorem 3.5.4.

A inj q (n, d) ≤ sup (s,t,i)∈Ω inj (d) x sti : (x sti ) (s,t,i)∈Ω inj (d) , x sti ≥ 0, n s=0
x sss = 1,

F k 0 for all k = 0, . . . , n/2
where Ω inj (d) is defined in (3.5.1) and the matrices F k are given in (3.4.6). 3.2: Bounds for the injection distance Remark 3.5.5. We observe that the bound obtained for A 2 (n, 4e + 1) is most of the time slightly larger than the one obtained for A inj 2 (n, 2e + 1). In [START_REF] Khaleghi | Projective space codes for the injection metric[END_REF], the authors notice that their constructions lead to codes that are slightly better for the injection distance that for the subspace distance. So both experimental observations tend to indicate that A 2 (n, 4e + 1) should be larger than A inj 2 (n, 2e + 1).

Note: All values of the linear programs have been obtained with the free solver LRS 4.2, while all values of the semidefinite programs have been obtained with the solvers SDPA or SDPT3, available on the NEOS website (http://www.neos-server.org/neos/).

Chapter 4

The chromatic number of the Euclidean space

The motivation for the work presented in this chapter is the problem of determining the chromatic number of the Euclidean space R n , that is, the least number of subsets which partition R n in such a way that no one of them contains points at distance 1. When trying to solve this problem, the idea of using well chosen embeddings in R n of some finite abstract graphs arises in a natural way. Indeed, in 1951, De Bruijn and Erdös ( [START_REF] De Bruijn | A colour problem for infinite graphs and a problem in the theory of relations[END_REF]) proved that the chromatic number of R n can be determined, at least theoretically, by using this approach. Using a so called "intersection theorem", Frankl and Wilson ( [START_REF] Frankl | Intersection theorems with geometric consequences[END_REF]) established a bound on the cardinality of sets avoiding one distance in the Johnson space and, as a consequence, they derived an aymptotic result on the chromatic number of R n which is still the best known. The drawback of their approach is that their bound is not good in low dimensions and moreover it works only for a limited choice of parameters.

On the other hand, bounds in the Johnson space coming from the semidefinite programming method apply to all possible parameters, as we show in the third section. The Delsarte linear programming bound is recalled. We prove a new semidefinite programming bound on sets avoiding one distance in the Johnson space by considering triples of words. This bound is a variant of Schrijver's bound on constant weight codes ( [START_REF] Schrijver | New code upper bounds from the Terwilliger algebra and semidefinite programming[END_REF]) and it is at least as good as Delsarte's one. We symmetrize it using a group theoretical setting in the spirit of this thesis. In most of the cases we computed, it improves the bound of Frankl and Wilson.

In [START_REF] De Oliveira Filho | Fourier analysis, linear programming and densities of distance avoiding sets in R n[END_REF], the authors established a linear program whose optimal value gives a lower bound for the measurable chromatic number of R n . Also, they showed how to strengthen it by including constraints on regular simplices. In the fifth section we show how our bounds on sets avoiding one distance in the Johnson space can be used in their linear program. Better results than the existing ones are obtained for n = 9, . . . , 23.

Introduction

Definition 4.1.1. The chromatic number of the real Euclidean space R n , denoted χ(R n ), is the minimum number of colors needed to color R n in such a way that points at distance 1 receive different colors.

In other words, consider the unit distance graph of R n : it is the (infinite) graph with vertex set R n and edges between points at Euclidean distance 1. Then χ(R n ) is the chromatic number of this graph according to the definition given in chapter 2. It is an old and open problem to determine χ(R n ), even for small dimensions.

The easiest case is that of n = 1, where the chromatic number of the real line is 2. The classes of coloring are i∈N [2i, 2i + 1[ and its complement (up to translation). So χ(R) = 2. Surprisingly, no other value is known. Consider for instance the plane: determining the chromatic number of R 2 is known as the Hadwiger-Nelson problem. Looking at an equilateral triangle with side length 1, it becomes clear that in a coloring of the plane, the three vertices will receive different colors. This allows us to establish the lower bound χ(R 2 ) ≥ 3. The role played by the triangle can be generalized as follows.

Definition 4.1.2. A unit distance graph in R n is a finite graph which can be embedded in R n in such a way that its adjacent vertices are exactly the vertices at Euclidean distance 1. In other words, it is a finite induced subgraph of the unit distance graph of R n .

Clearly, every cycle graph is a unit distance graph in the plane when seen as a regular polygon of side length 1. But, as the chromatic number of a graph is 2 or 3, according to the parity of n, we cannot hope to use cycles to improve the previous bound.

The Moser graph is a unit distance graph in R 2 whose chromatic number is 4, thus leading to the lower bound 4 ≤ χ(R 2 ). Let us mention also that, up to now, the best estimate in dimension 3 is given by 6 ≤ χ(R 3 ) ≤ 15 (see the overview in [START_REF] Kupavskii | On the chromatic numbers of smalldimensional Euclidean spaces[END_REF]).

In general, it is known by the De Bruijn-Erdos theorem ( [START_REF] De Bruijn | A colour problem for infinite graphs and a problem in the theory of relations[END_REF]) that χ(R n ) is attained by a finite unit distance graph G ⊂ R n .

Frankl-Wilson graphs

Of course, for any graph G = (V, E) we have

χ(G)α(G) ≥ |V | In particular, if G is a unit distance graph embedded in R n , we find χ(R n ) ≥ χ(G) ≥ |V | α(G) (4.2.1)
so any upper bound on α(G) will result in a lower bound for χ(R n ).

Definition 4.2.1 ([19]

). Given n, let p < (n + 1)/2 be a power of a prime number. The So we are considering vectors of length n with weight 2p-1 where non zero entries take the constant value 1/ √ 2p. Note that Frankl-Wilson graphs can be embedded in R n as unit distance graphs. In fact, denoting x the image of x in R n , we see that

d(x, y) = 1 ⇔ i (x i -y i ) 2 = √ 2p ⇔ |x ∩ y| = p -1 ⇔ xy ∈ E
Moreover, as all words have constant weight, they can actually be embedded in R n-1 . Following the previous discussion, we find that

χ(R n-1 ) ≥ n 2p-1 α(J(n, p))
Let us now focus on α(J(n, p)). Applying their intersection theorem ( [START_REF] Frankl | Intersection theorems with geometric consequences[END_REF]), Frankl and Wilson found

α(J(n, p)) ≤ n p -1 (4.2.2) which, optimizing over p, leads to χ(R n ) ≥ (1.207+o(1)) n , provided n is large enough. In 2000, Raigorodskii improved the lower bound to (1.239 + o(1)) n ([39]).
In what follows, we will compare the Frankl-Wilson bound 4.2.2 to other bounds coming from SDP. Notably, we have the ϑ number which, after symmetrization, reduces to a linear program, and the Schrijver-like bound involving triples of words.

The independent sets of the Frankl-Wilson graph J(n, p) are the constant weight codes in the Johnson space J w n , for w = 2p -1, with no words at Hamming distance d = 2p (i.e. Johnson distance δ := d/2 = p). Thus the independence number of J(n, p) is the maximal size of such a code. While the Frankl-Wilson bound is restricted to the choice of parameters of definition 4.2.1, the bounds that we give in the next section apply to all choices of parameters w ≤ n/2 and δ.

Bounds for sets avoiding one distance in the Johnson space

Let w ≤ n/2 and define J(n, w, i) as the graph with vertex set J w n with an edge xy whenever |x ∩ y| = i. Frankl-Wilson graphs correspond, up to a normalization factor, to J(n, 2p -1, p -1) and this is precisely the case in which the bound 4.2.2 holds. With the corresponding normalization factor, these graphs J(n, w, i) are also unit distance graphs in R n . Moreover, as they have constant weight, they can actually be embedded in R n-1 .

The LP bound

As the Johnson space J w n is 2-point homogeneous for the action of the symmetric group S n , the ϑ number for graphs in this space reduces to Delsarte linear program. The reduction, contained in [START_REF] Delsarte | Hahn polynomials, discrete harmonics and t-designs[END_REF], is essentially the same as for the symmetrization of the Grassmann space, which indeed is the q-analog of J w n (see section 3.3.3). It involves a simplified version of the Hahn polynomials, namely the family associated to parameters n, w, w in definition 2.4.5. Definition 4.3.1. The Hahn polynomials associated to the parameters n, w with 0 ≤ w ≤ n are the polynomials Q k (t) with 0 ≤ k ≤ w uniquely determined by the properties:

• Q k has degree k, • for all 0 ≤ k < l ≤ w, w i=0 w i n -w i Q k (i)Q l (i) = 0 • Q k (0) = 1.
Theorem 4.3.2. (Delsarte's linear programming bound [START_REF] Delsarte | Hahn polynomials, discrete harmonics and t-designs[END_REF]). The maximum number of words in J w n avoiding Johnson distance δ is upper bounded by the optimal value of the following linear program:

inf 1 + f 1 + • • • + f w : f k ≥ 0 ∀ k = 1, . . . , w F (t) ≤ 0 ∀ t = 1, . . . , δ -1, δ + 1, . . . , w} where F (t) = 1 + w k=1 f k Q k (t) and Q k (t)
is as in the definition above. Remark 4.3.3. From the previous discussion, applying theorem 4.3.2 with δ = w -i yields an upper bound on α(J(n, w, i)) which in the rest of the chapter will be referred to as LP bound.

The SDP bound on triples of words

The bound that we establish in this section is a strengthening of the ϑ number, obtained by constraints on triples of words. It was first obtained in [START_REF] Schrijver | New code upper bounds from the Terwilliger algebra and semidefinite programming[END_REF], where it is applied to constant weight codes. We will see that the symmetrization needed is closely related to the block diagonalization of the Terwilliger algebra (section 2.4.3), from which we take some notations and results. We restrict here to the case w < n/2. Set X := J w n and fix z 0 := 1 w 0 n-w . Then S n acts on X and Stab Sn (z 0 ) = S w × S n-w . We start by giving the general SDP formulation of our bound.

Theorem 4.3.4. (The SDP bound on triples).

The maximum number of points in a metric space X avoiding distance δ is upper bounded by the optimal value of the following semidefinite program:

sup X 2 F (x, y, x) : F (x, y, z) = F ({x, y, z}) ∀ z ∈ X, (x, y) → F (x, y, z) 0 F (x, y, z) ≥ 0 ∀ x, y, z X F (x, x, x) = 1 F (x, y, z) = 0 if δ ∈ {d(x, y), d(x, z), d(y, z)} (4.3.1)
where the first constraint means that F is invariant under permutation of the variables, that is, the value of F (x, y, z) depends only on the set {x, y, z}.

Proof. For every C ⊂ X with no words at pairwise distance δ, the function

F (x, y, z) := 1/|C| if all x, y, z ∈ C 0 else
is feasible for the program 4.3.1 and its objective value is

X 2 F (x, y, x) = 1 |C| |C| 2 = |C| .
Remark 4.3.5. It is easily seen that this bound improves the bound of ϑ (remark 2.3.8) applied to the corresponding graph. Indeed, for a feasible F , set G(x, y) := F (x, y, x).

Then G is feasible for ϑ and its objective value is the same as the one of F . In the Johnson space, this means that the SDP bound on triples is always at least as good as Delsarte LP bound.

In the case of the Johnson space, the program 4.3.1 need to be symmetrized to reduce its size in order to compute explicit optimal values. This can be done similarly to what we explained for ϑ in section 2.4.1.

Description of the orbits and first reduction

Consider the action of S n on triples of words. For (x, y, z) ∈ X 3 b,c,d). Moreover the collection of orbits is parametrized by the following set:

Ω(n, w) := (a, b, c, d) : 0 ≤ d ≤ a, b, c ≤ w max{a + b, a + c, b + c} ≤ w + d 2w ≤ n + min{a, b, c} 3w + d ≤ n + a + b + c (4.3.2)
Proof. The action of the symmetric group preserves cardinality of intersection of words, so the "only if" part obviously holds. Conversely, let us define the standard representative (x 0 , y 0 , z 0 ) of the S n -orbit parametrized by (a, b, c, d) as:

x 0 := 1 d 1 a-d 0 b-d 0 w-a-b+d 1 c-d 1 w-a-c+d 0 w-b-c+d 0 . . . 0 y 0 := 1 d 0 a-d 1 b-d 0 w-a-b+d 1 c-d 0 w-a-c+d 1 w-b-c+d 0 . . . 0 z 0 := 1 d 1 a-d 1 b-d 1 w-a-b+d 0 c-d 0 w-a-c+d 0 w-b-c+d 0 . . . 0
Then it is clear that for any other triple with the same parameters (a, b, c, d) we can act with S n by permuting each 0-1 block to transform such triple into the standard one (x 0 , y 0 , z 0 ).

As for the second statement of the proof, given (a, b, c, d) satisfying the constraints in 4.3.2 we can build (x 0 , y 0 , z 0 ) as above. Conversely, given any triple (x, y, z), the first constraint is clear, the second one comes by putting together relations of the kind (x ∩ z) ∪ (y ∩ z) ⊂ z, the third simply by |x ∪ z| ≤ n and the last one by |x ∪ y ∪ z| ≤ n.

The program 4.3.1 is invariant for the action of S n , so we can restrict to consider S n -invariant functions F . From the preceding theorem, these functions satisfy F (x, y, z) = F (a, b, c, d). Let x abcd denote the cardinality of the respective orbit for the action of S n on X. Then, program 4.3.1 is equivalent to:

sup w b=0 x wbbb F (w, b, b, b) : F (a, b, c, d) = F ({a, b, c}, d) ∀ z ∈ X, (x, y) → F (x, y, z) 0 F (a, b, c, d) ≥ 0 ∀ (a, b, c, d) ∈ Ω(n, w) x wwww F (w, w, w, w) = 1 F (a, b, c, d) = 0 if δ ∈ {w -a, w -b, w -c}
Now we focus on the second constraint. The following proposition is easy to prove.

Proposition 4.3.7. If the function (x, y, z) → F (x, y, z) is G-invariant, then for any z 0 ∈ X, the function (x, y) → F (x, y, z 0 ) is Stab G (z 0 )-invariant.
So we need a description of the positive semidefinite functions which are invariant under the stabilizer of one point. As S n acts transitively on X, all the stabilizer subgroups are conjugated. In what follows we fix the point z 0 := 1 w 0 n-w and Stab Sn (z 0 ) = S w ×S n-w . We are going to block diagonalize the algebra (R X×X ) Sw×S n-w with an explicit isomorphism which preserves positive semidefiniteness. To do this, we can follow the method given in sections 2.4.1 and 2.4.3. It will turn out that we are in fact block diagonalizing a tensor product of Terwilliger algebras, namely the ones associated to H w and H n-w . As a consequence, the zonal functions that we build will be a product of zonal functions of the respective spaces.

Decomposition of R X under S w × S n-w

Clearly, X has a partition into orbits

X i := {x ∈ X : |x ∩ z 0 | = i} which yields R X = R X 0 ⊕ R X 1 ⊕ • • • ⊕ R Xw
Yet, this decomposition is not irreducible. To decompose it further, note that

R X i R J i w ⊗ R J w-i n-w
The irreducible decomposition of the Johnson space into Specht modules was given in 2.4.9:

R J i w = H w 0,i ⊕ • • • ⊕ H w i,i if i ≤ w/2 H w 0,i ⊕ • • • ⊕ H w w-i,i else R J w-i n-w = H n-w 0,w-i ⊕ • • • ⊕ H n-w w-i,w-i if w -i ≤ (n -w)/2 H n-w 0,w-i ⊕ • • • ⊕ H n-w n-2w+i,w-i else where H w k,i S (w-k,k) and H n-w h,w-i S (n-w-h,h) . So we get R X i = H w 0,i ⊕ • • • ⊕ H w min{i,w-i},i ⊗ H n-w 0,w-i ⊕ • • • ⊕ H n-w min{w-i,n-2w+i},w-i H w 0,i ⊗ H n-w 0,w-i ⊕ • • • ⊕ H w min{i,w-i},i ⊗ H n-w min{w-i,n-2w+i},w-i
We know that the irreducible modules for the action of the direct product of groups are the tensor products of irreducible modules for the action of each of the group factor. We know that Specht modules are the irreducible modules for the action of the symmetric group. So, in the case of the product of symmetric groups S w × S n-w we have decomposed each R X i in its irreducible components. Theorem 4.3.8. The irreducible decomposition of the space R X under the action of S w × S n-w is given by:

R X = w i=0 min{i,w-i} k=0 min{w-i,n-2w+i} h=0 H w k,i ⊗ H n-w h,w-i w/2 k=0 (n-w)/2 h=0 H m k,h k,h
where

H k,h := H w k,k ⊗ H n-w h,h S (w-k,k) ⊗ S (n-w-h,h)
is of dimension

d k,h := w k - w k -1 • n -w h - n -w h -1
and the multiplicity is given by

m k,h := |{k, . . . , w -k} ∩ {h, . . . , n -w -h}| = max min{w -k, n -w -h} -max{k, h}, 0
Proof. From the previous discussion. To prove the multiplicity formula, it is enough to remark that (an isomorphic copy of) H k,h is contained in R X w-j if and only if j ∈ {k, . . . , w -k} ∩ {h, . . . , n -w -h}. Note that, depending on n and w, some of the multiplicities can be 0.

Construction of the zonal matrices

Recall from section 2.4.3 the following facts:

• For 0 ≤ k ≤ w/2 , we can take an orthonormal basis {e w k,k,1 , . . . , e w k,k,d k } for

H w k,k inside R J k w .
• Analogously, for 0 ≤ h ≤ (n -w)/2 , we can take an orthonormal basis {e n-w h,h,1 , . . . , e n-w h,h,d h } for H n-w h,h inside R J h n-w .

• Here

d k = w k -w k-1 and d h = n-w h -n-w h-1 .
• Whenever i > k and j > h, by mean of the corresponding valuation operators, we obtain basis {e w k,i,1 , . . . , e w k,i,d k } of H w k,i and {e n-w h,j,1 , . . . , e n-w h,j,d h } of H n-w h,j .

With this we can build a basis for the copy H w k,i ⊗ H n-w h,w-i of H k,h inside R X i as {e w k,i,1 e n-w h,w-i,1 , . . . , e w k,i,d k e n-w h,w-i,d h } Now, the zonal matrices satisfy:

E k,h ∈ R m k,h ×m k,h for k = 0, . . . , w/2 h = 0, . . . , (n -w)/2 E k,h,i,j (x, y) = 0 only if |x ∩ z 0 | = i, |y ∩ z 0 | = j
and they are given by:

E k,h,i,j (x, y) = 1 |X| d k =0 d h =0
e w k,i, (x)e n-w h,w-i, (x)e w k,j, (y)e n-w h,w-j, (y) = 1 |X| e w k,i, (x)e w k,j, (y) e n-w h,w-i, (x)e n-w h,w-j, (y)

= 1 |X| E w k,i,j (x, y)E n-w h,w-i,w-j (x, y)
where, by theorem 2.4.6,

E w k,i,j (x, y) = |H w | j-k i-k w-2k j-k w j j i Q k (w, i, j; i -|x ∩ y ∩ z 0 |) and E n-w h,w-i,w-j (x, y) = |H n-w | w-j-h w-i-h n-w-2h w-j-h n-w w-j w-j w-i Q h (n -w, w -i, w -j; w -i -|x ∩ y ∩ z 0 |)

The final reduction

We go back to program 4.3.1. By Bochner theorem 2.4.1 we know that the function F z (x, y) := F (x, y, z) is positive semidefinite and (S w × S n-w )-invariant if and only if there exist positive semidefinite matrices F k,h such that

F z (x, y) = F k,h , E k,h (x, y) .
We can recover the matrices F k,h by mean of the scalar product

F k,h = 1 |X| 2 x,y∈X F z (x, y)E k,h (x,
y abcd = 0 if δ ∈ {w -a, w -b, w -c} where, for 0 ≤ k ≤ w/2 , 0 ≤ h ≤ (n -w)/2 , F k,h ∈ R m k,h ×m k,h is defined by: (F k,h ) a,b = c,d y abcd b-k a-k w-2k b-k w-b-h w-a-h n-w-2h w-b-h w b b a n-w w-b w-b w-a Q k (w, a, b; a -d)Q h (n -w, w -a, w -b; w -a -c + d)
Remark 4.3.10. From the previous discussion, applying theorem 4.3.9 with δ = w -i yields an upper bound on α(J(n, w, i)) which in the rest of the chapter will be referred to as SDP bound.

Numerical results

In the following table we compare

• the Frankl-Wilson bound 4.2.2,
• the linear programming bound of theorem 4.3.2,

• the SDP bound of theorem 4.3.9 on the independence number of graphs J(n, w, i) for some choice of parameters. We recall that the F-W bound applies only in the case (w, i) = (2p -1, p -1) for some p power of a prime. Apart from these cases, we have chosen the graphs J(n, w, i) that we will use later on in tables 4.2 and 4. Also, the eigenvalues of Z are much easier to analyse if J and A commute i.e. if the graph is regular. To make the connection with the Laplacian introduced above, it is the case L 0 = dI -A if d is the degree of G. We can rewrite

Z = J + γdI -γL 0 , γ ∈ R.
If λ 1 ≥ • • • ≥ λ n ≥ 0 denote the eigenvalues of L 0 , because L 0 J = 0 we have λ n = 0 and the eigenvalues of Z are:

n + γd, γ(d -λ i ) (1 ≤ i ≤ n -1)
. The optimal choice for γ is obtained for

min γ max{n + γd, γ(d -λ i ) (1 ≤ i ≤ n -1)} which is equal to n(λ max (L 0 ) -d) λ max (L 0 )
in which we recognize the expression of the well-known Hoffman bound:

Theorem 5.1.1. (Hoffman bound) Let G be a regular graph of degree d, let A be its adjacency matrix. We have

α(G) ≤ ϑ(G) ≤ nλ min (A) λ min (A) -d .
Moreover, the last inequality is an equality for edge transitive graphs and for strongly regular graphs.

In general, L 0 and J commute between them, so restricting to matrices

Z = J + i≥0 γ i L i 0 in 5.
1.1, we obtain a linear program.

The original motivation for the work in this chapter is an attempt to build a SDP hierarchy based on generalizations of matrices J and L 0 , with the hope to get high order Hoffman-like eigenvalues bounds. We give the details of the construction of this new SDP hierarchy, then we discuss its properties and some possible modifications. High order generalizations of matrices J and L 0 arise in a natural way when considering simplicial complexes.

Simplicial complexes

An abstract simplicial complex is a family ∆ of finite subsets of a given set V such that whenever A ∈ ∆ and B ⊂ A, then B ∈ ∆. Elements of a simplicial complex Lemma 5.3.2. For any graph G, we have

ϑ k (G) ≤ min t : tI -L k-1 + M + x trr (E tr -E tr ) 0
where M is supported on the pairs (s, s ) such that |s ∪ s | ≥ k + 2 or s ∪ s contains an edge, the sum runs over the set

{(t, r, r ) : |t| = k + 1, t without edges , |r| = |r | = k -1, r = r }
and E tr denotes the matrix with a single upper non zero coefficient corresponding to indices s, s such that s ∩ s = r, s ∪ s = t and equal to ε(s, s ). Equivalently:

ϑ k (G) ≤ min λ max (Z) : Z = L k-1 + T, T s,s = 0 if s does not contain an edge where, for k ≥ 2, T verifies ε(s, s )T s,s + ε(v, v )T v,v = 0 for all {s, s } = {v, v } such that s ∪ s = v ∪ v has cardinality k + 1 and contains no edges.
At this point, several remarks are needed.

Remark 5.3.3. Clearly, ϑ 1 = ϑ. For k = 2 we are considering a matrix X whose rows and columns are indexed on pair of vertices; the only entries of X that are not set to zero are the diagonal ones corresponding to an index which does not contain an edge, and the ones whose union of row index and column index is a triangle without edges. In this last case, entries corresponding to the same triangle have the same absolute value, the sign is given according to the rule we introduced in section 5.2.

Remark 5.3.4. If we partition the set V k into two subsets, the subset of cocliques and the subset of k-tuples containing at least one edge, then a feasible matrix X for (5.3.1) satisfies X s,s = 0 if one of s, s is in the second part. So X has the form:

X = X 0 0 0
and we can replace in ϑ k (G) all matrices by matrices indexed by cocliques. In this way we obtain a program which is equivalent to ϑ k . Moreover in this case, strong duality holds with the same argument as for ϑ. In particular, for k = 2, the restricted matrix X is indexed by the set E of non-adjacent pairs. Remark 5.3.5. Note that ϑ k (G) = -∞ whenever k > α(G), so from now on we restrict ourselves to the cases k ∈ {1, 2, . . . , α(G)}.

We want to construct some feasible matrices Z for the dual formulation of ϑ k . More precisely, because L k-1 and L k-1 commute, we want Z to be a linear combination of L k-1 , and powers of L k-1 . So we introduce:

ϑ LP k (G) := min λ max (Z) : Z = γ -1 L k-1 + i≥0 γ i L i k-1 (γ -1 -1)L k-1 + i≥0 γ i L i k-1 ) s,s = 0 for (|s ∪ s | ≤ k + 1 containing no edges Then ϑ LP k (G)
is the optimal value of a linear program.

Properties of ϑ k

We are going to see that the number ϑ k conserve some well-known properties of ϑ, recalled in section 2.2.

Proposition 5.3.6. For all k ≤ α(G), α(G) ≤ ϑ k (G), with equality when k = α(G).

Proof. Let S be an independent set of G. Let V G k denote the set of all k-subsets of vertices of G. Define the matrix

X S k ∈ R V G k ×V G k by: (X S k ) s,s = (L k-1 ) s,s if s ∪ s ⊂ S 0 else
Because X S k is a submatrix of L k-1 , it is positive semidefinite. We compute

X S k , I = k |S| k (5.3.1)
and, with (5.2.12),

X S k , L k-1 = k 2 |S| k + |s∪s |=k+1 s∪s ⊆S 1 = k 2 |S| k + (k + 1)k |S| k + 1 = k |S| k |S|.
(

α(G) ≤ ϑ k (G). Now, if k = α(G)
, a subset of V (G) of size greater or equal to k + 1 must contain an edge. So, if s = s ∈ V G k , s ∪ s contains an edge, and the non diagonal coefficients of a primal feasible matrix X of (5.3.1) are equal to zero. So, taking account of the fact that the diagonal coefficients of L k-1 are equal to k, we have L

k-1 , X = k I, X = k = α(G).
For the rest of the chapter we take the following notation. Let V G k denote the set of all k-subsets of vertices of G. For any k, a graph homomorphism ϕ : G → H induces a linear application φk of

R V G k ×V G k into R V H k ×V H k ,
(G) ≤ ϑ k (H).
Proof. We begin the proof by two remarks. The first is that, given an order on the vertices of H, we can order the vertices of G in such a way that ϕ becomes an increasing function; it follows that ε(ϕ(s), ϕ(s

)) = ε(s, s ) for all s, s ∈ V G k such that |s ∪ s | = k + 1, ϕ(s), ϕ(s ) ∈ V H k , |ϕ(s) ∪ ϕ(s )| = k + 1. Now,
let X be a feasible solution of (5.3.1) with respect to the graph G. The second remark is that X s,s = 0 if ϕ(s) ∈ V H k or ϕ(s ) ∈ V H k , because in that case s or s contains an edge of G. For the same reason, X s,s = 0 if s = s are such that ϕ(s) = ϕ(s ). We will use these two facts all along the proof. Our goal now is to show that the matrix φk (X) is feasible for the program (5.3.1) with respect to the graph H. Such matrix is clearly symmetric, let us see that it is positive semidefinite:

for all vector α ∈ R V H k , u,u α u ( φk (X)) u,u α u = u,u α u ( s : ϕ(s)=u s : ϕ(s )=u X s,s ) α u = s,s ∈V G k ϕ(s),ϕ(s )∈V H k α ϕ(s) X s,s α ϕ(s ) = s,s ∈V G k α ϕ(s) X s,s α ϕ(s ) ≥ 0
Let us see also that φk (X) has trace 1:

Tr( φk (X)) = u ( φk (X)) u,u = u s : ϕ(s)=u s : ϕ(s )=u X s,s = u s : ϕ(s)=u X s,s = s : ϕ(s)∈V H k X s,s = Tr(X) = 1 . Next, if |u ∪ u | ≥ k + 2, then |s ∪ s | ≥ k + 2
for all s, s such that ϕ(s) = u and ϕ(s ) = u , hence ( φk (X)) u,u = 0. Also, s ∪ s contains an edge of G if u ∪ u contains an edge of H, so ( φk (X)) u,u = 0 also in this case. Finally, take u ∪ u = v ∪ v of cardinality k + 1. Then the collection of s ∪ s where (s, s ) is an inverse image of (u, u ) and the collection of t ∪ t where (t, t ) is an inverse image of (v, v ), coincide. So we verify that

ε(u, u )( φk (X)) u,u = ϕ(s)=u ϕ(s )=u ε(u, u )X s,s = ϕ(s)=u ϕ(s )=u ε(s, s )X s,s = ϕ(t)=v ϕ(t )=v ε(t, t )X t,t = ϕ(t)=v ϕ(t )=v ε(v, v )X t,t = ε(v, v )( φk (X)) v,v .
Up to now, we have shown that the matrix φk (X) is a feasible solution of the program (5.3.1) with respect to the graph H. Now we calculate its objective value:

L k-1 , φk (X) = 2 + u =u ε(u, u )( φk (X)) u,u = 2 + u =u ϕ(s)=u ϕ(s )=u ε(u, u )X s,s = 2 + u =u ϕ(s)=u ϕ(s )=u ε(s, s )X s,s = 2 + s =s ε(s, s )X s,s = L k-1 , X .
Every feasible matrix for ϑ k (G) gives a feasible matrix for ϑ k (H) with the same objective value. This concludes the proof. Now we want to establish an analog of the sandwich theorem 2.3.10 for every ϑ k . For this, we need the following equivalent definition of the chromatic number of a graph. is the largest cardinality of a clique of G and it can also be defined as the largest natural number m such that there exists a homomorphism K m → G. As independent sets correspond to cliques in the complement graph, ω(G) = α(G).

A decreasing hierarchy

We have seen that the sequence of programs ϑ k defined in the previous section has some remarkable properties, namely the sandwich theorem and the fact that for any graph G we reach the exact value α(G) at the α(G)-th step. Nevertheless another desirable property for a sequence of this kind would be to be decreasing as a function of k. At the moment we are not able neither to prove nor to disprove this in the general case, although practical computations show ϑ 2 < ϑ 1 . So in this section we consider a slightly different program obtained from ϑ k by adding the requirement that certain matrices are positive semidefinite. We show that this new sequence of programs conserve all properties of the original one and, moreover, it is decreasing with k.

Recall that V G k denotes the set of all k-subsets of vertices of G. For each k ≥ 2 we define the following linear application

τ k,k-1 : R V G k ×V G k → R V G k-1 ×V G k-1 by • if u ∈ V G k-1 , then τ k,k-1 (X) u,u := 1 k u⊂s X s,s • if u, u ∈ V G k-1 are such that |u ∪ u | = k, then ε(u, u )τ k,k-1 (X) u,u := 1 k(k -1) X u∪u ,u∪u + 1 (k + 1)k(k -1) |s∪s |=k+1 u∪u ⊂s∪s ε(s, s )X s,s • τ k,k-1 (X) u,u := 0 elsewhere. Remark that ε(u, u )τ k,k-1 (X) u,u is a function of u ∪ u . For each k > h ≥ 2, we denote by τ k,h the composition τ h+1,h • • • • • τ k-1,k-2 • τ k,k-1 .
Definition 5.4.1. For each graph G we define θk (G) as the optimal value of the program 5.3.1 to which we add the constraints τ k,k-1 (X) 0, τ k,k-2 (X) 0, . . . , τ k,1 (X) 0.

Proposition 5.4.2. For all k ≤ α(G), α(G) ≤ θk (G), with equality when k = α(G).

Proof. Almost all has already been proved in Proposition 5.3.6. Let S be an independent set of G of maximal size and recall the definition of X S k :

(X S k ) s,s = (L k-1 ) s,s if s ∪ s ⊂ S 0 else It remains to show that all matrices τ k,h (X S k ) are positive semidefinite. It is not diffi- cult to see that τ k,k-1 (X S k ) u,u = |S| -k + 1 whenever u ⊂ S and that τ k,k-1 (X S k ) u,u = |S|-k+1
k-1 ε(u, u ) whenever u ∪ u ⊂ S and that all other entries are zero. So we recognize that τ k,k-1 (X S k ) = |S|-k+1 k-1 X S k-1 which is positive semidefinite. Iterating this computation, we find that all others τ k,h (X S k ) are positive scalar multiples of X S h respectively, hence positive semidefinite. This concludes the proof.

Theorem 5.4.3. For all k, θk (G) ≤ θk-1 (G).

Proof. Let X be a feasible solution of the program θk (G) and note Y the matrix τ k,k-1 (X). We will see that this matrix is a feasible solution of θk-1 (G). Let us verify that Y has trace 1, as the other constraints are easily seen to be satisfied.

Tr(Y ) = u Y u,u = u 1 k s : u⊂s X s,s = s X s,s 1 k u : u⊂s 1 = s X s,s = Tr(X) = 1
The objective value of this solution is

L k-2 , Y = (k -1)Tr(Y ) + u,u : |u∪u |=k ε(u, u )Y u,u = (k -1) + s : |s|=k X s,s 1 k(k -1) u,u : u∪u =s 1 Tr(X)=1 + u,u : |u∪u |=k 1 (k + 1)k(k -1) |s∪s |=k+1 u∪u ⊂s∪s ε(s, s )X s,s = k + s,s : |s∪s |=k+1 ε(s, s )X s,s 1 (k + 1)k(k -1) |u∪u |=k u∪u ⊂s∪s 1 = k + s,s : |s∪s |=k+1 ε(s, s )X s,s = L k-1 , X
and this yields the announced inequality. Remark 5.4.4. Obviously, θk (G) ≤ ϑ k (G). Although the optimal solutions of both programs coincide in the cases we computed, it seems that to insure the decreasing of our programs, θk need to be considered, as the condition τ k,k-1 (X) 0 is not always satisfied when X is a feasible solution of ϑ k . Of course, for practical computations one can consider simply ϑ k .

Recall that a graph homomorphism ϕ : G → H induces a linear application φk of

R V G k ×V G k into R V H k ×V H k .
Proposition 5.4.5. The following diagram is commutative:

R V G k ×V G k R V G k-1 ×V G k-1 R V H k-1 ×V H k-1 R V H k ×V H k τ k,k-1 φk-1 τ k,k-1 φk Proof. Take X ∈ R V G k ×V G k . Let us call Y = τ k,k-1 ( φk (X)) and Z = φk-1 (τ k,k-1 (X)).
Along this proof we will make use of the remarks which appear in the proof of theorem (5.3.7). We calculate

Y r,r = 1 k v : r⊂v ( φk (X)) v,v = 1 k v : r⊂v s : ϕ(s)=v X s,s = 1 k s : r⊂ϕ(s) X s,s and, for |r ∪ r | = k, ε(r, r )Y r,r = 1 k(k -1) φk (X) r∪r ,r∪r + 1 (k + 1)k(k -1) r∪r ⊂v∪v ε(v, v ) φk (X) v,v = 1 k(k -1) ϕ(s)=r∪r X s,s + 1 (k + 1)k(k -1) r∪r ⊂v∪v ϕ(s)=v ϕ(s )=v ε(s, s )X s,s On the other hand, Z r,r = u : ϕ(u)=r 1 k u : u⊂s X s,s = 1 k s : ϕ -1 (r)⊂s X s,s and, for |r ∪ r | = k, Z r,r = ϕ(u)=r ϕ(u )=r (τ k,k-1 (X)) u,u = ϕ(u)=r ϕ(u )=r 1 k(k -1) X u∪u ,u∪u + ϕ(u)=r ϕ(u )=r 1 (k + 1)k(k -1) u∪u ⊂s∪s ε(s, s )X s,s
Now it is easy to see that Y = Z. Proof. It follows from theorem 5.3.7 and proposition 5.4.5, taking account of the fact that φk preserves positivity of matrices, as it is shown in the proof of theorem 5.3.7.

The sandwich theorem for θk holds as well with the same proof as for ϑ k .

Theorem 5.4.7. For all graph G and all k, α(G) ≤ θk (G) ≤ χ(G).

Numerical results

In this section we first introduce another program strictly related to ϑ k and then give some numerical results on two classical families of graphs.

ϑ + k (G) := max L + k-1 , X : X 0, I, X = 1, X s,s = 0 if |s ∪ s | ≥ k + 2 or s ∪ s contains an edge, X s,s = X t,t if s ∪ s = t ∪ t and |s ∪ s | = k + 1 (5.5.1)
where all matrices are indexed on

V G k and L + k-1 := (N + k-1 ) T (N + k-1 ) with N + k-1 ∈ R V G k-1 ×V G k defined by (N +
k-1 ) r,s := 1 if and only if r ⊂ s, and (N + k-1 ) r,s := 0 elsewhere. So

(L + k-1 ) s,s =      k if |s ∪ s | = k i.e. s = s 0 if |s ∪ s | ≥ k + 2 1 if |s ∪ s | = k + 1 (5.5.2)
In other words, ϑ + k is the program ϑ k on which we have forgotten all sign relations. Proposition 5.3.6 and theorem 5.3.7 hold also in this case. Although this program does not have a clear algebraic description, it is interesting for computations, as it seems to be competitive with the original one.

In table 5.1 we compare the optimal values of ϑ = ϑ 1 , ϑ 2 and ϑ + 2 for some cycle graphs C n and Paley graphs P (n). See next chapter for more details on this last family.

Note: All values of the semidefinite programs have been obtained with the solvers SDPA or SDPT3, available on the NEOS website (http://www.neos-server.org/neos/).

Bounds for generalized independence numbers

We define the generalized independence number α k (G) to be the maximal number of elements of a subset S of V (G) such that S does not contain any (k + 1)-clique. So α 1 (G) is the usual independence number α(G). Here we use a degenerated version of the cliques complex considered in Example 4. More precisely, we take for ∆ k the set of (k + 1)-cliques and for ∆ k-1 the set of all k-subsets. We note that then L k-1 is the same as before, while

L k-1 = L cl k-1 0 0 0
where we have partitioned the index set ∆ k-1 in cliques and non-cliques, and L cl k-1 is the Laplacian matrix for the cliques complex. Then:

ϑ cl k (G) := max L k-1 , X : X 0, I, X = 1, X s,s = 0 if |s ∪ s | ≥ k + 2 or s ∪ s ∈ ∆ k ε(s, s )X s,s = ε(t, t )X t,t if s ∪ s = t ∪ t and |s ∪ s | = k + 1 (5.6.1) Proposition 5.6.1. For all k ≤ α k (G), α k (G) ≤ ϑ cl k (G)
Proof. The same as for Proposition 5.3.6.

Open questions

In our opinion, this chapter has some points that deserve further discussion.

• First of all, can one prove or disprove the decreasing property for ϑ k ? Alternatively, is there an easier practical way to insure it?

• Secondly, it would be nice to have an explicit formula of ϑ 2 (G) when G runs over some families of graphs, e.g. cycle graphs.

• Next, can one find an analog of Hoffman bound for ϑ 2 ? If yes, which property should the graph have in order to reach equality in the given bound?

• Finally, the relation with existing hierarchies has still to be investigated.

Chapter 6

Some results on Paley graphs

In this final chapter we focus on Paley graphs. It is an open and interesting problem to determine their clique number, also in view of number theoretical applications. As these graphs are self complementary, the clique number coincides with the independence number. In the second section we symmetrize our program ϑ 2 for Paley graphs and we calculate some explicit values. In the third section we explore the circulant structure of a Paley graph and its subgraphs. We show that we can reduce the problem of determining the independence number from the original graph to the induced subgraph of non squares. In the fourth and last section, we show that the ϑ number of a circulant graph is in fact a linear program.

Introduction

Definition 6.1.1. Let q ≡ 1 mod 4 be a power of a prime. The Paley graph of order q is P (q) := (V, E) where V = F q and E = {xy : x -y is a square mod q, x = y}.

In other words, P (q) is the Cayley graph on the additive group F q with generating set Q, the subgroup of squares in F × q . The condition q ≡ 1 mod 4 is equivalent to say that -1 is a square modulo q and this is needed in order to get undirected edges. The Paley graph P (q) is isomorphic to its complement, via multiplication by a non square. The automorphism group of P (q) contains Γ(q) := (F q , +) Q and acts transitively on the edges as well as on the non edges. So P (q) is a strongly regular graph. If q = 4t + 1, its parameters are v = 4t + 1, k = 2t, λ = t -1, µ = t. Being strongly regular, its ϑ number reaches the Hoffman bound ϑ(P (q)) = √ q

Noting that ϑ(P (q))ϑ(P (q)) = |V | = q because P (q) is vertex transitive and that P (q) P (q) leads to the same conclusion. Paley graphs are interesting because of their quasi-random behaviour. The independence number of Paley graphs P (p) has been calculated for primes p up to 7000 by James B. Shearer ([1]); Geoffrey Exoo extended it to p < 10000 ([2]). If q = q 2 0 is a square, then the subfield F q 0 is a clique of size √ q so in this case α(P (q)) = √ q. If q is not a square, α(P (q)) is not known.

In the remaining we restrict to the case when q = p is a prime number. We already calculated some values of ϑ and ϑ 2 for Paley graphs in table 5.1. In order to compute more values of ϑ 2 (P (p)) we need to symmetrize it under Aut(P (p)). We analyse this action in the next section.

Symmetry reduction of ϑ 2 for Paley graphs

Let us take the following notations: Z p := Z/pZ, Γ 0 := Z p Q and Γ := Z p Z × p . We let α denote a primitive element in Z p . An element of Γ is denoted (t, s) with t ∈ Z p and s ∈ Z × p . The group multiplication is (t, s)(t , s ) = (t + st , ss ) and the inverse is (t, s) -1 = (-ts -1 , s -1 ). The action of Γ on Z p is given by (t, s).x = t + sx. We sometimes simplify (t, 1) to t and (0, s) to s.

Orbits

The group Γ 0 acts transitively on V := Z p . The 2-subsets split into two orbits: the edges and the non-edges of P (p). Let us now consider the orbits on 3-subsets (also called triangles). It is clear that the number of edges in each triangle is an invariant. For i = 0, 1, 2, 3, let T i denote the set of triangles containing i edges. Multiplication by α sends bijectively T 0 to T 3 and T 1 to T 2 . Using the property that P (p) is strongly regular with parameters (p, (p -1)/2, (p -5)/4, (p -1)/4), we count

|T 3 | = |T 0 | = p(p -1)(p -5)/48 and |T 1 | = |T 2 | = p(p -1) 2 /16.
The following lemma describes the orbits of Γ 0 on T 0 and on T 1 : Lemma 6.2.1. For the action of Γ 0 on T 1 , we have:

(1) Every orbit contains an element of the type {0, 1, β} where β ∈ Q and β-1 ∈ Q.

(2) The triangle {0, 1, β } is in the same orbit as {0, 1, β} if and only if β belongs to {β, 1 -β}.

(3) The stabiliser of {0, 1, β} is trivial, unless 2 ∈ Q and β = 2 -1 , in which case it is of order 2 and is equal to {(0, 1), (1, -1)}.

For the action of Γ 0 on T 0 , we have:

(1) Every orbit contains an element of the type {0, α, β} where β ∈ Q and β-α ∈ Q.

(2) The triangle {0, α, β } is in the same orbit as {0, α, β} if and only if β belongs to {β, α 2 β -1 , α -β, α 2 (α -β) -1 , αβ -1 (β -α), αβ(β -α) -1 }.

(3) The stabiliser of {0, α, β} is trivial, unless we are in one of the following cases:

(i) 2 ∈ Q and β = 2α, -α, α/2, all three triangles are in the same orbit, and the stabiliser is {±1}.

(ii) 3 ∈ Q and α 2 + β 2 -αβ = 0, the two corresponding triangles are in the same orbit, and the stabiliser has order 3 generated by γ := (α, -αβ -1 ).

To summarize, every orbit except maybe one or two has length p(p -1)/2 so the number of orbits of Γ 0 acting on T 0 is essentially (p -5)/24.

The irreducible representations of Γ 0

The irreducible representations of Γ 0 are the following:

• We have the characters of degree one lifted from Q, through the quotient map Γ 0 → Γ 0 /Z p Q. There are (p -1)/2 such characters.

• We have the induced representations from characters of (Z p , +). Let χ be a non trivial character of (Z p , +). To fix ideas, let ζ p ∈ C be a p-th root of 1 and χ(t) := ζ t p . The representation Ind Γ 0 Zp χ is irreducible and has degree (p -1)/2. It can be described as R = ⊕ a∈Q Ce a with the action (t, 1).e a = χ(ta -1 )e a and (0, s).e a = e sa (and thus (t, s).e a = χ(ts -1 a -1 )e sa ). We see from its characters that among Ind Γ 0 Zp χ r , r ∈ Z × p , there are two classes of isomorphism corresponding to r ∈ Q and r ∈ Q.

To summarize, we have (p -1)/2 representations of degree 1 and 2 representations of degree (p -1)/2. It matches with |Γ 0 | = p(p -1)/2 = 1 2 • (p -1)/2 + ((p -1)/2) 2 • 2.

6.2.3

The decomposition of 2 C Z p under Γ 0 Let W = C Zp = ⊕ p-1 i=0 Ce i . The action of γ = (t, s) ∈ Γ 0 on e i is thus γe i = e t+si and on e i ∧ e j it is γ(e i ∧ e j ) = e t+si ∧ e t+sj . In view of the symmetrization of ϑ 2 we need a precise description of the irreducible decomposition of 2 W , namely we need an explicit orthonormal basis for each irreducible subspace, and when there are isomorphic irreducible subspaces, we need basis in which the action of Γ 0 is expressed by the same matrices.

We consider the natural ordering 0 < 1 < • • • < (p -1) for the elements of Z p and thus the standard basis of Λ 2 W is {e i ∧ e j , 0 ≤ i < j ≤ (p -1)}. Theorem 6.2.2. The irreducible characters appearing in the decomposition of Λ 2 W under the action of Γ 0 are:

• the (p -1)/4 characters lifted from characters ψ of Q such that ψ(-1) = -1, each with multiplicity 2,

• the characters Ind Γ 0 Zp χ and Ind Γ 0 Zp χ α , where χ is a character of (Z p , +), each with multiplicity (p -1)/2.

Proof. Let ψ be a multiplicative character of Q. We again denote ψ its lift to Γ 0 . We apply the idempotent 1 We see that e t ∧ e t+s = ±e 0 ∧ e 1 if and only if (t, s) = (0, 1) or (t, s) = (1, -1). In the last case e t ∧ e t+s = e 1 ∧ e 0 = -e 0 ∧ e 1 so v ψ 1 = 0 if and only if ψ(-1) = -1. Moreover, if ψ(-1) = -1, the expression of v ψ 1 on the standard basis is:

v ψ 1 = 1 |Γ 0 | i<j j-i∈Q
2ψ((j -i) -1 )(e i ∧ e j ). So v ψ 1 = 0 and γv ψ 1 = ψ(γ)v ψ 1 . That is, the space generated by v ψ 1 is G-stable and G acts on it with character ψ. In a similar way, we construct an element v ψ 2 such that γv ψ 2 = ψ(γ)v ψ 2 :

v ψ 2 := 1 |Γ 0 | s∈Q ψ(s -1 ) t∈Zp e t ∧ e t+sα = 1 |Γ 0 | i<j j-i∈Q 2ψ((j -i) -1 α)(e i ∧ e j ).
We note that it is orthogonal to v ψ 1 . Now we look for the subspaces isomorphic to Ind Γ 0 Zp χ, where χ is a character of (Z p , +). We consider, for = 0, u χ := 1 p t∈Zp χ(-t)(e t ∧ e t+ ).

We have that t.u χ = χ(t)u χ , u χ = -χ( )u χ -and u χ , u χ = 0 if = ± mod p. So the character χ of Z p occurs with multiplicity (p-1)/2 in u χ : = 1, . . . , (p-1)/2 . The character Ind Γ 0 Zp χ of Γ 0 occurs with multiplicity at least (p -1)/2. Indeed, the subspaces R := ⊕ s∈Q s.u χ for = 1, . . . , (p -1)/2, realize this representation, and the action of Γ 0 in the basis {s.u χ , s ∈ Q} is as described in the subsection 6.3.2. Moreover, the vectors {s.u χ , s ∈ Q, = 1, . . . (p -1)/2} are pairwise orthogonal: s.u χ , s.u χ = u χ , u χ = 0 if = and s.u χ , t.u χ = 0 if s = t because Z p acts with different characters on this vectors. It remains to express s.u χ in the standard basis. We have To summarize, we have found in 2 W : the (p -1)/4 characters ψ of Q such that ψ(-1) = -1, each of dimension 1 and with multiplicity 2 and the characters Ind Γ 0 Zp χ and Ind Γ 0 Zp χ α , each of dimension (p -1)/2 and with multiplicity (p -1)/2. Indeed, dim( 2 W ) = p 2 = 2 • (p -1)/4 + 2 • ((p -1)/2) • ((p -1)/2) so the lower bounds found for the multiplicities are equalities.

Expression of the Γ 0 -invariant matrices

Let X ∈ R ( p 2 )×( p 2 ) , then by theorem 2.4.1 we know that X is Γ 0 -invariant and positive semidefinite if and only if

X(ij, k ) = ψ : ψ(-1)=-1 A ψ , E ψ (ij, k ) + A χ , E χ (ij, k ) + A χ α , E χ α (ij, k )
where A ψ , A χ , A χ α are hermitian positive semidefinite matrices of size respectively 2, (p -1)/2, (p -1)/2. ) + χ((j -l)s -1 ) if a -1 (j -i) = b -1 (l -k) =: s and s ∈ Q

-1 p χ((l -i)s -1 ) + χ((j -k)s -1 ) if a -1 (j -i) = -b -1 (l -k) =: s and s ∈ Q 0 otherwise
The same formula holds for E χ α replacing χ with χ α .

The final reduction

We are now ready to symmetrize the program 5.3.1 for Paley graphs for the case k = 2. Recall the original formulation:

ϑ 2 (P (p)) = max L 1 , X : X ∈ R ( p 2 )×( p 2 ) 0 I, X = 1 X s,s = 0 only if s = s ∈ E or s ∪ s is a triangle without edges X ab,ac = -X ab,bc = X ac,bc ∀ a < b < c This program is clearly invariant for the Γ 0 action. Then, using the definition of L 1 and lemma 6. where Ω is such that {(0, α, β) : β ∈ Ω} is the collection of the canonical representatives of the orbits of Γ 0 on T 0 , and C β is the cardinality of the corresponding orbit.

The trace of X is given by Tr(X) = a<b : ab∈E X ab,ab = p(p -1) 4 X 0α,0α

Then, with the zonal matrices for the action of Γ 0 derived before, we can announce the final reduction of the program: where A ψ , A χ , A χ α are obtained as the scalar product of X with E ψ , E χ , E χ α respectively:

A ρ a,b = 1 dim(ρ) i<j, k< X(ij, kl) E ρ a,b (ij, k ).
In the following table we compare the bound of theorem 6.3.3 with the bound L 2 (P (p)) in [START_REF] Gvozdenovic | Block-diagonal semidefinite programming hierarchies for 0/1 programming[END_REF] Note: All values of the semidefinite programs have been obtained with the solvers SDPA or SDPT3, available on the NEOS website (http://www.neos-server.org/neos/).

Circulant subgraphs of Paley graphs

Definition 6.3.1. Given n ≥ 2 and J ⊂ {1, . . . , n -1} such that J = -J, the circulant graph C n (J) is the graph with vertices Z/nZ and edges {ij : i -j ∈ J}.

Equivalently, a circulant graph is a graph whose adjacency matrix is circulant, i.e. all of its rows are obtained by a cyclic shift of the first one. In particular, a circulant graph is a Cayley graph on an additive group with generating set J. Clearly, C n (J) is regular of degree |J|.

Let J = {1, . . . , n -1} \ J; then C n (J) is the complementary graph of C n (J). We introduce J 0 = J ∩ {1, . . . , n/2 } and note that J = J 0 ∪ -J 0 . We have Proof. If α is a primitive element of Z p and β = α 2 , then Q is the graph with vertices {β i , 0 ≤ i ≤ (p -3)/2} and edges between β i and β j if and only if β i -β j ∈ Q, or equivalently β i-j -1 ∈ Q. So Q is isomorphic to the circulant graph of order (p -1)/2 with associated set Proof. An independent set for P (p) can be assumed to contain 0 after translation. Then the non zero elements are contained in Q. Conversely, the union of an independent set of Q and {0} makes an independent set of P (p).

So, α(P (p)) ≤ ϑ(Q) + 1 and, as Q is a subgraph of P (p), ϑ(Q) ≤ ϑ(P (p)).

Formulations for the ϑ number of a circulant graph

Remember that Q is a circulant graph of even order n = (p -1)/2. So for the rest of the section we assume that n is even and we look at ϑ(C n (J)) more in details. Due to transitivity of Z n , the ϑ number is a linear program. Proof. By definition, we have ϑ(C n (J)) = max{ F (γ, δ) : F ∈ R n×n , F 0 F (γ, γ) = 1 F (γ, δ) = 0 if γ -δ ∈ J } Such program is invariant for the additive action of Z/nZ on itself, thus we can restrict to consider functions F such that F (γ + x, δ + x) = F (γ, δ) for any x ∈ Z/nZ. Such functions can be written as F (γ, δ) = F (γ -δ) for some F : Z/nZ → R such that F (-j) = F (j).

Recall that the characters of Z/nZ are given by: χ : Z/nZ -→ C × j -→ e 2iπj /n for = 0, . . . , n -1. Then F expands as

F (j) = n-1 =0 f χ (j) = n-1 =0 f e 2iπj /n
with the following properties: So, renaming f 0 = nf 0 and f = 2nf for = 1, . . . , n -1, we find 6.5.1. By duality, 6.5.2 follows.

• F 0 ⇔ f ≥ 0 ∀ • F
We note J c 0 = {1, . . . , n/2} \ J 0 . For the Paley graph, J c 0 (Q) = J 0 (Q). For p ≡ 1 mod 8 they have the same number of elements. For p ≡ 5 mod 8 they differ by 1. Then the idea is that the two optimal values ϑ(Q) and ϑ(Q) are rather close because the sets J 0 (Q) and J 0 (Q) are random enough, with the consequence that the cosinus are "interlaced" enough.

We have computed some values of the linear program ϑ(Q) up to p < 20000. The optimal value is around (p -1)/2, but it doesn't seem to converge. Remark 6.4.2. The optimal value of (6.5.1) for Q is obtained for f * such that some of the coordinates f * = 0. Let us denote {0} ∪ L the support of the optimal solution f * . Then |L| = |J 0 | so that f * is uniquely obtained by solving a linear system (this is because the vertices of the polytope on which we are optimizing are all obtained this way: by setting an appropriate number of coordinates to zero). Then the optimal value for Q has support {0} ∪ L. However we couldn't so far find a relationship between J 0 and L.

Here the discussion remains open. From the relation ϑ(Q)ϑ(Q) = (p -1)/2 and the considerations above, one can hope that, roughly speaking,

ϑ(Q) ≈ ϑ(Q) ≈ (p -1)/2
This would lead to a minor improvement on the estimate of α(P (p)) with respect to the known bound α(P (p)) ≤ √ p. Nevertheless it seems that it is really hard to improve this bound, especially with a multiplicative factor. In [START_REF] Bachoc | Squares and difference sets in finite fields[END_REF] the authors prove α(P (p)) ≤ √ p -1 under some conditions on p.

  (a, b)(a , b ) : a = a or aa ∈ E and b = b or bb ∈ E}. Let G k denote the strong product of G with itself k times. Definition 2.3.3. The Shannon capacity of a graph G is defined by

  , 5), where D 3 ≤ 17 and, by Theorem 3.5.1, if D 5 = 1 then D 3 ≤ 16. So we can add D 3 + D 5 ≤ 17 and D 2 + D 4 ≤ 17, leading to: Theorem 3.5.2.

Figure 4 .

 4 Figure 4.a: Moser unit distance graph

Figure 4 .

 4 Figure 4.b: Hexagonal tiling

  Frankl-Wilson graph associated to the pair (n, p) is the graph J(n, p) with vertex set V = 1 √ 2p J 2p-1 n and edges set E = {xy : x.y = (p -1)/2p}.

  we define a := |x∩z|, b := |y ∩ z|, c := |x ∩ y|, d := |x ∩ y ∩ z| and we have:

Theorem 4 . 3 . 6 .

 436 Two elements of X 3 are in the same orbit under the action of S n if and only if they give rise to the same 4-tuple (a,

Theorem 4 . 3 . 9 . 3 F

 4393 y) thus obtaining an explicit formula in terms of the variables y abcd := x abcd F (a, b, c, d). This yields the final reduction of program 4.3.1 in J w n : The maximum number of words in J w n avoiding Johnson distance δ is upper bounded by the optimal value of the following semidefinite program: sup w b=0 y wbbb : y abcd = y σ(a)σ(b)σ(c)d ∀ σ ∈ S k,h 0 y abcd ≥ 0 ∀ (a, b, c, d) ∈ Ω(n, w) y wwww = 1

Proposition 5 . 3 . 8 .Lemma 5 . 3 . 9 .Corollary 5 . 3 . 11 .Theorem 5 . 3 . 12 .

 53853953115312 The chromatic number χ(G) of a graph G is the least natural number such that there exists a homomorphism G → K where K denotes the complete graph on vertices.If = χ(G), then ϑ k (G) ≤ ϑ k (K ).Proof. By previous definition and theorem 5.3.7. Proposition 5.3.10. If n is the number of vertices of G, then ϑ k (G) ≤ n for all k. Proof. A feasible solution of the dual program is given by the matrix L k-1 itself, which has largest eigenvalue n. For all k, ϑ k (K ) = . Proof. By proposition 5.3.6 together with proposition 5.3.10. From all previous results, we obtain the sandwich theorem for ϑ k . For all graph G and all k, α(G) ≤ ϑ k (G) ≤ χ(G). Remark 5.3.13. To prove corollary 5.3.11 we only need the special case of proposition 5.3.6 when G = K . Then the general inequality α(G) ≤ ϑ k (G) can also be derived from theorem 5.3.7 and corollary 5.3.11 via the clique number ω. By definition, ω(G)

Corollary 5 . 4 . 6 .

 546 If there exists a graph homomorphism ϕ : G → H, then, for any k, θk (G) ≤ θk (H).

Figure 6

 6 Figure 6.a: Paley graphs of order 13 and 17

|Γ 0 |

 0 γ∈Γ 0 ψ(γ -1 )γ to e 0 ∧ e 1 leading tov ψ 1 := 1 |Γ 0 | s∈Q ψ(s -1 ) t∈Zp e t ∧ e t+s

  s.u χ = 1 p t∈Zp χ(-t)(e st ∧ e st+s ) = 1 p t∈Zp χ(-ts -1)(e t ∧ e t+s ) is -1 )(e i ∧ e j ) -i<j j-i=-s χ(-js -1 )(e i ∧ e j )

For 1

 1 ≤ a, b ≤ 2, E ψ a,b (ij, k ) = v ψ a / v ψ a , e i ∧ e j v ψ b / v ψ b , e k ∧ e j-i) -1 (l-k)α a-b ) p(p-1) a, b ≤ (p -1)/2, E χ a,b (ij, k ) = s∈Q s.u χ a / s.u χ a , e i ∧ e j s.u χ b / s.u χ b , e k ∧ e (k -i)s -1

  3.1, the objective function writes asL 1 , X = 2 a<b X ab,ab + 6 a<b<c X ab,ac = 2Tr(X) + 6 a<b<c : abc∈T 0 X ab,ac = 2 + 6 β∈Ω C β X 0α,0β

Theorem 6 . 2 . 3 . 4 X

 6234 With the previous notation, for every p prime,α(P (p)) ≤ 2 + 6 max β∈Ω C β X 0α,0β : A ψ , A χ , A χ α 0 p(p-1) 0α,0α = 1

  |J 0 | = |J|/2 if n/2 / ∈ J and |J 0 | = (|J| + 1)/2 otherwise. Obviously C n (J) C n (aJ) for a ∈ Z × n .Because translations by Z n act transitively on vertices of C n (J), we haveϑ(C n (J))ϑ(C n (J)) = n. (6.3.1) Let Q be the subgroup of squares of Z × p and Q = Z × p \ Q, so that we have the disjoint union Z p = Q ∪ Q ∪ {0}.Proposition 6.3.2. The induced subgraphs Q and Q of the Paley graph P (p) are circulant graphs of order n = (p -1)/2.

J

  (Q) = {j ∈ [(p -3)/2] : β j ∈ 1 + Q} and similarly Q C (p-1)/2 (J(Q)) for J(Q) = {j ∈ [(p -3)/2] : β j ∈ 1 + Q}.We note that |J(Q)| = (p -5)/4 and |J(Q)| = (p -1)/4, due to strong regularity of Paley graphs. On the other hand we have Theorem 6.3.3. α(P (p)) = α(Q) + 1

  n (J)) = max{ nf 0 : f ∈ R 1+n/2 f 0 , f 1 , . . . , f n/2 ≥ 0 n/2 =0 f cos 2π j n = δ j,0 j ∈ {0} ∪ J 0 } (6.4.1) ϑ(C n (J)) = min{ ng 0 : g ∈ R 1+|J 0 | j∈{0}∪J 0 g j cos 2π j n ≥ δ ,0 ∈ [0, . . . , n/2] } (6.4.2)

  real-valued implies that f = f n-∀ • it follows that F (j) = f 0 + n/2 =1 2f cos(2πj /n) • we have γ,δ∈Z/nZ F (γ, δ) = n j∈Z/nZ F (j) = n nf 0 + 2f n-1 j=0 cos(2πj /n) = n 2 f 0 γ∈Z/nZ F (γ, γ) = n F (1) = n(f 0 + 2f 1 + • • • + 2f n/2 )F (j) = 0 for j ∈ J 0

  m d where parentheses correspond to isotypic components, i.e. we have H k,i H k ,i if and only if k = k . For all k, i we choose an orthonormal basis (e k,i,1 , . . . , e k,i,d k ) of H k,i , such that the complex numbers g.e k,i,s , e k,i,t do not depend on i (such a basis exists precisely because the G-isomorphism class of H k,i does not depend on i). From this data, we introduce the m k

Table 3 .

 3

	A 2 (4, 3) 6	6
	A 2 (5, 3) 20	20
	A 2 (6, 3) 124	124
	A 2 (7, 3) 832	776
	A 2 (7, 5) 36	35
	A 2 (8, 3) 9365	9268
	A 2 (8, 5) 361	360
	A 2 (9, 3) 114387	107419
	A 2 (9, 5) 2531	2485
	A 2 (10, 3) 2543747 2532929
	A 2 (10, 5) 49451	49394
	A 2 (10, 7) 1224	1223
	A 2 (11, 5) 693240	660285
	A 2 (11, 7) 9120	8990
	A 2 (12, 7) 323475	323374
	A 2 (12, 9) 4488	4487
	A 2 (13, 7) 4781932 4691980
	A 2 (13, 9) 34591	34306
	A 2 (14, 9) 2334298 2334086
	A 2 (14, 11) 17160	17159
	A 2 (15, 11) 134687	134095
	A 2 (16, 13) 67080	67079

1: Bounds for the subspace distance Theorem 3.5.1. Let C ⊂ P(F n q ), of minimal subspace distance d, and let D k

Table 3 .

 3 2 displays the numerical computations obtained from the two programs, in the same manner as for Table1.

		E-V LP SDP
	A inj 2 (7, 3)	37	37
	A inj 2 (8, 3)	362	364
	A inj 2 (9, 3)	2533	2536
	A inj 2 (10, 3) 49586	49588
	A inj 2 (10, 4) 1229	1228
	A inj 2 (11, 4) 9124	9126
	A inj 2 (12, 4) 323778	323780
	A inj 2 (12, 5) 4492	4492
	A inj 2 (13, 5) 34596	34600
	A inj 2 (14, 6) 17167	17164
	A inj 2 (15, 6) 134694	134698
	A inj 2 (16, 7) 67087	67084

Table

3 .

 3 Remark 4.4.1. Here we see that for small parameters the SDP bound is stronger than the bound of Frankl and Wilson. What is not known is the asymptotic behaviour of the SDP bound. In particular, can it beat the (1.207) n obtained withFrankl-

	(n, w, i) α(J(n, w, i)) F-W bound LP bound SDP bound
	(6, 3, 1)	4	6	4
	(7, 3, 1)	5	7	5
	(8, 3, 1)	8	8	8
	(9, 3, 1)	8	9	11
	(10, 5, 2) 27	45	30
	(11, 5, 2) 37	55	42
	(12, 5, 2) 57	66	72
	(12, 6, 2)			130
	(13, 5, 2)		78	109
				Wilson
	graphs?

  If there exists a graph homomorphism ϕ : G → H, then, for any k, ϑ k

		which goes as follows:
	φk (X) u,u :=	X s,s
	s : ϕ(s)=u
	s : ϕ(s )=u
	where u, u ∈ V H k and s, s ∈ V G k .
	Then the next theorem generalizes proposition 2.3.12.
	Theorem 5.3.7.

Table 5 .

 5 1: Values of ϑ, ϑ 2 , ϑ + 2 on some cycles and Paley graphs

	ϑ	ϑ 2	ϑ + 2
	C 5 2.236 2	2
	C 7 3.317 3	4
	C 9 4.36 4.019 4.119
	C 11 5.386 5	5
	C 15 7.417 7.007 7.021
	C 23 11.446 11.003 11.016
	P (13) 3.605 3	4
	P (17) 4.123 3.242 4.044
	P (29) 5.385 4.443 4.228
	P (37) 6.082 4.611 4.354
	P (41) 6.403 5.177 5
	P (53) 7.280 5.438 5.756

Table 6 .

 6 (see section 2.2.3) for several values of p. The reason is that both bounds involve triples of words. 1: Values of ϑ 2 (P (p))

	p	√ p	ϑ 2 (P (p)) L 2 (P (p)) α(P (p))
	61 7.810	5.874	5.465	5
	73 8.544	6.236	5.973	5
	89 9.433	6.304	6.304	5
	97 9.848	7.517	7.398	6
	101 10.049	6.898	6.611	5
	109 10.440	7.366	7.366	6
	113 10.630	7.676	7.599	7
	137 11.704	8.623	8.200	7
	149 12.206	8.750	8.231	7
	157 12.529	8.851	8.707	7
	173 13.152 10.020	9.426	8
	181 13.453	9.466	9.112	7
	193 13.892	9.301	9.210	7
	197 14.035	9.902	9.226	8
	229 15.132 10.707	10.290	9
	233 15.264 10.537	10.182	7
	241 15.524 10.073	9.891	7
	257 16.031 10.469	10.247	7
	269 16.401 11.450	10.624	8
	277 16.643 11.282	10.340	8
	281 16.763 11.034	10.605	7
	293 17.117 11.706	10.937	8
	313 17.691 12.182	11.551	8
	317 17.804 12.535	12.337	9
	337 18.357 12.129	11.658	9
	401 20.024 13.329	12.753	9
	509 22.561 14.974	14.307	9
	601 24.515 16.694	16.077	11
	701 26.476 17.581	16.857	10
	809 28.442 18.439	17.371	11

This chapter reproduces contents and results of[START_REF] Bachoc | Bounds for projective codes from semidefinite programming[END_REF].

Remerciements

Density of sets avoiding distance 1

The lower bounds on the Euclidean chromatic number obtained by the results of table [START_REF] Alizadeh | Interior point methods in semidefinite programming with applications to combinatorial optimization[END_REF].1 together with the inequality 4.2.1 don't improve over the existing ones. In this section we will explain how those results can be used to improve bounds on the so-called measurable chromatic number of the Euclidean space, that is in the case when the color classes are required to be measurable with respect to the Lebesgue measure of R n . Definition 4.5.1. The measurable chromatic number of the real Euclidean space R n , denoted χ m (R n ), is the minimum number of colors needed to color R n in such a way that points at distance 1 receive different colors and so that points receiving the same color form Lebesgue measurable sets.

Clearly, we have the inequality χ m (R n ) ≥ χ(R n ). For the plane, it is only known that 5 ≤ χ m (R 2 ) ≤ 7 ( [START_REF] Falconer | The realization of distances in measurable subsets covering R n[END_REF]). We introduce the density of a measurable set A:

and the extreme density of a set avoiding distance 1:

As a coloring gives a partition of R n and δ(R n ) = 1, we have the relation

so we can focus on upper bounds for the extreme density of sets avoiding distance 1 in order to find lower bounds for the measurable chromatic number.

In [START_REF] De Oliveira Filho | Fourier analysis, linear programming and densities of distance avoiding sets in R n[END_REF], an upper bound on m 1 is given in the form of the optimal value of a linear program (see [START_REF] De Oliveira Filho | Fourier analysis, linear programming and densities of distance avoiding sets in R n[END_REF] for the definition of the function Ω n ): Theorem 4.5.2 ([13], theorem 1.1).

Moreover, an explicit optimal solution of the program above can be described in terms of the absolute minimum of Ω n .

The linear program above can be strengthened by adding linear inequalities coming by well chosen finite unit distance graphs in R n . Indeed, in [START_REF] De Oliveira Filho | Fourier analysis, linear programming and densities of distance avoiding sets in R n[END_REF] it is shown how the bound 4.5.1 can be modified by using the regular simplex. With this new program, improvements are obtained on m 1 (R n ) (hence also on χ m (R n )) for n = 4, . . . , 24. The same reasoning can be applied with a unit distance graph other than the regular simplex and theorem 4.5.1 becomes:

where, for x i ∈ V , r i := x i . Remark 4.5.4. The program 4.5.2 involves an uncountable set of linear constraints. The method to solve a linear program of this kind is to discretize an interval ]0, M ], then solve the linear program for t restricted to such discretized values and finally (if needed) adjust the optimal solution by adding a constant factor.

At this point, it is clear how to use the upper bounds on α(J(n, w, i)) of table 4.1 in theorem 4.5.2 to upper bound m 1 (R n ).

Numerical results

In the following two tables we give improved upper bounds on m 1 (R n ) and lower bounds on χ m (R n ). For n = 9, . . . , 23 we give:

• the best previously known bound (from the table in [START_REF] De Oliveira Filho | Fourier analysis, linear programming and densities of distance avoiding sets in R n[END_REF]),

• the bound of theorem 4.5.2 applied with regular simplices, established in [START_REF] De Oliveira Filho | Fourier analysis, linear programming and densities of distance avoiding sets in R n[END_REF],

• the bound of theorem 4.5.2 together with our choice of the unit distance graph G = J(n, w, i). The "*" indicates that the upper bound on α(G) from our theorem 4.3.9 is used. Chapter 5

Hierarchy of semidefinite programs from simplicial complexes

In this chapter we introduce a new sequence ϑ k of semidefinite programs whose optimal value upper bound the independence number of a graph. To define it, we adopt the framework of simplicial complexes, which we introduce in the second section. In the third section we give the definition of ϑ k . We show that, as for the hierarchies recalled in chapter 2, the first step coincides with the ϑ number and, for a graph G, the α(G)-th step yields the exact value α(G). We prove that the sandwich theorem holds for any step of the new sequence ϑ k , along with a result involving graph homomorphisms which generalizes one well known property of ϑ. A drawback is that we don't know whether this "hierarchy" is decreasing at any step or not. To insure the decreasing property, in the fourth section we slightly modify the SDP formulation of ϑ k and we show that this modification is compatible with all the properties of ϑ k proved before. In the fifth section, some values of the second step of our hierarchy are computed for cycle graphs and Paley graphs. They show significant improvements over the first step.

Introduction

Let A be the adjacency matrix of a graph G = (V, E) and D be the diagonal matrix with D i,i = deg(i). The matrix L 0 := D -A is called the Laplacian of the graph G.

Recall the dual formulation for Lovász ϑ number of G:

We note that the constraint on Z is that Z = J outside of the support of A. So it is natural to optimize over the set

are called faces and the dimension of a face A ∈ ∆ is defined as dim(A) := |A| -1. The set of faces of dimension k is denoted by ∆ k . We remark that abstract simplicial complexes can be thought of as a generalization of graphs. Indeed, a graph is nothing else than a complex with faces of dimension 0 (vertices) and 1 (edges), apart from the empty set. For more details on simplicial complexes, see [START_REF] Jonsson | Simplicial complexes of graphs[END_REF]. The goal of this section is to define a pair of matrices associated to a simplicial complex, one of which is a generalization of the Laplacian of a graph. For the rest of this section, take V = {v 1 , . . . , v n } to be a finite set of cardinality n.

Let W := R V , let k W denote the k-th exterior power of W and let the boundary operator δ k be defined as:

where {s 0 , . . . , s k } ⊂ {v 1 , . . . , v n } and (s 0 ∧ • • • ∧ s k ) j means that s j has been removed from s 0 ∧• • •∧s k , leaving the others in place. The above definition makes sense because

The real vector spaces k W are endowed with the standard inner product. The adjoint operator δ * k is given by:

(5.2.2)

Let ∆ be an abstract simplicial complex on V , let C k be the subspace of k+1 W generated by

The dimension d k of C k is obviously equal to the number of faces of ∆ of dimension k. We remark that δ k (C k ) ⊂ C k-1 . We keep the same notation δ k for the restricted application δ k : C k → C k-1 and δ * k for its adjoint operator, which is given by

We introduce

In order to write L k-1 and L k-1 in matrix form, we need to choose basis of the spaces C k . For that we put an arbitrary order relation among elements of V and we will express all matrices of linear transformations of the spaces C k in the standard basis, given by the faces

We have

For all s ∈ ∆ k-1 , let deg(s) denote the number of k-dimensional faces that contain s. We note that the number of (k -2)-dimensional faces that are contained in s is necessarily equal to k as all subsets of s belong to ∆. Moreover, for s, s

We remark that the entries corresponding to (s, s ) with |s ∪ s | ≥ k + 2 are equal to zero in both matrices, and that (L k-1 ) s,s = -(L k-1 ) s,s if s ∪ s ∈ ∆ k .

Examples

Example 1: Let G = (V, E) be a graph and take ∆ = {E, V, ∅}. We have δ 1 (s 0 ∧s 1 ) = s 1 -s 0 and δ 0 (s k ) = 1.

We have

so, in terms of matrices, we see that

where D is the diagonal matrix with deg(u) on the diagonal and A is the adjacency matrix of G. We recognize in L 0 the Laplacian of G.

Example 2: Let G = (V, E) be a graph with no isolated vertex. Let ∆ be the set T of 3-sets of vertices t = {v 1 , v 2 , v 3 } such that t contains at least an edge, together with all subsets of elements of T .

where deg(uv) = |{t ∈ T : uv ⊂ t}|. We note that

For the matrices,

where |xyuv| stands for the the cardinal of {x, y, u, v}, and thesign occurs in the last case iff x < y = u < v or u < v = x < y.

and the + sign occurs in the last case iff

We analyse the spectrum of L 1 : from the above expressions it is easy to check that L 1 N T 1 = nN T 1 , hence (L 1 ) 2 = nL 1 , from which we derive that L 1 has eigenvalues n and 0. The multiplicity of n is Tr(L 1 )/n = n-1 and the eigenspace of n is Im(N T 1 ).

Example 3:

The above example extends to (k + 1)-subsets. We define ∆ as the set T of (k + 1)-subsets of V that contain at least an edge, together with all subsets of V with at most k elements. Then

We note that {∆ i , i ≤ k -1} is the complete complex which has trivial homology. We analyse the spectrum of L k-1 : from (5.2.5) it is easy to check that

) 2 = nL k-1 from which we derive that L k-1 has eigenvalues n and 0. The multiplicity of n is Tr(L k-1 )/n = k n k /n and the eigenspace of n is Im(N T k-1 ).

Example 4: Another complex of great interest is the cliques complex, where for i ≤ k, ∆ i is the set ∆ cl i of cliques on (i + 1) vertices in the graph. We note that the union of two k-cliques that intersect on k -1 vertices is a clique if and only if the two vertices that do not belong to the intersection are connected. The formulas for the coefficients of L k-1 and L k-1 are the same as above.

Example 5: More generally, if G is a (k+1)-uniform hypergraph, i.e. a set of vertices V together with a set S of (k + 1)-subsets of V called hyperedges, we can take for ∆ the set S of hyperedges together with all their subsets. For example S can be the set of induced subgraphs of G that belong to a given isomorphism class. The same formulas as in Example 3 give the coefficients of L k-1 and L k-1 . The matrix L k-1 (sometimes L k-1 + L k-1 ) is called the Laplacian of G.

Generalized ϑ numbers

Recall from chapter 2 the following formulations for Lovász ϑ number of a graph G = (V, E):

Since this program is not strictly feasible, we don't know if strong duality holds. However, its dual formulation is given in the following lemma:

Semidefinite programming in combinatorial optimization with applications to

coding theory and geometry.

Abstract: We apply the semidefinite programming method to obtain a new upper bound on the cardinality of codes made of subspaces of a linear vector space over a finite field. Such codes are of interest in network coding. Next, with the same method, we prove an upper bound on the cardinality of sets avoiding one distance in the Johnson space, which is essentially Schrijver semidefinite program. This bound is used to improve existing results on the measurable chromatic number of the Euclidean space. We build a new hierarchy of semidefinite programs whose optimal values give upper bounds on the independence number of a graph. This hierarchy is based on matrices arising from simplicial complexes. We show some properties that our hierarchy shares with other classical ones. As an example, we show its application to the problem of determining the independence number of Paley graphs. Keywords: graph theory, stable number, chromatic number, SDP, projective codes, hierarchies.

Discipline : Mathématiques pures

Institut de Mathématiques de Bordeaux

Université Bordeaux 1, 351, cours de la libération,