A paper, “Guessing games on triangle-free graphs”, by Anh Dang, Søren Riis, and me, has just appeared in the Electronic Journal of Combinatorics. Here is a brief discussion of what it is about. It is always a pleasant surprise when highly symmetric structures like the Higman–Sims graph turn up playing an important role in a topic far away from finite group theory (in this case, network coding).
Guessing number
The guessing number of a directed graph is a parameter arising in network coding, and was introduced by Søren Riis. You don’t need to know that background in order to understand the problem; just bear in mind that, even if it looks a bit artificial, there is an important practical problem underlying it.
The guessing game works like this. Each of n people is wearing a hat, of one of q colours. Players cannot see their own hats, and indeed they cannot see all the other hats. There is a directed graph G whose vertices are the players, and each player can see only the hat colours of his/her out-neighbours. The task of the players is for each player to guess his or her own hat colour. It is a cooperative game, the aim being to maximise the probability that all guesses are correct (assuming that the hat colours are randomly assigned).
If the players guess at random, then the probability that all guesses are correct is 1/qn. To see that considerable improvement is possible, consider the case of the complete directed graph, where each player can see the hats of all other players. In this case, it is possible to achieve a probability 1/q that all guesses are correct, by the following strategy. Regard the hat colours as elements of the integers modulo q. The players agree beforehand to assume that the sum of all the hat colours is zero mod q. The probability that this assumption is correct is 1/q. Now each player makes this assumption, and guesses that his/her own hat colour is minus the sum of all the others; if the assumption is correct, then all players guess correctly.
For information-theoretic reasons, we take a measure of the success of a strategy to be the logarithm, to base q, of the factor by which the probability of success is improved using that strategy, compared to guessing at random. Thus, for the complete directed graph, the above strategy gives the value n−1.
The guessing number gn(G,q) is defined to be the best value which can be achieved by any strategy, assuming that the best strategy is used; that is, the maximum over all strategies. The asymptotic guessing number gn(G) is the limit of this value as q→∞. (It can be shown that this limit exists, even though the guessing number is not a monotone function of q.) It is not hard to show that the guessing number of the complete directed graph is n−1, and that the strategy given is optimal.
From now on, we consider undirected graphs (with the convention that an undirected edge is a pair of directed edges, one in each direction).
Fractional clique cover number
A fractional clique cover of a graph G is a weighting of the cliques of G with real numbers from the unit interval [0,1] with the property that, for any vertex v of G, the sum of the weights of the cliques containing v is at least 1; it is regular if the sum is equal to 1 for every vertex. The fractional clique cover number is the minimum, over all fractional clique covers, of the sum of the weights of all the cliques. It can be shown that the same minimum value is obtained if we restrict to regular fractional clique covers.
I won’t give the general proof, but in the special case where there is an exact covering of the vertices by d cliques, it is easy to see that the guessing number is at least n−d: each player lies in exactly one of these cliques, and the players in that clique use the guessing strategy defined above for a complete graph.
Christofides and Markström showed that, for an n-vertex graph G, the guessing number is bounded below by n−κ(G), where κ(G) is the fractional clique cover number of G. They showed, moreover, that this bound is attained for various classes of graphs including perfect graphs, odd cycles, and complements of odd cycles. On the strength of this, they conjectured that the bound is always attained.
Triangle-free graphs
An obvious test case consists of triangle-free graphs, where the only cliques are vertices and edges. Clearly, the fractional clique cover number is at least n/2 in such a graph. In a regular graph, this bound is attained: if the valency is k, give each edge the weight 1/k.
Our paper shows that the bound of Christofides and Markström can be far from the truth, by using the famous triangle-free strongly regular graphs which I discussed here: the Higman–Sims graph on 100 vertices and various of its subgraphs.
The proof depends on two simple ideas.
- Suppose that a triangle-free graph is regular with valency k, and has the property that any two non-adjacent vertices have exactly μ common neighbours. Then the adjacency matrix A of the graph satisfies AJ = JA = kJ and A2 = kI+μ(J−I−A), where J is the all-1 matrix. This is a simple exercise in matrix multiplication.
- Given a graph G on n vertices, let M be a square matrix of order n (whose rows and columns are indexed by vertices of G) with entries from the finite field of order q, having the properties
- the diagonal entries of M are not zero;
- if the off-diagonal (i,j) entry is non-zero, then i and j are adjacent in G.
If M has rank d, then the guessing number of G is at least n−d. This is shown by making the assumption that the assignment of hat colours is a vector in the null space of M (this assumption has probability 1/qn−d); each player makes this assumption, looks at the corresponding row of M, and computes his/her hat colour from the assumption that the linear combination of hat colours using the player’s row of the matrix as coefficients is zero.
Now the Higman–Sims graph satisfies our assumptions with k = 22 and μ = 6. From this it is easy to show that, over the field of three elements, M = A+I has rank 23, so that the guessing number is at least 77; the Christofides–Markström lower bound is 50. (Working mod 3, we have A2 = I, so that M(M+I) = 0, so the eigenvalues of M are 0 and −1. Now the principal submatrix corresponding to the 22 neighbours of a point is the identity, and the all-1 vector is not in their span – it would have to be their sum, but each non-neighbour has coefficient 0 in the sum. So the rank is at least 23. It is not hard to show that these 23 vectors span the row space, so we have equality.)
Moreover, this graph can be “blown up” to give an infinite family of examples. Further examples come from the other triangle-free strongly regular graphs.
As an aside, we know that the asymptotic guessing number of the Higman–Sims graph is at least 77, and at most 78. What is it? (Note that guessing numbers are not necessarily integers!) Another open problem is whether there exist triangle-free graphs G on n vertices with with gn(G) > 78n/100.
Peter Cameron's Blog 
Very intresting!