2
$\begingroup$

$\DeclareMathOperator{\rk}{rk}$

For an integer $n\ge 1$, let $\mathcal R_n$ denote the set of all reflexive binary relations on $[n]$. I define the rank of a relation $R\in\mathcal R_n$ to be the smallest possible rank of a square, real matrix of order $n$, supported on $R$ and having its diagonal elements non-zero; that is, the smallest possible rank of a matrix $(a_{ij})_{1\le i,j\le n}$ with $a_{ii}\ne 0$ and $a_{ij}=0$ whenever $(i,j)\notin R$.

Thus, for example,

  • The complete relation $[n]^2$ (and only it) has rank $1$.
  • Any acyclic relation, including the identity relation, has rank $n$ (one can always extend an acyclic relation to a linear order relation, corresponding to triangular matrices after an appropriate permutation of the rows / columns). Moreover, it is not difficult to see that acyclic relations are the only relations of rank $n$.
  • The rank of an equivalence relation is equal to the number of induced equivalence classes.

Denoting the rank of a relation $R\in\mathcal R_n$ by $\rk(R)$,

Is it possible to classify the relations $R\in\mathcal R_n$ which are critical in the sense that $\rk(R')>\rk(R)$ for any proper (reflexive) sub-relation $R'\subset R$?

It is easily seen that every equivalence relation is critical, as well as every relation which is a union of the identity relation and a single cycle $\{(i_1,i_2),\dotsc,(i_{k-1},i_k),(i_k,i_1)\}$ with $i_1,\dotsc i_k\in[n]$ pairwise distinct.

One can construct critical relations observing that if $R=R_1\oplus R_2$, then $\rk(R)=\rk(R_1)+\rk(R_2)$; therefore, $R$ is critical if and only if so are both $R_1$ and $R_2$. This allows one to distinguish between primitive and induced critical relations.

For $n=2$, there is a unique primitive critical relation; namely, the complete relation $[2]^2$. For $n=3$, up to permutations, there are just two primitive critical relations: the complete relation $[3]^2$ and the relation visualized as $$ \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{bmatrix}. $$

As a last remark: I am aware of the notion of the minimum rank of a graph, but in my context the things look rather different.

Improve this question
$\endgroup$
5
  • $\begingroup$ I am curious as to how this problem arose. $\endgroup$
    – Nik Weaver
    Commented Jun 26, 2017 at 11:54
  • $\begingroup$ @NikWeaver: this is, basically, an attempt to solve this problem:mathoverflow.net/questions/266531/…. You can replace the elements $a_{ij}$ by zeroes as long as this can be done without enlarging the rank. Thus, one needs to understands what happens when the rank must grow. $\endgroup$
    – Seva
    Commented Jun 26, 2017 at 12:28
  • 1
    $\begingroup$ It seems that any proper sub-relation of a critical relation must also be critical. And equivalence relations are critical as you said. So "critical" relations form a "independence system" at the least. $\endgroup$
    – Pushpendre
    Commented Jun 27, 2017 at 8:26
  • $\begingroup$ Unfortunately, "critical" relations do not form a matroid as shown by the counter-example, Let $S=\{(i,i) \mid 1 \le i \le 5\}$, $A = S \cup \{(1,2), (2,3), (3,1)\}$, and $B = S \cup \{(4,5), (5,4)\}$. There does not exist any element $x \in \{(1,2), (2,3), (3,1)\}$ such that $\{x\} \cup B$ will be critical. $\endgroup$
    – Pushpendre
    Commented Jun 27, 2017 at 8:41
  • $\begingroup$ @Pushpendre: the complete relation $\{(1,1),(1,2),(2,1),(2,2)\}$ in $\mathcal R_2$ is critical, but its proper subrelation $\{(1,1),(1,2),(2,2)\}$ is not. $\endgroup$
    – Seva
    Commented Jun 27, 2017 at 9:45

0

Reset to default

You must log in to answer this question.