I thought in addition to the graph theory (which I’m enjoying writing, but doesn’t seem to be all that popular), I’d also try doing some writing about fractals. I know pretty much nothing about fractals, but I’ve wanted to learn about them for a while, and one of the advantages of having this blog is that it gives me an excuse to learn about things that that interest me so that I can write about them.
Fractals are amazing things. They can be beautiful: everyone has seen beautiful fractal images – like the ones posted by my fellow SBer Karmen. And they’re also useful: there are a lot of phenomena in nature that seem to involve fractal structures.
But what is a fractal?
The word is a contraction of fractional dimension. The idea of that is that there are several different ways of measuring the dimensionality of a structure using topology. The structures that we call fractals are things that have a kind of fine structure that gives them a strange kind of dimensionality; their conventional topological dimension is smaller than their Hausdorff dimension. (You can look up details of what topological dimension and Hausdorff dimension mean in one of my topology articles.) The details aren’t all that important here: the key thing to understand is that there’s a fractal is a structure that breaks the usual concept of dimension: it’s shape has aspects that suggest higher dimensions. The Sierpinski carpet, for example, is topologically one-dimensional. But if you look at it, you have a clear sense of a two-dimensional figure.
That’s all frightfully abstract. Let’s take a look at one of the simplest fractals. This is called Sierpinski’s carpet. There’s a picture of a finite approximation of it over to the right. The way that you generate this fractal is to take a square. Divide the square into 9 sub-squares, and remove the center one. Then take each of the 8 squares around the edges, and do the same thing to them: break them into 9, remove the center, then repeat on the even smaller squares. Do that an infinite number of times.
When you look at the carpet, you probably think it looks two dimensional. But topologically, it is a one-dimensional space. The “edges” of the resulting figure are infinitely narrow – they have no width that needs a second dimension to describe. The whole thing is an infinitely complicated structure of lines: the total area covered by the carpet is 0! Since it’s just lines, topologically, it’s one-dimensional.
In fact, it is more than just a one dimensional shape; what it is is a kind of canonical one dimensional shape: any one-dimensional space is topologically equivalent (homeomorphic) to a subset of the carpet.
But when we look at it, we can see it has a clear structure in two dimensions. In fact, it’s a structure which really can’t be described as one-dimensional – we defined by cutting finite sized pieces from a square, which is a 2-dimensional figure. It isn’t really two dimensional; it isn’t really one dimensional. The best way of describing it is by its Hausdorff dimension, which is 1.89. So it’s almost, but not quite, two dimensional.
Sierpinski’s carpet is a very typical fractal; it’s got the traits that we use to identify fractals, which are the following:
- Self-similarity: a fractal has a structure that repeats itself on ever smaller scales. In the case of the carpet, you can take any non-blank square, and it’s exactly the same as a smaller version of the entire carpet.
- Fine structure: a fractal has a fine structure at arbitrarily small scales. In the case of the carpet, no matter how small you get, it’s always got even smaller subdivisions.
- Fractional dimension: its Hausdorff dimension is not an integer. Its Hausdorff dimension is also usually larger than its topological dimension. Again looking at the carpet, it’s topological dimension is 1; it’s Hausdorff dimension is 1.89.
Yay! No more boring graphs! 🙂
(Actually, I’ve been furiously grant writing and haven’t had time to read lately… that’s my excuse!)
One of the interesting things about fractals is that there are a number of different ways of defining ‘fractal dimension’ and different ways of calculating it, some more intuitive than others, but your answer can depend on the technique used.
My favorite: The ‘box filling’ method (I don’t remember the exact name) suggests that you cover a fractal multiple times with boxes of various sizes, taking care that you use just enough boxes to cover the fractal, and no more. If you cover a square, the number of boxes goes roughly as x^(-2), with x the width of the box. The dimension is ‘2’. If you cover a line, the number of boxes goes as x^(-1). Evidently the number of boxes goes as x^(-d), where d is the dimension. For a Serpinski gasket, if we go from a single square which exactly covers the gasket to a collection of squares which are 1/3 as wide, we need eight boxes. If we look at the ratio of the number of boxes, we have (1/3)^(-d)=8, which we solve for d=ln8/ ln3=1.89! Voila!
For what it is worth: I have a puny pure math degree and did not learn about fractals then. I read these with a lot more interest than the graph articles which I did learn.
Sierpinski’s carpet… [is] more than just one dimensional – it’s a kind of canonical one dimensional shape: any one-dimensional space is topologically equivalent (homeomorphic) to a subset of the carpet. … The best way of describing it is by it’s Hausdorff dimension, which is 1.89. So it’s almost, but not quite, two dimensional.
So… taken together, what do these two statements imply? It seems to me it would have to be one of the following three things: Which?
1. There are no structures with Hausdorff dimension between 1.89 and 2.0 noninclusive
2. There exist structures with Hausdorff dimension between 1.89 and 2.0 noninclusive, but their topological dimension is always two or greater
3. It is possible to take a subspace of the Sierpinski carpet and get something which has a larger Hausdorff dimension than the Sierpinski carpet itself
Um, no. According to James Gleick’s Chaos (1987), Benoit Mandelbrot coined the word fractal after finding the word fractus (past participle of the verb frangere, “to break”) in his son’s Latin dictionary. This is the same root as the English words fraction and frangible.
Also:
Your article need some editing–especially in the use of it’s versus its.
thanks, for spending your time for people like us, your graphth was also written well i did learn a bit though i may never use it, bravo,univparis.
I was enjoying the graph theory, thank you very much. But fractals are just as good. I suppose we’ll be discussing fractal shorelines next.
Quick correction: Not every fractal has fractional dimension, funnily enough. The Mandelbrot set was proven to be 2-dimensional in 1996.
gg: I learned the same way to measure it, but I didn’t have the explanation behind it. I was just taught to take the log of the number of shapes over the log of the the scale reduction. Ended up being the exact same expression.
Coin:
4. Hausdorff dimension is defined for metric spaces, not general topological ones, so it is preserved or diminished when taking subspaces, but not preserved under distance-changing topological equivalences.
Ørjan: That makes a lot of sense. Thanks!
Does that imply though that you could have one topological space with wildly different hausdorff dimension depending on which distance function you use?
Yes. The Koch snowflake and the unit interval are topologically the same space, but the snowflake has Hausdorff dimension about 1.3, while the interval has dimension 1.
#9: Did you mean to say that the boundary of the Mandelbrot set is 2-dimensional? That the full Mandelbrot set is 2-dimensional is after all trivial, since it has nonempty interior.
A perhaps nicer example is the Sierpinski tetrahedron, a fractal with dimension 3. It is formed by removing a central octahedron from a tetrahedron, leaving four smaller tetrahedra touching each other at the corners. Then do the same to the smaller tetrahedra, and so on.
Also, one can make a simple curve in the plane with positive area (W. F. Osgood, A Jordan curve of positive area. Trans. Amer. Math. Soc. 4 (1903) 107-112). Such a curve will necessarily be two-dimensional. It is clearly fractal in some sense, though not quite self-similar.
me likey graph theory!, just been reading a biography of paul erdos. I’ll be happy to read any more posts on graphs that you put up!
I like the graph posts.
Just because I don’t comment doesn’t mean I don’t like, normally means I’ve nothing constructive to add.
Rather like this comment :o)
Graph theory is very underrated. Please keep up your posts there as well as here.
Many thanks for your efforts.
I liked the graph stuff better. I’ll read the fractals, too, though.
Harald:
Yes, space filling curves are fractals, and I’d argue that they’re self-similar. Self-similarity isn’t self-isomorphism or self-homeomorphism – it’s approximate similarity of small parts to the larger parts. Space filling beasts like the Hilbert curve certainly do have a kind of self similarity – not a strict precise one like the carpet, but it’s definitely there.
MCC wrote: “Self-similarity isn’t self-isomorphism or self-homeomorphism – it’s approximate similarity of small parts to the larger parts.”
This is especially important when looking at physical systems which have an approximate fractal dimension. A classic paper on this (apologies to those without PRL access) is: “Fractal Geometry of Colloidal Aggregates”, Schaefer et al., Phys. Rev. Lett. 52, 2371 – 2374 (1984). This paper also has a nice demonstration of how to determine fractal dimension from scattering experiments.
fractals! awesome! i discovered these things when i was about eight and they’ve always fascinated me. can we get a discussion of the carpet?
(and pretty pictures please. my degree is in computing science.)
Lepht
In the line “The Seirpinski carpet, for example, is topologically one-dimensional”, Seirpinski should be spelt Sierpinski. Anyway, great post!
I am afraid that you have wandered into something that I might be considered an expert in, so I feel compelled to make a few corrections (apologies in advance):
The Sierpinski curve is universal among planer 1-dim continua (those that are subsets of the plane). The Menger curve is universal among all 1-dim continua. For example the complete graph on 5 vertices is 1-dim but will not embed in the plane (and so cannot embed in the Sierpinski curve). However it does embed in the Menger curve.
For a nice picture of the Menger curve see: http://mathworld.wolfram.com/MengerSponge.html
You just take a cube, and drill the middle one 1/9 out of each face, rinse and repeat.
From a topological standpoint, you can make a Sierpinski curve with area more than 0. (just make your holes smaller)
It will not have the same Hausdorff dimension, but it will still be universal among planer 1-dim continua.
In fact the higher dimensional analogues of Menger continua exist in all dimensions. There is a nice classification of them in Bestivina’s Thesis.
You mean “Sierpiński”. 🙂
Ørjan:
Well, yeah, except that I don’t even know how to type that :-). These silly american keyboards don’t give us any obvious way of typing accents.
The graph theory posts will be great once they connect to some problem that will make us go “Aha!” You started with Bridges of Konigsberg, there must be some more current problem that will turn out to be a graph theory problem.
Until then, pretty fractals 🙂
A follow-up post on the Menger sponge would be nice, as discussing the Sierpenski carpet almost begs for it.
hmm, no ASCII alt code for an accent on a n. That IS a dozy.
So you can cheat and copy one from the wiky entry for the name, Wacław Sierpiński.
You’re confusing topological dimension – which will be an integer and is akin to our natural sense of dimension – and fractal / Hausdorff dimension, which is a way of measuring (in simple terms) how well a shape (or set) fills the space.
So you could consider that the carpet fills the same amount of room as 1.89 of a square of similar size, but is composed only of 1D lines (and so has no area so to speak!).
Mark,
The Hilbert curve is actually self-similar in a precise way, I think. The Osgood curve is not quite, but almost. My use of the phrase “not quite self-similar” back in #13 was carefully chosen, to allow the sort of vague sort of self-similarity that you allude to in #17. So I don’t think we really disagree. OTOH, I don’t think it’s true that all spacefilling curves are self-similar in some vague sense even: That is true only of the tiny minority among them we know how to construct.
By the way, for readers of this blog who can read Norwegian, I have an expository article on the Osgood curve, including some history regarding the Peano and Hilbert curve, available on the web. Even those unfamiliar with the Scandinavian languages may get something out of the pictures. (Technically, it’s not the Osgood curve: Osgood based his construction on the original Peano curve, while I have applied Osgood’s idea to the Hilbert curve instead.)
The graph theory posts will be great once they connect to some problem that will make us go “Aha!” You started with Bridges of Konigsberg, there must be some more current problem that will turn out to be a graph theory problem.
Stephen Wells:
There are many “current problems” as you put it but needs some
groundwork first (think networks and design).
(Emphasis mine.)
Don’t you mean ‘central tetrahedron’ rather than ‘central octahedron’?
llewelly: One can consider the procedure to involve cutting a tetrahedron from each corner, removing everything left in the middle, and then putting the corners back in their original location. The solid removed from the middle then has one face created by each of the four cuts, and an additional face for each of the four faces of the original tetrahedron; this produces an octohedron by simple addition.
llewelly: Rheun answered your question. But I now note that I claimed the Sierpinski tetrahedron has dimension 3, whereas it really has (fractal, or Hausdorff) dimension 2. Duh!
I really *liked* the graph theory stuff. Sorry for not speaking up to that effect sooner.