
Celtix is NPcomplete
Celtix is a puzzle recently developed by Andrew Taylor, in which one is given a rectangular array filled with thick diagonal lines that reflect off the walls of the rectangle to form a crisscrossing knotted pattern.

Linkage
 Congratulations to Robert Hickingbotham (\(\mathbb{M}\)), a student of David Wood at Monash University who just finished his PhD with an impressive portfolio of research in graph structure theory. Next step: a postdoc at ENS Lyon.

Linkage
 Discrete spirographlike patterns from Gaussian periods and their analogues (\(\mathbb{M}\), via): see figures by Samantha Platt, based on her paper “Visual aspects of gaussian periods and analogues” which has many more. Here the Gaussian periods are certain sums of roots of unity.

Teachable suffix tree construction
I often cover suffix trees in my algorithm and data structure classes, but until now haven’t generally covered the algorithms to build them. These are data structures describing the suffixes of a string (start at any position of the string and continue until the end), useful in many string algorithms.

Congratulations, Dr. Khodabandeh!
‘Tis the season for dissertation defenses and candidacy exams, and my doctoral student Hadi Khodabandeh successfully defended his dissertation today.

Linkage
 Lots of flat foldable structures with arbitrary crosssections. Images from a talk whose slide titles appear to be related to “Generalizing rigidfoldable tubular structures of Thedral type”, a 2023 preprint by Sharifmoghaddam, Maleczek, and Nawratil.

Congratulations, Dr. Ozel!
I participated today in the successful doctoral defense of Evrim Ozel, one of Mike Goodrich’s students at UCI. Evrim is Turkish, and came to UCI from Middle East Technical University in Ankara.

Linkage

Gray parking?
After another Good Article pass for an article on ordered Bell numbers, I thought it might be interesting to investigate Gray codes for the things counted by these numbers. That is, one would like to find a sequence (or preferably a cyclic sequence) through all of the things, making only a small change from thing to thing, preferably easy to compute.

Random perfection
The Wikipedia article on perfect graphs is now a Good Article! Along the way, the reviewer asked me whether random graphs are likely to be perfect. I didn’t have a published source for that, so you won’t find it in the article. But as with most properties of random graphs, the answer depends how dense you want the graph to be. In the usual Erdős–Rényi–Gilbert \(G(n,p)\) model of random graphs, we fix \(n\) vertices and include each edge independently of the others with probability \(p\). This turns out to have two phase transitions, between graphs that are likely to be perfect and graphs that are likely to be imperfect, one when the edge probability is \(\tfrac1n\) and another when it is \(1\tfrac1n\). More precisely, if I’m not mistaken (which I could easily be):
subscribe via RSS