Variations : Anti-Symmetric Relations on an $n$-Element Set : Graph Theoretic Elucidation

Question

---

Question:

How many antisymmetric relations are there on an $n$-element set?

---

Guess:

I suspect that there are $2^n$ such relations.

---

Discussion:

I'm told that anti-symmetric relations on a set with $n$ elements can be seen as directed subgraphs, perhaps also called a diagraph, of a complete graph with $n$ vertices. Would anyone here be willing to pictorially represent what is being said here using the example where $n=3$?

---

Thoughts:

What I think the first answerer is trying to say is that any pair of points amongst $n$ points can be connected by a directed arrow which represents that $aRb$ holds. A line between any two distinct pairs could then be seen as the instance of when $aRb$ and $bRa$, which can occur in exactly $\frac{n^2-n}{2}$ ways. Thus, for each "line" one has a binary choice, namely $1:=$ true or $0:=$ false. Therefore, there are exactly $2^{\frac{n^2-n}{2}}$ variations.

---

---

Answer 1

---

$2^n\cdot 3^{\frac{n^2-n}{2}}$ possible outcomes exist, right? $\leftarrow$ Please check...

---

A relation is anti-symmetric when the following holds: $$\forall~a,b\in X,~aRb~\wedge~bRa\implies a=b$$ Now, it is interesting to note that antisymmetry on an $n$-element set can be viewed as a directed subgraph of a complete graph; that is, subgraphs of a complete graph where every edge $e$ has an orientation:

$\hspace{4cm}$image http://sophia-blackbook.com/resources/complete_graphs.JPG

The complete graph $K_n$ has $n$ vertices and exactly $\frac{n^2-n}{2}$ edges, so for each edge we have three choices, namely if a directed arrow points from $a$ to $b$, from $b$ to $a$, or no arrow whatsoever, where an arrow between pairs of points in the set connotes that an anti-symmetric relation holds between them. Now, this would then mean that there are precisely $3^{\frac{n^2-n}{2}}$ many variants, as there are $\frac{n^2-n}{2}$ edges for $K_n$; however, we are forgetting that $a$ can be related to itself, so for each such variation there are exactly $2^n$ variations, namely whether $a$ is related to itself or not. Hence, there are $$3^{\frac{n^2-n}{2}}\cdot 2^n$$ total outcomes for such demands.

---

Answer 2

Hint:

• Any antisymmetric relation on $n$-element set can be viewed as a directed subgraph of a complete graph $K_n$.
• Complete graph $K_n$ has $\binom{n}{2}$ edges.
• Each edge can be directed (independently) in 2 ways (and of course, there might not be an edge).
• Finally, there are $2^n$ choices for different $x$es in $R(x,x)$.

I hope this helps ;-)

Edit: pointed out explicitly reflexivity choices.

Edit: As you wished, a diagram for $n = 3$. Please note that the loops $R(x,x)$ were not pictured, and as such there are in fact $2^3 = 8$ times as many cases as in the following figure: