I’ve been in a bit of a problem-posing mood recently. Hopefully I’ll do some problem-solving soon. Here are a few questions I’ve thought of but haven’t got solutions for. I haven’t done any literature searching, so these might have been done before.
All the problems are quite computery. Maybe I’m a computer scientist, really.
Problem 1: Reordering the alphabet
What reordering of the letters of the alphabet contains the most (contiguous) English words? This is a big search space problem. I did a little bit of tinkering in python, trying first of all to find the single word which contains the most smaller words.
The output: (I can only apologise for the rather rude result!)
My current line of thinking is that if you draw out the complete graph on 26 vertices (one for each letter), words are paths on that, and the question is to find the Hamiltonian cycle which traces over the most complete paths. Not sure if that helps matters or not.
Problem 2: graph symmetries
Suppose you have a graph $G$ and its automorphism group $Aut(G)$. In particular, suppose you know all the “lines of symmetry” of the graph – pairs of edges around a vertex which can be swapped, or pairs of vertices at the ends of an edge which can be reflected.
If you add an edge (or a vertex) to the graph, can you work out how the automorphism group changes?
This is probably a problem for a) 5 minutes on google scholar, b) 5 minutes on mathoverflow, or c) 5 minutes’ thinking.
Problem 3: A princess kidnapped by a robot on a graph
This is a further generalisation of the princess in a castle puzzle. The princess still inhabits a graph, but the way she moves is changed. In the classic puzzle she could move to any adjacent room. What if her movements are determined by a nondeterministic finite state automaton? If you know how the automaton works but not its input, for which graphs can you catch the princess?
FSAs, if you don’t care about what the input is, are equivalent to directed graphs, and extending the princess on a graph puzzle to directed graphs is already hard enough. But that’s a bit of a red herring, because if you draw out the transition diagram of the FSA, where “room the princess is in” is an extra bit of state, you have multiple vertices for each room. That might make things easier or just more complicated.