14
$\begingroup$

The topology of a graph (i.e. a network topology), as far as I can tell, doesn't actually have anything to do with open or closed sets, nor does it have any consistent, rigorous definition in practice.

So why is it called a topology?

Also, simplicial complexes kind of look like graphs -- is their topology related to this "topology"?

Possibly related: Is a "network topology'" a topological space?, but here I'm asking for the etymology of the term (topology I thought was invented specifically for the mathematical field, why is the topology of a graph, which isn't necessarily related, called that? Why don't they call it the connectivity or something like that?)

$\endgroup$
  • 1
    $\begingroup$ I suspect it's because it specifies the way the network is connected. $\qquad$ $\endgroup$ – Michael Hardy May 18 '16 at 19:53
  • 4
    $\begingroup$ I've always assumed it had to do with the fact that it didn't matter how the edges or vertices were drawn, the graph had the same properties "up to homotopy." $\endgroup$ – Ben Sheller May 18 '16 at 19:54
  • 1
    $\begingroup$ Every graph is a 1-dimensional CW complex and it's topology in any reasonable sense is the same as the CW complex topology. What is a bit misleading is that two graphs can be homeomorphic without being isomorphic. $\endgroup$ – Moishe Kohan May 18 '16 at 23:29
  • 1
    $\begingroup$ Probably because it specifies the first homology group of the graph.. $\endgroup$ – Henry May 19 '16 at 0:32
10
$\begingroup$

While topology is "implemented" using open and closed sets, etc., it is ultimately the study of properties that are invariant under continuously stretching things. Since you're modding out by so many transformations, it has a distinctly qualitative flavour, and thus captures many of our intuitions that might be otherwise hard to write down without its language. For example, the very intuitive notion of shape is formalized through topology. The most basic question - are these two shapes the same - still bugs us, and has lead to algebraic invariants such as the fundamental group, homology and cohomology and so on.

What do graphs have to do with that? It is true that how a graph is drawn doesn't matter for its properties, but when mathematicians talk about the topology of a graph they talk about phenomena that are beyond that. I can think of three reasons: First, there are natural qualitative questions of that flavour you can ask about graphs too, like, is it connected, "how" connected is it, are there bottlenecks? Second, graphs arise as discrete approximations of higher-dimensional topological objects, and display analogous 'topological' properties. And third, approaching graphs from a topological point of view has proven to be fruitful. I'm sure there are many nice illustrations of all these, but here's my bag of examples.

For one, the planarity problem, which has been solved, classifies the graphs $G$ that can be embedded "faithfully" in the plane, that is, with no edge intersections. Not surprisingly, there is a condition of topological flavor: there are certain subgraphs ($K_{3,3},K_5$) that are topologically forbidden from arising in $G$, in the sense that we cannot subdivide the edges of $K_{3,3}$ or $K_5$ by introducing new vertices along them to obtain a subgraph of $G$. These questions generalize, so you can ask, which graphs can be embedded in a given surface faithfully? The book Topological graph theory by Gross and Tucker considers these questions, and uses the graph-theoretic analogue of a covering space from algebraic topology.

For another maybe less related example, sometimes it makes sense to talk about the geometry of a graph too: for example, if you have an expander graph, it is a direct consequence of the definition that the volume of a ball of radius $r$ at a vertex grows exponentially with $r$; in other graphs, like a $d$-dimensional grid for example, it grows polynomially. So an expander looks more like hyperbolic space, while the grid looks more like Euclidean space - you can see the same sort of 'qualitative shape' stuff happening.

For a yet another example, the Cheeger constant which describes 'how connected' a manifold is has close analogues for graphs.

For a final example (I'm biased because I've worked on that), the study of the aforementioned covering spaces of graphs has led to some exciting developments in spectral graph theory, such as this paper, and it seems like (check out work by Amit and Linial on graph lifts) the coverings of a graph are an interesting probability space, which in particular gives us a useful model for random regular graphs which the Erdos-Renyi model doesn't.

(and in fact the wikipedia entry for topology starts the history of the subject with Euler's bridges of Konigsberg problem! )

$\endgroup$
  • 1
    $\begingroup$ Huh, I didn't know that the Cheeger constant was defined for manifolds. +1 $\endgroup$ – Eric Stucky May 19 '16 at 3:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.