A "$n$-order matrix" $T\in M_n(\mathbb F_2)$ is a matrix such that there exists a partial ordered relation $\leq_T\subset [1,n]^2$ such that :

$T_{ij}=1\Leftrightarrow i\leq_T j$

(where $T_{ij}$ is the $i,j$ coefficient of $T$)

A "$n$-graph matrix" $S\in M_n(\mathbb F_2)$ is a symmetric matrix such that $S_{ii}=0$ for all $i\in [1,n]$

(where $G^t$ is the transposed matrix of $G$)

Is it true that for any "$n$-graph matrix" $S$ there exists a "$n$-order matrix" $T$ s.t. $S=T+T^t$ ?

  • $\begingroup$ Presumably you want also to require that your $S$ have $0$ entries along the diagonal. $\endgroup$ – LSpice Jul 21 '18 at 20:14
  • $\begingroup$ Of course, thank you LSpice! (I'm editing) $\endgroup$ – jcdornano Jul 21 '18 at 20:21

Even with $0$'s on the diagonal it's still false. Consider the matrix $S = \left[\begin{matrix}0&1&0&0&1\cr 1&0&1&0&0\cr 0&1&0&1&0\cr 0&0&1&0&1\cr 1&0&0&1&0\end{matrix}\right]$. Suppose $S = T + T^t$ for some order matrix $T$. Then this order must have either $1 < 2$ or $2 < 1$ since $s_{12} = 1$. Wlog say $1 < 2$. Similarly we must have $2 < 3$ or $3 < 2$.

Suppose $2 < 3$. Then $1 <2 < 3$, and hence $t_{13} = 1$, but $s_{13} = 0$ so this implies that $t_{31} = 1$, i.e., $3 < 1$. If a "partial order" is antisymmetric this is impossible, but even if you allow $1 < 3 < 1$ we then get $2 < 3 < 1$, so that $t_{12} = t_{21} = 1$ and this contradicts $s_{12} = 1$. So $2 < 3$ is impossible.

We have shown that $1 < 2$ implies $3 < 2$, and similarly $2 > 3$ implies $4 > 3$, and then $3 < 4$ implies $5 < 4$.

But what is the relation between $1$ and $5$? Since $s_{15} = 1$ we need either $1 < 5$ or $5 < 1$. Wlog say $1 < 5$. Then $1 < 5 < 4$ so $t_{14} = 1$, but since $s_{14}= 0$ this forces $t_{41} = 1$, i.e., $4 < 1$. Again this contradicts antisymmetry, but even if you drop antisymmetry it forces $5 < 4 < 1$ so that $t_{51} = t_{15} = 1$ and this contradicts $s_{15} = 1$. So $S = T + T^t$ is impossible.

  • $\begingroup$ Thank you for this very nice counterexample with very elegant smart proof. You also shown that it is still a counterexample for "pre-order" not only "partial order"!! thank you! $\endgroup$ – jcdornano Jul 21 '18 at 21:14
  • 1
    $\begingroup$ I modified the hypothesies and ask a new question here mathoverflow.net/questions/306560/… $\endgroup$ – jcdornano Jul 21 '18 at 22:28
  • $\begingroup$ The essence of this example is that $S$ is the matrix of $C_5$ (the $5$-cycle), and $C_5$ is not a comparability graph (not even perfect). $\endgroup$ – Jan Kyncl Jul 21 '18 at 23:07

Here is a counting argument showing that almost all $n$-graph matrices are counterexamples.

There are $2^{(1/2+o(1))\cdot n^2}$ graphs on $n$ vertices, but only $2^{(1/4+o(1))\cdot n^2}$ partial orders on $n$ elements; see these papers by Kleitman and Rothschild:

Asymptotic enumeration of partial orders on a finite set

The number of finite topologies

The main reason for the separation is that the Hasse diagram is triangle-free, and there are only $2^{(1/4+o(1))\cdot n^2}$ triangle-free graphs on $n$ vertices (see e.g. https://arxiv.org/abs/1409.8123 for references).

  • $\begingroup$ I wrote the first attempt to weakening hypothesis after reading your very instructive and nice answer! This answer suggests that we might try to get $S=T+T'$ with $S$ equal to a graph matrix "up to a permutations" (i.e of permutation of rows and a permutation of columns) , and $T$ and $T'$ equal to an order matrix "up to permutations" ...(but maybe it would'nt be a nice or interesting statement to make after all...) $\endgroup$ – jcdornano Jul 21 '18 at 23:37
  • $\begingroup$ Anyway I think it's wrong too, because $T+T'$ is almost never symmetric up to right and left permutations matrix product, fora random couple $(T,T')$... $\endgroup$ – jcdornano Jul 22 '18 at 0:04
  • 1
    $\begingroup$ This is a good answer. $\endgroup$ – Nik Weaver Jul 22 '18 at 0:33

As pointed out by others, the answer is no. In fact, the graphs that can be obtained this way are exactly the Comparability Graphs. This graph class is very well studied and well understood. It is also a subclass of perfect graphs, which are known to not allowing any induced off cycle with at least 5 vertices (such as the one in Nik Weaver's answer). Hence, any graph that consists of an odd cycle (or contains one as induced subgraph) cannot be obtained this way.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.