Rainbow-independent set

In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color.

Formally, let Template:Math be a graph, and suppose vertex set Template:Mvar is partitioned into Template:Mvar subsets Template:Math, called "colors". A set Template:Mvar of vertices is called a rainbow-independent set if it satisfies both the following conditions:

• It is an independent set – every two vertices in Template:Mvar are not adjacent (there is no edge between them);
• It is a rainbow set – Template:Mvar contains at most a single vertex from each color Template:Mvar.

Other terms used in the literature are independent set of representatives, independent transversal, and independent system of representatives.

As an example application, consider a faculty with Template:Mvar departments, where some faculty members dislike each other. The dean wants to construct a committee with Template:Mvar members, one member per department, but without any pair of members who dislike each other. This problem can be presented as finding an ISR in a graph in which the nodes are the faculty members, the edges describe the "dislike" relations, and the subsets Template:Math are the departments.

Variants

It is assumed for convenience that the sets Template:Math are pairwise-disjoint. In general the sets may intersect, but this case can be easily reduced to the case of disjoint sets: for every vertex Template:Mvar, form a copy of Template:Mvar for each Template:Mvar such that Template:Mvar contains Template:Mvar. In the resulting graph, connect all copies of Template:Mvar to each other. In the new graph, the Template:Mvar are disjoint, and each ISR corresponds to an ISR in the original graph.

ISR generalizes the concept of a system of distinct representatives (SDR, also known as transversal). Every transversal is an ISR where in the underlying graph, all and only copies of the same vertex from different sets are connected.

Existence of rainbow-independent sets

There are various sufficient conditions for the existence of an ISR.

Condition based on vertex degree

Intuitively, when the departments Template:Mvar are larger, and there is less conflict between faculty members, an ISR should be more likely to exist. The "less conflict" condition is represented by the vertex degree of the graph. This is formalized by the following theorem:Template:Rp

If the degree of every vertex in Template:Mvar is at most Template:Mvar, and the size of each color-set is at least Template:Math, then Template:Mvar has an ISR.

The Template:Math is best possible: there are graph with vertex degree Template:Mvar and colors of size Template:Math without an ISR. But there is a more precise version in which the bound depends both on Template:Mvar and on Template:Mvar.

Condition based on dominating sets

Below, given a subset Template:Mvar of colors (a subset of Template:Math), we denote by Template:Math the union of all subsets in Template:Mvar (all vertices whose color is one of the colors in Template:Mvar), and by Template:Mvar the subgraph of Template:Mvar induced by Template:Math. The following theorem describes the structure of graphs that have no ISR but are edge-minimal, in the sense that whenever any edge is removed from them, the remaining graph has an ISR.

If Template:Mvar has no ISR, but for every edge Template:Mvar in Template:Mvar, Template:Mvar has an ISR, then for every edge Template:Math in Template:Mvar, there exists a subset Template:Mvar of the colors Template:Math and a set Template:Mvar of edges of Template:Mvar, such that:

• The vertices Template:Mvar and Template:Mvar are both in Template:Math;
• The edge Template:Math is in Template:Mvar;
• The set of vertices adjacent to Template:Mvar dominates Template:Mvar;
• Template:Math;
• Template:Mvar is a matching – no two edges of it are adjacent to the same vertex.

Hall-type condition

Below, given a subset Template:Mvar of colors (a subset of Template:Math), an independent set Template:Mvar of Template:Mvar is called special for Template:Mvar if for every independent subset Template:Mvar of vertices of Template:Mvar of size at most Template:Math, there exists some Template:Mvar in Template:Mvar such that Template:Math is also independent. Figuratively, Template:Mvar is a team of "neutral members" for the set Template:Mvar of departments, that can augment any sufficiently small set of non-conflicting members, to create a larger such set. The following theorem is analogous to Hall's marriage theorem:

If, for every subset S of colors, the graph Template:Mvar contains an independent set Template:Mvar that is special for Template:Mvar, then Template:Mvar has an ISR.

Proof idea. The theorem is proved using Sperner's lemma.Template:Rp The standard simplex with Template:Mvar endpoints is assigned a triangulation with some special properties. Each endpoint Template:Mvar of the simplex is associated with the color-set Template:Mvar, each face Template:Math of the simplex is associated with a set Template:Math of colors. Each point Template:Mvar of the triangulation is labeled with a vertex Template:Math of Template:Mvar such that: (a) For each point Template:Mvar on a face Template:Mvar, Template:Math is an element of Template:Mvar – the special independent set of Template:Mvar. (b) If points Template:Mvar and Template:Mvar are adjacent in the 1-skeleton of the triangulation, then Template:Math and Template:Math are not adjacent in Template:Mvar. By Sperner's lemma, there exists a sub-simplex in which, for each point Template:Mvar, Template:Math belongs to a different color-set; the set of these Template:Math is an ISR.

The above theorem implies Hall's marriage condition. To see this, it is useful to state the theorem for the special case in which Template:Mvar is the line graph of some other graph Template:Mvar; this means that every vertex of Template:Mvar is an edge of Template:Mvar, and every independent set of Template:Mvar is a matching in Template:Mvar. The vertex-coloring of Template:Mvar corresponds to an edge-coloring of Template:Mvar, and a rainbow-independent-set in Template:Mvar corresponds to a rainbow-matching in Template:Mvar. A matching Template:Mvar in Template:Mvar is special for Template:Mvar, if for every matching Template:Mvar in Template:Mvar of size at most Template:Math, there is an edge Template:Mvar in Template:Mvar such that Template:Math is still a matching in Template:Mvar.

Let Template:Mvar be a graph with an edge-coloring. If, for every subset Template:Mvar of colors, the graph Template:Mvar contains a matching Template:Mvar that is special for Template:Mvar, then Template:Mvar has a rainbow-matching.

Let Template:Math be a bipartite graph satisfying Hall's condition. For each vertex Template:Mvar of Template:Mvar, assign a unique color Template:Mvar to all edges of Template:Mvar adjacent to Template:Mvar. For every subset Template:Mvar of colors, Hall's condition implies that Template:Mvar has at least Template:Math neighbors in Template:Mvar, and therefore there are at least Template:Math edges of Template:Mvar adjacent to distinct vertices of Template:Mvar. Let Template:Mvar be a set of Template:Math such edges. For any matching Template:Mvar of size at most Template:Math in Template:Mvar, some element Template:Mvar of Template:Mvar has a different endpoint in Template:Mvar than all elements of Template:Mvar, and thus Template:Math is also a matching, so Template:Mvar is special for Template:Mvar. The above theorem implies that Template:Mvar has a rainbow matching Template:Mvar. By definition of the colors, Template:Mvar is a perfect matching in Template:Mvar.

Another corollary of the above theorem is the following condition, which involves both vertex degree and cycle length:Template:Rp

If the degree of every vertex in Template:Mvar is at most 2, and the length of each cycle of Template:Mvar is divisible by 3, and the size of each color-set is at least 3, then Template:Mvar has an ISR.

Proof. For every subset Template:Mvar of colors, the graph Template:Mvar contains at least Template:Math vertices, and it is a union of cycles of length divisible by 3 and paths. Let Template:Mvar be an independent set in Template:Mvar containing every third vertex in each cycle and each path. So Template:Math contains at least Template:Math vertices. Let Template:Mvar be an independent set in Template:Mvar of size at most Template:Math. Since the distance between each two vertices of Template:Mvar is at least 3, every vertex of Template:Mvar is adjacent to at most one vertex of Template:Mvar. Therefore, there is at least one vertex of Template:Mvar which is not adjacent to any vertex of Template:Mvar. Therefore Template:Mvar is special for Template:Mvar. By the previous theorem, Template:Mvar has an ISR.

Condition based on homological connectivity

One family of conditions is based on the homological connectivity of the independence complex of subgraphs. To state the conditions, the following notation is used:

• Template:Math denotes the independence complex of a graph Template:Mvar (that is, the abstract simplicial complex whose faces are the independent sets in Template:Mvar).
• Template:Math denotes the homological connectivity of a simplicial complex Template:Mvar (i.e., the largest integer Template:Mvar such that the first Template:Mvar homology groups of Template:Mvar are trivial), plus 2.
• Template:Math is the set of indices of colors, Template:Math For any subset Template:Mvar of Template:Math, Template:Mvar is the union of colors Template:Mvar for Template:Mvar in Template:Mvar.
• Template:Math is the subgraph of Template:Mvar induced by the vertices in Template:Mvar.

The following condition is implicit in and proved explicitly in.

If, for all subsets Template:Mvar of Template:Math:

${\eta }_H(\text{Ind}(G[V_J]))\ge |J|$

then the partition Template:Math admits an ISR.

As an example, suppose Template:Mvar is a bipartite graph, and its parts are exactly Template:Math and Template:Math. In this case Template:Math so there are four options for Template:Mvar:

• Template:Math then Template:Math and Template:Math and the connectivity is infinite, so the condition holds trivially.
• Template:Math then Template:Math is a graph with vertices Template:Math and no edges. Here all vertex sets are independent, so Template:Math is the power set of Template:Math, i.e., it has a single Template:Mvar-simplex (and all its subsets). It is known that a single simplex is Template:Mvar-connected for all integers Template:Mvar, since all its reduced homology groups are trivial (see simplicial homology). Hence the condition holds.
• Template:Math this case is analogous to the previous one.
• Template:Math then Template:Math, and Template:Math contains two simplices Template:Math and Template:Math (and all their subsets). The condition Template:Math is equivalent to the condition that the homological connectivity of Template:Math is at least 0, which is equivalent to the condition that $\widetilde{H_0}(\text{Ind}(G))$ is the trivial group. This holds if-and-only-if the complex Template:Math contains a connection between its two simplices Template:Math and Template:Math. Such a connection is equivalent to an independent set in which one vertex is from Template:Math and one is from Template:Math. Thus, in this case, the condition of the theorem is not only sufficient but also necessary.

Other conditions

Every properly coloured triangle-free graph of chromatic number Template:Mvar contains a rainbow-independent set of size at least Template:Math.

Several authors have studied conditions for existence of large rainbow-independent sets in various classes of graphs.

Computation

The ISR decision problem is the problem of deciding whether a given graph Template:Math and a given partition of Template:Mvar into Template:Mvar colors admits a rainbow-independent set. This problem is NP-complete. The proof is by reduction from the 3-dimensional matching problem (3DM). The input to 3DM is a tripartite hypergraph Template:Math, where Template:Mvar, Template:Mvar, Template:Mvar are vertex-sets of size Template:Mvar, and Template:Mvar is a set of triplets, each of which contains a single vertex of each of Template:Mvar, Template:Mvar, Template:Mvar. An input to 3DM can be converted into an input to ISR as follows:

• For each edge Template:Math in Template:Mvar, there is a vertex Template:Math in Template:Mvar;
• For each vertex Template:Mvar in Template:Mvar, let Template:Math
• For each Template:Mvar, Template:Math, Template:Math, Template:Math, Template:Math, there is an edge Template:Math in Template:Mvar;
• For each Template:Math, Template:Math, Template:Mvar, Template:Math, Template:Math, there is an edge Template:Math in Template:Mvar;

In the resulting graph Template:Math, an ISR corresponds to a set of triplets Template:Math such that:

• Each triplet has a different Template:Mvar value (since each triplet belongs to a different color-set Template:Mvar);
• Each triplet has a different Template:Mvar value and a different Template:Mvar value (since the vertices are independent).

Therefore, the resulting graph admits an ISR if and only if the original hypergraph admits a 3DM.

An alternative proof is by reduction from SAT.

Related concepts

If Template:Mvar is the line graph of some other graph Template:Mvar, then the independent sets in Template:Mvar are the matchings in Template:Mvar. Hence, a rainbow-independent set in Template:Mvar is a rainbow matching in Template:Mvar. See also matching in hypergraphs.

Another related concept is a rainbow cycle, which is a cycle in which each vertex has a different color.

When an ISR exists, a natural question is whether there exist other ISRs, such that the entire set of vertices is partitioned into disjoint ISRs (assuming the number of vertices in each color is the same). Such a partition is called strong coloring.

Using the faculty metaphor:

• A system of distinct representatives is a committee of distinct members, with or without conflicts.
• An independent set is a committee with no conflict.
• An independent transversal is a committee with no conflict, with exactly one member from each department.
• A graph coloring is a partitioning of the faculty members into committees with no conflict.
• A strong coloring is a partitioning of the faculty members into committees with no conflict and with exactly one member from each department. Thus this problem is sometimes called the happy dean problem.

Template:AnchorA rainbow clique or a colorful clique is a clique in which every vertex has a different color. Every clique in a graph corresponds to an independent set in its complement graph. Therefore, every rainbow clique in a graph corresponds to a rainbow-independent set in its complement graph.

See also

• Graph coloring
• List coloring
• Rainbow coloring
• Rainbow-colorable hypergraph
• Independence complex