複体の数と列挙

• 要素があるときに、集合族を考えて、さらにその中で複体制約を満足することを考える
• さらに、複体であって、がすべて複体を構成する単体に帰属するものとする
• その個数はこちらに書いたように、数列ID:A006126 "Number of hierarchical models with linear terms forced. Also number of antichain covers of a labeled n-set"になる
• これを「自力で数えよう」
• 個のべき集合の要素が半順序を構成している
• ここにできる複体とは、半順序関係にあって、到達できない点の集合のことである
• したがって
  • (1)半順序のグラフを作る
  • (2)到達可能性を確認する
  • (3)到達不可能な部分集合間にエッジを張ったグラフを作る
  • (4)このグラフにみとめられるすべてのクリークが、作りうる複体である
  • (5)がすべて要素単体に含まれるとは、このようにして確認できる複体のうち、が含まれているものを取り出すことでできる
  • (6)この条件を満たす複体を列挙することもできる

# 格子グラフの隣接行列(有向グラフ)を作る
# 到達可能性のないノード間にエッジを張る
# クリークを全列挙する
# それがすべての複体
# 1:nを網羅する複体は、ノードIDを二進数にして、
# それをクリーク構成ノード全体について調べ、
# 1:nを網羅していればOK

to_bin.ry <- function(k, x){
  if(k <= 0){
    return(c())
  } else {
    return(append(Recall(k-1, x%/%2), x%%2))
  }
}
make.lattice.adj <- function(n){
	E <- list()
	E[[1]] <- matrix(0,1,1)
	if(n>1){
		for(i in 2:n){
			up.e <- cbind(E[[i-1]],diag(rep(1,2^(i-2))))
			lw.e <- cbind(diag(rep(1,2^(i-2))),E[[i-1]])
			E[[i]] <- rbind(up.e,lw.e)
		}
	}
	E
}

library(igraph)
n <- 6
E <- make.lattice.adj(n)



G <- G.unreach <- CL <- CL.full <- list()
N.cl <- N.cl.full <- rep(0,n)
for(i in 1:n){
	tmp.E <- E[[i]]
	tmp.E[lower.tri(tmp.E)] <- 0
	G[[i]] <- graph.adjacency(tmp.E,mode = "directed")
	sh.p <- shortest.paths(G[[i]],mode="out")
	E.unreach <- (sh.p==Inf)
	E.unreach[lower.tri(E.unreach)] <- FALSE
	G.unreach[[i]] <- graph.adjacency(E.unreach,mode = "undirected")
	plot(G.unreach[[i]])
	tmp.cl <- cliques(G.unreach[[i]])
	N.cl[i] <- length(tmp.cl)
	CL[[i]] <- list()
	CL.full[[i]] <- list()
	tmp.cnt <- 1
	for(j in 1:N.cl[i]){
		CL[[i]][[j]] <- matrix(0,length(tmp.cl[[j]]),i-1)
		for(jj in 1:length(tmp.cl[[j]])){
			CL[[i]][[j]][jj,] <- to_bin.ry(i-1,tmp.cl[[j]][jj]-1)
		}
		#print(apply(CL[[i]][[j]],2,sum))
		if(prod(apply(CL[[i]][[j]],2,sum))>0){
			CL.full[[i]][[tmp.cnt]] <- CL[[i]][[j]]
			tmp.cnt <- tmp.cnt + 1
		}
	}
	N.cl.full[i] <- length(CL.full[[i]])
}
N.cl
N.cl.full