Skip to main content
switch i and j to make the notation consistent
Source Link
Emil Jeřábek
  • 47.4k
  • 4
  • 150
  • 209

I don’t see what the problem is supposed to be; you just compose the functions witnessing the two domination relations in the obvious way:

Fix $c=u_0,\dots,u_n=d$ and $f_1,\dots,f_n\in F$ such that $\{f_i(a),f_i(b)\}=\{u_{i-1},u_i\}$ for each $i=1,\dots,n$.

Fix $e=v_0,\dots,v_m=f$ and $g_1,\dots,g_m\in F$ such that $\{g_j(c),g_j(d)\}=\{v_{j-1},v_j\}$ for each $j=1,\dots,m$.

Then the fact that $\{a,b\}$ dominates $\{e,f\}$ is witnessed by the sequence $$e=v_0=w_{1,0},w_{1,1},\dots,w_{1,n}=v_2=w_{2,0},w_{2,1},\dots,w_{m,n}=v_m=f,$$ where $$w_{i,j}=\begin{cases}g_i(u_j)&\text{if }g_i(c)=v_{i-1}\text{ and }g_i(d)=v_i,\\ g_i(u_{n-j})&\text{otherwise.}\end{cases}$$$$w_{j,i}=\begin{cases}g_j(u_i)&\text{if }g_j(c)=v_{j-1}\text{ and }g_j(d)=v_j,\\ g_j(u_{n-i})&\text{otherwise.}\end{cases}$$ We have $\{w_{i,j-1},w_{i,j}\}=\{h_{i,j}(a),h_{i,j}(b)\}$$\{w_{j,i-1},w_{j,i}\}=\{h_{j,i}(a),h_{j,i}(b)\}$, where $$h_{i,j}=\begin{cases}g_i\circ f_j&\text{if }g_i(c)=v_{i-1}\text{ and }g_i(d)=v_i,\\ g_i\circ f_{n+1-j}&\text{otherwise}\end{cases}$$$$h_{j,i}=\begin{cases}g_j\circ f_i&\text{if }g_j(c)=v_{j-1}\text{ and }g_j(d)=v_j,\\ g_j\circ f_{n+1-i}&\text{otherwise}\end{cases}$$ is in $F$ as it is closed under composition.

I don’t see what the problem is supposed to be; you just compose the functions witnessing the two domination relations in the obvious way:

Fix $c=u_0,\dots,u_n=d$ and $f_1,\dots,f_n\in F$ such that $\{f_i(a),f_i(b)\}=\{u_{i-1},u_i\}$ for each $i=1,\dots,n$.

Fix $e=v_0,\dots,v_m=f$ and $g_1,\dots,g_m\in F$ such that $\{g_j(c),g_j(d)\}=\{v_{j-1},v_j\}$ for each $j=1,\dots,m$.

Then the fact that $\{a,b\}$ dominates $\{e,f\}$ is witnessed by the sequence $$e=v_0=w_{1,0},w_{1,1},\dots,w_{1,n}=v_2=w_{2,0},w_{2,1},\dots,w_{m,n}=v_m=f,$$ where $$w_{i,j}=\begin{cases}g_i(u_j)&\text{if }g_i(c)=v_{i-1}\text{ and }g_i(d)=v_i,\\ g_i(u_{n-j})&\text{otherwise.}\end{cases}$$ We have $\{w_{i,j-1},w_{i,j}\}=\{h_{i,j}(a),h_{i,j}(b)\}$, where $$h_{i,j}=\begin{cases}g_i\circ f_j&\text{if }g_i(c)=v_{i-1}\text{ and }g_i(d)=v_i,\\ g_i\circ f_{n+1-j}&\text{otherwise}\end{cases}$$ is in $F$ as it is closed under composition.

I don’t see what the problem is supposed to be; you just compose the functions witnessing the two domination relations in the obvious way:

Fix $c=u_0,\dots,u_n=d$ and $f_1,\dots,f_n\in F$ such that $\{f_i(a),f_i(b)\}=\{u_{i-1},u_i\}$ for each $i=1,\dots,n$.

Fix $e=v_0,\dots,v_m=f$ and $g_1,\dots,g_m\in F$ such that $\{g_j(c),g_j(d)\}=\{v_{j-1},v_j\}$ for each $j=1,\dots,m$.

Then the fact that $\{a,b\}$ dominates $\{e,f\}$ is witnessed by the sequence $$e=v_0=w_{1,0},w_{1,1},\dots,w_{1,n}=v_2=w_{2,0},w_{2,1},\dots,w_{m,n}=v_m=f,$$ where $$w_{j,i}=\begin{cases}g_j(u_i)&\text{if }g_j(c)=v_{j-1}\text{ and }g_j(d)=v_j,\\ g_j(u_{n-i})&\text{otherwise.}\end{cases}$$ We have $\{w_{j,i-1},w_{j,i}\}=\{h_{j,i}(a),h_{j,i}(b)\}$, where $$h_{j,i}=\begin{cases}g_j\circ f_i&\text{if }g_j(c)=v_{j-1}\text{ and }g_j(d)=v_j,\\ g_j\circ f_{n+1-i}&\text{otherwise}\end{cases}$$ is in $F$ as it is closed under composition.

Source Link
Emil Jeřábek
  • 47.4k
  • 4
  • 150
  • 209

I don’t see what the problem is supposed to be; you just compose the functions witnessing the two domination relations in the obvious way:

Fix $c=u_0,\dots,u_n=d$ and $f_1,\dots,f_n\in F$ such that $\{f_i(a),f_i(b)\}=\{u_{i-1},u_i\}$ for each $i=1,\dots,n$.

Fix $e=v_0,\dots,v_m=f$ and $g_1,\dots,g_m\in F$ such that $\{g_j(c),g_j(d)\}=\{v_{j-1},v_j\}$ for each $j=1,\dots,m$.

Then the fact that $\{a,b\}$ dominates $\{e,f\}$ is witnessed by the sequence $$e=v_0=w_{1,0},w_{1,1},\dots,w_{1,n}=v_2=w_{2,0},w_{2,1},\dots,w_{m,n}=v_m=f,$$ where $$w_{i,j}=\begin{cases}g_i(u_j)&\text{if }g_i(c)=v_{i-1}\text{ and }g_i(d)=v_i,\\ g_i(u_{n-j})&\text{otherwise.}\end{cases}$$ We have $\{w_{i,j-1},w_{i,j}\}=\{h_{i,j}(a),h_{i,j}(b)\}$, where $$h_{i,j}=\begin{cases}g_i\circ f_j&\text{if }g_i(c)=v_{i-1}\text{ and }g_i(d)=v_i,\\ g_i\circ f_{n+1-j}&\text{otherwise}\end{cases}$$ is in $F$ as it is closed under composition.