What is Zykov Algebra

Zykov Algebra on the Go

This is a simplified introduction to the work A Zykov Algebra Approach to Clique Propagation, co-authored with Gete Umbrey, Botem Moyong, Bhaba Kumar Sarma, and me.

---

What is Zykov Algebra?
Zykov Algebra is a symbolic language to describe networks using algebraic expressions. It is based on two operations:

• The overlay operator, written as \(+\),  to merge  graphs.
• The link operator, written as \(*\), to connect every vertex in one part with every vertex in another.

Each number like 1,2,3 represents a vertex.
So:

• 1 + 2 + 3 means three disconnected vertices.
• 1 * 2 * 3 means all three are connected — a triangle.

If you define a vertex a \( i=(\{v_i\},\emptyset)\), then

• \( G_1 + G_2 = (V_1 \cup V_2, E_1 \cup E_2) \)
• \( G_1∗G_2=(V_1 \cup V_2,E_1 \cup E_2 \cup (V1 \otimes V2)), \) where

\( V_1 \otimes V_2:=\{\{u,v\} ∣ u \in V_1,v \in V_2 \} \).

---

Why does this matter?
Instead of listing connections manually (which becomes unwieldy), we write:

G = 1 * 2 * 3 * 4 + 4 * 5 * 6

This defines a large 4-node clique connected to a triangle in a single node.

---