Academic literature on the topic 'Matrice partitions'

On dit d'un sous-ensemble de NP qu'il présente une dichotomie s'il contient des problèmes qui sont soit résolubles en temps polynomial (dans Ptime), soit difficiles (NP-complets). La classe des problèmes de satisfaction de contraintes (CSP) finis est un sous-ensemble bien connu de NP qui présente une telle dichotomie. La classe de complexité NP n'a pas de dichotomie à moins que P = NP. Pour ces deux classes, il existe des logiques qui leur sont associées. -- NP est capturé par la logique Existentielle du second ordre (ESO) par le théorème de Fagin, c'est-à-dire qu'un problème est dans NP si et seulement s'il est exprimable par une formule ESO.-- CSP est un sous-ensemble de la logique de Feder et Vardi, le fragment monotone, monadique et sans inégalités de SNP, lui-même un fragment syntaxique de ESO (MMSNP); et, pour chaque formule de MMSNP, il existe un problème CSP équivalent via des réductions polynomiales.Ceci implique que la logique ESO, tout comme NP, n'a pas de dichotomie, à contraster avec le fait que MMSNP a une dichotomie tout comme CSP. L'objectif principal de cette thèse est d'étudier les propriétés de dichotomie de sous-ensembles de NP qui contiennent strictement CSP ou MMSNP.Feder et Vardi ont prouvé que si nous omettons une des trois propriétés qui définissent MMSNP, à savoir être monotone, monadique ou omettre les inégalités, alors la logique résultante n'a pas de dichotomie. Comme leurs preuves restent parfois sommaires, nous revisitons ces résultats et fournissons des preuves détaillées. Le fragment guardé et monotone de SNP (GMSNP) est une extension connue de MMSNP qui est obtenue en relâchant la restriction "monadique" de MMSNP. Nous définissons de manière similaire une nouvelle logique appelée MMSNP avec des inégalités gardées, en relâchant la restriction d'être "sans inégalités". Nous prouvons qu'elle est strictement plus expressive que MMSNP et qu'elle possède également une dichotomie.Il existe une logique MMSNP₂ qui étend MMSNP de la même manière que MSO₂ étend la logique monadique du second ordre (MSO). On sait que MMSNP₂ est un fragment de GMSNP et que ces deux classes ont toutes deux une dichotomie ou n'en ont pas. Nous revisitons ce résultat et le renforçons en prouvant que, en ce qui concerne le fait d'avoir une dichotomie, sans perte de généralité, on peut considérer seulement les problèmes MMSNP₂ sur des signatures à un élément, au lieu des problèmes GMSNP sur des signatures finies arbitraires.Nous cherchons à prouver l'existence d'une dichotomie pour les MMSNP₂ en construisant en temps polynomial, pour tout problème MMSNP₂, un problème MMSNP équivalent. Nous rencontrons quelques obstacles pour construire une telle équivalence. Cependant, si nous permettons aux formules MMSNP d'être composées d'un nombre dénombrable de conjonctions négatives, nous prouvons qu'une telle équivalence existe. De plus, la formule MMSNP infinie correspondante a la propriété d'être "régulière". Cette propriété de régularité signifie que, dans un certain sens, cette formule est essentiellement finie. Il est connu que les problèmes MMSNP réguliers peuvent être exprimés par CSP sur des modèles oméga-catégoriques. De plus, il existe une caractérisation de la dichotomie algébrique pour les CSP oméga-catégoriques qui décrivent des problèmes MMSNP. Si l'on parvient à étendre cette caractérisation algébrique sur les problèmes réguliers MMSNP, alors notre résultat fournirait une dichotomie algébrique pour MMSNP₂. (...)<br>A subset of NP is said to have a dichotomy if it contains problem that are either solvable in P-time or NP-complete. The class of finite Constraint Satisfaction Problems (CSP) is a well-known subset of NP that follows such a dichotomy. The complexity class NP does not have a dichotomy unless P = NP. For both of these classes there exist logics that are associated with them. -- NP is captured by Existential Second-Order (ESO) logic by Fagin's theorem, i.e., a problem is in NP if and only if it is expressible by an ESO sentence.-- CSP is a subset of Feder and Vardi's logic, Monotone Monadic Strict NP without inequalities (MMSNP), and for every MMSNP sentence there exists a P-time equivalent CSP problem. This implies that ESO does not have a dichotomy as well as NP, and that MMSNP has a dichotomy as well as CSP. The main objective of this thesis is to study subsets of NP that strictly contain CSP or MMSNP with respect to the dichotomy existence.Feder and Vardi proved that if we omit one of the three properties that define MMSNP, namely being monotone, monadic or omitting inequalities, then the resulting logic does not have a dichotomy. As their proofs remain sketchy at times, we revisit these results and provide detailed proofs. Guarded Monotone Strict NP (GMSNP) is a known extension of MMSNP that is obtained by relaxing the "monadic" restriction of MMSNP. We define similarly a new logic that is called MMSNP with Guarded inequalities, relaxing the restriction of being "without inequalities". We prove that it is strictly more expressive than MMSNP and that it also has a dichotomy.There is a logic MMSNP₂ that extends MMSNP in the same way as MSO₂ extends Monadic Second-Order (MSO) logic. It is known that MMSNP₂ is a fragment of GMSNP and that these two classes either both have a dichotomy or both have not. We revisit this result and strengthen it by proving that, with respect to having a dichotomy, without loss of generality, one can consider only MMSNP₂ problems over one-element signatures, instead of GMSNP problems over arbitrary finite signatures.We seek to prove the existence of a dichotomy for MMSNP₂ by finding, for every MMSNP₂ problem, a P-time equivalent MMSNP problem. We face some obstacles to build such an equivalence. However, if we allow MMSNP sentences to consist of countably many negated conjuncts, then we prove that such an equivalence exists. Moreover, the corresponding infinite MMSNP sentence has a property of being "regular". This regular property means that, in some sense, this sentence is still finite. It is known that regular MMSNP problems can be expressed by CSP on omega-categorical templates. Also, there is an algebraic dichotomy characterisation for omega-categorical CSPs that describe MMSNP problems. If one manages to extend this algebraic characterisation onto regular MMSNP, then our result would provide an algebraic dichotomy for MMSNP₂.Another potential way to prove the existence of a dichotomy for MMSNP₂ is to mimic the proof of Feder and Vardi for MMSNP. That is, by finding a P-time equivalent CSP problem. The most difficult part there is to reduce a given input structure to a structure of sufficiently large girth. For MMSNP and CSP, it is done using expanders, i.e., structures, where the distribution of tuples is close to a uniform distribution. We study this approach with respect to MMSNP₂ and point out the main obstacles. (...)

Cette thèse est consacrée à l'étude d'identités qu'on observe à l'interface entre le domaine des modèles intégrables en physique statistique et la combinatoire. L'histoire a commencé quand Mills, Robbins et Rumsey étudiaient des Matrices à Signes Alternants (ASM). En 1982, ils proposèrent une formule d'énumération. Pendant qu'ils cherchaient une preuve de cette formule ils découvrirent l'existence d'autres objets comptés par la même formule : les Partitions Planes Totalement Symétriques Auto-Complémentaires (TSSCPP). C'est seulement quelques années plus tard que Zeilberger fut capable de prouver cette égalité, prouvant que les deux objets sont comptés par la même formule. La même année, Kuperberg utilise l'intégrabilité quantique (notion venue de la physique statistique) pour donner une preuve plus simple. En 2001, Razumov et Stroganov conjecturèrent une intrigante relation entre les ASM et l'état fondamental du modèle de spins XXZ (pour Delta=-1/2), lui aussi intégrable. Cette conjecture a été démontrée en 2010 par Cantini et Sportiello. L'objectif principal de ce manuscrit est de comprendre le rôle de l'intégrabilité dans cette histoire, notamment le rôle joué par l'équation de Knizhnik-Zamolodchikov quantique. Grâce à cette équation nous avons été capables de démontrer plusieurs conjectures combinatoires, dont une version raffinée de l'équalité entre le nombre des TSSCPP et des ASM proposée en 1986 par Mills, Robbins et Rumsey et certains propriétés des composantes du vecteur fondamental du modèle XXZ. Est présentée aussi une série de nouvelles conjectures concernant l'état fondamental.

Cette thèse est consacrée à l'étude d'identités qu'on observe à l'interface entre le domaine des modèles intégrables en physique statistique et la combinatoire. L'histoire commence quand Mills, Robbins et Rumsey étudiaient des Matrices de Signe Alternant (ASM). En 1982, ils proposèrent une formule d'énumeration. Pendant qu'ils cherchaient une preuve de cette formule ils découvrirent l'existence d'autres objets comptés par la même formule : les Partitions Planes Totalement Symétriques Auto-Complementaires (TSSCPP). C'est seulement quelques années plus tard que Zeilberger fut capable de prouver cet équalité, prouvant que tout les deux objets sont comptés par la même formule. La même année, Kuperberg utilise l'integrabilité quantique (notion venu de la physique statistique) pour donner une preuve plus simple. En 2001, Razumov et Stroganov conjecturèrent une intrigante relation entre les ASM et l'état fondamental du modèle de spins XXZ (pour Delta=-1/2), lui aussi intégrable. Cette conjecture fut démontrée en 2010 par Cantini et Sportiello. L'objectif principal de ce manuscrit est de comprendre le rôle de l'intégrabilité dans cette histoire, notamment, le rôle joué par l'équation Knizhnik-Zamolodchikov quantique. Grâce à cette équation nous avons été capables de démontrer plusieurs conjectures combinatoires, dont une version raffinée de l'équalité entre le nombre des TSSCPP et des ASM proposée en 1986 par Mills, Robbins et Rumsey et certains propriétés des composantes du vecteur fondamental du modèle XXZ. Est présentée aussi une série de nouvelles conjectures concernant l'état fondamental.

Cette thèse se situe dans le domaine de la combinatoire bijective et est consacrée à la construction d’une bijection explicite entre deux familles d’objets combinatoires : les matrices à signes alternants (ASMs) et les partitions planes totalement symétriques auto-complémentaires (TSSCPPs). L’histoire a commencé lorsque Milis, Robbins et Rumsey étudiaient les ASMs et proposèrent une formule d’énumération en 1982. Durant leurs recherches, ils découvrirent l’existence d’autres objets comptés par la même formule : les TSSCPPs. Dix ans plus tard, une preuve non bijective de l’équiénumération de ces deux familles fut donnée par Zeilberger. Pour ce faire, Zeilberger utilise deux sous classes de motif de Gelfand-Tsetlin ; les triangles Gog et les triangles Magog. Pendant ces dernières années les recherches se sont multipliées afin de donner une preuve bijective du théorème de Zeilberger. Citons notamment les travaux de Krattenthaler qui construit une bijection explicite entre les trapézoïdes Gog et Magog à une ligne. L’étape suivante, celle des trapézoïdes à deux lignes, semblait inaccessible. L’objectif de cette thèse est de résoudre ce problème grace à l’utilisation d’un outil fondamental en combinatoire, l’involution de Schiitzenberger. Nous avons pour cela défini des nouvelles statistiques sur les triangles Gog et les triangles Magog et nous montrons expérimentalement que la bijection que nous construisons respecte ces statistiques. Nous présentons également de nouvelles conjectures sur ces statistiques.

We explore two methods for calculating the Taylor Coefficients of the terms of the asymptotic expansion of the partition function of random matrices for specific even potentials. The first of these methods applies to the leading order term. We show that this term has an elementary form in terms of a solution to an algebraic equation. This generates a general formula for the Taylor Coefficients of this term. Next we exploit the relationship between orthogonal polynomials and the Toda Lattice Equations to derive ODE's for the general terms of the expansion of the partition function of random matrices, which leads to a method of calculating the Taylor Coefficients of these functions.

The interplay between spectrum and structure of graphs is the recurring theme of the three more or less independent chapters of this thesis. The first chapter provides a method to relate the eigensolutions of two matrices, one being the principal submatrix of the other, via an arbitrary annihilating polynomial. This is extended to lambda-matrices and to matrices the entries of which are rational functions in one variable. The extension may be interpreted as a possible generalization of other known techniques which aim at reducing the size of a matrix while preserving the spectral information. Several aspects of an application in order to reduce the computational costs of ordinary eigenvalue problems are discussed. The second chapter considers the straightforward extension of the well known concept of equitable partitions to weighted graphs, i.e. complex matrices. It provides a method to divide the eigenproblem into smaller parts corresponding to the front divisor and its complementary factor in an easy and stable way with complexity which is only quadratic in matrix size. The exploitation of several equitable partitions ordered by refinement is discussed and a suggestion is made that preserves hermiticity if present. Some generalizations of equitable partitions are considered and a basic procedure for finding an equitable partition of complex matrices is given. The third chapter deals with isospectral and unitary equivalent graphs. It introduces a construction for unitary equivalent graphs which contains the well known GM-switching as a special case. It also considers an algebra of graph matrices generated by the adjacency matrix that corresponds to the 1-dimensional Weisfeiler-Lehman stabilizer in a way that mimics the correspondence of the coherent closure and the 2-dimensional Weisfeiler-Lehman stabilizer. The algebra contains the degree matrix, the (combinatorial, signless and normalized) Laplacian and the Seidel matrix. An easy construction produces graph pairs that are simultaneously unitary equivalent w.r.t. that algebra.

Neste trabalho, com base em representações por matrizes de duas linhas para alguns tipos de partição (algumas já conhecidas e outras novas), identificamos propriedades sugeridas por classificá-las de acordo com a soma dos elementos de sua segunda linha. Esta soma sempre fornece alguma propriedade da partição relacionada. Se considerarmos versões sem sinal de algumas funções Mock Theta, seu termo geral pode ser interpretado como função geradora para algum tipo de partição com restrições. Para retornar aos coeficientes originais, é possível definir um peso para cada matriz e depois somá-las para contá-los. Uma representação análoga para essas partições nos permite observar propriedades sobre elas, novamente por meio de uma classificação referente à soma dos seu elementos da segunda linha. Esta seriação é feita por meio de tabelas criadas pelo software matemático Maple, as quais nos sugerem padrões e identidades relacionadas com outros tipos de partições conhecidas e, muitas vezes, encontrando uma fórmula fechada para contá-las. Tendo as conjecturas obtidas, elas são provadas por meio de bijeções entre conjuntos ou por contagem.<br>In this work, based on representations by matrices of two lines for some kind of partition (some already known and other new ones), we identify properties suggested by classifying them according to the sum of its second line. This sum always provides some properties of the related partition. If we consider unsigned versions of some Mock Theta Functions, its general term can be interpreted as generating function for some kind of partition with restrictions. To come back to the original coefficients, you can set a weight for each array and so add them to evaluate the coefficients. An analogous representation for partitions allows us to observe properties, again by classificating them according to the sum of its elements on the second row. This classification is made by means of tables created by mathematical software Maple, which suggest patterns, identities related to other known types of partitions and often, finding a closed formula to count them. Having established conjectured identities, all are proved by bijections between sets or counting methods.