## r-mobius-kantor-configuration-levi-graph.r
## # Unlicense (Ø) 2022 CLP, MR-Amsterdam.
## ----------------------------------------------------------------------------
## Levi graph of the Möbius-Kantor configuration.
## SELF-DUAL CONFIGURATIONS AND REGULAR GRAPHS.
## Author: H. S. M. Coxeter.
## Journal: Bull. Amer. Math. Soc. 56 (1950), 413-455.
## DOI: https://doi.org/10.1090/S0002-9904-1950-09407-5 (free access) .
##
## Three points x,y,z form a Möbius-Kantor triplet iff the sum of the triplet is zero modulo 3.
##
## Galois field GF(3^2) with modulus the irreducible quadratic p(x) = x^2 + x + 2.
## Multiply times x == shift left and reduce overflow by
## k.x^2 == -k.x - k.2, k in Z3
## Successive powers of the primitive root λ = 1.x + 0 (=10) in GF(3, 2):
## (λ1) primitive root λ = 10, shift left, overflow = 1.
## (λ2) λ*10 = 1 | (0,0) + (-1, -2) = 21, shift left, overflow = 2.
## (λ3) λ*21 = 2 | (1,0) + (-2, -4) = 22, shift left, overflow = 2.
## (λ4) λ*22 = 2 | (2,0) + (-2, -4) = 02, shift left, overflow = 0.
## (λ5) λ*02 = 0 | (2,0) + ( 0, 0) = 20, shift left, overflow = 2.
## (λ6) λ*20 = 2 | (0,0) + (-2, -4) = 12, shift left, overflow = 1.
## (λ7) λ*12 = 1 | (2,0) + (-1, -2) = 11, shift left, overflow = 1.
## (λ8) λ*11 = 1 | (1,0) + (-1, -2) = 01
##
## λ1 .. λ8 = 10, 21, 22, 02, 20, 12, 11, 01 (coordinates).
## Note that for example 21 = 2x + 1 in GF(3, 2).
## Three points are collinear when their sum equals 0x + 0 in GF(3,2).
## This is a consequence of the identity λr(1 + λ + λ3) = 0, which holds since
## λ3 + λ + 1 = (λ + 2)(λ2 + λ + 2), (p. 429).
## For example: (1, 2, 4) = 10 + 21 + 02 = 00 (mod 3).
##
## We have a system of eight triples 124, 235, 346, 457, 568, 671, 782, 813,
## derived from one another by cyclic permutation of the digits.
## Möbius-Kantor configuration in RxR:
## 6
## 7 3
## 8 5
## 1 2 4
###############################################################################
require(igraph)
## build Möbius-Kantor configuration. Eulerian path + two edges
mkc <- make_graph(~ 1-2-5-3-4-2-8-3-6-5-7-6-8-7-1, 1-8, 4-5)
mkc$main <- "Möbius-Kantor configuration\n Vertex ids from K[x] / p(x)\n p(x) = x^2 + x + 2, K = Z3"
## set edge attributes to curved, solid and dotted (line type lty)
E(mkc)$curved <- 0
mkc <- set_edge_attr(mkc, name="curved", E(mkc)[9,14], c(-1.5, 1.5))
mkc <- set_edge_attr(mkc, name="lty" , E(mkc), 1L )
mkc <- set_edge_attr(mkc, name="lty" , E(mkc)[9,14], c(3L,3L) )
q3 <- sqrt(3)
## 1 2 5 3 4 8 6 7
ltmkc <- c( 0, 1, 1.25, 1.50 , 2, .75 , 1 , .50
, 0, 0, q3/4, q3/2 , 0, q3/4, q3, q3/2
)
dim(ltmkc) <- c(8, 2)
plot(mkc, layout=ltmkc, edge.width=4, vertex.size=12, sub="Fig.1", vertex.color="green")
###############################################################################
## compute edges of the Möbius-Kantor graph as sequence of vertex pairs.
## levi graph construction.
## append vertex pair (i, ll) if point i is incident with line ll.
mkconf <- list( c(1,2,4) , c(2,3,5) , c(3,4,6) , c(4,5,7)
, c(5,6,8) , c(6,7,1) , c(7,8,2) , c(8,1,3)
)
vp <- c()
for ( i in seq(length(mkconf))){
for (ll in mkconf) {
if (!all(is.na(match(ll, i))) ) {
vp <- append(vp, c(i, paste(ll, collapse="")))
}
}
}
## build Levi graph.
## and reorder to match Galois sequence.
mkl <- make_graph(vp, directed=FALSE)
mkl$main <- "Möbius-Kantor graph\nLevi graph construction"
degree(mkl)
## vertex <-> index
## 1 124 671 813 2 235 782 3 346 4 457 5 568 6 7 8
## 2 1 12 16 3 4 14 5 6 7 8 9 10 11 13 15
vn <- V(mkl)$name # vertex names.
pp <- match(vn, sort(vn))
mkg <- permute(mkl, pp)
## Levi / incidence graph of the Möbius–Kantor configuration.
dev.new(); plot(mkg, layout=layout_in_circle, edge.width=2, sub="Fig. 2")
degree(mkg)
## plot coordinates
## 001 124 002 235 003 346 004 457 005 568 006 671 007 782 008 813
ltmkg <- c(10, 8, 3,1.5, 5, 5, 3,1.5, 0, 2, 7,8.5, 5, 5, 7,8.5,
5, 5, 7,8.5, 10, 8, 3,1.5, 4, 5, 3,1.5, 0, 2, 7,8.5
)
dim(ltmkg) <- c(16, 2)
dev.new(); plot(mkg, layout=ltmkg, edge.width=2, main = "Möbius-Kantor graph\n{8} + {8/3} ", sub="Fig. 3")
###############################################################################
## manual construction Möbius–Kantor graph ({8} + {8/3}).
## see also igraph_generalized_petersen(8, 3)
mkd <-
make_graph(~ 1, 124, 2, 235, 3, 346, 4, 457
, 5, 568, 6, 671, 7, 782, 8, 813 # vertex ids.
, 1-813-3-235-5-457-7-671-1 # outer octagon.
, 124-2-782-8-568-6-346-4-124 # inner octagon.
, 1-124, 813-8, 3-346, 235-2
, 5-568, 457-4, 7-782, 6-671 # connections.
)
mkd$main <- "Möbius-Kantor graph\nManual construction"
degree(mkd)
dev.new(); plot(mkd, layout=layout_in_circle, edge.width =2, sub="Fig. 4")
###############################################################################
# graph as a Swiss tournament
vps <- c( 1,124, 2,235, 3,346, 4,457, 5,568 ,6,671, 7,782, 8,813 # round 1.
, 124,2, 235,3, 346,4, 457,5, 568,6, 671,7, 782,8, 813,1 # round 2.
, 1,671, 2,782, 3,813, 4,124, 5,235, 6,346, 7, 457,8,568 # round 3.
)
mks <- make_graph(as.character(vps), directed=FALSE)
mks$main <- "Möbius-Kantor graph\nConstructed as Swiss tournament"
E(mks)[ 1: 8]$color <- 'red'
E(mks)[ 9:16]$color <- 'blue'
E(mks)[17:24]$color <- 'green'
dev.new(); plot(mks, layout=layout_in_circle, edge.width=2, sub="Fig. 5")
dev.new(); plot(mks, layout=ltmkg, edge.width=2, sub="Fig. 6")
