One of my colleagues has an interesting combinatorial problem, perhaps the mathematically-minded among you might be interested to think trying to find a solution:
“I’m trying to work out the minimum size of a colouring of strings on a finite ordered alphabet, as follows.
Let Q be the set of integers from 1 to q, {1,…,q}
We consider all strings of length n on Q represented as path graphs with labelled edges:
Let G be the set of all qn path graphs consisting of n+1 nodes and n edges where there is an edge between node ni and ni+1 for each i = {1,…,n} and each edge is labelled with a integer from Q.
For any two nodes e and g on a graph in G, let max(e,g) be the highest label on the path between e and g.
Each node x in each graph in G is assigned a colour colour(x) from a set of colours C such that the following constraint holds:
For any pair of colours (a,b) from C, there is an integer f(a,b) in Q, such that whenever a and b appear on a graph in G, say colour(x) = a and colour(y) = b, then max(x,y) = f(a,b).
Question:
- If q is constant, what is the minimum size of C?
- What is the minimum number of colours I need to colour there graphs so that the maximum label between a pair of colours is always the same?
So far, I’ve manage to bound the minimum size of C between O(nq) and Ω(n logn). ie. O(nq) colours are sufficient but it can’t be done with fewer than Ω(n logn) colours.
Can you
- Show that there is a colouring of size O(n logn) or
- Come up with a higher lower bound? For example, show that a colouring has to be at least say 0.5n0.5q to respect this constraint
This problem has ratifications on unsolved problems in complexity theory related to the complexity of parity games and modal mu.”
Any thoughts? It has been far too long since I have done any real maths.
