goodmath

Suppose you've got a huge graph - millions of nodes. And you know that it's not connected - so the graph actually consists of some number of pieces (called the connected components of the graph). And there are constantly new vertices and edges being added to the graph, but nothing is ever removed…

There are a lot of very cool problems in computer science that can be solved by using an appropriate data structure; and the data structures are often easiest to describe in terms of graphs. And of those data structures, one thing that often comes up is amortized algorithmic complexity. Amortized…

I've now uploaded nearly all of the Yellowstone pictures. There are two additional photo albums on Picasa: one for the Mammoth Hot Springs area, and one for the Yellowstone canyon. Here are the links: Yellowstone Vacation, Mammoth Hot Springs area Yellowstone Vacation, Canyon Area

I'm back from vacation! There was no network access in Yellowstone, and virtually no cellphone service. Anyway, a bunch of people asked me to post photos. I've got three sets of photographs, for the three main areas of the park that I visited: the Geyser area, the Terrace area, and the Canyon…

Bright and early tomorrow morning, I'm leaving on vacation. I'll be spending the week in Yellowstone National Park. I'm not sure what the network situation is there, but I'm not expecting much. Unfortunately, this year I didn't have time to prepare some reruns of old posts before I left. If I…

The next interesting variant on graphs is directed graphs, or digraphs for short. A digraph is a graph where each edge distinguished between its source and its target - so an edge is from one node, and to another node. Unlike a simple graph, where if A is adjacent to B, then you can follow the…

Aside from the Mandelbrot set, the most famous fractals are the Julia sets. You've almost definitely seen images of the Julias (like the ones scattered through this post), but what you might not have realized is just how closely related the Julia sets are to the Mandelbrot set. Remember what the…

A bunch of readers, and one commenter in another thread, have all hit me with a pathetic monstrosity of a purported proof of God. Several have even been misled by the URL where the dreadful thing is posted, thinking that ScienceBlogs have picked up a creationist. Rest assured, this bozo and his…

This weekend, Seed Media, our benevolent and beloved corporate overlords, sponsored a Scibling gathering: ScienceBloggers from all over the country (and outside) all gathered in New York, ate, drank, and partied. It made for quite an interesting weekend. I didn't end up being able to hang around…

Sonic Youth, "Or": Very smooth for SY. But great. They're an amazing band. The Flower Kings, "Blue Planet": A typical track from one of my favorite neo-progressive rock bands. For the Flower Kings, this is a short one at only 10 minutes. The Clogs, "Lantern": once again, one of my favorite…

My friend and blog-father Orac sent me a truly delectable piece of bad math today. It's just astonishing: a supposed mathematical model for why homeopathic dilution works, and for why the standard dilutions are correct. It's called "The octave potencies convention: a mathematical model of dilution…

This post is quite thoroughly off-topic for this blog. But as someone who is openly religious and who has written a number of posts that criticize Christian institutions, I get a fair bit of mail from cretins who make demands that I speak up to defend their pathetic insistence that all religious…

One of the reasons that I like about graph theory so much is because of how it ties into computer science. Graphs are fundamental to many problems in computer science, and a lot of the work in graph theory has direct implications for algorithm design. It also has a lot of resonance for me, because…

One amusing thing in graph theory is graph traversal. Many of the interesting algorithms on graph are ultimately based on the idea of iterating through the nodes of the graph in some order that is related to the structure of the graph. There are two fundamental orders of graph traversal, known as…

Despite having written about it before, I still get a lot of questions about William Dembski's "No Free Lunch" (NFL) theorems. One message recently contained the question in a particularly interesting form, so I thought I'd take the opportunity to answer it with a post. Here's the question I…

Another really fun and fundamental weighted graph problem is the shortest path problem. The question in: given a connected weighted graph G, what is the shortest path between two vertices v and w in G? To be precise, the weight of a path is just the sum of the weight of the edges that make up the…

Once upon a time, I wrote about a jackass who was criticizing his college math instructor, because the instructor couldn't explain what made the calculus class christian, or why it was different from what would be taught in a math class at a secular college. That kind of thinking is quite strong…

One of the most fundamental properties of fractals that we've mostly avoided so far is the idea of dimension. I mentioned that one of the basic properties of fractals is that their Hausdorff dimension is larger than their simple topological dimension. But so far, I haven't explained how to figure…

I got started on this series about graph theory by writing a post debunking something foolish that George Gilder said about network theory. Today I'm going to talk about one of the classic problems in graph theory, which happens to be a network problem. It's called the maximum flow problem. The…

So, in my last post, I promised to explain how the chaos game is is an attractor for the Sierpinski triangle. It's actually pretty simple. First, though, we'll introduce the idea of an affine transformation. Affine transformations aren't strictly necessary for understanding the Chaos game, but…

There's one piece of bad math that I've encountered relatively frequently in conversations. It's incredibly frustrating to me, because it's just so crazy - but the way we teach math and physics, far to many people just don't have enough of a clue to see how foolish it really is. This comes up…

Most of the fractals that I've written about so far - including all of the L-system fractals - are examples of something called iterated function systems. Speaking informally, an iterated function system is one where you have a transformation function which you apply repeatedly. Most iterated…

As I alluded to yesterday, there's an analogue of L-systems for things more complicated than curves. In fact, there are a variety of them. I'm going to show you one simple example, called a geometric L-system, which is useful for generating a certain kind of iterated function fractal; other…

Moving on from simple graphs, one of the things you can do to make things more interesting is to associate numeric values with the edges, called the weights of those edges. This variation of a graph is called a weighted graph. Weighted graphs are extremely useful buggers: many real-world…

In the post about Koch curves, I talked about how a grammar-rewrite system could be used to describe fractals. There's a bit more to the grammar idea that I originally suggested. There's something called an L-system (short for Lindenmayer system, after Aristid Lindenmayer, who invented it for…

While reading Mandelbrot's text on fractals, I found something that surprised me: a relationship between Shannon's information theory and fractals. Thinking about it a bit, it's not really that suprising; in fact, it's more surprising that I've managed to read so much about information theory…

One of the strangest things in fractals, at least to me, is the idea of space filling curves. A space filling curve is a curve constructed using a Koch-like replacement method, but instead of being self-avoiding, it eventually contacts itself at every point. What's so strange about these things…

Often, we use graphs as a structured representation of some kind of information. Many interesting problems involving the things we're representing can then by described in terms of operations over graphs. Today, I'm going to talk about some of the basic operations that we can do on graphs, and in…

After seeing PZs comments on Stuart Pivar's new version of his book, titled "Lifecode: From egg to embryo by self-organization", I thought I would try taking a look. I've long thought that much of the stuff that I've read in biology is missing something when it comes to math. Looking at things, it…

I got hit by a mutant meme; I don't remember who tagged me. I'm not terribly into these meme things, but I don't pass up excuses to post recipes. So below the fold are four recipes that I've created: seared duck breast with ancho chile sauce; saffron fish stew; smoked salmon hash; and spicy…