Path counts in a graph via enumerating independent sets of a graphic matroid

96 Views Asked by At

If I have a simple graph $G$, and what to count the number of simple paths between two distinct vertices, can the paths be seen as independent sets of a matroid?

Perhaps yes, because the edge space of the graph and the cycles form a matroid (the cycle matroid), but the union of two paths (overlapping or otherwise) forms a series of loops, at least 1. Also, there is the notion of the paths spanning the union of paths, if we think of this as a vector space over $\text{GF}(2)$ (so paths as elements of a basis are either scaled by 0 or 1, i.e. exist of don't exist, and addition means the two paths become the respective union, and multiplication is set up properly i.e. considering the edges as part of vector space).

I do not think this matroid is the path matroid or gammoid. But, crucially, though you may be able to construct a matroid like this, is there a theory of enumerating the independent sets, for example, when the graph is random, in order to get some probabilities for path counts in e.g. continuum percolation?

1

There are 1 best solutions below

4
On BEST ANSWER

The set of all "partial simple paths" between two vertices is a simplicial complex. More precisely, if $v,w$ are vertices of the graph $G$ then the set of all simple paths between $v$ and $w$ is a subgraph $G(v,w)$ that can be directed so that $v$ is the unique source and $w$ the unique sink. This directed graph is acyclic so it is the Hasse diagram of a partially-ordered set $P = P(G;v,w)$. Now take the chain complex $\Delta = \Delta(G;v,w)$ of this poset.

The independent sets of a matroid form a pure simplicial complex, that is, a simplicial complex all of whose facets have the same cardiniality. Since $P$ is a bounded poset, $\Delta$ is pure if and only if $P=P(G;v,w)$ is graded if and only if every simple path in $G$ from $v$ to $w$ has the same length. It is easy to construct graphs and select vertices such that $\Delta$ is not pure and hence not a matroid. For example let $G$ be any odd cycle and $v,w$ be arbitrary distinct vertices.

For an example of a triple $D = (G,v,w)$ such that $\Delta(D)$ is pure but still not a matroid take $G = T_{m,n}$ to be the tadpole graph with $m$ even and $m \ge 4$ and take $v,w$ to be the two vertices at distance $m/2+n$. Then $\Delta(D)$ is pure because its two facets both have size $m/2+n$ but it is not a matroid because these facets don't satisfy the matroid basis exchange axiom.

EDIT: The "partial simple paths" in the graph $G(v,w)$ are the chains in the poset $P = P(G;v,w)$. The chain complex of $P$ is also known as the order complex which is a main topic of Wachs' wonderful lecture notes. See page six of those notes for the definition for a full accounting. In short, a "partial simple path" turns out to be a collection of edges in $G(v,w)$ that can be completed to a (directed) path from $v$ to $w$.