Let $A=\{1,2,3,\cdots, n\}$. Let $T$ denote a transitive relation on $A$ such that $T\neq A\times A$.
What is the possibility for the maximum size for $T$?
I considered the case $n=3$. I found that the largest such $T$ is given by $T=\{(1,1),(2,2),(3,3),(1,2),(1,3),(3,2)\}$.
Best Answer
$\{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,3)\}$ is a bigger transitive relation when $n=3.$
Given $(x,x)\notin T,$ $T\cup\{(x,x)\}$ is a bigger transitive order. So any maximal relation contains $(x,x)$ for all $x\in A.$ This means that a maximal $T$ must be a preorder. (Indeed, the rest of this came from knowledge of the nature of preorders.)
If we define $\sim$ on $A$ as: $x\sim y$ if both $(x,y)$ and $(y,x)$ are in $T,$ then by (1) if $T$ is maximal, then $\sim$ is an equivalence relation on $A.$ Since $T$ is not the complete relation, $A/\sim$ has two or more elements.
If we define $\leq$ on $A/\sim$ as $[x]\leq [y]$ iff $(x,y)\in T.$ Then $\leq$ is a partial order on $A.$
If $\leq$ is not a total order on $A/\sim,$ then we can define a compatible total order $\preccurlyeq$ on $A/\sim.$ Then define a bigger $T’$ where $(x,y)\in T’$ when $[x]\preccurlyeq [y].$
So any maximum $T$ comes from a total order on $A/\sim,$ for some equivalence relation on $A.$
So if the equivalence classes are of sizes $a_1,\dots,a_k$ where the classes are in the total order, then $T$ will have: $$\sum_{i=1}^{k} \sum_{j=i}^k a_ia_k=\frac{1}2n^2+\frac12\sum_{i=1}^ka_i^2$$ elements.
So you want to maximize $\sum_{i} a_i^2,$ with $k>1.$ (Where $k=1, a_1=n$ is the total relation.)
This is maximized when $k=2,$ since we can always merge two equivalence classes when $k>2$ and get a bigger relation. If $k=2,a_1=i,a_2=n-i,$ then $i^2+(n-i )^2$ for $i0<i<n$ is maximized when $i=1$ and $i=n-1.$
So the maximal $T$ has $n^2-n+1$ elements.
Once you have (2), you actually get that $T$ can’t have more than $n^2-n+1$ elements.
This is because for each $x\sim 1$ and $y\not\sim 1,$ either $(x,y)\notin T$ or $(y,x)\notin T.$ So there are at least $i(n-i)$ elements of $A\times A$ not in $T,$ where $1\leq i\leq n-1$ is the number of elements in $x\sim 1.$
But $i(n-i)$ is at least $n-1.$
We can get an example with with $n^2-n+1$ elements with $$ \begin{align} T&=\{(x,y)\in A\times A\mid x<n\text{ or } x=y=n\}\\&=A\times A\setminus\{(n,i)\mid i<n\} \end{align} $$
There are in fact exactly $2n$ $T$ with $|T|=n^2-n+1,$ when $n>2.$ There are $n$ choices for the singleton equivalence class, and two choices for whether the singleton is the minimum or maximum element of the total ordering on $A/\sim.$
Given any transitive $T_0,$ we can find the maximal transitive $T\neq A\times A$ such that $T_0\subseteq T$ by doing steps (1) and (2) and (3) to $T_0.$, to get a partial order on $A/\sim.$ Then find the size $i$ of the smallest $[x]$ which is minimal or maximal in the partial order. Then the maximal $T$ containing $T_0$ is of size $n(n-i)+i^2$ n^2-in+i^2.$