I learned that there are 103 topological irreducible graphs for the projective plane but I am unable to find examples of said graphs. I am unsure of how to find them on my own and I would like to see examples.
2
-
7$\begingroup$ This was proved in Dan Archdeacon's PhD thesis. You can find the thesis here. emba.uvm.edu/~darchdea/papers/thesis.pdf All 103 graphs are drawn in the Appendix. $\endgroup$– Tony HuynhCommented Dec 9, 2013 at 21:27
-
1$\begingroup$ @TonyHuynh gave an answer (disguised as a comment), but the rest of us are still in the dark as to what a topological irreducible graph in the projective plane is. $\endgroup$– Igor RivinCommented Dec 10, 2013 at 1:26
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Dec 10, 2013 at 8:26