-
Invertible Bloom antimatroids
I’ve written here many times about ready lists, the familiar programming pattern in which you collect actions to be performed and pull them off the list one at a time to perform them, and about antimatroids, the algebraic structure generated by the orderings of events that you can get in this way. Here’s another example that I didn’t notice until recently, despite it being prominent in my own publications: the peeling sequences of invertible Bloom filters and invertible Bloom lookup tables.
-
Linkage
- The code that revolutionized orbital simulation (\(\mathbb{M}\)), video by braintruffle on how updating velocity and position sequentially rather than in parallel causes orbital simulations to preserve symplectic invariants and thereby become much more stable.
-
Winter break linkage
- Elsevier is resisting a push by Australian and NZ academics to include its journals in a uniform open-access agreement (\(\mathbb{M}\), archived, via), and especially resisting providing “pricing transparency”. The situation may result in a boycott. As the article notes, the situation resembles past breakdowns in negotiations with Elsevier and ensuing boycotts including one from 2018 to 2023 in Germany and another from 2019 to 2021 in California.
-
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”.
subscribe via RSS