-
Regular link-irregular graphs
In two recent works, Akbar Ali, Gary Chartrand, and Ping Zhang conjecture that there is no regular link-irregular graph. Here “regular” means all vertices have equal degrees and “link-irregular” means all vertices induce non-isomorphic neighborhoods. In support of this conjecture, they show that it is true for degrees three and four. However, the probabilistic method shows this to be false for sufficiently high degrees.
-
Congratulations to three new doctorates!
This has been a busy week for doctoral defenses for me: I attended three, participating in the committees for the last two.
-
Linkage
- In a discussion on Wikipedia (\(\mathbb{M}\)), I asserted that it is typical to group the operations within mathematical formulas into meaningful chunks, analogously to the way we group sequences of sounds or letters into meaningful words. The example I was looking at concerned covering the edges of a random graph \(G(n,\tfrac12)\) by few cliques, for which the number of cliques needed turns out to be
-
Linkage
- Lattice path matroids (\(\mathbb{M}\)). An interesting generalization of the uniform matroids with which I was previously unfamiliar. They are defined by two monotone lattice paths in a rectangular grid, one below the other. The bases are lattice paths between the two defining paths, described by the set of positions at which they step upwards.
-
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
subscribe via RSS