3
$\begingroup$

The fact that acyclicity corresponds to having unique paths powers a lot of useful arguments in various areas of mathematics. What is the most fundamental reason you can come up with to explain the correspondence?

Also, what are more sophisticated generalizations of this correspondence? By this, I mean connections between negative and positive structural properties of an object, which in some way, perhaps only informally, generalize the fact about acyclicity. I'm looking to collect examples.

Please feel free to close this question if it's deemed too vague or philosophical for MathOverflow.

Improve this question
$\endgroup$
3
  • $\begingroup$ For clarity, you are talking about undirected graphs, right? $\endgroup$
    – François G. Dorais
    Commented May 7, 2010 at 3:47
  • $\begingroup$ Maybe you could get it started with a couple of examples of what you have in mind? $\endgroup$
    – Cam McLeman
    Commented May 7, 2010 at 5:40
  • $\begingroup$ @Cam, by generalization, I meant something like connections between forbidden minors or forbidden subgraphs to structural properties of the (undirected) graph. Or, in another direction, maybe there is some way to view Cauchy's integral theorem as an analytic statement about cycles. In general, it's intriguing to me how the negative fact about acyclicity implies the positive fact about unique paths. Can one construct a formalism in which they are dual properties? $\endgroup$
    – lifeofpi
    Commented May 7, 2010 at 7:09

2 Answers 2

Reset to default
2
$\begingroup$

One possible generalization comes from the graph minors project of Robertson and Seymour. In particular the notion of tree-width is in some sense dual to the notion of a bramble (I will define this in a second). Note that a connected graph has tree-width 1 if and only if it is a tree.

Now, let $G$ be a graph. Two subsets of $V(G)$ touch if they have a vertex in common or $G$ contains an edge between them. A set of pairwise touching connected vertex sets in $G$ is a bramble. A subset of vertices covers a bramble $\mathcal{B}$ if it intersects every set in $\mathcal{B}$. The least number of vertices covering $\mathcal{B}$ is the order of $\mathcal{B}$.

Here is the duality relation that I alluded to earlier.

Theorem. A graph has tree-width $< k$ if and only if it does not contain a bramble of order $>k$.

So, loosely think of tree-width as a generalized unique paths property and brambles as generalized cycles.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! This is a very helpful answer. Is something similar also known for forbidden (induced) subgraphs? I'm pretty naive in graph theory, but I've heard that people also study linear spaces generated by associating each vertex or each edge with independent elements of a vector space. Can one get interesting duality relations from there? I guess such a study will also have intersection with matroid theory. $\endgroup$
    – lifeofpi
    Commented May 7, 2010 at 23:48
  • $\begingroup$ You're welcome. Regarding (induced) subgraphs I'm not sure what you are looking for exactly. But with respect to matroids there is indeed a nice duality relation. For matroids we use branch-width instead of tree-width (since graphic matroids don't really have vertices). The corresponding dual notion is tangles instead of brambles. We can think of branch-width as a measure of how tree-like a structure is, and a tangle as a highly connected component of the structure. Again, we have the same duality relation. See math.uwaterloo.ca/~jfgeelen/publications/net.pdf $\endgroup$
    – Tony Huynh
    Commented May 8, 2010 at 6:25
2
$\begingroup$

I think the most straightforward generalization would be to algebraic topology. The analogue to acyclicity is the property of being simply connected, and uniqueness of a path between two vertices becomes the uniqueness of a homotopy class of paths between two points.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .