9
$\begingroup$

Preliminaries

Let $[n] = \{0,\dots,n-1\}$ and $P([n])$ be the power set of $[n]$.

Let the correlation between two subsets $x,y$ of $[n]$ be the number $\kappa(x,y) = 1 - \frac{2}{n}|x\triangle y|$ with $x\triangle y$ the symmetric difference between $x$ and $y$.

$\kappa$ measures how strongly $x, y$ do agree in terms of their members and non-members, from $\kappa=1$ for $x=y$ to $\kappa=-1$ when $x$ and $y$ are complements of each other. When $|x\triangle y|=n/2$ the sets $x,y$ are uncorrelated, $\kappa = 0$.

Question

I wonder how, why and under which circumstances it is possible to literally see the symmetries of a structure (or at least some of them), and how to interpret systematically what is seen.

As a non-trivial example consider the correlation graph $(V,E)$ of the powerset $P([8]) =: V$ where $(x,y)\in E$ when $\kappa(x,y) \neq 0$.

Some symmetries of this graph are due to the fact that for every permutation $\pi$ of $\{0,\dots,7\}$ it holds that $\kappa(x,y) = \kappa(\pi(x),\pi(y))$. Further, the graph is invariant against complements, since $\kappa(x,y) = \kappa(\overline{x},\overline{y})$

Many more symmetries can be seen in one of the 256x256 adjacency matrices of the graph:

enter image description here

To see some kind of translational symmetries it is helpful to bend this square to a torus. Then it is also seen, that on the highest level the pattern consists of two pairs of symmetric squares:

enter image description here

On a lower level, it consists of five smaller symmetric squares:

enter image description here

On an even lower level, it consists of two symmetric squares:

enter image description here

Even lower, it consists of three symmetric squares:

enter image description here

Even lower, it consists of two symmetric squares:

enter image description here

Finally we find, that it consists of only two tiny symmetric squares:

enter image description here

Question 1: Are there other than the canonical labeling of the elements of $V$ (by Ackermann encoding which was used for the adjacency matrix above) that show the symmetries to the eye? If not so: How can I understand that it is essentially this labeling that has this property?

Question 2: How can these visual observations be put in correspondence to abstract facts about the automorphism group of the graph, including its size?

Question 3: To which visible symmetries corresponds the invariance of the graph with respect to permutations of $\{0,\dots,7\}$ and with respect to complements?

Question 4: How might an algorithm look like that - given a scrambled adjacency matrix (without any visible symmetries) - finds a sequence of transpositions that lead to the unscrambled matrix above? (see Rubik's cube)

$\endgroup$
  • $\begingroup$ Um, $x\triangle y \ne \varnothing$ exactly when $x\ne y$, and that's not the graph you're drawing. $\endgroup$ – Henning Makholm Oct 27 '16 at 9:37
  • $\begingroup$ Sorry for that, I fixed the question. $\endgroup$ – Hans-Peter Stricker Oct 28 '16 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.