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 Γ1 and Γ2 be graphs with no isolated vertices. I say that these graphs are dual if there is a bipartite graph B with bipartition (V1),V2)) such that, for i = 1,2, two vertices in Vi) are joined in Γi if and only if they have a common neighbour in B.

Now it is straightforward to see that, if Γ1 and Γ2 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?

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, open problems and tagged , , , . Bookmark the permalink.

4 Responses to Two things that should be related

  1. dsp says:

    Hasn’t the weak perfectness of zero-divisor graphs of posets already been proven by Xue and Liu?

  2. Let P be a finite poset, a join graph on P is created by joining all pair of elements which have a join, and similary with meet graph. The join graph and meet graph are dual graph, the bipartite graph we need is created by joining vertex j of join graph to vertex m of meet graph such that j<=m. The zero-divisor graph of P is the complement of the meet graph of P/{0}. Not sure if it is a good connection.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.