On simple Taylor algebras

On simple Taylor algebras

Libor Barto, joint work with Marcin Kozik

Charles University in Prague

SSAOS 2014, September 7, 2014

2-intersection property

for R⊆A₁× · · · ×A_n, i,j ∈[n]

let R_ij denote the projection ofR onto the coordinates (i,j) i.e. Rij ={(a_i,aj) : (a1, . . . ,aj)∈R}

Definition

An algebra Ahas the2-intersection property if for anyn, R,S ≤Aⁿ

∀i,j R_ij =S_ij ⇒ R∩S 6=∅

Question: Which finite idempotent algebras have the 2-intersection property?

One of the motivations: CSP

2-intersection property

for R⊆A₁× · · · ×A_n, i,j ∈[n]

let R_ij denote the projection ofR onto the coordinates (i,j) i.e. Rij ={(a_i,aj) : (a1, . . . ,aj)∈R}

Definition

An algebraA has the2-intersection property if for anyn, R,S ≤Aⁿ

∀i,j R_ij =S_ij ⇒ R∩S 6=∅

Question: Which finite idempotent algebras have the 2-intersection property?

One of the motivations: CSP

2-intersection property

for R⊆A₁× · · · ×A_n, i,j ∈[n]

let R_ij denote the projection ofR onto the coordinates (i,j) i.e. Rij ={(a_i,aj) : (a1, . . . ,aj)∈R}

Definition

An algebraA has the2-intersection property if for anyn, R,S ≤Aⁿ

∀i,j R_ij =S_ij ⇒ R∩S 6=∅

Question: Which finite idempotent algebras have the 2-intersection property?

One of the motivations: CSP

2-intersection property

for R⊆A₁× · · · ×A_n, i,j ∈[n]

let R_ij denote the projection ofR onto the coordinates (i,j) i.e. Rij ={(a_i,aj) : (a1, . . . ,aj)∈R}

Definition

An algebraA has the2-intersection property if for anyn, R,S ≤Aⁿ

∀i,j R_ij =S_ij ⇒ R∩S 6=∅

Question: Which finite idempotent algebras have the 2-intersection property?

One of the motivations: CSP

Examples

Ahas the 2-intersection property if

I A has an NU (near unanimity) term operation Baker, Pixley

I Recallf is NU iff(x, . . . ,x,y,x, . . . ,x)≈x

I In factR≤Aⁿ is determined by binary projections: R={(a1, . . . ,an) :∀i,j (ai,aj)∈Rij}

I A has a semilattice term operation

I In fact it has the 1-intersection property

I R3(a1, . . . ,an), whereai = minRi

I A is CD(3) Kiss, Valeriote

I A has a 2-semilattice term operation Bulatov

I Example: rock-paper-scissors 3-element algebra

Examples

Ahas the 2-intersection property if

I A has an NU (near unanimity) term operation Baker, Pixley

I Recallf is NU iff(x, . . . ,x,y,x, . . . ,x)≈x

I In factR≤Aⁿ is determined by binary projections: R={(a1, . . . ,an) :∀i,j (ai,aj)∈Rij}

I A has a semilattice term operation

I In fact it has the 1-intersection property

I R3(a1, . . . ,an), whereai = minRi

I A is CD(3) Kiss, Valeriote

I A has a 2-semilattice term operation Bulatov

I Example: rock-paper-scissors 3-element algebra

Examples

Ahas the 2-intersection property if

I A has an NU (near unanimity) term operation Baker, Pixley

I Recallf is NU iff(x, . . . ,x,y,x, . . . ,x)≈x

I In factR≤Aⁿ is determined by binary projections: R={(a1, . . . ,an) :∀i,j (ai,aj)∈Rij}

I A has a semilattice term operation

I In fact it has the 1-intersection property

I R3(a1, . . . ,an), whereai = minRi

I A is CD(3) Kiss, Valeriote

I A has a 2-semilattice term operation Bulatov

I Example: rock-paper-scissors 3-element algebra

Examples

Ahas the 2-intersection property if

I A has an NU (near unanimity) term operation Baker, Pixley

I Recallf is NU iff(x, . . . ,x,y,x, . . . ,x)≈x

I In factR≤Aⁿ is determined by binary projections:

R={(a1, . . . ,an) :∀i,j (ai,aj)∈Rij}

I A has a semilattice term operation

I In fact it has the 1-intersection property

I R3(a1, . . . ,an), whereai = minRi

I A is CD(3) Kiss, Valeriote

I A has a 2-semilattice term operation Bulatov

I Example: rock-paper-scissors 3-element algebra

Examples

Ahas the 2-intersection property if

I A has an NU (near unanimity) term operation Baker, Pixley

I Recallf is NU iff(x, . . . ,x,y,x, . . . ,x)≈x

I In factR≤Aⁿ is determined by binary projections:

R={(a1, . . . ,an) :∀i,j (ai,aj)∈Rij}

I A has a semilattice term operation

I In fact it has the 1-intersection property

I R3(a1, . . . ,an), whereai = minRi I A is CD(3) Kiss, Valeriote

I A has a 2-semilattice term operation Bulatov

I Example: rock-paper-scissors 3-element algebra

Examples

Ahas the 2-intersection property if

I A has an NU (near unanimity) term operation Baker, Pixley

I Recallf is NU iff(x, . . . ,x,y,x, . . . ,x)≈x

I In factR≤Aⁿ is determined by binary projections:

R={(a1, . . . ,an) :∀i,j (ai,aj)∈Rij}

I A has a semilattice term operation

I In fact it has the 1-intersection property

I R3(a1, . . . ,an), whereai = minRi I A is CD(3) Kiss, Valeriote

I A has a 2-semilattice term operation Bulatov

I Example: rock-paper-scissors 3-element algebra

Examples

Ahas the 2-intersection property if

I A has an NU (near unanimity) term operation Baker, Pixley

I Recallf is NU iff(x, . . . ,x,y,x, . . . ,x)≈x

I In factR≤Aⁿ is determined by binary projections:

R={(a1, . . . ,an) :∀i,j (ai,aj)∈Rij}

I A has a semilattice term operation

I In fact it has the 1-intersection property

I R3(a1, . . . ,an), where ai= minRi

I A is CD(3) Kiss, Valeriote

I A has a 2-semilattice term operation Bulatov

I Example: rock-paper-scissors 3-element algebra

Examples

Ahas the 2-intersection property if

I A has an NU (near unanimity) term operation Baker, Pixley

I Recallf is NU iff(x, . . . ,x,y,x, . . . ,x)≈x

I In factR≤Aⁿ is determined by binary projections:

R={(a1, . . . ,an) :∀i,j (ai,aj)∈Rij}

I A has a semilattice term operation

I In fact it has the 1-intersection property

I R3(a1, . . . ,an), where ai= minRi I A is CD(3) Kiss, Valeriote

I A has a 2-semilattice term operation Bulatov

I Example: rock-paper-scissors 3-element algebra

Examples

Ahas the 2-intersection property if

I A has an NU (near unanimity) term operation Baker, Pixley

I Recallf is NU iff(x, . . . ,x,y,x, . . . ,x)≈x

I In factR≤Aⁿ is determined by binary projections:

R={(a1, . . . ,an) :∀i,j (ai,aj)∈Rij}

I A has a semilattice term operation

I In fact it has the 1-intersection property

I R3(a1, . . . ,an), where ai= minRi I A is CD(3) Kiss, Valeriote

I A has a 2-semilattice term operation Bulatov

I Example: rock-paper-scissors 3-element algebra

Examples

Ahas the 2-intersection property if

I A has an NU (near unanimity) term operation Baker, Pixley

I Recallf is NU iff(x, . . . ,x,y,x, . . . ,x)≈x

I In factR≤Aⁿ is determined by binary projections:

R={(a1, . . . ,an) :∀i,j (ai,aj)∈Rij}

I A has a semilattice term operation

I In fact it has the 1-intersection property

I R3(a1, . . . ,an), where ai= minRi I A is CD(3) Kiss, Valeriote

I A has a 2-semilattice term operation Bulatov

I Example: rock-paper-scissors 3-element algebra

Non-examples and characterization

Adoes not have the 2-intersection property if

I A is affine (=essentially a module)

I R^b={(a1, . . . ,a_n) :a₁+· · ·+a_n=b}

I (R^b)_ij =A²

I ifb6=b⁰ thenR_b∩R_b=∅

I B∈HS(A) is a reduct of an affine algebra

Recall: No algebra inHS(A) is a reduct of affine algebra

⇔ HSP(A) omits1 and2

⇔ A is SD(∧) (= HSP(A) is congruence meet semi-distributive)

Theorem (BK, conjectured by Valeriote) Ahas the2-intersection property ⇔A is SD(∧).

Non-examples and characterization

Adoes not have the 2-intersection property if

I A is affine (=essentially a module)

I R^b={(a1, . . . ,a_n) :a₁+· · ·+a_n=b}

I (R^b)_ij =A²

I ifb6=b⁰ thenR_b∩R_b=∅

I B∈HS(A) is a reduct of an affine algebra

Recall: No algebra inHS(A) is a reduct of affine algebra

⇔ HSP(A) omits1 and2

⇔ A is SD(∧) (= HSP(A) is congruence meet semi-distributive)

Theorem (BK, conjectured by Valeriote) Ahas the2-intersection property ⇔A is SD(∧).

Non-examples and characterization

Adoes not have the 2-intersection property if

I A is affine (=essentially a module)

I R^b={(a1, . . . ,an) :a1+· · ·+an=b}

I (R^b)_ij =A²

I ifb6=b⁰ thenR_b∩R_b=∅

I B∈HS(A) is a reduct of an affine algebra

Recall: No algebra inHS(A) is a reduct of affine algebra

⇔ HSP(A) omits1 and2

⇔ A is SD(∧) (= HSP(A) is congruence meet semi-distributive)

Theorem (BK, conjectured by Valeriote) Ahas the2-intersection property ⇔A is SD(∧).

Non-examples and characterization

Adoes not have the 2-intersection property if

I A is affine (=essentially a module)

I R^b={(a1, . . . ,an) :a1+· · ·+an=b}

I (R^b)_ij =A²

I ifb6=b⁰ thenR_b∩R_b=∅

I B∈HS(A) is a reduct of an affine algebra

Recall: No algebra inHS(A) is a reduct of affine algebra

⇔ HSP(A) omits1 and2

⇔ A is SD(∧) (= HSP(A) is congruence meet semi-distributive)

Theorem (BK, conjectured by Valeriote) Ahas the2-intersection property ⇔A is SD(∧).

Non-examples and characterization

Adoes not have the 2-intersection property if

I A is affine (=essentially a module)

I R^b={(a1, . . . ,an) :a1+· · ·+an=b}

I (R^b)_ij =A²

I ifb6=b⁰ thenR_b∩R_b=∅

I B∈HS(A) is a reduct of an affine algebra

Recall: No algebra inHS(A) is a reduct of affine algebra

⇔ HSP(A) omits1 and2

⇔ A is SD(∧) (= HSP(A) is congruence meet semi-distributive)

Theorem (BK, conjectured by Valeriote) Ahas the2-intersection property ⇔A is SD(∧).

Non-examples and characterization

Adoes not have the 2-intersection property if

I A is affine (=essentially a module)

I R^b={(a1, . . . ,an) :a1+· · ·+an=b}

I (R^b)_ij =A²

I ifb6=b⁰ thenR_b∩R_b=∅

I B∈HS(A) is a reduct of an affine algebra

Recall: No algebra inHS(A) is a reduct of affine algebra

⇔ HSP(A) omits1 and2

⇔ A is SD(∧) (= HSP(A) is congruence meet semi-distributive)

Theorem (BK, conjectured by Valeriote) Ahas the2-intersection property ⇔A is SD(∧).

Non-examples and characterization

Adoes not have the 2-intersection property if

I A is affine (=essentially a module)

I R^b={(a1, . . . ,an) :a1+· · ·+an=b}

I (R^b)_ij =A²

I ifb6=b⁰ thenR_b∩R_b=∅

I B∈HS(A) is a reduct of an affine algebra

Recall: No algebra inHS(A) is a reduct of affine algebra

⇔ HSP(A) omits1 and2

⇔ A is SD(∧) (= HSP(A) is congruence meet semi-distributive)

Theorem (BK, conjectured by Valeriote) Ahas the2-intersection property ⇔A is SD(∧).

Non-examples and characterization

Adoes not have the 2-intersection property if

I A is affine (=essentially a module)

I R^b={(a1, . . . ,an) :a1+· · ·+an=b}

I (R^b)_ij =A²

I ifb6=b⁰ thenR_b∩R_b=∅

I B∈HS(A) is a reduct of an affine algebra

Recall: No algebra inHS(A) is a reduct of affine algebra

⇔ HSP(A) omits1 and2

⇔ A is SD(∧) (= HSP(A) is congruence meet semi-distributive)

Theorem (BK, conjectured by Valeriote) Ahas the2-intersection property ⇔A is SD(∧).

End of story?

Possible generalizations to Taylor algebras?

Recall: A is Taylor

⇔ No algebra inHS(A) is a set

⇔ HSP(A) omits1

⇔ . . .

End of story?

Possible generalizations to Taylor algebras?

Recall: A is Taylor

⇔ No algebra inHS(A) is a set

⇔ HSP(A) omits1

⇔ . . .

The old and the new (result)

Theorem (The old) If

I A is SD(∧)

Then Ahas the2-intersection property

Theorem (The new) If

I A1, . . . , An are Taylor, simple, non-abelian

I R,S ≤_sd A1× · · · ×An I ∀i,j Rij =Sij

Then R∩S 6=∅

The old and the new (result)

Theorem (The old) If

I A is SD(∧)

I R,S ≤Aⁿ

I ∀i,j R_ij =S_ij Then R∩S 6=∅

Theorem (The new) If

I A1, . . . , An are Taylor, simple, non-abelian

I R,S ≤_sd A1× · · · ×An I ∀i,j Rij =Sij

Then R∩S 6=∅

The old and the new (result)

Theorem (The old) If

I A1, . . . , An are SD(∧)

I R,S ≤_sd A1× · · · ×An (sd=subdirect product)

I ∀i,j R_ij =S_ij Then R∩S 6=∅

Theorem (The new) If

I A1, . . . , An are Taylor, simple, non-abelian

I R,S ≤_sd A1× · · · ×An I ∀i,j Rij =Sij

Then R∩S 6=∅

The old and the new (result)

Theorem (The old) If

I A1, . . . , An are SD(∧)

I R,S ≤_sd A1× · · · ×An (sd=subdirect product)

I ∀i,j R_ij =S_ij Then R∩S 6=∅

Theorem (The new) If

I A1, . . . , An are Taylor, simple, non-abelian

I R,S ≤_sd A1× · · · ×An I ∀i,j Rij =Sij

Then R∩S 6=∅

The real result: a rectangularity theorem

Recall: B≤Ais absorbingif Ahas a term operationt with t(B,B, . . . ,B,A,B,B, . . . ,B)⊆B

Theorem If

I A₁, . . . , A_n are Taylor, simple, non-abelian

I B1, . . . ,Bn are minimal absorbing subuniverses ofA1, . . . ,An I R ≤_sd A1× · · · ×Anis irredundant

I R∩(B₁× · · · ×B_n)6=∅ Then B₁× · · · ×B_n⊆R.

I One of theA_is can be abelian and non-simple

I Proof of the intersection result using this result: non-trivial, but uses known techniques

I Similar theorem for conservative algebras → Dichotomy for conservative CSPs

The real result: a rectangularity theorem

Recall: B≤Ais absorbingif Ahas a term operationt with t(B,B, . . . ,B,A,B,B, . . . ,B)⊆B

Theorem If

I A₁, . . . , A_n are Taylor, simple, non-abelian

I B1, . . . ,Bnare minimal absorbing subuniverses of A1, . . . , An I R ≤_sd A1× · · · ×An is irredundant

I R∩(B₁× · · · ×B_n)6=∅ Then B₁× · · · ×B_n⊆R.

I One of theA_is can be abelian and non-simple

I Proof of the intersection result using this result: non-trivial, but uses known techniques

I Similar theorem for conservative algebras → Dichotomy for conservative CSPs

The real result: a rectangularity theorem

Recall: B≤Ais absorbingif Ahas a term operationt with t(B,B, . . . ,B,A,B,B, . . . ,B)⊆B

Theorem If

I A₁, . . . , A_n are Taylor, simple, non-abelian

I B1, . . . ,Bnare minimal absorbing subuniverses of A1, . . . , An I R ≤_sd A1× · · · ×An is irredundant

I R∩(B₁× · · · ×B_n)6=∅ Then B₁× · · · ×B_n⊆R.

I One of theA_is can be abelian and non-simple

I Proof of the intersection result using this result: non-trivial, but uses known techniques

I Similar theorem for conservative algebras → Dichotomy for conservative CSPs

The real result: a rectangularity theorem

Recall: B≤Ais absorbingif Ahas a term operationt with t(B,B, . . . ,B,A,B,B, . . . ,B)⊆B

Theorem If

I A₁, . . . , A_n are Taylor, simple, non-abelian

I B1, . . . ,Bnare minimal absorbing subuniverses of A1, . . . , An I R ≤_sd A1× · · · ×An is irredundant

I R∩(B₁× · · · ×B_n)6=∅ Then B₁× · · · ×B_n⊆R.

I One of theA_is can be abelian and non-simple

I Proof of the intersection result using this result: non-trivial, but uses known techniques

I Similar theorem for conservative algebras → Dichotomy for conservative CSPs

The real result: a rectangularity theorem

Recall: B≤Ais absorbingif Ahas a term operationt with t(B,B, . . . ,B,A,B,B, . . . ,B)⊆B

Theorem If

I A₁, . . . , A_n are Taylor, simple, non-abelian

I B1, . . . ,Bnare minimal absorbing subuniverses of A1, . . . , An I R ≤_sd A1× · · · ×An is irredundant

I R∩(B₁× · · · ×B_n)6=∅ Then B₁× · · · ×B_n⊆R.

I One of theA_is can be abelian and non-simple

I Proof of the intersection result using this result: non-trivial, but uses known techniques

I Similar theorem for conservative algebras → Dichotomy for conservative CSPs

A consequence: pointing operation

Definition

A a term operationt ofA points tob ∈A if

∃(a₁, . . . ,a_n)∈Aⁿ such that

t(c1, . . . ,cn) =b whenever ai =ci for all but at most onei

Theorem

Every (idempotent, finite) Taylor, simple, absorption-free algebra has a pointing term operation.

I Let A={1, . . . ,n}

I Let b₁, . . . ,b_k be a list of 2n-tuples of elements ofA which differ from (1,1,2,2, . . . ,n,n) on at most 1-coordinate

I Let R={(t(b₁), . . . ,t(b_k)) :t ∈Clo_2nA}

I R is a subdirect subpower of A(a projection of the free algebra to some coordinates)

I R is irredundant

I Rectangularity theorem ⇒ R =A^k.

A consequence: pointing operation

Definition

A a term operationt ofA points tob ∈A if

∃(a₁, . . . ,a_n)∈Aⁿ such that

t(c1, . . . ,cn) =b whenever ai =ci for all but at most onei Known: A is SD(∧)⇔ every subalgebra of Ahas a pointing term operation.

Theorem

Every (idempotent, finite) Taylor, simple, absorption-free algebra has a pointing term operation.

I Let A={1, . . . ,n}

I Let b₁, . . . ,b_k be a list of 2n-tuples of elements ofA which differ from (1,1,2,2, . . . ,n,n) on at most 1-coordinate

I Let R={(t(b₁), . . . ,t(b_k)) :t ∈Clo2nA}

I R is a subdirect subpower of A(a projection of the free algebra to some coordinates)

I R is irredundant

I Rectangularity theorem ⇒ R =A^k.

A consequence: pointing operation

Definition

A a term operationt ofA points tob ∈A if

∃(a₁, . . . ,a_n)∈Aⁿ such that

t(c1, . . . ,cn) =b whenever ai =ci for all but at most onei Theorem

Every (idempotent, finite) Taylor, simple, absorption-free algebra has a pointing term operation.

I Let A={1, . . . ,n}

I Let b₁, . . . ,b_k be a list of 2n-tuples of elements ofA which differ from (1,1,2,2, . . . ,n,n) on at most 1-coordinate

I Let R={(t(b₁), . . . ,t(b_k)) :t ∈Clo_2nA}

I R is a subdirect subpower of A(a projection of the free algebra to some coordinates)

I R is irredundant

I Rectangularity theorem ⇒ R =A^k.

A consequence: pointing operation

Definition

A a term operationt ofA points tob ∈A if

∃(a₁, . . . ,a_n)∈Aⁿ such that

t(c1, . . . ,cn) =b whenever ai =ci for all but at most onei Theorem

Every (idempotent, finite) Taylor, simple, absorption-free algebra has a pointing term operation.

I Let A={1, . . . ,n}

I Let b₁, . . . ,b_k be a list of 2n-tuples of elements ofA which differ from (1,1,2,2, . . . ,n,n) on at most 1-coordinate

I Let R={(t(b₁), . . . ,t(b_k)) :t ∈Clo_2nA}

I R is a subdirect subpower of A(a projection of the free algebra to some coordinates)

I R is irredundant

I Rectangularity theorem ⇒ R =A^k.

A consequence: pointing operation

Definition

A a term operationt ofA points tob ∈A if

∃(a₁, . . . ,a_n)∈Aⁿ such that

t(c1, . . . ,cn) =b whenever ai =ci for all but at most onei Theorem

Every (idempotent, finite) Taylor, simple, absorption-free algebra has a pointing term operation.

I Let A={1, . . . ,n}

I Let b₁, . . . ,b_k be a list of 2n-tuples of elements ofA which differ from (1,1,2,2, . . . ,n,n) on at most 1-coordinate

I Let R={(t(b₁), . . . ,t(b_k)) :t ∈Clo_2nA}

I R is a subdirect subpower of A(a projection of the free algebra to some coordinates)

I R is irredundant

I Rectangularity theorem ⇒ R =A^k.

A consequence: pointing operation

Definition

A a term operationt ofA points tob ∈A if

∃(a₁, . . . ,a_n)∈Aⁿ such that

t(c1, . . . ,cn) =b whenever ai =ci for all but at most onei Theorem

Every (idempotent, finite) Taylor, simple, absorption-free algebra has a pointing term operation.

I Let A={1, . . . ,n}

I Let b₁, . . . ,b_k be a list of 2n-tuples of elements ofA which differ from (1,1,2,2, . . . ,n,n) on at most 1-coordinate

I Let R={(t(b₁), . . . ,t(b_k)) :t ∈Clo_2nA}

I R is a subdirect subpower of A(a projection of the free algebra to some coordinates)

I R is irredundant

I Rectangularity theorem ⇒ R =A^k.

A consequence: pointing operation

Definition

A a term operationt ofA points tob ∈A if

∃(a₁, . . . ,a_n)∈Aⁿ such that

t(c1, . . . ,cn) =b whenever ai =ci for all but at most onei Theorem

Every (idempotent, finite) Taylor, simple, absorption-free algebra has a pointing term operation.

I Let A={1, . . . ,n}

I Let b₁, . . . ,b_k be a list of 2n-tuples of elements ofA which differ from (1,1,2,2, . . . ,n,n) on at most 1-coordinate

I Let R={(t(b₁), . . . ,t(b_k)) :t ∈Clo_2nA}

I R is a subdirect subpower of A(a projection of the free algebra to some coordinates)

I R is irredundant

I Rectangularity theorem ⇒ R =A^k.

A consequence: pointing operation

Definition

A a term operationt ofA points tob ∈A if

∃(a₁, . . . ,a_n)∈Aⁿ such that

t(c1, . . . ,cn) =b whenever ai =ci for all but at most onei Theorem

Every (idempotent, finite) Taylor, simple, absorption-free algebra has a pointing term operation.

I Let A={1, . . . ,n}

I Let b₁, . . . ,b_k be a list of 2n-tuples of elements ofA which differ from (1,1,2,2, . . . ,n,n) on at most 1-coordinate

I Let R={(t(b₁), . . . ,t(b_k)) :t ∈Clo_2nA}

I R is a subdirect subpower of A(a projection of the free algebra to some coordinates)

I R is irredundant

I Rectangularity theorem ⇒ R =A^k.

A consequence: pointing operation

Definition

A a term operationt ofA points tob ∈A if

∃(a₁, . . . ,a_n)∈Aⁿ such that

t(c1, . . . ,cn) =b whenever ai =ci for all but at most onei Theorem

Every (idempotent, finite) Taylor, simple, absorption-free algebra has a pointing term operation.

I Let A={1, . . . ,n}

I Let b₁, . . . ,b_k be a list of 2n-tuples of elements ofA which differ from (1,1,2,2, . . . ,n,n) on at most 1-coordinate

I Let R={(t(b₁), . . . ,t(b_k)) :t ∈Clo_2nA}

I R is a subdirect subpower of A(a projection of the free algebra to some coordinates)

I R is irredundant

I Rectangularity theorem ⇒ R=A^k.

A piece of proof of the rectangularity theorem

I Assume R≤_sd A1×A2×A3 is irredundant and each A_i is simple, absorption-free, non-abelian.

I R irredundant,A1,A2 simple⇒ R12 linked

I absorption theorem⇒ R12=A1×A2 (similarly forR23,R13)

I View R as ¯R≤_sd R₁₂×A₃ = (A₁×A₂)×A₃

I for b ∈A₃ denoteS_b={(a₁,a₂) : (a₁,a₂,b)∈R}

I R23,R13 full ⇒S_b ≤_sd A1×A2 (for eachb)

I for eachb,Sb either linked or graph of a bijectionA1 →A2

(from simplicity)

I if Sb is a graph of a bijection for everyb

I R¯ is a graph of surjective mappingR₁₂→A₃(from simplicity)

I ⇒ {Sb:b∈A₃}is a partition ofA₁×A₂that defines a congruenceαon A₁×A₂

I Usingαwe can find a congruence β onA²₁ whose one block is the diagonal

I ⇒A1(and A2) is abelian.

A piece of proof of the rectangularity theorem

I Assume R≤_sd A1×A2×A3 is irredundant and each A_i is simple, absorption-free, non-abelian.

I R irredundant,A1,A2 simple⇒ R12 linked

I absorption theorem⇒ R12=A1×A2 (similarly forR23,R13)

I View R as ¯R≤_sd R₁₂×A₃ = (A₁×A₂)×A₃

I for b ∈A₃ denoteS_b={(a₁,a₂) : (a₁,a₂,b)∈R}

I R23,R13 full ⇒S_b ≤_sd A1×A2 (for eachb)

I for eachb,Sb either linked or graph of a bijectionA1 →A2

(from simplicity)

I if Sb is a graph of a bijection for everyb

I R¯ is a graph of surjective mappingR₁₂→A₃(from simplicity)

I ⇒ {Sb:b∈A₃}is a partition ofA₁×A₂that defines a congruenceαon A₁×A₂

I Usingαwe can find a congruence β onA²₁ whose one block is the diagonal

I ⇒A1(and A2) is abelian.

A piece of proof of the rectangularity theorem

I Assume R≤_sd A1×A2×A3 is irredundant and each A_i is simple, absorption-free, non-abelian.

I R irredundant,A1,A2 simple⇒ R12 linked

I absorption theorem⇒ R12=A1×A2 (similarly forR23,R13)

I View R as ¯R≤_sd R₁₂×A₃ = (A₁×A₂)×A₃

I for b ∈A₃ denoteS_b={(a₁,a₂) : (a₁,a₂,b)∈R}

I R23,R13 full ⇒S_b ≤_sd A1×A2 (for eachb)

I for eachb,Sb either linked or graph of a bijectionA1 →A2

(from simplicity)

I if Sb is a graph of a bijection for everyb

I R¯ is a graph of surjective mappingR₁₂→A₃(from simplicity)

I ⇒ {Sb:b∈A₃}is a partition ofA₁×A₂that defines a congruenceαon A₁×A₂

I Usingαwe can find a congruence β onA²₁ whose one block is the diagonal

I ⇒A1(and A2) is abelian.

A piece of proof of the rectangularity theorem

I Assume R≤_sd A1×A2×A3 is irredundant and each A_i is simple, absorption-free, non-abelian.

I R irredundant,A1,A2 simple⇒ R12 linked

I absorption theorem⇒ R12=A1×A2 (similarly forR23,R13)

I View R as ¯R≤_sd R₁₂×A₃ = (A₁×A₂)×A₃

I for b ∈A₃ denoteS_b={(a₁,a₂) : (a₁,a₂,b)∈R}

I R23,R13 full ⇒S_b ≤_sd A1×A2 (for eachb)

I for eachb,Sb either linked or graph of a bijectionA1 →A2

(from simplicity)

I if Sb is a graph of a bijection for everyb

I R¯ is a graph of surjective mappingR₁₂→A₃(from simplicity)

I ⇒ {Sb:b∈A₃}is a partition ofA₁×A₂that defines a congruenceαon A₁×A₂

I Usingαwe can find a congruence β onA²₁ whose one block is the diagonal

I ⇒A1(and A2) is abelian.

A piece of proof of the rectangularity theorem

I Assume R≤_sd A1×A2×A3 is irredundant and each A_i is simple, absorption-free, non-abelian.

I R irredundant,A1,A2 simple⇒ R12 linked

I absorption theorem⇒ R12=A1×A2 (similarly forR23,R13)

I View R as ¯R≤_sd R₁₂×A₃ = (A₁×A₂)×A₃

I for b ∈A₃ denoteS_b={(a₁,a₂) : (a₁,a₂,b)∈R}

I R23,R13 full ⇒S_b ≤_sd A1×A2 (for eachb)

I for eachb,Sb either linked or graph of a bijectionA1 →A2

(from simplicity)

I if Sb is a graph of a bijection for everyb

I R¯ is a graph of surjective mappingR₁₂→A₃(from simplicity)

I ⇒ {Sb:b∈A₃}is a partition ofA₁×A₂that defines a congruenceαon A₁×A₂

I Usingαwe can find a congruence β onA²₁ whose one block is the diagonal

I ⇒A1(and A2) is abelian.

A piece of proof of the rectangularity theorem

I Assume R≤_sd A1×A2×A3 is irredundant and each A_i is simple, absorption-free, non-abelian.

I R irredundant,A1,A2 simple⇒ R12 linked

I absorption theorem⇒ R12=A1×A2 (similarly forR23,R13)

I View R as ¯R≤_sd R₁₂×A₃ = (A₁×A₂)×A₃

I for b ∈A₃ denoteS_b={(a₁,a₂) : (a₁,a₂,b)∈R}

I R23,R13 full⇒ S_b ≤_sd A1×A2 (for eachb)

I for eachb,Sb either linked or graph of a bijectionA1 →A2

(from simplicity)

I if Sb is a graph of a bijection for everyb

I R¯ is a graph of surjective mappingR₁₂→A₃(from simplicity)

I ⇒ {Sb:b∈A₃}is a partition ofA₁×A₂that defines a congruenceαon A₁×A₂

I Usingαwe can find a congruence β onA²₁ whose one block is the diagonal

I ⇒A1(and A2) is abelian.

A piece of proof of the rectangularity theorem

I Assume R≤_sd A1×A2×A3 is irredundant and each A_i is simple, absorption-free, non-abelian.

I R irredundant,A1,A2 simple⇒ R12 linked

I absorption theorem⇒ R12=A1×A2 (similarly forR23,R13)

I View R as ¯R≤_sd R₁₂×A₃ = (A₁×A₂)×A₃

I for b ∈A₃ denoteS_b={(a₁,a₂) : (a₁,a₂,b)∈R}

I R23,R13 full⇒ S_b ≤_sd A1×A2 (for eachb)

I for eachb,Sb either linked or graph of a bijectionA1 →A2

(from simplicity)

I if Sb is a graph of a bijection for everyb

I R¯ is a graph of surjective mappingR₁₂→A₃(from simplicity)

I ⇒ {Sb:b∈A₃}is a partition ofA₁×A₂that defines a congruenceαon A₁×A₂

I Usingαwe can find a congruence β onA²₁ whose one block is the diagonal

I ⇒A1(and A2) is abelian.

A piece of proof of the rectangularity theorem

I Assume R≤_sd A1×A2×A3 is irredundant and each A_i is simple, absorption-free, non-abelian.

I R irredundant,A1,A2 simple⇒ R12 linked

I absorption theorem⇒ R12=A1×A2 (similarly forR23,R13)

I View R as ¯R≤_sd R₁₂×A₃ = (A₁×A₂)×A₃

I for b ∈A₃ denoteS_b={(a₁,a₂) : (a₁,a₂,b)∈R}

I R23,R13 full⇒ S_b ≤_sd A1×A2 (for eachb)

I for eachb,Sb either linked or graph of a bijectionA1 →A2

(from simplicity)

I if Sb is linked for someb

I S_b=A₁×A₂(from absorption theorem)

I R¯ is linked

I Fact: R₁₂=A₁×A₂ is absorption-free

I absorption theorem⇒R¯=R₁₂×A₃= (A₁×A₂)×A₃

I if Sb is a graph of a bijection for everyb

I R¯ is a graph of surjective mappingR12→A3(from simplicity)

I ⇒ {Sb:b∈A3}is a partition ofA1×A2that defines a congruenceαon A₁×A₂

I Usingαwe can find a congruence β onA²₁ whose one block is the diagonal

I ⇒A₁(and A₂) is abelian.

A piece of proof of the rectangularity theorem

I Assume R≤_sd A1×A2×A3 is irredundant and each A_i is simple, absorption-free, non-abelian.

I R irredundant,A1,A2 simple⇒ R12 linked

I absorption theorem⇒ R12=A1×A2 (similarly forR23,R13)

I View R as ¯R≤_sd R₁₂×A₃ = (A₁×A₂)×A₃

I for b ∈A₃ denoteS_b={(a₁,a₂) : (a₁,a₂,b)∈R}

I R23,R13 full⇒ S_b ≤_sd A1×A2 (for eachb)

I for eachb,Sb either linked or graph of a bijectionA1 →A2

(from simplicity)

I if Sb is linked for someb

I Sb=A1×A2(from absorption theorem)

I R¯ is linked

I Fact: R₁₂=A₁×A₂ is absorption-free

I absorption theorem⇒R¯=R₁₂×A₃= (A₁×A₂)×A₃

I if Sb is a graph of a bijection for everyb

I R¯ is a graph of surjective mappingR12→A3(from simplicity)

I ⇒ {Sb:b∈A3}is a partition ofA1×A2that defines a congruenceαon A₁×A₂

I Usingαwe can find a congruence β onA²₁ whose one block is the diagonal

I ⇒A₁(and A₂) is abelian.