Submodular partition functions

Adapting the method introduced in Graph Minors X [6], we propose a new proof of the duality between the bramble-number of a graph and its tree-width. This proof is based on a new definition of submodularity on partition functions which naturally extends the usual one on set functions. The technique simplifies the proof of bramble/tree-width duality since it does not rely on Menger’s theorem. One can also derive from it all known dual notions of other classical width-parameters. Finally, it provides a dual for matroid tree-width. 1 Introduction. In their seminal paper Graph Minors X [6], Robertson and Seymour intro-duced the notion of branch-width of a graph and its dual notion of tangle. 1 research supported by the french ANR-project ”Graph decompositions and algo