2020/07/08 by Nathan Bowler, Bowler, Nathan, Susan Jowett +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.2007.04469
arxiv created 2020/07/08 · arxiv updated 2020/07/10
A \em connectivity function on a set E is a function λ:2E→ \mathbb 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 paper 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. In contrast, we show that the problem of identifying when a connectivity function comes from a matroid cannot be solved in polynomial time. We also show that the problem of identifying when a connectivity function is not that of a matroid cannot be solved in polynomial time.