rahtml/ra3053.html

The 16 element relation algebra with the longest proof of nonrepresentability

(still under construction...:-)

a is red, b is blue, c is green

Consistent triples (must appear on each matching edge in a representation)

Inconsistent triples (must NOT appear in any representation)

Game theoretic proof that this relation algebra is not representable:

N₁ = c₁₂ b₁₃a₂₃ a₁₄b₂₄c₃₄ A:a₁₅a₅₂

N₂ = c₁₂ a₁₃b₂₃ a₁₄b₂₄c₃₄ A:a₁₅a₅₂

N₃ = c₁₂ b₁₃c₂₃ b₁₄a₂₄b₃₄ a₁₅b₂₅c₃₅b₄₅ A:a₁₆a₆₂ [ 2, 2, 3, 4 ], N₂[ 2, 3, 4, 6 ]

N₄ = c₁₂ c₁₃a₂₃ a₁₄c₂₄b₃₄ a₁₅b₂₅c₃₅c₄₅ A:a₁₆a₆₂

N₅ = c₁₂ c₁₃a₂₃ b₁₄c₂₄a₃₄ b₁₅a₂₅c₃₅c₄₅ A:a₁₆a₆₂

N₆ = c₁₂ c₁₃b₂₃ b₁₄c₂₄a₃₄ b₁₅c₂₅c₃₅b₄₅ A:a₁₆a₆₂ [ 2, 2, 3, 3, 3 ], N₃[ 2, 3, 4, 5, 6 ]
[ 2, 2, 3, 3, 4 ], N₃[ 1, 3, 4, 5, 6 ]
[ 2, 2, 3, 4 ], N₁[ 1, 3, 4, 6 ]
[ 2, 2, 4, 3 ], N₁[ 2, 3, 4, 6 ]
[ 2, 2, 4, 4 ], N₄[ 1, 2, 3, 4, 6 ]

N₇ = b₁₂ c₁₃c₂₃ c₁₄c₂₄b₃₄ a₁₅b₂₅b₃₅b₄₅ A:a₁₆c₆₂ [ 2, 4, 2, 3, 4 ], N₂[ 1, 4, 5, 6 ]
[ 2, 4, 3, 2, 4 ], N₂[ 1, 3, 5, 6 ]
[ 2, 4, 3, 3 ], N₆[ 1, 2, 3, 4, 6 ]

N₈ = b₁₂ b₁₃c₂₃ b₁₄b₂₄a₃₄ a₁₅b₂₅c₃₅b₄₅ A:a₁₆c₆₂ [ 2, 4, 3, 3, 2 ], N₃[ 2, 3, 4, 5, 6 ]
[ 2, 4, 3, 3, 4 ], N₇[ 2, 3, 4, 5, 6 ]
[ 2, 4, 3, 4 ], N₃[ 1, 2, 3, 4, 6 ]

N₉ = b₁₂ c₁₃a₂₃ b₁₄c₂₄c₃₄ b₁₅a₂₅c₃₅b₄₅ A:a₁₆c₆₂ [ 2, 4, 2, 3, 3 ], N₈[ 1, 2, 4, 5, 6 ]
[ 2, 4, 2, 3, 4 ], N₅[ 2, 3, 4, 5, 6 ]
[ 2, 4, 3 ], N₁[ 1, 2, 3, 6 ]
[ 2, 4, 4, 3, 3 ], N₈[ 1, 2, 4, 5, 6 ]

N₁₀ = c₁₂ b₁₃c₂₃ b₁₄c₂₄b₃₄ b₁₅a₂₅a₃₅b₄₅ A:a₁₆b₆₂ [ 2, 3, 3, 3, 3 ], N₈[ 1, 2, 4, 5, 6 ]
[ 2, 3, 3, 3, 4 ], N₁[ 1, 2, 5, 6 ]
[ 2, 3, 3, 4, 3 ], N₃[ 1, 2, 4, 5, 6 ]
[ 2, 3, 3, 4, 4 ], N₁[ 1, 2, 5, 6 ]
[ 2, 3, 4, 3, 3 ], N₈[ 1, 2, 4, 5, 6 ]
[ 2, 3, 4, 3, 4 ], N₁[ 1, 2, 5, 6 ]
[ 2, 3, 4, 4 ], N₆[ 1, 2, 3, 4, 6 ]

N₁₁ = b₁₂ b₁₃c₂₃ b₁₄c₂₄b₃₄ b₁₅a₂₅a₃₅b₄₅ A:a₁₆c₆₂ [ 2, 4, 3, 3, 3 ], N₈[ 1, 2, 4, 5, 6 ]
[ 2, 4, 3, 3, 4 ], N₉[ 2, 3, 4, 5, 6 ]

N₁₂ = b₁₂ c₁₃c₂₃ b₁₄a₂₄a₃₄ a₁₅b₂₅a₃₅c₄₅ A:b₁₆b₆₂ [ 3, 3, 2, 4 ], N₂[ 1, 3, 4, 6 ]
[ 3, 3, 3, 3 ], N₁₁[ 1, 2, 3, 4, 6 ]
[ 3, 3, 3, 4 ], N₂[ 2, 3, 4, 6 ]
[ 3, 3, 4, 3 ], N₁₀[ 1, 2, 3, 4, 6 ]
[ 3, 3, 4, 4 ], N₉[ 1, 2, 3, 4, 6 ]

G(0) = [ [ 4 ], [ 3, 2 ], [ 2, 3, 4 ], [ 2, 2, 4, 4 ], [ 3, 2, 4, 4, 4 ] ]
c₁₂ b₁₃a₂₃ a₁₄b₂₄b₃₄ a₁₅a₂₅c₃₅c₄₅ A:b₁₆a₆₂[ 1, 2, 3, 4, 5 ]12
c₁₂ b₁₃a₂₃ a₁₄b₂₄c₃₄ a₁₅a₂₅c₃₅c₄₅ A:b₁₆a₆₂[ 1, 2, 3, 4 ]1