Fermeture de la BCU-Centrale suite au déménagement: 4 juillet – 16 août : La BCU-Centrale est fermée pour déménagement. Les commandes en magasins ainsi que les demandes de prêt entre bibliothèques ne seront pas possibles.
17 août : Réouverture de la BCU à Beauregard (rue de la Carrière 22)
Hors campus: Membres de la communauté universitaire ou de la HES-SO: n'oubliez pas d'utiliser le VPN de votre institution pour bénéficier de tous les accès.
Titre: Tangle-tree duality in abstract separation systems Auteur:Diestel, Reinhard Contributeur:Diestel, Reinhard (pacrepositoryorg) Sujet:Data Management ; Cohesion ; Substructures ; Image Analysis ; Duality Theorem ; Graphs ; Combinatorial Analysis ; Parameters ; Separation ; Existence Theorems ; Axioms Description:
We prove a general width duality theorem for combinatorial structures with well-defined notions of cohesion and separation. These might be graphs and matroids, but can be much more general or quite different. The theorem asserts a duality between the existence of high cohesiveness somewhere local and a global overall tree structure. We describe cohesive substructures in a unified way in the format of tangles: as orientations of low-order separations satisfying certain consistency axioms. These axioms can be expressed without reference to the underlying structure, such as a graph or matroid, but just in terms of the poset of the separations themselves. This makes it possible to identify tangles, and apply our tangle-tree duality theorem, in very diverse settings. Our result implies all the classical duality theorems for width parameters in graph minor theory, such as path-width, tree-width, branch-width or rank-width. It yields new, tangle-type, duality theorems for tree-width and path-width....
Fait partie de:
arXiv.org, Apr 26, 2018
Titre: Locally finite graphs with ends: a topological approach Auteur:Diestel, Reinhard Contributeur:Diestel, Reinhard (pacrepositoryorg) Sujet:Graphs ; Graph Theory ; Topology ; Combinatorics ; Geometric Topology Description:
This paper is intended as an introductory survey of a newly emerging field: a topological approach to the study of locally finite graphs that crucially incorporates their ends. Topological arcs and circles, which may pass through ends, assume the role played in finite graphs by paths and cycles. This approach has made it possible to extend to locally finite graphs many classical theorems of finite graph theory that do not extend verbatim. The shift of paradigm it proposes is thus as much an answer to old questions as a source of new ones; many concrete problems of both types are suggested in the paper. This paper attempts to provide an entry point to this field for readers that have not followed the literature that has emerged in the last 10 years or so. It takes them on a quick route through what appear to be the most important lasting results, introduces them to key proof techniques, identifies the most promising open problems, and offers pointers to the literature for more detail.
Fait partie de:
arXiv.org, Jul 10, 2012
Titre: Forcing finite minors in sparse infinite graphs by large-degree assumptions Auteur:Diestel, Reinhard Contributeur:Diestel, Reinhard (pacrepositoryorg) Sujet:Graphs ; Graph Theory Description:
Developing further Stein's recent notion of relative end degrees in infinite graphs, we investigate which degree assumptions can force a locally finite graph to contain a given finite minor, or a finite subgraph of given minimum degree. This is part of a wider project which seeks to develop an extremal theory of sparse infinite graphs.
Fait partie de:
arXiv.org, Sep 24, 2012