Post History

50%

+0 −0

Q&A What is an example of a pathological imbedding of a(n allowed) graph into an oriented surface?

posted 7mo ago by The Amplitwist‭ · edited 6mo ago by The Amplitwist‭

Answer

#3: Post edited by $user avatar$ The Amplitwist‭ · 2024-05-19T07:38:27Z (6 months ago)

Copy Link

Raw

Markdown

The pathological embeddings arise because an "allowed graph" is a very general object. The goal of the assumption **TM1** is to restrict attention to precisely the kind of allowed graphs that are described in the question as being
> slightly more general than an undirected pseudograph in that it allows the existence of edges that are free at one end
However, the full definition in the paper says that an allowed graph is a topological space $\mathcal{G}$ equipped with collections $\mathcal{V}$ and $\mathcal{E}$ of subspaces that are (homeomorphic to) singletons and circles/closed unit intervals, respectively, such that:
- [AG0] $\mathcal{G} = \bigcup_{e \in \mathcal{E}} e$;
- [AG1] if $e$ is (homeomorphic to) a circle, then $\Delta e := e \cap \mathcal{V}$ is a singleton, and if $e$ is (homeomorphic to) a closed unit interval, then $\Delta e$ consists of either one or both of the end-points of $e$ (and in the latter case, $e$ is called a _free edge_).
- [AG2] if $e^\sharp := e \setminus \Delta e$, then $e_1^\sharp \cap e_2^\sharp = \emptyset$ for all distinct $e_1,e_2 \in \mathcal{E}$;
- [AG3] for any $v \in \mathcal{V}$, at most finitely many $e \in \mathcal{E}$ satisfy $v \in \Delta e$.
Now, consider the following example.
_Example._ Let $\mathcal{G} = [0,1] \times [0,1]$ with the product topology. Let $\mathcal{V} = \{ (a,b) : a = 0 \text{ or } a = 1 \}$.
Let $\mathcal{E} = \{ [0,1] \times \{ b \} : b \in [0,1] \}$.
Then, it is easy to see that $(\mathcal{G},\mathcal{V},\mathcal{E})$ is an allowed graph as per the above definition, but it is not possible to embed it into a surface such that the assumption **TM1** is satisfied. Essentially, the topology on $\mathcal{G}$ can prevent such nice embeddings from existing, and nothing in the definition rules out such topological spaces from being allowed graphs.
But if we restrict ourselves to allowed graphs that are just undirected pseudographs that permit free edges, then it seems highly likely to me that **TM1** will always be satisfied, though I can't write down a rigorous proof.

The pathological embeddings arise because an "allowed graph" is a very general object. The goal of the assumption **TM1** is to restrict attention to precisely the kind of allowed graphs that are described in the question as being
> slightly more general than an undirected pseudograph in that it allows the existence of edges that are free at one end
However, the full definition in the paper says that an allowed graph is a topological space $\mathcal{G}$ equipped with collections $\mathcal{V}$ and $\mathcal{E}$ of subspaces that are (homeomorphic to) singletons and circles/closed unit intervals, respectively, such that:
- [AG0] $\mathcal{G} = \bigcup_{e \in \mathcal{E}} e$;
- [AG1] if $e$ is (homeomorphic to) a circle, then $\Delta e := e \cap \mathcal{V}$ is a singleton, and if $e$ is (homeomorphic to) a closed unit interval, then $\Delta e$ consists of either one or both of the end-points of $e$ (and in the latter case, $e$ is called a _free edge_).
- [AG2] if $e^\sharp := e \setminus \Delta e$, then $e_1^\sharp \cap e_2^\sharp = \emptyset$ for all distinct $e_1,e_2 \in \mathcal{E}$;
- [AG3] for any $v \in \mathcal{V}$, at most finitely many $e \in \mathcal{E}$ satisfy $v \in \Delta e$.
Now, consider the following example.
_Example._ Let $\mathcal{G} = [0,1] \times [0,1]$ with the product topology. Let $\mathcal{V} = \{ (a,b) : a = 0 \text{ or } a = 1 \}$.
Let $\mathcal{E} = \{ [0,1] \times \{ b \} : b \in [0,1] \}$.
Then, it is easy to see that $(\mathcal{G},\mathcal{V},\mathcal{E})$ is an allowed graph as per the above definition, but it is not possible to embed it into a surface such that the assumption **TM1** is satisfied. Essentially, the topology on $\mathcal{G}$ can prevent such nice embeddings from existing, and nothing in the definition rules out such topological spaces from being allowed graphs.
But if we restrict ourselves to allowed graphs that are just undirected pseudographs that permit free edges, then **TM1** will be satisfied. For a rigorous proof, see the paper [Embedding graphs in surfaces](https://doi.org/10.1016/0095-8956(84)90014-5) (_P. Hoffman_ and _B. Richter_, J. Comb. Theory, Ser. B 36, 65–84 (1984; [Zbl 0514.05028](https://zbmath.org/0514.05028))). In particular, see Section 3:
> ### 3. The Neighbourhood Theorem
> In this section, we state and prove the "neighbourhood theorem," which is required for the proof of the scissors theorem.
>
> Let $G^m$ denote the graph with two vertices and $m$ edges, each edge being a link joining the two vertices. For [sic] positive integer $k$, let $Y_k$ be the set $\{ re^{i\theta} ;\ 0 \leq r < \infty \text{ and } \theta \in \{2\pi n / k ;\ n \in \mathbb{Z} \} \} \subset \mathbb{C}$.
>
> Theorem 3.1 (The neighbourhood theorem). _Let $K$ be a graph, without isolated vertices, contained in the surface $M$. For each $x \in K$, there is an embedding $h \colon \mathbb{C} \to M$ such that $h(0) = x$ and $h(Y_{\operatorname{val}(x)}) = j(\mathbb{C}) \cap K$._

#2: Post edited by $user avatar$ The Amplitwist‭ · 2024-04-30T12:17:00Z (7 months ago)

Copy Link

Raw

Markdown

The pathological embeddings arise because an "allowed graph" is a very general object. The goal of the assumption **TM1** is to restrict attention to precisely the kind of allowed graphs that are described in the question as being
~~> slightly more general than an undirected pseudograph in that it allows the existence of edges that are free at one end;~~
However, the full definition in the paper says that an allowed graph is a topological space $\mathcal{G}$ equipped with collections $\mathcal{V}$ and $\mathcal{E}$ of subspaces homeomorphic to singletons and circles/closed unit intervals, respectively, such that:
- [AG0] $\mathcal{G} = \bigcup_{e \in \mathcal{E}} e$;
- [AG1] if $e$ is (homeomorphic to) a circle, then $\Delta e := e \cap \mathcal{V}$ is a singleton, and if $e$ is (homeomorphic to) a closed interval, then $\Delta e$ consists of either one or both of the end-points of $e$ (and in the latter case, $e$ is called a _free edge_).
- [AG2] if $e^\sharp := e \setminus \Delta e$, then $e_1^\sharp \cap e_2^\sharp = \emptyset$ for all distinct $e_1,e_2 \in \mathcal{E}$;
- [AG3] for any $v \in \mathcal{V}$, at most finitely many $e \in \mathcal{E}$ satisfy $v \in \Delta e$.
Now, consider the following example.
_Example._ Let $\mathcal{G} = [0,1] \times [0,1]$ with the product topology. Let $\mathcal{V} = \{ (a,b) : a = 0 \text{ or } a = 1 \}$.
Let $\mathcal{E} = \{ [0,1] \times \{ b \} : b \in [0,1] \}$.
Then, it is easy to see that $(\mathcal{G},\mathcal{V},\mathcal{E})$ is an allowed graph as per the above definition, but it is not possible to embed it into a surface such that the assumption **TM1** is satisfied. Essentially, the topology on $\mathcal{G}$ can prevent such nice embeddings from existing, and nothing in the definition rules out such topological spaces from being allowed graphs.
But if we restrict ourselves to allowed graphs that are just undirected pseudographs that permit free edges, then it seems highly likely to me that **TM1** will always be satisfied, though I can't write down a rigorous proof.

The pathological embeddings arise because an "allowed graph" is a very general object. The goal of the assumption **TM1** is to restrict attention to precisely the kind of allowed graphs that are described in the question as being
> slightly more general than an undirected pseudograph in that it allows the existence of edges that are free at one end
However, the full definition in the paper says that an allowed graph is a topological space $\mathcal{G}$ equipped with collections $\mathcal{V}$ and $\mathcal{E}$ of subspaces that are (homeomorphic to) singletons and circles/closed unit intervals, respectively, such that:
- [AG0] $\mathcal{G} = \bigcup_{e \in \mathcal{E}} e$;
- [AG1] if $e$ is (homeomorphic to) a circle, then $\Delta e := e \cap \mathcal{V}$ is a singleton, and if $e$ is (homeomorphic to) a closed unit interval, then $\Delta e$ consists of either one or both of the end-points of $e$ (and in the latter case, $e$ is called a _free edge_).
- [AG2] if $e^\sharp := e \setminus \Delta e$, then $e_1^\sharp \cap e_2^\sharp = \emptyset$ for all distinct $e_1,e_2 \in \mathcal{E}$;
- [AG3] for any $v \in \mathcal{V}$, at most finitely many $e \in \mathcal{E}$ satisfy $v \in \Delta e$.
Now, consider the following example.
_Example._ Let $\mathcal{G} = [0,1] \times [0,1]$ with the product topology. Let $\mathcal{V} = \{ (a,b) : a = 0 \text{ or } a = 1 \}$.
Let $\mathcal{E} = \{ [0,1] \times \{ b \} : b \in [0,1] \}$.
Then, it is easy to see that $(\mathcal{G},\mathcal{V},\mathcal{E})$ is an allowed graph as per the above definition, but it is not possible to embed it into a surface such that the assumption **TM1** is satisfied. Essentially, the topology on $\mathcal{G}$ can prevent such nice embeddings from existing, and nothing in the definition rules out such topological spaces from being allowed graphs.
But if we restrict ourselves to allowed graphs that are just undirected pseudographs that permit free edges, then it seems highly likely to me that **TM1** will always be satisfied, though I can't write down a rigorous proof.

#1: Initial revision by $user avatar$ The Amplitwist‭ · 2024-04-29T16:36:41Z (7 months ago)

Copy Link

Raw

Markdown

The pathological embeddings arise because an "allowed graph" is a very general object. The goal of the assumption **TM1** is to restrict attention to precisely the kind of allowed graphs that are described in the question as being

> slightly more general than an undirected pseudograph in that it allows the existence of edges that are free at one end;

However, the full definition in the paper says that an allowed graph is a topological space $\mathcal{G}$ equipped with collections $\mathcal{V}$ and $\mathcal{E}$ of subspaces homeomorphic to singletons and circles/closed unit intervals, respectively, such that:

- [AG0] $\mathcal{G} = \bigcup_{e \in \mathcal{E}} e$;
- [AG1] if $e$ is (homeomorphic to) a circle, then $\Delta e := e \cap \mathcal{V}$ is a singleton, and if $e$ is (homeomorphic to) a closed interval, then $\Delta e$ consists of either one or both of the end-points of $e$ (and in the latter case, $e$ is called a _free edge_).
- [AG2] if $e^\sharp := e \setminus \Delta e$, then $e_1^\sharp \cap e_2^\sharp = \emptyset$ for all distinct $e_1,e_2 \in \mathcal{E}$;
- [AG3] for any $v \in \mathcal{V}$, at most finitely many $e \in \mathcal{E}$ satisfy $v \in \Delta e$.

Now, consider the following example.

_Example._ Let $\mathcal{G} = [0,1] \times [0,1]$ with the product topology. Let $\mathcal{V} = \{ (a,b) : a = 0 \text{ or } a = 1 \}$.
Let $\mathcal{E} = \{ [0,1] \times \{ b \} : b \in [0,1] \}$.
Then, it is easy to see that $(\mathcal{G},\mathcal{V},\mathcal{E})$ is an allowed graph as per the above definition, but it is not possible to embed it into a surface such that the assumption **TM1** is satisfied. Essentially, the topology on $\mathcal{G}$ can prevent such nice embeddings from existing, and nothing in the definition rules out such topological spaces from being allowed graphs.

But if we restrict ourselves to allowed graphs that are just undirected pseudographs that permit free edges, then it seems highly likely to me that **TM1** will always be satisfied, though I can't write down a rigorous proof.

Communities

Post History