m

F Nous contacter

0

Documents  05C85 | enregistrements trouvés : 44

O

-A +A

P Q

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Combinatorics

The chromatic number $\chi(G)$ of a graph $G$ is always at least the size of its largest clique (denoted by $\omega(G)$), and there are graphs $G$ with $\omega(G)=2$ and $\chi(G)$ arbitrarily large.
On the other hand, the perfect graph theorem asserts that if neither $G$ nor its complement has an odd hole, then $\chi(G)=\omega(G)$ . (A "hole" is an induced cycle of length at least four, and "odd holes" are holes of odd length.) What happens in between?
With Alex Scott, we recently proved the following, a 1985 conjecture of Gyárfás:

For graphs $G$ with no odd hole, $\chi(G)$ is bounded by a function of $\omega(G)$.

Gyárfás also made the stronger conjecture that for every integer $k$ and for all graphs $G$ with no odd hole of length more than $k$, $\chi(G)$ is bounded by a function of $k$ and $\omega(G)=2$. This is far from settled, and indeed the following much weaker statement is not settled: for every integer $k$, every triangle-free graph with no hole of length at least $k$ has chromatic number bounded by a function of $k$. We give a partial result towards the latter:

For all $k$, every triangle-free graph with no hole of length at least $k$ admits a tree-decomposition into bags with chromatic number bounded by a function of $k$.

Both results have quite pretty proofs, which will more-or-less be given in full.
The chromatic number $\chi(G)$ of a graph $G$ is always at least the size of its largest clique (denoted by $\omega(G)$), and there are graphs $G$ with $\omega(G)=2$ and $\chi(G)$ arbitrarily large.
On the other hand, the perfect graph theorem asserts that if neither $G$ nor its complement has an odd hole, then $\chi(G)=\omega(G)$ . (A "hole" is an induced cycle of length at least four, and "odd holes" are holes of odd length.) What happens in ...

05C15 ; 05C35 ; 05C85

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research School;Combinatorics;Computer Science;Mathematics in Science and Technology

Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des réseaux biologiques, comme par exemple des réseaux d'interaction de protéines ou des réseaux métaboliques. Graph Motif a fait depuis l'objet d'une attention particulière qui se traduit par un nombre relativement élevé de publications, essentiellement orientées autour de sa complexité algorithmique.
Je présenterai un certain nombre de résultats algorithmiques concernant le problème Graph Motif, en particulier des résultats de FPT (Fixed-Parameter Tractability), ainsi que des bornes inférieures de complexité algorithmique.
Ceci m'amènera à détailler diverses techniques de preuves dont certaines sont plutôt originales, et qui seront je l'espère d'intérêt pour le public.
Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des ...

05C15 ; 05C85 ; 05C90 ; 68Q17 ; 68Q25 ; 68R10 ; 92C42 ; 92D20

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research School;Combinatorics;Computer Science

Graph searching, a mechanism to traverse a graph visiting one vertex at a time in a specific manner, is a powerful tool used to extract structure from various families of graphs. In this talk, we focus on two graph searches: Lexicographic Breadth First Search (LBFS), and Lexicographic Depth First Search (LDFS).
Many classes of graphs have a vertex ordering characterisation, and we review how graph searching is used to produce efficiently such vertex orderings.
These orderings expose structure that we exploit to develop efficient linear and near-linear time algorithms for some NP-hard problems (independent set, colouring, Hamiltonicity for instance) on some special classes of graphs such as cocomparability graphs.
In particular, we will prove fixed point type theorems for LexBFS, and then focus on a LexDFS-based framework to lift algorithms from interval graphs to cocomparability graphs. Then I will present the relationships between graph searches, graph geometric convexities and antimatroids. These relationships are for to be completely understood and I will pose some hard conjectures and some interesting problems to consider.
To finish I will present some recent results about Robinsonian matrices by M. Laurent and M. Seminaroti and their relationships with graph searches. This yields a new area of research to investigate.
Graph searching, a mechanism to traverse a graph visiting one vertex at a time in a specific manner, is a powerful tool used to extract structure from various families of graphs. In this talk, we focus on two graph searches: Lexicographic Breadth First Search (LBFS), and Lexicographic Depth First Search (LDFS).
Many classes of graphs have a vertex ordering characterisation, and we review how graph searching is used to produce efficiently such ...

05C85 ; 68R10

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.


ISBN 978-0-444-86216-7

North-holland mathematics studies

Localisation : Colloque 1er étage (BRUS)

algorithme polynomiale # collection des paapiers # programmation discrète # théorie de graphe

05-06 ; 05C20 ; 05C85 ; 05Cxx ; 90C10

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 152 p.
ISBN 978-0-8218-6600-9

DIMACS series in discrete mathematics and theoretical computer science , 0009

Localisation : Collection 1er étage

algorithme # architecture parallèle # graphe aléatoire # graphe planaire # sphérique # théorie des graphes

05C10 ; 05C35 ; 05C38 ; 05C75 ; 05C85

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 142 p.
ISBN 978-0-8218-6602-3

DIMACS series in discrete mathematics and theoretical computer science , 0010

Localisation : Collection 1er étage

approche corps de fonction de graphe et diagramme de Ramanuj # construction algébrique de graphe dense de grand contour et # graphe de Cayley aléatoire et expanseur # graphe demi-plan supérieur fini et Ramanujan # graphe en expansion # graphe en expansion hautement tiré de groupe diédral # groupe et expanseur # géométrie spectral et constante de Cheeger # investigation numérique du spectre pour famille de graphe de # laplacien d'hypergraphe # seconde valeur propre et développement linéaire de graphe ré # simulation de chaîne de Markov # échantillonnage uniforme modulo ou groupe de symétrie approche corps de fonction de graphe et diagramme de Ramanuj # construction algébrique de graphe dense de grand contour et # graphe de Cayley aléatoire et expanseur # graphe demi-plan supérieur fini et Ramanujan # graphe en expansion # graphe en expansion hautement tiré de groupe diédral # groupe et expanseur # géométrie spectral et constante de Cheeger # investigation numérique du spectre pour famille de graphe de # laplacien d'hypergraphe # ...

05-06 ; 05C35 ; 05C80 ; 05C85 ; 60Jxx

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 160 p.
ISBN 978-0-8218-0992-1

DIMACS series in discrete mathematics and theoretical computer science , 0045

Localisation : Collection 1er étage

algorithme # analyse # application # combinatoire # cryptographie # graphe # industrie # mathématique appliquée # mobile # passage # protocole réseau # réseau ATM # réseau de communication # réseau radio # système distribué # théorie des graphes # traitement des données # électronique

05C05 ; 05C10 ; 05C38 ; 05C85 ; 05C90 ; 68M07 ; 68M10 ; 68M20 ; 68Q05 ; 68Q10

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 375 p.
ISBN 978-0-8218-0842-9

DIMACS series in discrete mathematics and theoretical computer science , 0048

Localisation : Collection 1er étage

ADN # algorithme de graphe # algorithme distribué # algorithme parallèle # biomathématique # calcul formel # informatique théorique # langage formel # mode calculatoire # molécule # réécriture de système

05C85 ; 68-06 ; 68Q05 ; 68Q10 ; 68Q22 ; 68Q42 ; 68Q45 ; 92-06

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- xviii; 562 p.
ISBN 978-3-540-76795-4

Localisation : Colloque 1er étage (BONN)

optimisation # combinatoires # optimisation combinatoire # problème extreme # recherche opérationnelle # analyse mathématique

90Cxx ; 90-06 ; 05-06 ; 90C27 ; 05C35 ; 05C85 ; 00B25

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- xiii; 240 p.
ISBN 978-0-8218-9038-7

Contemporary mathematics , 0588

Localisation : Collection 1er étage

combinatoires # arbres # hypergraphe # factorisation # algorithme

05C85 ; 68W05 ; 68W10 ; 68R05 ; 68R10 ; 05C05 ; 05C65 ; 05-06 ; 05C70 ; 00B25

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- xi; 556 p.
ISBN 978-2-85629-371-3

Astérisque , 0352

Localisation : Périodique 1er étage

Algorithme d'approximation # carte brownienne # cartes planaires # champ libre gaussien # champ moyen # choix social # concentration-compacité # condition nulle # configuration polynomiale # courbe elliptique # D-module holonome # difficulté d'approximation # équation aux dérivées partielles # équations d'Einstein # équations différentielles partielles # équations non-linéaires dispersives # espaces adiques # espaces de Berkovich # espaces homogènes # espaces métriques # espaces normés # espaces perfectoïdes # existence globale # fibré de Higgs # fibré holomorphe plat # forme quartique binaire # formule de KPZ # gravité quantique # groupe de Galois motivique # groupe de Selmer # groupes de Lie # groupes quasi-fuchsiens # hamiltonien # marches aléatoires # mélange exponentiel du fibré des repères # mesures de Liouville # mesures stationnaires # métrique harmonique # modération topologique # monodromie-poids # motifs de Tate mixtes # multizêtas # nonlinéaire # norme d'uniformité # orbites coadjointes # plongement métrique # principe de transfert # programmation semi-définie # Programme de Ribe # progression arithmétique # pureté # rang # réarrangement # Relativité générale # représentations des groupes algébriques réductifs # représentations des groupes de Lie compacts # résonances en espace temps # rigidité # singularités irrégulières # stabilité orbitale # surfaces enfermées # système stellaire auto-gravitant # théorème de Lefschetz difficile # théorie de Hodge # théorie géométrique des invariants # topologie étale # trous noirs # types stablement dominés # variétés de drapeaux # variétés hyperboliques de dimension 3 # Vlasov-Poisson Algorithme d'approximation # carte brownienne # cartes planaires # champ libre gaussien # champ moyen # choix social # concentration-compacité # condition nulle # configuration polynomiale # courbe elliptique # D-module holonome # difficulté d'approximation # équation aux dérivées partielles # équations d'Einstein # équations différentielles partielles # équations non-linéaires dispersives # espaces adiques # espaces de Berkovich # espaces ...

14L24 ; 14M15 ; 20G05 ; 22E46 ; 35-XX ; 35Qxx ; 37-XX ; 37NXX ; 37N20 ; 82-XX ; 82Cxx ; 85-XX ; 85AXX ; 05C12 ; 05C85 ; 46N10 ; 68Q17 ; 68R10 ; 68W25 ; 90C22 ; 91B14 ; 11G99 ; 11G05 ; 11E76 ; 14J60 ; 32C38 ; 53C07 ; 83C57 ; 83C75 ; 83C05 ; 35L67 ; 60C05 ; 60F17 ; 60-02 ; 05C10 ; 05C80 ; 82B20 ; 82B05 ; 82B27 ; 35B34 ; 35E20 ; 35B60 ; 35Q60 ; 35Q35 ; 11N13 ; 11B25 ; 30F99 ; 03C64 ; 03C65 ; 03C99 ; 14G22 ; 11G25 ; 14F20 ; 14G20 ; 22E40 ; 37D40 ; 60B99

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Combinatorics;Computer Science

La méthode probabiliste est un outil extrêmement puissant, qui consiste à montrer l'existence d'un objet via une génération aléatoire bien choisie. Nous discuterons ici en particulier de son rôle en théorie des graphes.

05C85 ; 68R10

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Combinatorics;Computer Science

A central concept in graph theory is the notion of tree decompositions - these are decompositions that allow us to split a graph up into "nice" pieces by "small" cuts. It is possible to solve many algorithmic problems on graphs by decomposing the graph into "nice" pieces, finding a solution in each of the pieces, and then gluing these solutions together to form a solution to the entire graph. Examples of this approach include algorithms for deciding whether a given input graph is planar, the $k$-Disjoint paths algorithm of Robertson and Seymour, as well as many algorithms on graphs of bounded tree-width. In this talk we will look at a way to compare two tree decompositions of the same graph and decide which of the two is "better". It turns out that for every cut size $k$, every graph $G$ has a tree decomposition with (approximately) this cut size, such that this tree-decomposition is "better than" every other tree-decomposition of the same graph with cut size at most $k$. We will discuss some consequences of this result, as well as possible improvements and research directions. A central concept in graph theory is the notion of tree decompositions - these are decompositions that allow us to split a graph up into "nice" pieces by "small" cuts. It is possible to solve many algorithmic problems on graphs by decomposing the graph into "nice" pieces, finding a solution in each of the pieces, and then gluing these solutions together to form a solution to the entire graph. Examples of this approach include algorithms for ...

05C85 ; 05C35 ; 68Q25

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Combinatorics

A hole in a graph is an induced cycle of length at least four, and an odd hole is a hole of odd length. A famous conjecture of A. Gyárfás [1] from 1985 asserts:
Conjecture 1: For all integers $k,l$ there exists $n(k,l)$ such that every graph $G$ with no clique of carnality more than $k$ and no odd hole of length more than $l$ has chromatic number at most $n(k,l)$.

In other words, the conjecture states that the family of graphs with no long odd holes is $\chi$-bounded. Little progress was made on this problem until recently Scott and Seymour proved that Conjecture 1 is true for all pairs $(k,l)$ when $l=3$ (thus excluding all odd holes guarantees $\chi$-boundedness) [3].
No other cases have been settled, and here we focus on the case $k=2$. We resolve the first open case, when $k=2$ and $l=5$, proving that
Theorem 1. Every graph with no triangle and no odd hole of length $>5$ is $82200$-colorable.

Conjecture 1 has a number of other interesting special cases that still remain open; for instance
* Conjecture: For all $l$ every triangle-free graph $G$ with sufficiently large chromatic number has an odd hole of length more than $l$;
* Conjecture: For all $k,l$ every graph with no clique of size more than $k$ and sufficiently large chromatic number has a hole of length more than $l$.

We prove both these statements with the additional assumption that $G$ contains no $5$-hole. (The latter one was proved, but not published, by Scott earlier, improving on [2]). All the proofs follows a similar outline. We start with a leveling of a graph with high chromatic number, that is a classification of the vertices by their distance from a fixed root. Then the graph undergoes several rounds of "trimming" that allows us to focus on a subgraph $M$ with high chromatic number that is, in some sense, minimal. We also ensure that certain pairs of vertices with a neighbor in $M$ can be joined by a path whose interior is anticomplete to $M$. It is now enough to find two long paths between some such pair of vertices, both with interior in $M$ and of lengths of different parity, to obtain a long odd hole.
A hole in a graph is an induced cycle of length at least four, and an odd hole is a hole of odd length. A famous conjecture of A. Gyárfás [1] from 1985 asserts:
Conjecture 1: For all integers $k,l$ there exists $n(k,l)$ such that every graph $G$ with no clique of carnality more than $k$ and no odd hole of length more than $l$ has chromatic number at most $n(k,l)$.

In other words, the conjecture states that the family of graphs with no long odd ...

05C15 ; 05C85

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research schools;Combinatorics;Computer Science

68Q25 ; 68R10 ; 05C85

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research schools;Combinatorics;Computer Science;Topology

05C10 ; 68R10 ; 05C85

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research School;Combinatorics;Computer Science;Mathematics in Science and Technology

Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des réseaux biologiques, comme par exemple des réseaux d'interaction de protéines ou des réseaux métaboliques. Graph Motif a fait depuis l'objet d'une attention particulière qui se traduit par un nombre relativement élevé de publications, essentiellement orientées autour de sa complexité algorithmique.
Je présenterai un certain nombre de résultats algorithmiques concernant le problème Graph Motif, en particulier des résultats de FPT (Fixed-Parameter Tractability), ainsi que des bornes inférieures de complexité algorithmique.
Ceci m'amènera à détailler diverses techniques de preuves dont certaines sont plutôt originales, et qui seront je l'espère d'intérêt pour le public.
Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des ...

05C15 ; 05C85 ; 05C90 ; 68Q17 ; 68Q25 ; 68R10 ; 92C42 ; 92D20

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Combinatorics;Computer Science

We present new results concerning restricted types of matchings such as uniquely restricted matchings and acyclic matchings, and we also consider the corresponding edge coloring notions. Our focus lies on bounds, exact and approximative algorithms. Furthermore, we discuss some matching removal problems. The talk is based on joined work with J. Baste, C. Lima, L. Penso, I. Sau, U. Souza, and J. Szwarcfiter.

05C70 ; 05C35 ; 05C15 ; 05C85 ; 68Q25

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Combinatorics

The problem of testing if a graph can be colored with a given number $k$ of colors is $NP$-complete for every $k>2$. But what if we have more information about the input graph, namely that some fixed graph $H$ is not present in it as an induced subgraph? It is known that the problem remains $NP$-complete even for $k=3$, unless $H$ is the disjoint union of paths. We consider the following two questions: 1) For which graphs $H$ is there a polynomial time algorithm to 3-color (or in general $k$-color) an $H$-free graph? 2) For which graphs $H$ are there finitely many 4-critical $H$-free graphs? This talk will survey recent progress on these questions, and in particular give a complete answer to the second one. The problem of testing if a graph can be colored with a given number $k$ of colors is $NP$-complete for every $k>2$. But what if we have more information about the input graph, namely that some fixed graph $H$ is not present in it as an induced subgraph? It is known that the problem remains $NP$-complete even for $k=3$, unless $H$ is the disjoint union of paths. We consider the following two questions: 1) For which graphs $H$ is there a ...

05C15 ; 05C85

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Combinatorics;Computer Science

Robinsonian matrices are structured matrices that have been introduced in the 1950's by the archeologist W.S. Robinson for chronological dating of Egyptian graves. A symmetric matrix is said to be Robinsonian if its rows and columns can be simultaneously reordered in such a way that the entries are monotone nondecreasing in the rows and columns when moving toward the main diagonal. Robinsonian matrices can be seen as a matrix analog of unit interval graphs, which are precisely the graphs having a Robinsonian adjacency matrix. We will discuss several aspects of Robinsonian matrices: links to unit interval graphs; new efficient combinatorial recognition algorithm based on Similarity-First Search, a natural extension to weighted graphs of Lex-BFS; structural characterization by minimal forbidden substructures; and application to tractable instances of the Quadratic Assignment Problem. Robinsonian matrices are structured matrices that have been introduced in the 1950's by the archeologist W.S. Robinson for chronological dating of Egyptian graves. A symmetric matrix is said to be Robinsonian if its rows and columns can be simultaneously reordered in such a way that the entries are monotone nondecreasing in the rows and columns when moving toward the main diagonal. Robinsonian matrices can be seen as a matrix analog of unit ...

05C62 ; 05C85 ; 68R10

... Lire [+]

Z