Graphical Modeling of Combinatorial Chemistry
Shinsaku FUJITA and Sherif ELBASIL
Return
1 Introduction
Traditional textbooks [1  3] on chemical group theory deal with linear representations and character tables of groups, which are usually directed to modeling molecular vibrations, infrared spectroscopy, and symmetrysimplification of seculardeterminants in molecular orbital calculations. On the other hand, Fujita [4] adopted an alternative approach which is based on permutation representations (coset representations) and mark tables}, where he developed the USCI (unitsubducedcycleindex) method [4, 5], aiming at studying combinatorial enumeration in chemistry.
The two approaches of chemical group theory have been compared [6] after the development of the characteristicmonomial method for combinatorial enumeration on the basis of the former approach [7, 8]. While the former approach requires conjugacy relations between elements of a group only, the latter approach requires a knowledge of all group/subgroup relations which may not be trivial to find out.
Usually a group G is expressed as the set of elements of symmetry g's which it contains:
where G is the order of G and g_{1} = I (the identity element). The set of elements of symmetry generates a sequence of subgroups (SSG), which are usually ordered in a nondescending way of their orders:
in which G_{1} = C_{1} = {I} and G_{s} = G. Each subgroup G_{i} (1 <= i <= s) is selected as a representative of conjugate subgroups and may be used to express G as a (right) coset. Thus, a set of cosets may be defined by:
where r represents the number of cosets in the coset decomposition expressed by:
Equation 3 allows one to generate a set of permutations G(/G_{i}) given by:
where each permutation p_{g} is expressed by:
The set of permutations (eq. 5) is called coset representation, the symbol of which has been coined as G(/G_{i}) in order to emphasize the distinction between the global (G) and the local symmetry (G_{i}) [9]. Equations 5 and 6 allow the computation of marks of G as the numbers of cosets which are stabilized by G_{j}'s (1 <= j <= s). When the above types of computation is repeated for all values of i = [1, s] and j = [1, s], the table of marks of G results.
Fujita showed how to use such a table of marks to specify the type of orbit which controls substitution pattern in a given graph [4, 5]. Thus, when this orbit of substitution is specified, it is subdued by all subgroups of G, as expressed by
where G_{i}, G_{j}, G_{k}, and G_{l} are all subgroups of G, while G_{k} G_{l}, ... are subgroups of the (subducing) subgroup G_{j}. Thereby, monomial expressions called unit subduced cycle indices (USCI's) are obtained as general formulas [4, 5]:
where one places d_{jk} = G_{j}/G_{k}, d_{jl} = G_{j}/G_{l}}, and so on and selects the superscripts from the multiplicity factors b_{jk}, b_{jk}, etc. in eq. 7. Naturally, when G_{i} is equal to C_{1}= {I} in eq. 5, the regular representation G(/C_{1}) results.
In general, coset representations (CR's) and their subductions control orbits (equivalence classes) of ligands or vertices in a molecule or graph [10  12] as well as orbits (equivalence classes) of isomeric molecules or graphs (configurations) [4, 5]. The latter point is an essence of combinatorial enumeration (cf. Chapter 15 of Ref. [4]); however, it has been discussed rather mathematically and abstractly in the formulation of theorems for combinatorial enumeration, as pointed out in a recent review [13]. Although a few exceptional efforts have recently appeared [14  16], further studies would be desirable so as to make up for such situations, especially, when the education or popularization of these concepts is taken into consideration.
It is the main objective of this work to model the above abstract concepts such as CR's, marks, subductions, and USCI's by using (colored) graphs which can easily be generated by experimental chemists by analogy with "derivatives by substitution".
2 Modeling Coset Representations and Marks
As an illustration, one considers the D_{4h}group given by:
These symmetry elements are designated in a graph model of D_{4h} depicted in Figure 1.
Figure 1. A moldel of the D_{4h}group. The vertical mirror planes s_{v} and s_{v}^{′} respectively contain twofold rotation axes C_{2(v)} and C_{2(v)}^{′}, while the diagonal mirror planes s_{d} and s_{d}^{′} respectively contain twofold axes C_{2(d)} and C^{′}_{2(d)}^{′}, which are perpendicular to each other and in paperplane. The inversion i and the horizontal mirror plane s_{h} are not depicted.
Let us consider G_{i} = C_{2h} = {I, C_{2}, s_{h}, i}, which is one of the twentyseven subgroups of D_{4h} (up to conjugacy). Then, the cosets of this case are obtained as follows according to eq. 3:
After numbering the cosets sequentially as above, eqs. 5 and 6 are applied to give the permutations shown in Table 1.
Table 1. Coset Representation of D_{4h}(/C_{2h})
By starting from the permutation representation (Table 1), one obtains a fixedpoint vector (FPV) as a row vector:
For example, the checked elements in the C_{s}column of Table 1 indicate that the number of fixed cosets is equal to 4 so that the value for C_{s} in the FPV (eq. 11) is placed to be 4. The FPV constructs the row of D_{4h}(/C_{2h}) in the mark table of D_{4h}, the full list of which has been reported elsewhere [17].
Permutations of a coset representation such as listed in Table 1 are modeled by a set of colored graphs called homomers which is given by
so that a onetoone function exists, i.e.,
This has been generally proved previously (Theorem 15.2 of [4]). It should be noted that the present term "homomer" designates both homomers and enantiomers from the stereochemical point of view.
To obtain such homomers (colored graphs), one proceeds as follows:

Finding a parent graph: Find a graph which models the identity representation G(/G). This graph has once been discussed in terms of regular bodies [10]. This graph has two properties.

It has G number of vertices, which are governed by the regular representation G(/C_{1}).

It stays fixed under the action of all of the elements of G.
Thus, this graph is a single uncolored graph, i.e., H[G(/G)] = {h}, which may be here called the parent graph of the group G.

Partition of vertices: Graphs which model other coset representations are colored graphs because they represent reduction of the symmetry of the parent graph h. The term "coloring" is the mathematical synonym of "substitution" in chemistry, which has been once discussed in terms of subductive and inductive derivation [11, 12]. Thus, to find H[G(/G_{i})] = {h_{1}, h_{2},..., h_{r}}, one applies all of the elements of G_{i} on an appropriate vertex (v_{a}) of the parent graph h, where one can obtain a set of equivalent vertices, e.g., (v_{a} v_{b} v_{c} v_{d}). Among the remaining vertices of h, one next selects a vertex v_{e} and the same operation is conducted to give another set of equivalent vertices, e.g., (v_{e} v_{f} v_{g} v_{h}). Such an operation is repeated to cover all of the vertices of h to obtain a product of "color identities" (v_{a} v_{b} v_{c} v_{d})(v_{e} v_{f} v_{g} v_{h})... as a vertex partition, where the number of vertices in every set has been previously proved to be equal to G_{i} in general (Lemma 2 of [10]).

Selecting a starting homomer: The vertices of an arbitrary set are colored in black, where one selects the number of black (colored) vertices to be smaller than (or equal to) the number of white (uncolored) vertices. It should be noted that, generally speaking, the coloring of the first set (v_{a} v_{b} v_{c} v_{d}), the second set (v_{e} v_{f} v_{g} v_{h}), etc. produces isomers of the G_{i}symmetry but not always homomers (cf. Lemma 2 and Theorem 1 of [10]). Among such isomers, one selects an arbitrary one as h_{1}.

Generating a homomer set: The resulting colored homomer, h_{1}, is operated upon by the elements of G to generate the full set of (symmetry equivalent) graphs H[G(/G_{i})] = {h_{1},h_{2},...,h_{r}}.
For example, let us consider D_{4h}(/C_{2h}), the parent graph h of which is depicted in Figure 1. The numbering of vertices can be selected arbitrarily, as found in Figure 1. Then, one selects vertex 1, which is moved by the elements of C_{2h} ={I, C_{2}, s_{h}, i}. Thereby, one obtains a set of equivalent vertices (1 5 9 13), which are colored in black so as to give a homomer h_{1} shown in Figure 2. By applying the representative C_{4} of the coset C_{2h}C_{4} (eq. 10) to the first homomer h_{1}, its numbering is changed to the second homomer h_{2}, in which vertices 1, 5, 9, 13 are colored in black. Note that each element of the coset C_{2h}C_{4} produces the identical homomer h_{2}, although the numbering may alter according to the element. On the same line, the applications of C_{2(d)} (ÎC_{2h}C_{2(d)}) and C_{2(v)} (ÎC_{2h}C_{2(v)}) yield homomers h_{3} and h_{4}, respectively. As a result, it can be shown that the set H[D_{4h}(/C_{2h})] experiences the bijection, h_{1}® 1, h_{2}® 2, h_{3}® 3, and h_{4}® 4, where the cosets at issue are numbered as shown in eq. 10.
Figure 2. H[D_{4}(/C_{2h})] = {h_{1},h_{2},h_{3},h_{4}}. The four homomers which model D_{4h}(/C_{2h}) and generate the permutations in Table 1 when h_{i}'s are moved over i = [1,4]. All of the four homomers are stabilized (fixed) under the action of C_{1}, C_{2}, C_{s}, C_{i}, and C_{2h}, leading to the mark row (the FPV) given by eq. 11.
As found easily by the procedure described in the preceding paragraph, each element of the coset C_{2h}I fixes all of the homomers (h_{1}, h_{2}, h_{3}, and h_{4}), where this corresponds to the permutation (1)(2)(3)(4); each element of the coset C_{2h}C_{4} exchanges the pair of h_{1} and h_{2} as well as the pair of h_{3} and h_{4}, where this corresponds to the permutation (1 2)(3 4); each element of the coset C_{2h}C_{2(d)} exchanges the pair of h_{1} and h_{3} as well as the pair of h_{2} and h_{4}, where this corresponds to the permutation (1 3)(2 4); and finally each element of the coset C_{2h}C_{2(v)} exchanges the pair of h_{1} and h_{4} as well as the pair of h_{2} and h_{3}, where this corresponds to the permutation (1 4)(2 3). Thereby, one can obtain the permutations of D_{4h}(/C_{2h}) collected in Table 1. Moreover, all of the four homomers (Figure 2) are stabilized (fixed) under the action of C_{1}, C_{2}, C_{s}, C_{i}, and C_{2h} so that their marks (the numbers of fixed homomers) are equal to 4, leading graphically tothe mark row (the FPV) given by eq. 11.
Let us next consider C_{4v}(/C_{s}). The parent graph h which produces the colored graphs depicted in Figure 3 is selected by referring to the parent graph of D_{4h} (Figure 1) so that the elements of C_{4v} = {I, C_{4}, C_{4}^{3}, C_{2}, s_{v}, s_{v}^{′}, s_{d}, s_{d}^{′}} are related to those illustrated in Figure 1. The numbering of vertices can be selected arbitrarily, as found in h_{1} of Figure 3. By considering a subgroup C_{s} = {I, s_{v}}, one can obtain the corresponding cosets: C_{s}I = {I, s_{v}}, C_{s}C_{4} = {C_{4}, s_{d}}, C_{s}C_{2} = {C_{2}, s_{v}^{′}}, and C_{s}C_{4}^{3} = {C_{4}^{3}, s_{d}^{′}}.
Figure 3. H[C_{4h}(/C_{s})] = {h_{1},h_{2},h_{3},h_{v4}}. Subgroups which fix each homomer are indicated to generate the mark row (FPV) given by eq. 14.
The partition step described above is applied to this case so as to produce the vertex partition: (1 2)(3 8)(4 7)(5 6). When one selects the first set (1 2) of the vertex partition and colors the two vertices, one can produce the first colored graph h_{1} shown in Figure 3. The coloring of the second set (3 8) or (4 7) produces another graph h_{1}^{′}, which is an isomer of h_{1}.
By applying the representative C_{4} of the coset C_{s}C_{4} to the first homomer h_{1}, its numbering is changed to the second homomer h_{2}, in which vertices 1 and 2 are colored in black, as shown in Figure 3. On the same line, the applications of C_{2} (ÎC_{s}C_{2}) and C_{4}^{3} (ÎC_{s}C_{4}^{3}) yield homomers h_{3} and h_{4}, respectively (Figure 3). It follows that the four homomers of the homomer set H[C_{4v}(/C_{s})] exhibit onetoone correspondence to the sets of cosets through their representatives.
By the inspection of Figure 3, one can immediately write the following mark row:
3 Modeling OneDimensional Irreducible Representations
Fujita demonstrated that rows of marks may be resolved into sums of irreducible representations [10]. When a given row of marks contains only 2's and 0's, then it is the sum of totally symmetric representation (all characters are ones) and a onedimensional irreducible representation [15]. Figure 4 portrays several colored graphs which model coset representations, marks, and onedimensional representations for the group D_{4h}.
Figure 4. Modeling coset representations, stabilizer subgroups, and onedimensional irreducible representations. In all these cases, one has H = {h_{1},h_{2}}, among which h_{1} is shown and h_{2} is the complement graph.
4 Modeling Group Subductions
To find G(/G_{i})¯G_{j}, where G_{i} and G_{j} are both subgroups of G, one considers the set of permutations of G(/G_{i}), which remains after eliminating all permutations except those which correspond to G_{j}. Then the corresponding row of marks is expressed as the sum shown in eq. 7. Graphically, one might write the corresponding equations:
Figure 5 illustrates an example of eq. 15. The homomer set H[C_{3v}(/C_{s})] = {h_{1},h_{2},h_{3}} shown in the top row of Figure 5 is divided into two sets, i.e., = {h_{1},h_{2}} and {h_{3}}, under the subduction into C_{s}. These subduced sets correspond to a homomer set H[C_{s}(/C_{1})] = {h_{1}^{′},h_{2}^{′}} and a homomer set H[C_{s}(/C_{s})] = {h^{′}}, respectively, as shown in the bottom row of Figure 5. To test such subductions, a systematic method based on Cayley graphs has been reported [14].
Figure 5. Modeling a group subduction represented by C_{3v}(/C_{s})¯C_{s} = C_{s}}(/C_{1}) + C_{s}(/C_{s}).
A more direct model of G(/G_{i})¯G_{j} would be helpful to understand the process of subduction. Thus, one first considers the case of G(/G)¯G_{j}. The corresponding homomer set H[G(/G)] contains only one (uncolored) graph (the parent graph). Obviously, one can find G(/G)¯G_{j} = G_{j}(/G_{j}), which corresponds to a homomer set H[G_{j}(/G_{j})] containing one (uncolored) graph. This step corresponds to a kind of coloring other than the vertex coloring described in the preceding paragraphs. For example, Figure 6 illustrates a direct model for the subduction C_{3v}(/C_{3v})¯C_{s} = C_{s}(/C_{s}), where the coloring ("substitution") of two bridgehead positions by nitrogens restricts the symmetry of the parent graph.
Figure 6. Direct modeling of a group subduction represented by C_{3v}(/C_{3v})¯C_{s} = C_{s}(/C_{s}).
It should be noted that the left diagram for H[C_{3v}(/C_{3v})] in Figure 6 contains a set of six equivalent vertices, while the right diagram for H[C_{s}(/C_{s})] contains three pairs of equivalent vertices. Each of the three pairs indicates a parent graph representing H[C_{s}(/C_{s})].
Keeping Figure 6 in mind, one considers a direct model for the subduction C_{3v}(/C_{s})¯C_{s}, as shown in Figure 7. The homomer set H[C_{3v}(/C_{s})] = {h_{1},h_{2},h_{3}} shown in the top row of Figure 7 (the same as those in Figure 5) is divided into two sets, i.e., = {h_{1}^{′},h_{2}^{′}} and = {h^{′}} by the symmetry restriction (into C_{s}) due to the bridgehead coloring by nitrogens, as shown in the bottom row of Figure 7. These subduced sets correspond to H[C_{s}(/C_{1})] and H[C_{s}(/C_{s})], respectively. The comparison of Figure 7 with Figure 5 indicates that the two kinds of modeling for group subductions are closely related to each other.
Figure 7. Direct modeling of a group subduction represented by C_{3v}(/C_{s})¯C_{s} = C_{s}(/C_{1}) + C_{s}(/C_{s}).
5 Conclusion
Four abstract concepts, i.e., coset representations, marks, characters, and group subductions, are modeled by using colored graphs and a set of symmetry operations. Thereby, their fruitful contents are so much visualized that one would get an intimate knowledge on these concepts.
References
[ 1] H. H. Jaffe and M. Orchin, Symmetry in Chemistry, Wiley, Chichester (1965).
[ 2] F. A. Cotton, Chemical Applications of Group Theory, WileyInternational, New York (1971).
[ 3] D. M. Bishop, Group Theory and Chemistry, Clarendon, Oxford (1973).
[ 4] S. Fujita, Symmetry and Combinatorial Enumeration in Chemistry, SpringerVerlag, BerlinHeidelberg (1991).
[ 5] S. Fujita, Theor. Chim. Acta, 76, 247–268 (1989).
[ 6] S. Fujita, J. Math. Chem., 30, 249–270 (2001).
[ 7] S. Fujita, Theor. Chem. Acc., 99, 224–230 (1998).
[ 8] S. Fujita, Theor. Chem. Acc., 101, 409–420 (1999).
[ 9] S. Fujita, J. Am. Chem. Soc., 112, 3390–3397 (1990).
[10] S. Fujita, Theor. Chim. Acta, 78, 45–63 (1990).
[11] S. Fujita, Bull. Chem. Soc. Jpn, 64, 3313–3323 (1991).
[12] S. Fujita, J. Chem. Inf. Comput. Sci., 31, 540–546 (1991).
[13] S. ElBasil, MATCH, 46, 7–23 (2002).
[14] S. ElBasil, Combinatorial Organic Chemistry, An Educational Approach, Nova Scientific, New York (1999).
[15] S. Fujita and S. ElBasil, MATCH, 46, 121–135 (2002).
[16] S. Fujita and S. ElBasil, J. Math. Chem., 33, 255–277 (2003).
[17] S. Fujita, Helv. Chim. Acta, 85, 2440–2457 (2002).
Return