Academic literature on the topic 'Polytope des couplages parfaits'

International audience Recently, Kenyon and Wilson introduced a certain matrix M in order to compute pairing probabilities of what they call the double-dimer model. They showed that the absolute value of each entry of the inverse matrix $M^-1$ is equal to the number of certain Dyck tilings of a skew shape. They conjectured two formulas on the sum of the absolute values of the entries in a row or a column of $M^-1$. In this paper we prove the two conjectures. As a consequence we obtain that the sum of the absolute values of all entries of $M^-1$ is equal to the number of complete matchings. We also find a bijection between Dyck tilings and complete matchings. Récemment, Kenyon et Wilson ont introduit une certaine matrice M afin de calculer des probabilités d'appariement dans ce qu'ils appellent le modèle double-dimère. Ils ont montrè que la valeur absolue de chaque entrée de la matrice inverse $M^-1$ est égal au nombre de pavages de Dyck d'une certaine forme gauche. Ils ont conjecturè deux formules sur la somme des valeurs absolues des entrées dans une rangée ou une colonne de $M^-1$. Dans cet article, nous prouvons les deux conjectures. En conséquence on obtient que la somme des valeurs absolues de toutes les entrées de M^-1 est égale au nombre de couplages parfaits. Nous trouvons aussi une bijection entre les pavages de Dyck et les couplages parfaits.

International audience We study cluster algebras with principal coefficient systems that are associated to unpunctured surfaces. We give a direct formula for the Laurent polynomial expansion of cluster variables in these cluster algebras in terms of perfect matchings of a certain graph $G_{T,\gamma}$ that is constructed from the surface by recursive glueing of elementary pieces that we call tiles. We also give a second formula for these Laurent polynomial expansions in terms of subgraphs of the graph $G_{T,\gamma}$ . Nous étudions des algèbres amassées avec coefficients principaux associées aux surfaces. Nous présentons une formule directe pour les développements de Laurent des variables amassées dans ces algèbres en terme de couplages parfaits d'un certain graphe $G_{T,\gamma}$ que l'on construit a partir de la surface en recollant des pièces élémentaires que l'on appelle carreaux. Nous donnons aussi une seconde formule pour ces développements en termes de sous-graphes de $G_{T,\gamma}$ .

International audience An important problem from invariant theory is to describe the subspace of a tensor power of a representation invariant under the action of the group. According to Weyl's classic, the first main (later: 'fundamental') theorem of invariant theory states that all invariants are expressible in terms of a finite number among them, whereas a second main theorem determines the relations between those basic invariants.Here we present a transparent, combinatorial proof of a second fundamental theorem for the defining representation of the symplectic group $Sp(2n)$. Our formulation is completely explicit and provides a very precise link to $(n+1)$-noncrossing perfect matchings, going beyond a dimension count. As a corollary, we obtain an instance of the cyclic sieving phenomenon. Un problème important de la théorie des invariantes est de décrire le sous espace d’une puissance tensorielle d’une représentation invariant à l’action du groupe. Suivant la classique de Weyl, le théorème fondamental premier pour la représentation standard du groupe sympléctique dit que tous les invariants peuvent être exprimés entre un nombre fini d’entre eux. Par ailleurs, un théorème fondamental second détermine les relations entre ces invariants basiques.Ici, nous présentons une preuve transparente d’un théorème fondamental second pour la représentation standard du groupe sympléctique $Sp(2n)$. Notre formulation est complètement explicite et elle fournit un lien très précis avec les couplages parfaits $(n+1)$ -noncroissants, plus précis qu’un dénombrement de la dimension. Comme corollaire nous exhibons un phénomène de crible cyclique.

International audience We consider a Markov chain Monte Carlo approach to the uniform sampling of meanders. Combinatorially, a meander $M = [A:B]$ is formed by two noncrossing perfect matchings, above $A$ and below $B$ the same endpoints, which form a single closed loop. We prove that meanders are connected under appropriate pairs of balanced local moves, one operating on $A$ and the other on $B$. We also prove that the subset of meanders with a fixed $B$ is connected under a suitable local move operating on an appropriately defined meandric triple in $A$. We provide diameter bounds under such moves, tight up to a (worst case) factor of two. The mixing times of the Markov chains remain open. Nous considérons une approche de Monte Carlo par chaîne de Markov pour l'échantillonnage uniforme des méandres. Combinatoirement, un méandre $M = [A : B]$ est constitué par deux couplages (matchings) parfaits sans intersection $A$ et $B$, définis sur le même ensemble de points alignés, et qui forment une boucle fermée simple lorsqu'on dessine $A$ "vers le haut'' et $B$ "vers le bas''. Nous montrons que les méandres sont connectés sous l'action de paires appropriées de mouvements locaux équilibrés, l'un opérant sur $A$ et l'autre sur $B$. Nous montrons également que le sous-ensemble de méandres avec un $B$ fixe est connecté sous l'action de mouvements locaux définis sur des "triplets méandriques'' de $A$. Nous fournissons des bornes sur les diamètres pour de tels mouvements, exactes à un facteur 2 près (dans le pire des cas). Les temps de mélange des chaînes de Markov demeurent une question ouverte.

Dans cette thèse, nous étudions les polyèdres total dual box-intègraux (box-TDI) associés à plusieurs problèmes et matrices totalement équimodulaires. De plus, nous étudions la complexité de certaines questions fondamentales liées à ces polyèdres. Nous commençons par considérer les matrices totalement équimodulaires, qui sont des matrices telles que, pour chaque sous-ensemble de lignes linéairement indépendantes, toutes les sous-matrices maximales non-singulières ont le même déterminant en valeur absolue. Malgré leurs similitudes avec les matrices totalement unimodulaires, nous mettons en évidence plusieurs différences, même dans le cas des matrices d'incidence et d'adjacence des graphes. Comme on le sait, la matrice d'incidence d'un graphe donné est totalement unimodulaire si et seulement si le graphe est biparti. Cependant, la totale équimodularité d'une matrice d'incidence dépend du fait que nous considérons la représentation sommet-arête ou arête-sommet. Nous fournissons des caractérisations pour les deux cas. En conséquence, nous prouvons que reconnaître si un polyèdre donné est box-TDI est un problème co-NP-complet. La caractérisation de la totale unimodularité ou de la totale équimodularité de la matrice d'adjacence d'un graphe biparti donné reste non résolue, alors que nous avons résolu le problème correspondant dans le cas de la totale équimodularité lorsque le graphe est non-biparti. Dans une dernière partie, nous caractérisons les graphes pour lesquels le polytope des couplages parfaits (PMP) est décrit par des inégalités triviales et des inégalités correspondant à des coupes serrées. Les coupes serrées sont définies comme des coupes qui partagent précisément une arête avec chaque couplage parfait. Nous prouvons ensuite que tout graphe pour lequel le PMP correspondant est box-TDI appartient à cette classe. En conséquence, reconnaître si le PMP est box-TDI est un problème résoluble en temps polynomial. Cependant, nous fournissons plusieurs contre-exemples montrant que cette classe de graphes ne garantit pas la box-TDIness du PMP. Enfin, nous présentons des conditions nécessaires pour un polytope de couverture des arêtes pour être box-TDI et caractérisons quand le polytope des couplages extensibles est box-TDI, qui est l'enveloppe convex des couplages inclus dans un couplage parfait
In this thesis, we study box-totally dual integral (box-TDI) polyhedra associated with severalproblems and totally equimodular matrices. Moreover, we study the complexity of some funda-mental questions related to them.We start by considering totally equimodular matrices, which are matrices such that, forevery subset of linearly independent rows, all nonsingular maximal submatrices have the samedeterminant in absolute value. Despite their similarities with totally unimodular matrices, wehighlight several differences, even in the case of incidence and adjacency matrices of graphs.As is well-known, the incidence matrix of a given graph is totally unimodular if and only if thegraph is bipartite. However, the total equimodularity of an incidence matrix depends on whetherwe consider the vertex-edge or the edge-vertex representation. We provide characterizations forboth cases. As a consequence, we prove that recognizing whether a given polyhedron is box-TDIis a co-NP-complete problem.Characterizing the total unimodularity or total equimodularity of the adjacency matrix of agiven bipartite graph remains unsolved, while we solved the corresponding problem in the case oftotal equimodularity when the graph is nonbipartite.In a later part of this work, we characterize the graphs for which the perfect matching polytope(PMP) is described by trivial inequalities and the inequalities corresponding to tight cuts. Tightcuts are defined as cuts that share precisely one edge with each perfect matching. We thenprove that any graph for which the corresponding PMP is box-TDI belongs to this class. Asa consequence, it turns out that recognizing whether the PMP is box-TDI is a polynomial-timeproblem. However, we provide several counterexamples showing that this class of graphs does notguarantee the box-TDIness of the PMP.Lastly, we present necessary conditions for the box-TDIness of the edge cover polytope andcharacterize the box-TDIness of the extendable matching polytope, which is the convex hull ofthe matchings included in a perfect matching

Le calcul du nombre chromatique et la détermination d'une colo- ration optimale des sommets d'un graphe sont des problèmes NP- difficiles en général. Ils peuvent cependant être résolus en temps po- lynomial dans les graphes parfaits. Par ailleurs, la perfection d'un graphe peut être décidée efficacement. Les graphes parfaits sont caractérisés par la structure de leur poly- tope des stables : les facettes non-triviales sont définies exclusivement par des inégalités de cliques. Réciproquement, une structure similaire des facettes du polytope des stables détermine-t-elle des propriétés combinatoires et algorithmiques intéressantes? Un graphe est h-parfait si les facettes non-triviales de son polytope des stables sont définies par des inégalités de cliques et de circuits impairs. On ne connaît que peu de résultats analogues au cas des graphes parfaits pour la h-perfection, et on ne sait pas si les problèmes sont NP-difficiles. Par exemple, les complexités algorithmiques de la re- connaissance des graphes h-parfaits et du calcul de leur nombre chro- matique sont toujours ouvertes. Par ailleurs, on ne dispose pas de borne sur la différence entre le nombre chromatique et la taille maxi- mum d'une clique d'un graphe h-parfait. Dans cette thèse, nous montrons tout d'abord que les opérations de t-mineurs conservent la h-perfection (ce qui fournit une extension non triviale d'un résultat de Gerards et Shepherd pour la t-perfection). De plus, nous prouvons qu'elles préservent la propriété de décompo- sition entière du polytope des stables. Nous utilisons ce résultat pour répondre négativement à une question de Shepherd sur les graphes h-parfaits 3-colorables. L'étude des graphes minimalement h-imparfaits (relativement aux t-mineurs) est liée à la recherche d'une caractérisation co-NP com- binatoire de la h-perfection. Nous faisons l'inventaire des exemples connus de tels graphes, donnons une description de leur polytope des stables et énonçons plusieurs conjectures à leur propos. D'autre part, nous montrons que le nombre chromatique (pondéré) de certains graphes h-parfaits peut être obtenu efficacement en ar- rondissant sa relaxation fractionnaire à l'entier supérieur. Ce résultat implique notamment un nouveau cas d'une conjecture de Goldberg et Seymour sur la coloration d'arêtes. Enfin, nous présentons un nouveau paramètre de graphe associé aux facettes du polytope des couplages et l'utilisons pour donner un algorithme simple et efficace de reconnaissance des graphes h- parfaits dans la classe des graphes adjoints
Computing the chromatic number and finding an optimal coloring of a perfect graph can be done efficiently, whereas it is an NP-hard problem in general. Furthermore, testing perfection can be carried- out in polynomial-time. Perfect graphs are characterized by a minimal structure of their sta- ble set polytope: the non-trivial facets are defined by clique-inequalities only. Conversely, does a similar facet-structure for the stable set polytope imply nice combinatorial and algorithmic properties of the graph ? A graph is h-perfect if its stable set polytope is completely de- scribed by non-negativity, clique and odd-circuit inequalities. Statements analogous to the results on perfection are far from being understood for h-perfection, and negative results are missing. For ex- ample, testing h-perfection and determining the chromatic number of an h-perfect graph are unsolved. Besides, no upper bound is known on the gap between the chromatic and clique numbers of an h-perfect graph. Our first main result states that the operations of t-minors keep h- perfection (this is a non-trivial extension of a result of Gerards and Shepherd on t-perfect graphs). We show that it also keeps the Integer Decomposition Property of the stable set polytope, and use this to answer a question of Shepherd on 3-colorable h-perfect graphs in the negative. The study of minimally h-imperfect graphs with respect to t-minors may yield a combinatorial co-NP characterization of h-perfection. We review the currently known examples of such graphs, study their stable set polytope and state several conjectures on their structure. On the other hand, we show that the (weighted) chromatic number of certain h-perfect graphs can be obtained efficiently by rounding-up its fractional relaxation. This is related to conjectures of Goldberg and Seymour on edge-colorings. Finally, we introduce a new parameter on the complexity of the matching polytope and use it to give an efficient and elementary al- gorithm for testing h-perfection in line-graphs