Return to Answer

replaced http://mathoverflow.net/ with https://mathoverflow.net/

Source Link

edited Apr 13, 2017 at 12:57

1
2
3

Here is an expansion of my answer in the comments. A graph $G$ is irreducible for a surface $\Sigma$, if $G$ does not embed in $\Sigma$, but for every proper subgraph $H$ of $G$, $H$ does embed in $\Sigma$. For each surface $\Sigma$, let $\mathcal{I}(\Sigma)$ denote the homeomorphism classes of irreducible graphs for $\Sigma$.

In his PhD thesis, Dan Archdeacon proved that there are exactly 103 homeomorphism classes of irreducible graphs for the projective plane. These graphs are all drawn in the appendix of his thesis. Note that a year earlier (1979), Glover, Huneke and Wang had shown that these 103 graphs are irreducible for the projective plane, and Archdeacon's contribution was that there are in fact no others.

Nowadays, by the Robertson-Seymour graph minor theory, we know that $\mathcal{I}(\Sigma)$ is finite for every surface $\Sigma$. In fact, there is now a reasonably short proof of this fact that avoids much of the graph minors machinery. See my answer here here. However, the projective plane and the sphere are still the only two surfaces for which we know the set $\mathcal{I}(\Sigma)$ explicitly.

Here is an expansion of my answer in the comments. A graph $G$ is irreducible for a surface $\Sigma$, if $G$ does not embed in $\Sigma$, but for every proper subgraph $H$ of $G$, $H$ does embed in $\Sigma$. For each surface $\Sigma$, let $\mathcal{I}(\Sigma)$ denote the homeomorphism classes of irreducible graphs for $\Sigma$.

In his PhD thesis, Dan Archdeacon proved that there are exactly 103 homeomorphism classes of irreducible graphs for the projective plane. These graphs are all drawn in the appendix of his thesis. Note that a year earlier (1979), Glover, Huneke and Wang had shown that these 103 graphs are irreducible for the projective plane, and Archdeacon's contribution was that there are in fact no others.

Nowadays, by the Robertson-Seymour graph minor theory, we know that $\mathcal{I}(\Sigma)$ is finite for every surface $\Sigma$. In fact, there is now a reasonably short proof of this fact that avoids much of the graph minors machinery. See my answer here. However, the projective plane and the sphere are still the only two surfaces for which we know the set $\mathcal{I}(\Sigma)$ explicitly.

Here is an expansion of my answer in the comments. A graph $G$ is irreducible for a surface $\Sigma$, if $G$ does not embed in $\Sigma$, but for every proper subgraph $H$ of $G$, $H$ does embed in $\Sigma$. For each surface $\Sigma$, let $\mathcal{I}(\Sigma)$ denote the homeomorphism classes of irreducible graphs for $\Sigma$.

In his PhD thesis, Dan Archdeacon proved that there are exactly 103 homeomorphism classes of irreducible graphs for the projective plane. These graphs are all drawn in the appendix of his thesis. Note that a year earlier (1979), Glover, Huneke and Wang had shown that these 103 graphs are irreducible for the projective plane, and Archdeacon's contribution was that there are in fact no others.

Nowadays, by the Robertson-Seymour graph minor theory, we know that $\mathcal{I}(\Sigma)$ is finite for every surface $\Sigma$. In fact, there is now a reasonably short proof of this fact that avoids much of the graph minors machinery. See my answer here. However, the projective plane and the sphere are still the only two surfaces for which we know the set $\mathcal{I}(\Sigma)$ explicitly.

Source Link

created Dec 10, 2013 at 8:26

32.1k
11
112
187

Here is an expansion of my answer in the comments. A graph $G$ is irreducible for a surface $\Sigma$, if $G$ does not embed in $\Sigma$, but for every proper subgraph $H$ of $G$, $H$ does embed in $\Sigma$. For each surface $\Sigma$, let $\mathcal{I}(\Sigma)$ denote the homeomorphism classes of irreducible graphs for $\Sigma$.

In his PhD thesis, Dan Archdeacon proved that there are exactly 103 homeomorphism classes of irreducible graphs for the projective plane. These graphs are all drawn in the appendix of his thesis. Note that a year earlier (1979), Glover, Huneke and Wang had shown that these 103 graphs are irreducible for the projective plane, and Archdeacon's contribution was that there are in fact no others.

Nowadays, by the Robertson-Seymour graph minor theory, we know that $\mathcal{I}(\Sigma)$ is finite for every surface $\Sigma$. In fact, there is now a reasonably short proof of this fact that avoids much of the graph minors machinery. See my answer here. However, the projective plane and the sphere are still the only two surfaces for which we know the set $\mathcal{I}(\Sigma)$ explicitly.