2
$\begingroup$

The independence complex $I(G)$ of a graph $G=(V,E)$ has as point set the vertex set $V$ and as simplices the independent sets of $G$.

Now, if $G$ is a well-covered graph (where all maximal independent sets have the same cardinality $\alpha$) then $I(G)$ is obviously the uniform matroid $U_{n,\alpha}$.

Can the graphs $G$ for which $I(G)$ is a matroid be characterized?

$\endgroup$
3
  • 1
    $\begingroup$ Dear @Felix Goldberg, this question does not appear to be about algebraic topology. $\endgroup$ Mar 28, 2014 at 22:32
  • 2
    $\begingroup$ It is not true that if $G$ is well-covered, then $I(G)$ is a uniform matroid. In fact, $I(G)$ need not be a matroid complex, e.g., the complement of a 4-vertex path. $\endgroup$ Mar 29, 2014 at 2:42
  • $\begingroup$ Looks like I've dropped the ball on this one. Still, I think I shan't delete as perhaps this can be useful as a "don't try that" post... $\endgroup$ Mar 29, 2014 at 23:56

2 Answers 2

7
$\begingroup$

A (finite) simplicial complex is the independent set complex of a graph $G$ if and only if its minimal nonfaces have two elements. If it is also a matroid complex, if follows that the circuits of the matroid have two elements. Thus $G$ is a disjoint union of complete graphs, not just a single complete graph.

$\endgroup$
2
  • $\begingroup$ I stand corrected. $\endgroup$ Mar 30, 2014 at 13:57
  • $\begingroup$ My favorite example is the cross polytope (i.e., generalized octahedron), which is the independence complex of the disjoint union of $K_2$'s. $\endgroup$ Mar 30, 2014 at 19:38
2
$\begingroup$

Assume $G$ connected (thanks to Richard Stanley for pointing this out). The only possibility is that $G$ is a complete graph. Indeed, if $G$ has a path $abc$ of length 2, so that there is no edge between $a$ and $c$, then one can see that the augmentation property for independent (in the sense of matroid) sets with vertices in $abc$ will be violated. Take the independent sets $\{a,c\}$ and $\{b\}$. Then by the augmentation property there should be an element in the bigger independent set that one can add to the smaller one, and still have an independent set. But this is not possible, as $b$ is connected by edges to both $a$ and $c$. QED

$\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.