Skip to main content
deleted 2 characters in body
Source Link

$\newcommand{Po}{{\cal P}(\omega)}$ $\newcommand{lh}{\leq_{\text{hom}}}$ If $H_i = (V_i, E_i)$ are hypergraphs for $i = 1,2$, then a map $f:V_1 \to V_2$ is said to be a (hypergraph) homomorphism if $f(e_1) \in E_2$ for all $e_1 \in E_1$. We say $f:V_1\to V_2$ is an isomorphism if $f$ is a bijection and we have $e_1\in E_1$ if and only if $f(e_1) \in E_2$.

In this question we focus on hypergraphs $H=(\omega,E)$ (having base set $\omega$ and $E\subseteq \Po$).

For $E_1, E_2 \subseteq \Po$ we write $E_1 \lh E_2$ if there is a homomorphism $f:(\omega, E_1)\to (\omega, E_2)$.

Questions. Let $E_1, E_2 \subseteq \Po$.

  1. Is there necessarily a set $E^* \in\Po$ with $E_1, E_2 \lh E^*$ and the following property?

Whenever $E\subseteq \Po$ such that $E_1, E_2 \lh E$, then $E^* \leq E$$E^* \lh E$.

  1. Dually: Is there necessarily a set $E_* \in\Po$ with $E_*\lh E_1, E_2$ and the following property?

Whenever $E\subseteq \Po$ such that $E\lh E_1, E_2$, then $E\leq E_*$$E\lh E_*$.

$\newcommand{Po}{{\cal P}(\omega)}$ $\newcommand{lh}{\leq_{\text{hom}}}$ If $H_i = (V_i, E_i)$ are hypergraphs for $i = 1,2$, then a map $f:V_1 \to V_2$ is said to be a (hypergraph) homomorphism if $f(e_1) \in E_2$ for all $e_1 \in E_1$. We say $f:V_1\to V_2$ is an isomorphism if $f$ is a bijection and we have $e_1\in E_1$ if and only if $f(e_1) \in E_2$.

In this question we focus on hypergraphs $H=(\omega,E)$ (having base set $\omega$ and $E\subseteq \Po$).

For $E_1, E_2 \subseteq \Po$ we write $E_1 \lh E_2$ if there is a homomorphism $f:(\omega, E_1)\to (\omega, E_2)$.

Questions. Let $E_1, E_2 \subseteq \Po$.

  1. Is there necessarily a set $E^* \in\Po$ with $E_1, E_2 \lh E^*$ and the following property?

Whenever $E\subseteq \Po$ such that $E_1, E_2 \lh E$, then $E^* \leq E$.

  1. Dually: Is there necessarily a set $E_* \in\Po$ with $E_*\lh E_1, E_2$ and the following property?

Whenever $E\subseteq \Po$ such that $E\lh E_1, E_2$, then $E\leq E_*$.

$\newcommand{Po}{{\cal P}(\omega)}$ $\newcommand{lh}{\leq_{\text{hom}}}$ If $H_i = (V_i, E_i)$ are hypergraphs for $i = 1,2$, then a map $f:V_1 \to V_2$ is said to be a (hypergraph) homomorphism if $f(e_1) \in E_2$ for all $e_1 \in E_1$. We say $f:V_1\to V_2$ is an isomorphism if $f$ is a bijection and we have $e_1\in E_1$ if and only if $f(e_1) \in E_2$.

In this question we focus on hypergraphs $H=(\omega,E)$ (having base set $\omega$ and $E\subseteq \Po$).

For $E_1, E_2 \subseteq \Po$ we write $E_1 \lh E_2$ if there is a homomorphism $f:(\omega, E_1)\to (\omega, E_2)$.

Questions. Let $E_1, E_2 \subseteq \Po$.

  1. Is there necessarily a set $E^* \in\Po$ with $E_1, E_2 \lh E^*$ and the following property?

Whenever $E\subseteq \Po$ such that $E_1, E_2 \lh E$, then $E^* \lh E$.

  1. Dually: Is there necessarily a set $E_* \in\Po$ with $E_*\lh E_1, E_2$ and the following property?

Whenever $E\subseteq \Po$ such that $E\lh E_1, E_2$, then $E\lh E_*$.

Source Link

"Infima" and "suprema" in the homomorphism preorder on hypergraphs on $\omega$

$\newcommand{Po}{{\cal P}(\omega)}$ $\newcommand{lh}{\leq_{\text{hom}}}$ If $H_i = (V_i, E_i)$ are hypergraphs for $i = 1,2$, then a map $f:V_1 \to V_2$ is said to be a (hypergraph) homomorphism if $f(e_1) \in E_2$ for all $e_1 \in E_1$. We say $f:V_1\to V_2$ is an isomorphism if $f$ is a bijection and we have $e_1\in E_1$ if and only if $f(e_1) \in E_2$.

In this question we focus on hypergraphs $H=(\omega,E)$ (having base set $\omega$ and $E\subseteq \Po$).

For $E_1, E_2 \subseteq \Po$ we write $E_1 \lh E_2$ if there is a homomorphism $f:(\omega, E_1)\to (\omega, E_2)$.

Questions. Let $E_1, E_2 \subseteq \Po$.

  1. Is there necessarily a set $E^* \in\Po$ with $E_1, E_2 \lh E^*$ and the following property?

Whenever $E\subseteq \Po$ such that $E_1, E_2 \lh E$, then $E^* \leq E$.

  1. Dually: Is there necessarily a set $E_* \in\Po$ with $E_*\lh E_1, E_2$ and the following property?

Whenever $E\subseteq \Po$ such that $E\lh E_1, E_2$, then $E\leq E_*$.