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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Dear @Felix Goldberg, this question does not appear to be about algebraic topology. $\endgroup$
    – Ricardo Andrade
    Commented 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$
    – Richard Stanley
    Commented 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$
    – Felix Goldberg
    Commented Mar 29, 2014 at 23:56

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I stand corrected. $\endgroup$
    – Dima Pasechnik
    Commented 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$
    – Russ Woodroofe
    Commented 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

Improve this answer
$\endgroup$

You must log in to answer this question.

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