3
$\begingroup$

Let $G$ be an undirected graph with no multiple edges or loops. Recall that the independece system $\mathcal{I}(G)$ consists of all those subsets $A$ of the vertex set such that the induced subgraph $G[A]$ is totall disconnected. The independence system is an abstract simplicial complex and a lot of its topological invariants are related to combinatorial properties (like, chromatic number, domination number etc.) of the underlying graph.

I have following two generalization of the independence system in mind. A simple Google search did not yield any work that explores these complexes.

  1. For a natural number $j\geq 2$ denote by $\mathcal{C}_j(G)$ the collection of subsets of vertices of $G$ such that for $A$ in that collection the induced subgraph $G[A]$ does not contain a $j$-clique.
  2. For a natural number $r\geq 1$ denote by $\mathcal{E}_r(G)$ the collection such that for every $A\in \mathcal{E}_r(G)$ each connectedd component of $G[A]$ has at most $r$ vertices.

It is clear from above definitions that $\mathcal{I}(G) = \mathcal{C}_2(G) = \mathcal{E}_1(G)$. Can anybody point me to a reference where either of these generalizations are studied? I would like to know if any of topological invariants of these complexes relate to graph theoretic information.

$\endgroup$
1
  • $\begingroup$ You can see clique complex for the first complex you mention $\endgroup$
    – vidyarthi
    Jan 13, 2020 at 11:01

4 Answers 4

3
$\begingroup$

Although I am not sure if these concepts been studied much as simplicial complexes, at least the second has been studied quite extensively in graph theory and theoretical computer science (including by me).

The earliest studies I am aware of are

Sampathkumar. Discrete Math., 1993. https://doi.org/10.1016/0012-365X(93)90493-D

Edwards and Farr. JCTB, 2001. https://doi.org/10.1006/jctb.2000.2018

These come at the problem from independent perspectives, but the concept is natural enough that maybe it gets reintroduced regularly.

For instance, it has some connection to vaccination protocols:

Britton, Janson, Martin-Löf. Adv. Appl. Prob., 2007. https://doi.org/10.1239/aap/1198177233

There is a rather extensive study of efficient partitions of the vertex set of a graph into such (and related) types of sets, a partial (dynamic) survey of which is given by Wood in the Electr. J. Comb.

As an act of pure vanity, my own study of this type of independence concerns the binomial random graph:

Broutin and Kang. J. Comb., 2019. http://dx.doi.org/10.4310/JOC.2018.v9.n3.a1

As for the first concept, it has also been studied a bit I believe, but less so (probably because it is much harder to make progress on).

$\endgroup$
3
$\begingroup$

The notion of $\mathcal{C}_j(G)$ is natural in terms of hypergraphs where is has been studied. If you rephrase in terms of a hypergraphs, then $\mathcal{C}_j(G)$ becomes the independence complex of the hypergraph. These have been studied a lot in (combinatorial) commutative algebra.

An independent set in a hypergraph is any subset of vertices which does not contain any hyperedge. The independence complex of a hypergraph is (just like for graphs) the simplicial complex whose faces are the independent sets. Now for any graph $G$ let $H_j(G)$ be the hypergraph on the same vertex set whose hyperedges are $j$-cliques. Now $\mathcal{C}_j(G)$ is the independence complex of $H_j(G)$. Many references can be found by searching for "independence complex hypergraph" and also changing "hypergraph" to "clutter" is useful in search and you'll find more articles.

The minimal non-faces of the independence complex are the hyperedges. Thus, the square-free monomial ideal with a generator corresponding to each hyperedge is the Stanley–Reisner ideal for the independence complex. As such the topology along with properties like shellability and vertex decomposability are of great interest. Searching things like "Cohen-Macaulay clutters" will turn up more results.

The hypergraphs obtained as $H_j(G)$ will be $j$-uniform (i.e. all hyperedges contain $j$ vertices) and in fact all $j$-uniform hypergraphs are $H_j(G)$ for some $G$. So, the study of the complexes $\mathcal{C}_j(G)$ is the same of the study of independence complexes of $j$-uniform hypergraphs. Also, the map $G \mapsto H_j(G)$ is not one-to-one; so, it makes more sense to consider relations of the topology of the complex and properties of the hypergraph. One such property that arises is chordality and generalizations of it:

Chordal and Sequentially Cohen-Macaulay Clutters by Woodroofe

A class of hypergraphs that generalizes chordal graphs by Emtander

$\endgroup$
1
$\begingroup$

An answer for 1. would definitely include keywords "simplicial complex" and most probably "triangle-free" or some other "-free subgraphs". There's not many results and the only relevant one is this article, which discusses methods for the complex of $\mathcal{F}$-free induced subgraphs in general, where $\mathcal{F}$ is a family of graphs to be excluded as subgraphs (not induced). In your case you would take, respectively, $\mathcal{F}=\{K_j\}$ and $\mathcal{F}=$ $(r+1)$-vertex trees. Motivations are given for other $\mathcal{F}$ only, though, and there's no follow-up work on those devoid complexes.

What has been studied a bit more is simplicial complexes of all graphs on $n$ vertices with a given monotone property, meant as subsets of $\binom{n}{2}$. In other words, all subsets of edges of the $n$-clique, with some property. See the book Simplicial complexes of graphs by Jakob Jonsson, in particular sections 26.7 Triangle-Free Graphs (p. 351-352) and 18.2 Graphs with No Large Components (pp. 247-258).

$\endgroup$
1
$\begingroup$

To add to my previous answer, a paper of Szabó and Tardos from 2006 ("Extremal problems for transversals in graphs with bounded degree") has a result related to the complex you defined in 2.

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