Two things that should be related

Here are two things that look as if there should be a relation between them.

A graph duality

In my paper on graphs defined on groups, I invented an ad hoc duality relation between pairs of graphs.

The context is that, in a little break from his PhD work, Saul Freedman had looked at the intersection graph of a finite group G, the graph whose vertices are the non-trivial proper subgroups of G, two subgroups joined if the subgroups have non-trivial intersection. This graph was first studied by Csákány and Pollák in 1969; they showed that, for a non-simple group G, if the graph is connected, its diameter is at most&nbs[;4. For simple groups, Shen proved in 2010 that the graph is connected, and asked for a bound on its diameter. Herzog, Longobardi and Maj gave a bound of 64, reduced to 28 by Ma. Saul was able to show that the correct upper bound for simple groups is 5, and that this bound is attained only by the Baby Monster and possibly certain unitary groups.

I was thinking about graphs such as the enhanced power graph, commuting graph, and non-generating graph at the time, and when I wrote the survey I realised that there was a connection.

Let Γ₁ and Γ₂ be graphs with no isolated vertices. I say that these graphs are dual if there is a bipartite graph B with bipartition (V(Γ₁),V(Γ₂)) such that, for i = 1,2, two vertices in V(Γ_i) are joined in Γ_i if and only if they have a common neighbour in B.

Now it is straightforward to see that, if Γ₁ and Γ₂ are dual, then there is a natural bijection between their connected components, and corresponding components have diameters differing by at most 1.

Question: What other properties are shared by dual pairs of graphs?

The relevance of this is that, for a group which is not cyclic of prime order, the non-generating graph is dual to the subgroup intersection graph. (We make a bipartite graph whose vertices are the non-identity elements and non-trivial proper subgroups, with adjacency being membership. Then two non-identity elements fail to generate the group if and only if they lie in a proper subgroup; and two non-identity proper subgroups have non-trivial intersection if and only if some non-identity element lies in both.

So Saul’s result is almost equivalent to a result on the diameter of the non-generating graph of a simple group.

But there is more. We can replace the subgroup intersection graph by the (usually much smaller) maximal subgroup intersection graph, and the duality still applies. (The number of subgroups of a group can be greater than polynomial in the group order, but the number of maximal subgroups cannot. According to Wall’s conjecture, the number of maximal subgroups is strictly less than the group order. This is now known to be false, but it is known to be bounded by c|G|^3/2, and the true exponent is thought to be much lower.)

It is easy to see that the maximal subgroup intersection graph is also dual to the non-generating graph. So similar comments also apply.

There are further results of this sort. For example, if G is minimal non-abelian, then the (maximal) subgroup intersection graph is dual to the commuting graph. And so on.

This looks like it should be a potential unifying principle for results about graphs defined on groups and related graphs.

The zero-divisor graph of a poset

The research discussion on graphs and groups, run by Ambat Vijayakumar and Aparna Lakshmanan in Kochi, produced a cornucopia of ideas, results, and papers. Tamizh Chelvam told us about the zero-divisor graph of a commutative ring with identity, and then Vinayak Joshi told us about the zero-divisor graph of a poset with zero. He proposes this as a unifying principle for various graphs defined on algebraic structures.

Let P be a poset which has a unique minimal element 0. A non-zero element a of P is a zero-divisor if there exists a non-zero element b in P such that the only element below both a and b is 0. The zero-divisor graph of P has as vertices the zero-divisors, two elements a and b adjacent if they have the above relation.

Now among several examples of such graphs, we have the following:

• The annihilating ideal graph of a commutative ring with identity is defined as follows: vertices are those annihilating ideals (ideals with non-zero annihilator) I for which there exists an annihilating ideal J with IJ = 0; adjacency of I and J is defined by this relation.
• Let G be a finite group. Define a relation R on G by the rule that x and y are in the relation if y is a power of x. This is a partial preorder, that is, a reflexive and transitive relation; so the set of equivalence classes of the equivalence relation S (in which two elements are equivalent if each is a power of the other) is partially ordered by R. Extending R by an arbitrary total order on each equivalence class, we obtain a partial order on G, whose comparability graph is the power graph of G. Now take the reverse of this partial order, and introduce a new least element 0 below everything else. Two elements a and b have the property that only 0 lies below both if and only if there is no cyclic subgroup containing a and b. So the zero-divisor graph is the complement of the enhanced power graph of G.
• Angsuman Das studied component graphs of finite vector spaces with a given basis. These turn out to be the joins of zero-divisor graphs of a lattice derived from the vector space with complete graphs.
• Any graph Γ can be considered as a simplicial complex, whose elements are the empty set and the vertices and edges of the graph. We can regard this complex as a poset, and take the zero-divisor graph of it. If we adjoin the edges of Γ to this graph, we obtain a graph whose chromatic number is the total chromatic number of Γ.

A concept which includes four such different graphs as special cases is obviously a good candidate for a unifying principle. Moreover, any general results that can be proved about zero-divisor graphs of posets will contain as corollaries results about the three types of graph above.

In particular, it often happens (for example, in the second and fourth examples above) that the graph is weakly perfect, that is, has clique number equ al to chromatic number. A good start would be to prove this for posets under som e additional condition which would have these results as special cases.

Question: Can we connect the above theories of dual graphs and zero-divisor graphs of posets?