Title: Recognition Problems for Connectivity Functions
| Speaker: | Susan Jowett |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract: A connectivity function on a set E is a function λ : 2E → R such that λ(∅) = 0, that λ(X) = λ(E−X) for all X ⊆ E, and that λ(X)+λ(Y) ≥ λ(X∩Y)+λ(X∪Y) for all X,Y ⊆ E. Graphs, matroids and, more generally, polymatroids have associated connectivity functions. In this talk we give a method for identifying when a connectivity function comes from a graph. This method uses no more than a polynomial number of evaluations of the connectivity function. We also prove that we cannot find such a method for identifying when a connectivity function comes from a matroid.