Max value of Anti-symmetric Relation

Question

Here is the question: Let A be a set with |A| = n and R be a relation on A that is anti-symmetric. What is the max value for |R|? How many antisymmetric relations can have this size?

So I'm not sure how to answer this. My first inclination is to just use the formula that tells you how to many antisymmetric relations there can be : $(2^n)(3^{n^2-n}/2)$. But then I figured that R can have more than just antisymmetric relations. My next thought was to count up equivalence relations and subtract the number of symmetric relations. I'm not sure if this will work, but this just seems more complicated than it should.

What should I be doing?

No clue on how to do the second part.

Note: Not homework. This is just me trying my hand at some practice problems for a test.

Edit: I'm saying the max value of |R| is .5(n^2 +n). I got this by adding n + (n^2-n)/2. I arrived at this by considering an upper triangular matrix. If this is correct, I'm still not sure how to the second part.

Answer 1

$\newcommand{\bb}{\color{blue}{\bullet}}\newcommand{\br}{\color{brown}{\bullet}}\newcommand{\bu}{\bullet}$Look instead at where the formula for the number of antisymmetric relations on $A$ comes from. Here’s a diagram of $A\times A$ for a set $A$ of $9$ elements. A relation on $A$ is a subset of this diagram. If that relation is antisymmetric, can it include all of the brown dots? If it includes a blue dot, can it include the brown dot symmetrically opposite it on the other side of the brown diagonal or vice versa (like the orange/cyan pair)?

$$\begin{array}{c|cc} &a_1&a_2&a_3&a_4&a_5&a_6&a_7&a_8&a_9\\ \hline a_1&\br&\bb&\bb&\bb&\bb&\bb&\bb&\bb&\bb\\ a_2&\bu&\br&\bb&\bb&\bb&\bb&\color{orange}\bullet&\bb&\bb\\ a_3&\bu&\bu&\br&\bb&\bb&\bb&\bb&\bb&\bb\\ a_4&\bu&\bu&\bu&\br&\bb&\bb&\bb&\bb&\bb\\ a_5&\bu&\bu&\bu&\bu&\br&\bb&\bb&\bb&\bb\\ a_6&\bu&\bu&\bu&\bu&\bu&\br&\bb&\bb&\bb\\ a_7&\bu&\color{cyan}\bullet&\bu&\bu&\bu&\bu&\br&\bb&\bb\\ a_8&\bu&\bu&\bu&\bu&\bu&\bu&\bu&\br&\bb\\ a_9&\bu&\bu&\bu&\bu&\bu&\bu&\bu&\bu&\br \end{array}$$

Added: Every one of these largest antisymmetric relations on $A$ must include all of the diagonal pairs. It must include exactly one of each symmetric pair, like $\langle a_2,a_7\rangle$ and $\langle a_7,a_2\rangle$ in the diagram. In the comments you found that there are $\frac12n(n-1)$ symmetric pairs. From each of those pairs you make a $2$-way choice; how many ways are there to make $\frac12n(n-1)$ $2$-way choices?

Answer 2

The first part of the problem is not asking how many possible antisymmetric relations there are, but how many pairs there can be in a single antisymmetric relation. (Remember, a relation is a set of pairs).

For example there cannot be $n^2$ pairs, because that would mean everything is related to everything else, and that is not an antisymmetric relation (unless $n\le 1$, which is kind of an uninteresting case). So there is some smaller upper bound for how large an antisymmetric relation can be.

Then it asks how many antisymmetric relations of that particular size there are. Do you know how to derive the formula you're using (which I think should be $2^n3^{(n^2-n)/2}$ rather than $2^n3^{n^2-n}/2$. It should be possible to adapt that derivation into a solution for the second part, once you have the answer to the first.