MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
How do you know that those are the only relations among the $lc_i$'s? – Gjergji Zaimi Apr 3 '11 at 3:08
To be a (quotient of a) Coxeter group you would also need the relations $lc_i^2=1$ i.e. $m_{ii}=1$. – Derek Holt Apr 3 '11 at 9:42
@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. – Johannes Hahn Apr 3 '11 at 13:28
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? – Jim Humphreys Apr 3 '11 at 15:46
@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$. – P.H. Apr 3 '11 at 20:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.