Skip to main content
added 1224 characters in body
Source Link
Klaus Draeger
  • 2.5k
  • 1
  • 23
  • 19

For the intermediate question (a core with three top-bottom runs), how about this?

Some notation: I will be describing runs by words in $\{l,r\}^*$, with e.g. $llrl$ corresponding to a subgraph $\cdot\leftarrow\cdot\leftarrow\cdot\to\cdot\leftarrow\cdot$. The level increases on $r$ arcs and decreases on $l$ arcs, and I assume that its minimum is $0$. Some straightforward constraints are:

  • There cannot be a run consisting only of $l$s or only of $r$s, because otherwise there is an obvious homomorphism from $D$ to this run (mapping each node of $D$ to the one with the same level). This also implies that the maximum level must be at least $3$.
  • If the maximum level were $3$, then all top-bottom (resp bottom-top) runs would be of the form $llr(lr)^ill$ (resp. $rrl(rl)^irr)$; again it is not very hard to find a homomorphism from $D$ to the run which minimizes $i$.

However, for maximum level $4$ there is a solution, of length $36$: consider $D$ given by $(rrrlrrlllrll)^3$. Unless I missed something, thisThis has the required top-bottom runs and is a core, and by (see below). By the above constraints, it is necessarily minimal, since each run only has a single "backwards" edge.

To convince ourselves that this is a core, let's first name the vertices ($v_1,\ldots,v_{36}$). The bottom (i.e. level $0$) vertices are $v_1,v_{13},v_{25}$. Any homomorphism $\varphi$ from $D$ to a subgraph must preserve levels, and in particular $\varphi(v_1)\in\{v_1,v_{13},v_{25}\}$; modulo the obvious automorphism $v_i\mapsto v_{i+12}$, it is enough to consider the case $\varphi(v_1)=v_1$. Consider the neighbourhood of $v_1$ in $D$ (annotated with levels):

$v_{34}(1)\to v_{35}(2)\leftarrow v_{36}(1)\leftarrow v_1(0)\to v_2(1)\to v_3(2)\to v_4(3)\leftarrow v_5(2)\to v_6(3)\to v_7(4)$

Starting with $\varphi(v_1)=v_1$, we have $\varphi(v_2)\in\{v_{36},v_2\}$. But if $\varphi(v_2)=v_{36}$, then $\varphi(v_3)=v_{35}$, and we have no possible value for $\varphi(v_4)$. We get $\varphi(v_2)=v_2,\varphi(v_3)=v_3,\varphi(v_4)=v_4$. Next $\varphi(v_5)\in\{v_3,v_5\}$, but for $\varphi(v_5)=v_3$ we get $\varphi(v_6)=v_4$, with no possible value for $\varphi(v_7)$. So $\varphi$ must be the identity on the entire run $v_1\to\ldots\to v_7$, and by repeating the same argument for the remaining runs, the same is true on all of $D$. In particular, $\varphi$ does not map $D$ onto a proper subgraph.

For the intermediate question (a core with three top-bottom runs), how about this?

Some notation: I will be describing runs by words in $\{l,r\}^*$, with e.g. $llrl$ corresponding to a subgraph $\cdot\leftarrow\cdot\leftarrow\cdot\to\cdot\leftarrow\cdot$. The level increases on $r$ arcs and decreases on $l$ arcs, and I assume that its minimum is $0$. Some straightforward constraints are:

  • There cannot be a run consisting only of $l$s or only of $r$s, because otherwise there is an obvious homomorphism from $D$ to this run (mapping each node of $D$ to the one with the same level). This also implies that the maximum level must be at least $3$.
  • If the maximum level were $3$, then all top-bottom (resp bottom-top) runs would be of the form $llr(lr)^ill$ (resp. $rrl(rl)^irr)$; again it is not very hard to find a homomorphism from $D$ to the run which minimizes $i$.

However, for maximum level $4$ there is a solution, of length $36$: consider $D$ given by $(rrrlrrlllrll)^3$. Unless I missed something, this is a core, and by the above constraints, it is necessarily minimal, since each run only has a single "backwards" edge.

For the intermediate question (a core with three top-bottom runs), how about this?

Some notation: I will be describing runs by words in $\{l,r\}^*$, with e.g. $llrl$ corresponding to a subgraph $\cdot\leftarrow\cdot\leftarrow\cdot\to\cdot\leftarrow\cdot$. The level increases on $r$ arcs and decreases on $l$ arcs, and I assume that its minimum is $0$. Some straightforward constraints are:

  • There cannot be a run consisting only of $l$s or only of $r$s, because otherwise there is an obvious homomorphism from $D$ to this run (mapping each node of $D$ to the one with the same level). This also implies that the maximum level must be at least $3$.
  • If the maximum level were $3$, then all top-bottom (resp bottom-top) runs would be of the form $llr(lr)^ill$ (resp. $rrl(rl)^irr)$; again it is not very hard to find a homomorphism from $D$ to the run which minimizes $i$.

However, for maximum level $4$ there is a solution, of length $36$: consider $D$ given by $(rrrlrrlllrll)^3$. This has the required top-bottom runs and is a core (see below). By the above constraints, it is necessarily minimal, since each run only has a single "backwards" edge.

To convince ourselves that this is a core, let's first name the vertices ($v_1,\ldots,v_{36}$). The bottom (i.e. level $0$) vertices are $v_1,v_{13},v_{25}$. Any homomorphism $\varphi$ from $D$ to a subgraph must preserve levels, and in particular $\varphi(v_1)\in\{v_1,v_{13},v_{25}\}$; modulo the obvious automorphism $v_i\mapsto v_{i+12}$, it is enough to consider the case $\varphi(v_1)=v_1$. Consider the neighbourhood of $v_1$ in $D$ (annotated with levels):

$v_{34}(1)\to v_{35}(2)\leftarrow v_{36}(1)\leftarrow v_1(0)\to v_2(1)\to v_3(2)\to v_4(3)\leftarrow v_5(2)\to v_6(3)\to v_7(4)$

Starting with $\varphi(v_1)=v_1$, we have $\varphi(v_2)\in\{v_{36},v_2\}$. But if $\varphi(v_2)=v_{36}$, then $\varphi(v_3)=v_{35}$, and we have no possible value for $\varphi(v_4)$. We get $\varphi(v_2)=v_2,\varphi(v_3)=v_3,\varphi(v_4)=v_4$. Next $\varphi(v_5)\in\{v_3,v_5\}$, but for $\varphi(v_5)=v_3$ we get $\varphi(v_6)=v_4$, with no possible value for $\varphi(v_7)$. So $\varphi$ must be the identity on the entire run $v_1\to\ldots\to v_7$, and by repeating the same argument for the remaining runs, the same is true on all of $D$. In particular, $\varphi$ does not map $D$ onto a proper subgraph.

Source Link
Klaus Draeger
  • 2.5k
  • 1
  • 23
  • 19

For the intermediate question (a core with three top-bottom runs), how about this?

Some notation: I will be describing runs by words in $\{l,r\}^*$, with e.g. $llrl$ corresponding to a subgraph $\cdot\leftarrow\cdot\leftarrow\cdot\to\cdot\leftarrow\cdot$. The level increases on $r$ arcs and decreases on $l$ arcs, and I assume that its minimum is $0$. Some straightforward constraints are:

  • There cannot be a run consisting only of $l$s or only of $r$s, because otherwise there is an obvious homomorphism from $D$ to this run (mapping each node of $D$ to the one with the same level). This also implies that the maximum level must be at least $3$.
  • If the maximum level were $3$, then all top-bottom (resp bottom-top) runs would be of the form $llr(lr)^ill$ (resp. $rrl(rl)^irr)$; again it is not very hard to find a homomorphism from $D$ to the run which minimizes $i$.

However, for maximum level $4$ there is a solution, of length $36$: consider $D$ given by $(rrrlrrlllrll)^3$. Unless I missed something, this is a core, and by the above constraints, it is necessarily minimal, since each run only has a single "backwards" edge.