Auswahl der wissenschaftlichen Literatur zum Thema „Graphes de Helly bipartis“

Graphs and Algorithms International audience A biclique is a set of vertices that induce a complete bipartite graph. A graph G is biclique-Helly when its family of maximal bicliques satisfies the Helly property. If every induced subgraph of G is also biclique-Helly, then G is hereditary biclique-Helly. A graph is C4-dominated when every cycle of length 4 contains a vertex that is dominated by the vertex of the cycle that is not adjacent to it. In this paper we show that the class of hereditary biclique-Helly graphs is formed precisely by those C4-dominated graphs that contain no triangles and no induced cycles of length either 5 or 6. Using this characterization, we develop an algorithm for recognizing hereditary biclique-Helly graphs in O(n2+αm) time and O(n+m) space. (Here n, m, and α= O(m1/2) are the number of vertices and edges, and the arboricity of the graph, respectively.) As a subprocedure, we show how to recognize those C4-dominated graphs that contain no triangles in O(αm) time and O(n+m) space. Finally, we show how to enumerate all the maximal bicliques of a C4-dominated graph with no triangles in O(n2 + αm) time and O(αm) space.

A poset is $(3+1)$-free if it does not contain the disjoint union of chains of length 3 and 1 as an induced subposet. These posets are the subject of the $(3+1)$-free conjecture of Stanley and Stembridge. Recently, Lewis and Zhang have enumerated $\textit{graded}$ $(3+1)$-free posets, but until now the general enumeration problem has remained open. We enumerate all $(3+1)$-free posets by giving a decomposition into bipartite graphs, and obtain generating functions for $(3+1)$-free posets with labelled or unlabelled vertices. Un poset sans $(3 + 1)$ est un poset qui n’a pas de sous-poset induit formé de deux chaînes disjointes de longueur 3 et 1. Ces posets sont l’objet de la conjecture $(3+1)$ de Stanley et Stembridge. Récemment, Lewis et Zhang ont énuméré les posets $\textit{étagés}$ sans $(3 + 1)$, mais en général la question d’énumération est restée ouverte jusqu'à maintenant. Nous énumérons tous les posets sans $(3 + 1)$ en donnant une décomposition de ces posets en graphes bipartis, et obtenons des fonctions génératrices qui les énumèrent, qu’ils soient étiquetés ou non.

The $(\Delta,D)$ (degree/diameter) problem consists of finding the largest possible number of vertices $n$ among all the graphs with maximum degree $\Delta$ and diameter $D$. We consider the $(\Delta,D)$ problem for maximal planar bipartite graphs, that is, simple planar graphs in which every face is a quadrangle. We obtain that for the $(\Delta,2)$ problem, the number of vertices is $n=\Delta+2$; and for the $(\Delta,3)$ problem, $n= 3\Delta-1$ if $\Delta$ is odd and $n= 3\Delta-2$ if $\Delta$ is even. Then, we prove that, for the general case of the $(\Delta,D)$ problem, an upper bound on $n$ is approximately $3(2D+1)(\Delta-2)^{\lfloor D/2\rfloor}$, and another one is $C(\Delta-2)^{\lfloor D/2\rfloor}$ if $\Delta\geq D$ and $C$ is a sufficiently large constant. Our upper bounds improve for our kind of graphs the one given by Fellows, Hell and Seyffarth for general planar graphs. We also give a lower bound on $n$ for maximal planar bipartite graphs, which is approximately $(\Delta-2)^{k}$ if $D=2k$, and $3(\Delta-3)^k$ if $D=2k+1$, for $\Delta$ and $D$ sufficiently large in both cases.

AbstractGiven q-uniform hypergraphs (q-graphs) F, G and H, where G is a spanning subgraph of F, G is called weaklyH-saturated in F if the edges in $$E(F)\setminus E(G)$$ E ( F ) \ E ( G ) admit an ordering $$e_1,\ldots , e_k$$ e 1 , … , e k so that for all $$i\in [k]$$ i ∈ [ k ] the hypergraph $$G\cup \{e_1,\ldots ,e_i\}$$ G ∪ { e 1 , … , e i } contains an isomorphic copy of H which in turn contains the edge $$e_i$$ e i . The weak saturation number of H in F is the smallest size of an H-weakly saturated subgraph of F. Weak saturation was introduced by Bollobás in 1968, but despite decades of study our understanding of it is still limited. The main difficulty lies in proving lower bounds on weak saturation numbers, which typically withstands combinatorial methods and requires arguments of algebraic or geometrical nature. In our main contribution in this paper we determine exactly the weak saturation number of complete multipartite q-graphs in the directed setting, for any choice of parameters. This generalizes a theorem of Alon from 1985. Our proof combines the exterior algebra approach from the works of Kalai with the use of the colorful exterior algebra motivated by the recent work of Bulavka, Goodarzi and Tancer on the colorful fractional Helly theorem. In our second contribution answering a question of Kronenberg, Martins and Morrison, we establish a link between weak saturation numbers of bipartite graphs in the clique versus in a complete bipartite host graph. In a similar fashion we asymptotically determine the weak saturation number of any complete q-partite q-graph in the clique, generalizing another result of Kronenberg et al.

International audience The standard supercharacter theory of the finite unipotent upper-triangular matrices $U_n(q)$ gives rise to a beautiful combinatorics based on set partitions. As with the representation theory of the symmetric group, embeddings of $U_m(q) \subseteq U_n(q)$ for $m \leq n$ lead to branching rules. Diaconis and Isaacs established that the restriction of a supercharacter of $U_n(q)$ is a nonnegative integer linear combination of supercharacters of $U_m(q)$ (in fact, it is polynomial in $q$). In a first step towards understanding the combinatorics of coefficients in the branching rules of the supercharacters of $U_n(q)$, this paper characterizes when a given coefficient is nonzero in the restriction of a supercharacter and the tensor product of two supercharacters. These conditions are given uniformly in terms of complete matchings in bipartite graphs. La théorie standard des supercaractères des matrices triangulaires supérieures unipotentes finies $U_n(q)$ donne lieu à une merveilleuse combinatoire basée sur les partitions d'ensembles. Comme avec la théorie des représentations du groupe symétrique, Les plongements $U_m(q) \subseteq U_n(q)$ pour $m \leq n$ mènent aux règles de branchement. Diaconis et Isaacs ont montré que la restriction d'un supercaractère de $U_n(q)$ est une combinaison linéaire des supercaractères de $U_m(q)$ avec des coefficients entiers non négatifs (en fait, elle est polynomiale en $q$). Dans une première étape vers la compréhension de la combinatoire des coefficients dans les règles de branchement des supercaractères de $U_n(q)$, ce texte caractérise les coefficients non nuls dans la restriction d'un supercaractère et dans le produit des tenseurs de deux supercaractères. Ces conditions sont données uniformément en termes des couplages complets dans des graphes bipartis.

International audience A $\textit{grid shape}$ is a set of boxes chosen from a square grid; any Young diagram is an example. This paper considers a notion of pattern-avoidance for $0-1$ fillings of grid shapes, which generalizes permutation pattern-avoidance. A filling avoids some patterns if none of its sub-shapes equal any of the patterns. We focus on patterns that are $\textit{pairs}$ of $2 \times 2$ fillings. For some shapes, fillings that avoid specific $2 \times 2$ pairs are in bijection with totally nonnegative Grassmann cells, or with acyclic orientations of bipartite graphs. We prove a number of results analogous to Wilf-equivalence for these objects ―- that is, we show that for certain classes of shapes, some pattern-avoiding fillings are equinumerous with others. Une $\textit{forme de grille}$ est un ensemble de cases choisies dans une grille carrée; un diagramme de Young en est un exemple. Cet article considère une notion de motif exclu pour un remplissage d'une forme de grille par des $0$ et des $1$, qui généralise la notion correspondante pour les permutations. Un remplissage évite certains motifs si aucune de ses sous-formes n'est égale à un motif. Nous nous concentrons sur les motifs qui sont des $\textit{paires de remplissages}$ de taille $2 \times 2$. Pour certaines formes, les remplissages évitant certaines paires de taille $2 \times 2$ sont en bijection avec les cellules de Grassmann totalement positives, ou bien avec les orientations acycliques de graphes bipartis. Nous démontrons plusieurs résultats analogues à l'équivalence de Wilf pour ces objets ―- c'est-à-dire, nous montrons que, pour certaines classes de formes, des remplissages évitant un motif donné sont en nombre égal à d'autres remplissages.

Le problème du médian est un des problèmes les plus étudiés en théorie des espaces métriques. Nous l'étudions dans les graphes médians d'un point de vue algorithmique. Nous présentons un algorithme linéaire basé sur un calcul rapide des classes de parallélisme des arêtes (les Thêta-classes) via un parcours en largeur particulier (LexBFS). Nous donnons également un algorithme linéaire pour le problème du médian dans les l1-complexes cubiques des graphes médians et dans les structures d'évènements.Ensuite, nous présentons une caractérisation des graphes aux médians connexes dans la p-ième puissance Gp du graphe et donnons une méthode polynomiale pour vérifier si un graphe est un graphe aux médians Gp-connexes, étendant un résultat de Bandelt et Chepoi (cas p=1). Nous utilisons cette caractérisation pour montrer que certaines classes de graphes sont G2-connexes, comme les graphes de Helly bipartis et les graphes pontés. Nous travaillons également sur l'aspect axiomatique en étudiant l'ABC-problème, qui consiste à déterminer les graphes (nommés ABC-graphes) dans lesquels la fonction médian est l'unique fonction consensus respectant trois axiomes simples (A) Anonymat, (B) Intervalle (Betweeness) et (C) Cohérence. Nous montrons que les graphes modulaires aux médians G2-connexes sont des ABC-graphes et définissons de nouveaux axiomes pour caractériser la fonction médian dans d'autres classes de graphes, comme les graphes aux médians connexes. Nous prouvons également que les graphes respectant la propriété d'appariement (qui sont des ABC-graphes) est une sous-classe propre des graphes de Helly bipartis et étudions la complexité de la reconnaissance de ces graphes
The median problem is one of the most investigated problem in metric graph theory. We will start by studying this problem in median graphs. We present a linear time algorithm based on the majority rule which characterize the median in median graphs and on a fast computation of the parallelism classes of the edges (the \Theta-classes) via LexBFS which is a particular breadth first search algorithm.We also provide linear time algorithms to compute the median set in the l_1-cube complexes of median graphs and in event structures. Then, we provide a characterization of the graphs with connected medians in the pth power of the graph and provide a polynomial method to check if a graph is a G^p-connected median graph, extending a result of Bandelt and Chepoi (case p=1). We use this characterization to prove that some important graph classes in metric graph theory have G2-connected medians, such as bipartite Helly graphs and bridged graphs. We will also studied the axiomatic aspect of the median function by investigating the ABC-problem, which determine the graphs (named ABC-graphs) in which the median function is the only consensus function verifying three simples axioms (A) Anonymat, (B) Betweeness and (C) Consistency. We show that modular graphs with G2-connected medians are ABC-graphs and define new axioms allowing us to characterize the median function on some graph classes. For example the graphs with connected medians (including Helly graphs). We also show that a known class of ABC-graphs (graphs satisfying the pairing property) is a proper subclass of bipartite Helly graphs and we investigate their recognition

Étude sur les graphes bipartis orientes de Moore montrant que de tels graphes existent, pour certaines valeurs du diamètre, et servent a la construction d'une classe de graphes bipartis orientes, asymptotiquement optimaux. Dans la deuxième partie du travail, quelques notions de coloration des graphes sont présentées. Celles-ci permettent de généraliser certains résultats déjà connus dans le cadre de la coloration habituelle et d'en obtenir d'autres plutôt spécifiques a ces notions. La généralisation de la notion de perfection en b-perfection est proposée ce qui permet l'obtention des graphes triangules représentant la seule classe de graphes b-parfaits

Cette thèse traite de différents problèmes liés à la théorie des graphes. La plupart des résultats sont liés à l’existence de circuits et de chemins, le reste est consacré à l’étude du diamètre et du routage. Le premier chapitre est consacré à l’étude du pancyclisme dans les graphes vérifiant une condition du type de celle de V. Chvatal et P. Erdos : la connectivité du graphe est supérieure ou égale à sa stabilité. Dans le deuxième chapitre nous nous intéressons aux graphes antisymétriques dont les degrés sont minorés. On y traite principalement des liens existants entre degrés et diamètre dans les graphes antisymétriques. Le troisième chapitre est axé sur la recherche de chemins et circuits dans les graphes bipartis orientés dont le nombre d’arcs ou les degrés sont minorés. Dans le quatrième chapitre, nous précisions la structure des graphes fortement connexes sans C≥₄. Le cinquième chapitre est la synthèse d’une étude sur le routage dans les réseaux d’interconnexion effectuée chez Thomson-C. S. F dans le cadre d’un projet de Réseau Numérique à Intégration de Service (RNIS), permettant de commuter des signaux à débits variables.

Dans cette thèse, nous étudions le problème de la prévision d'apparition de nouveaux liens dans les réseaux d'interactions. Nous nous intéressons en particulier aux réseaux dynamiques ayant une structure bipartite. Nous proposons un modèle de prévision de liens utilisant les techniques d'apprentissage automatique supervisé. Le problème de prévision de liens est considéré dans ce cas comme un problème de classification binaire. Notre approche applique un schéma de propositionnalisation où chaque paire de noeuds est décrite par un ensemble d'attributs représentant des mesures topologiques. Ces mesures sont calculées dans le graphe biparti et dans les graphes projetés qui en découlent. Nous montrons que ces nouvelles similarités dites " indirectes " apportent un gain d'information bénéfique par rapport aux seules similarités directes. Cette thèse apporte aussi de nouvelles solutions au problème de déséquilibre des données dû à la disproportion inhérente entre le nombre de liens qui peuvent se former et le nombre de liens qui se forment réellement. Nous proposons tout d'abord d'utiliser des méthodes de sous-échantillonnage informé pour réduire le déséquilibre. Une deuxième solution au niveau algorithmique consiste en une approche d'apprentissage semi-supervisé. Dans ce cas, le problème de prévision de liens est vu comme un problème d'apprentissage à partir d'un ensemble d'instances étiquetées (classe minoritaire) et un ensemble d'instances non-étiquetées (classe majoritaire). Nous montrons que cette nouvelle approche permet d'améliorer les performances du classifieur sur la classe minoritaire. Les différentes approches proposées sont appliquées sur les données réelles dans le cadre de deux applications : recommandation de collaborations académiques et recommandation de produits dans un site de vente de musique en ligne
In this work, we handle the problem of new link prediction in dynamic complex networks. We mainly focus on studying networks having a bipartite underlaying structure. We propose to apply a propositionnalization approach where each couple of nodes in the network is described by a set of topological measures. One first contribution in this thesis is to consider measures computed in the bipartite graph and also in the associated projected graphs. A supervised machine learning approach is applied. This approach though it gives some good results, suffers from the obvious problem of class skewness. We hence focus on handling this problem. Informed sub-sampling approaches are first proposed. A semi-supervised machine learning approach is also applied. All proposed approaches are applied and evaluated on real datasets used in real application of academic collaboration recommendation and product recommendation in an e-commerce site

Dans cette thèse, nous apportons une contribution à l'étude de l'existence de cycles de longueur donnée dans certaines familles de graphes. La thèse se divise en deux parties. La première partie est dédiée aux graphes bipartis. Nous nous y intéressons aux graphes bipartis équilibrés hamiltoniens, bipancycliques, S-cyclables et S-pancyclables. Les conditions envisagées portent sur les degrés, le nombre d'indépendance biparti et la k-bifermeture. La seconde partie concerne les graphes sans K₁,₃ que nous appellerons aussi graphes "claw-free". On examine dans cette partie plusieurs familles de graphes qui généralisent la classe des graphes sans K₁,₃ , en particulier la famille des graphes λ-claw-free et celle des graphes sans S(K₁,₃), et l'on s'intéresse aux propriétés d'existence de cycles dans ces familles de graphes ou dans leurs carrés
In this thesis, we study sufficient conditions for the existence of cycles of given length in several families of graphs. The thesis consists of two parts: The first one is dedicated to bipartite graphs. We consider mainly bipartite balanced graphs that are hamiltonian, bipancyclic, S-cyclable and S-pancyclable. The conditions we investigate concern degree, independence number and k-biclosure. The second part concerns claw-free graphs. We examine several families that generalize the claw-free graphs family, mainly the λ-claw-free graphs and the S(K₁,₃)-free graphs. We look for sufficient conditions that insure some special cycles in those families of graphs or in their squares

Beaucoup de graphes de terrain comme les relations acteur-film ou fichier-fournisseur sont modélisables par des graphes bipartis, dont les noeuds sont divisés en deux ensembles avec des liens entre les noeuds de différents ensembles seulement. Cependant, des méthodes manquent actuellement pour analyser correctement ces graphes, la plupart des méthodes existantes étant conçues pour des graphes classiques. Une approche courante, mais limitée, consiste à transformer les graphes bipartis en graphes classiques, par un procédé appelé projection. Cependant ceci entraîne une perte importante d'informations. Nous introduisons dans cette thèse les liens internes, et les proposons comme une nouvelle notion importante pour analyser les graphes de terrain bipartis : elle permet de mesurer la redondance dans ces graphes, et de mesurer la perte d'information entre un graphe biparti et ses projections. Nous montrons en étudiant différents jeux de données que les liens internes sont très fréquents, et que les statistiques associées permettent de souligner leurs ressemblances et leurs différences avec les graphes bipartis aléatoires. Ensuite, nous montrons que nous pouvons tirer profit de cette notion pour modéliser les graphes de terrain bipartis et les stocker dans un format compact. La plupart des graphes de terrain sont de plus dynamiques, c'est-à-dire que leur structure évolue au fil du temps par l'ajout et/ou le retrait de noeuds et/ou de liens. L'étude de la dynamique des graphes de terrain peut s'aborder par le problème de la prédiction de nouveaux liens dans ces graphes. Plusieurs travaux ont étudié le problème de la prédiction de liens dans les graphes classique (non-bipartis). Toutefois, leurs méthodes ne sont pas directement applicables aux graphes bipartis ou sont inappropriées. Nous proposons une approche basée sur les liens internes pour la prédiction dans les graphes bipartis. Nous montrons que notre méthode fonctionne très bien, beaucoup mieux que l'approche de recommandation classique.

Mon travail de these porte principalement sur l'etude de l'extension respectueuse entre posets a hauteur constante et ses rapports avec les graphes bipartis (ou tableaux bivalents). Le probleme d'extension respectueuse est trivial pour la classe de toutes les relations binaires ou pour la classe des posets finis. Cependant, il devient interessant avec la condition d'une hauteur constante h, ce que nous appelons h-extensibilite. Nous avons etudie des exemples de posets h-extensibles et de posets 2- inextensibles. Nous avons transforme les posets de hauteur 2 en tableaux bivalents et avons fait une comparaison entre l'extension respectueuse des posets finis de hauteur 2 et celle des tableaux bivalents. Nous donnons des exemples de tableaux bivalents inextensibles. En appendice, nous avons etudie le probleme d'unimodalite

Il existe dans le monde réel un nombre important de réseaux qui apparaissent naturellement, on les retrouve un peu partout, dans de nombreuses disciplines, par exemple en informatique avec les réseaux de routeurs, les réseaux de satellites, les réseaux de pages Web, en biologie avec les réseaux des neurones, en écologie avec les réseaux d’interactions biologiques, en linguistiques avec les réseaux de synonymes, en droit avec les réseaux de décisions juridiques, en économie avec les réseaux interbancaires, en sciences humaines avec les réseaux sociaux. De manière générale, un réseau reflète les interactions entre les nombreuses entités d’un système. Ces interactions peuvent être de différentes natures, un lien social ou un lien d’amitié dans un réseau social constitué de personnes, un câble dans un réseau de routeurs, une réaction chimique dans un réseau biologique de protéines, un hyperlien dans un réseau de pages Web, etc. Plus encore, la rapide démocratisation du numérique dans nos sociétés, avec Internet notamment, a pour conséquence de produire de nouveaux systèmes qui peuvent être représentés sous forme de réseaux. Finalement, tous ces réseaux présentent des particularités bien spécifiques : ils sont issus de contextes pratiques, ils sont le plus souvent de grande taille (on retrouve quelques fois des réseaux constitués de plusieurs milliards de nœuds et de liens, contenant donc une grande quantité d’information), ils présentent des propriétés statistiques communes. À cet égard, ils sont regroupés sous l’appellation de réseaux réels, graphes de terrain ou encore réseaux complexes. Aujourd'hui, la science des réseaux est un domaine de recherche à part entière dont l’enjeu principal est de parvenir à décrire et modéliser ces réseaux avec précision afin de révéler leurs caractéristiques générales et de mieux comprendre leurs mécanismes. La plupart des travaux dans ce domaine utilisent le formalisme des graphes qui fournit un ensemble d’outils mathématiques particulièrement adaptés à l’analyse topologique et structurelle des réseaux. Il existe de nombreuses applications dans ce domaine, par exemple des applications concernant la propagation d’épidémie ou de virus informatique, la fragilité du réseau en cas de panne, sa résilience en cas d’attaque, l’étude de la dynamique pour prédire l’apparition de nouveaux liens, la recommandation, etc. L’un des problèmes complexes actuels, qui a beaucoup d’applications, est l’identification de la structure communautaire. La grande majorité des réseaux réels sont caractérisés par des niveaux d’organisation dans leur structure mésoscopique. Du fait de la faible densité globale des réseaux réels couplée à la forte densité locale, on observe la présence de groupes de nœuds fortement liés entre eux et plus faiblement liés avec le reste du réseau, que l’on appelle communautés. Ces structures ont également du sens dans le réseau lui-même, par exemple les communautés d’un réseau social peuvent correspondre à des groupes sociaux (amis, familles, etc.), les communautés d’un réseau de protéines peuvent traduire des réponses fonctionnelles, elles peuvent correspondre à des sujets similaires dans un réseau de pages Web, pour donner quelques exemples [...]
In the real world, numerous networks appear naturally, they are everywhere, in many disciplines, for example in computer science with router networks, satellite networks, webpage networks, in biology with neural networks, in ecology with biological interaction networks, in linguistic with synonym networks, in law with legal decision networks, in economy with interbank networks, in social sciences and humanities with social networks. Generally, a network reflects the interactions between many entities of a system. These interactions have different sources, a social link or a friendship link in a social network, a cable in a router network, a chemical reaction in a protein-protein interaction network, a hyperlink in a webpage network. Furthermore, the rapid democratization of digital technology in our societies, with internet in particular, leads to create new systems which can be seen as networks. Finally, all these networks depict very specific features : they come from pratical contexts, most of the time they are big (they may be comprised of several billion of nodes and links, containing a large amount of information), they share statistical properties. In this regard, they are called real-world networks or complex networks. Nowaday, network science is a research area in its own right focusing on describing and modeling these networks in order to reveal their main features and improve our understanding of their mecanisms. Most of the works in this area use graphs formalism which provides a set of mathematical tools well suited for analyzing the topology of these networks. It exists many applications, for instance applications in spread of epidemy or computer viruses, weakness of networks in case of a breakdown, attack resilience, study for link prediction, recommandation, etc. One of the major issue is the identification of community structure. The large majority of real-world networks depicts several levels of organization in their structure. Because of there is a weak global density coupled with a strong local density, we observe that nodes are usually organized into groups, called communities, which are more internally connected than they are to the rest of the network. Moreover, these structures have a meaning in the network itself, for example communities of a social network may correspond to social groups (friends, families, etc.), communities of a protein-protein network may translate fonctions of a cell, communities may be also related to similar subjects in a webpage network [...]

We present a series of results related to the structural properties of the bipartite graph class known as circular-arc bigraphs. We also propose the definition of a Helly circular-arc bigraph subclass, based on a concept known as bipartite-Helly, along with a few results related to its structural properties.