4
$\begingroup$

I have a (directed graded) graph $G=(V,E)$ with two distinguished subsets of $V$: sources and destinations. I am to show that the set of indicator functions of paths starting in a source and ending in a destination generate the linear spaсe $\mathbb R^V$.

I've found an ad hoc proof for my case but while at it I got the feeling that this is, in general, a pretty natural problem. Are there are any general results of this type?

Clarification. My graph $G$ is a very particular graph which I came across in my research and which turned to have this property: vertices are expressible as linear combinations of paths. I, on the other hand, would like to know now whether this actually holds for any broad enough classes of graphs.

$\endgroup$
2
  • $\begingroup$ What are the hypotheses on the distinguished subsets? If the sources are disconnected from the destinations (for example, if either collection is empty), then the result is not true. $\endgroup$
    – LSpice
    Mar 24, 2016 at 0:41
  • $\begingroup$ @LSpice The hypotheses are whatever you like them to be. I'm interested in any related general results. Let me add a clarification. $\endgroup$ Mar 24, 2016 at 7:26

1 Answer 1

1
$\begingroup$

In full generality you have the condition that a collection $\mathcal C$ of vertex subsets fails to span if and only if there is some (signed) weighting of the vertices such that every $C \in \mathcal C$ has zero weight (other than the constant zero weighting). This is just a restating of the algebraic fact that a proper subspace is orthogonal to at least one non-zero vector, but the phrasing makes it easier to choose suitable vectors combinatorially. For example, if the sources $S$ and destinations $T$ are disjoint independent sets then giving the elements of $S$ weight $1$ and the elements of $T$ weight $-1$ witnesses that the $S$–$T$ paths don't span, as every path contains exactly one element of $S$ and one element of $T$.

Depending on what exactly you mean by a graded directed graph, that structure might make it easy to find bad weightings (e.g. if every path passes exactly once between a fixed pair of adjacent levels).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.