-
Hanoi graphs redrawn
A Hanoi graph is an abstract representation of the well-known Tower of Hanoi puzzle, in which one stacks disks of different sizes on several pegs (usually three pegs). Initially the disks are all on one peg, and one must get them all to another peg by moving one disk at a time, without ever placing a bigger disk on a smaller disk. The vertices of the graph are all valid states of the puzzle: placements of disks on pegs in sorted order with the largest at the bottom and smallest at the top. Its edges represent valid moves of the puzzle. For any puzzle with \(p\) pegs and \(n\) disks, there is a Hanoi graph parameterized by \(p\) and \(n\), with \(p^n\) vertices.
-
Entropy in algorithm analysis
What follows are some half-baked ideas for how the quantity called “entropy” used in some forms of algorithm analysis for algorithms including sorting and convex hulls can justify being called entropy.
-
Linkage
- Well-meaning but misguided editors are using AI to translate Wikipedia into vulnerable languages (\(\mathbb{M}\)). The result is to accelerate the deterioration of online content in these languages, sending them into a “doom spiral”.
-
The hyperbolic spiral as a trisectrix
It is, of course, impossible to subdivide an arbitrary angle into equal thirds using a compass and straightedge alone. But there are many known constructions that rely on other techniques. One of those techniques is the use of a trisectrix, a curve of a special form that is assumed to be already drawn for you, so that with your compass and straightedge you can find its crossing points with lines and circles. More strongly, some curves can be used as a “sectrix” to subdivide an angle into any given number of equal parts; these include the Archimedean spiral, quadratrix of Hippias, and sine curve.
-
Hamiltonian-paired graphs
The five-vertex complete graph \(K_5\) is commonly drawn with its vertices on a regular polygon. In this layout, it is easy to find two Hamiltonian cycles that are complementary to each other, forming a Hamiltonian decomposition: the outer pentagon and the inner pentagram. In fact in this graph every Hamiltonian cycle is complementary to another one: the complement graph must be 2-regular (because a Hamiltonian cycle uses exactly two of the four edges at each vertex, leaving another two) and the only two-regular graph on five vertices is a cycle.
-
Linkage
-
Linkage with feijoas
- The season’s first feijoas (aka pineapple guavas) fell from the trees in my front garden (that’s how to tell they are ripe). They are the ones in the bowl on the right; other fruit included for scale (\(\mathbb{M}\)).
-
Norrköpingsfallen
I just returned from the International Symposium on Graph Drawing and Network Visualization, held this year in Norrköping, Sweden. Norrköping was an early paper and textile milling town, set at the mouth of the Motala ström, a river that flows into the Baltic Sea. At this point of the river, a cascade of three waterfalls, Norrköpingsfallen, provided power for the mills. The old industrial buildings surrounding the falls have largely survived but been turned to other uses. The conference was held in the Louis de Geer Concert & Congress, at the lowest and biggest of these falls. Despite having long since been dammed and tamed, it was still spectacular.
-
Linkage
- A crowdsourced project to link erdosproblems.com with OEIS (\(\mathbb{M}\), see also), launched by Thomas Bloom and Terry Tao.
-
Planarizing matchings
The drawing below shows the Petersen graph (blue vertices), with order-six dihedral symmetry rather than the order-10 symmetry that you’re probably more used to. Three edges are highlighted by shaded ovals surrounding them; these edges form a matching, a set of edges that don’t touch each other. If you contract these edges, you get a graph with seven vertices: the three ovals and the remaining four blue vertices. This seven-vertex graph is planar, because all of the Petersen graph’s crossings are hidden inside the ovals. It turns out that, whenever you can contract a matching to make the resulting graph planar, the graph you started out with (here, the Petersen graph) is a string graph. This means that we can draw a curve in the plane (called a string) for each vertex of \(G\), so that two strings intersect if and only if the corresponding vertices are adjacent. Strings are allowed to intersect any number of times, not just once.
subscribe via RSS