The Structure of Connectivity Functions

Graphs, matroids and polymatroids all have associated connectivity functions, and many properties of these structures follow from properties of their connectivity functions. This motivates the study of connectivity functions in general. It turns out that connectivity functions are surprisingly highly structured. We prove some interesting results about connectivity functions. In particular we show that every connectivity function is a connectivity function of a half-integral polymatroid.