2
$\begingroup$

Can the group generated by local complementations, ${lc_i|i=1,\cdots,n}$ on simple graphs on $n$ vertices, be categorized as a coxeter group? After all these obey: \begin{equation} \langle lc_i| (lc_i lc_j)^{m_{ij}}=1\rangle \quad where \quad m_{ij}=\{ 2,3,6\} \end{equation}

If so, which classification do they belong to?

A few definitions:

Local complementation, $lc_k$, of vertex $k$ replaces the subgraph induced on the neighborhood, $N_k$ of $k$, by its complement. The transformation on the adjacency matrix, $A_G$ of a graph, $G$ is:

$lc_k: (A_G)_{ij} \rightarrow (A_G)_{ij}+(A_G)_{ik}(A_G)_{jk}+Diagonal[(A_G)_{ij}+(A_G)_{ik}(A_G)_{jk}]$.

Where the addition is $mod(2)$.

We did some numerical work in this regard, see my question "the group of local complementation on simple graphs". We find an interesting pattern which leads us to believe there must be an (if not trivial) interesting underlying group structure.

Improve this question
$\endgroup$
18
  • $\begingroup$ How do you know that those are the only relations among the $lc_i$'s? $\endgroup$
    – Gjergji Zaimi
    Apr 3, 2011 at 3:08
  • $\begingroup$ To be a (quotient of a) Coxeter group you would also need the relations $lc_i^2=1$ i.e. $m_{ii}=1$. $\endgroup$
    – Derek Holt
    Apr 3, 2011 at 9:42
  • $\begingroup$ @Derek: If I understand it correctly a local complementation is the operation of selecting a vertex and changing the subgraph of this vertex and all its neighbors into its complement. Therefore local complementations are involutions by definition. $\endgroup$
    – Johannes Hahn
    Apr 3, 2011 at 13:28
  • 1
    $\begingroup$ Suggestions from a non-specialist: 1) Define "local complementation" for people closer to groups than to graphs, making the involutive property explicit. 2) Indicate what range of examples you've looked at so far, since at first sight there's no reason to expect that you always get Coxeter groups. 3) If there are Coxeter groups in the picture, would that have any immediate implications from the viewpoint of graph theory? $\endgroup$
    – Jim Humphreys
    Apr 3, 2011 at 15:46
  • $\begingroup$ @Zaimi they can easily be worked out. The $m_{ij}=2$ is for when $i=j$ or $i$ and $j$ are disconnected, and $m_{ij}=3$ when $i$ and $j$ are disconnected. So for a given $(lc_i lc_j)^{m_{ij}}=1$,$m_{ij}=2,3 or 6$. $\endgroup$
    – P.H.
    Apr 3, 2011 at 20:42

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.