Using your Head is Permitted

March 2016 solution

The answer is that this ratio is at most 5/6.

To prove this, let us consider, as in the December riddle, a weighted average between the number of appearances of L2, K2,3 and T+, which we'll henceforth call our "usual suspects". (Here and throughout, we use terminology defined in the December 2015 riddle and its solution.) This time we will use the following weighing of these three graphs:

0.6 #(L2) + 0.3 #(K2,3) + 0.1 #(T+) = Σi Xi (3/5 + i(i-1)/20) = Σi Xi (1/20 i2 - 1/20 i + 3/5)

For each i value, the number of appearances of C4 is Xii/4, so the ratio between the number of C4 appearances and the weighted average number of appearances of the three other graphs mentioned is for each i equal to i/(1/5 i2 - 1/5 i + 12/5). Differentiation shows that this function increases when i≤3 and decreases when i≥4, so the fact that at both i=3 and i=4 it equals 5/6 means that this is the maximum over all i.

The ratio over all i is a weighted average over these local ratios, so it, too, cannot be greater than 5/6.

To describe a graph G for which this ratio is exactly 5/6, let us first consider three simpler graphs. The first graph is "C4 x C3". The notation "G x H" for two graphs G and H indicates the graph whose vertices are the pairs

{ (g,h) | g in V(G), h in V(H) }

and whose edges are

{ ((g1,h1),(g2,h2)) | (g1 = g2 or (g1,g2) in E(G)) and (h1 = h2 or (h1,h2) in E(H)) and ((g1,h1) ≠ (g2,h2)) }

The other two are K4,4 and K5,5, where Kn,n is the complete bipartite graph with n vertices on each side.

We use these graphs because in each of them all Xi are zero except X3 and X4. Each of them has one of our "usual suspects" appear in more than the desired amount, but each of the usual suspects appears in less than the desired amount in at least one.

Our target graph, G will be the following:

G = 100 (C4 x C3) + 225 K4,4 + 108 K5,5
This notation means that G is not a connected graph: it is composed of 100 disjoint components isomorphic to C4 x C3, a further 225 components isomorphic to K4,4, and a further 108 components isomorphic to K5,5.

The structure of this 4080-vertex graph makes the number of appearances in any subgraph of it quite easy to compute. In particular, the numbers have been designed so that all of our usual suspects will have exactly the same number of appearances, 32,400, meaning that the number of appearances of C4, 27,000, is exactly at the desired ratio, 5/6, of this number.

To complete the proof, however, we still need to show that our usual suspects are the most frequent connected induced subgraphs of G. To prove this, note that all subgraphs of K4,4 and K5,5 are bipartite, while almost all connected induced subgraphs of C4 x C3 except the single vertex and single edge subgraphs include a triangle, so cannot be bipartite. The subgraphs that do not appear in both types of components will certainly not appear more than the maximum frequency connected induced subgraphs of these components, which are our usual suspects.

All in all, there are 5 subgraphs of G that have the same maximal frequency, 32,400. These are our three usual suspects, a 6-node subgraph with the adjacency matrix 

011110
101110
110001
110011
110101
001110

and a 7-node subgraph with the adjacency matrix 

0110011
1011100
1101100
0110111
0111011
1001101
1001110

Q.E.D.

I am not aware of any connected G that satisfies the criteria of this riddle. Any reader who discovers such a G is most welcome to send me its description.

Back to riddle

Back to main page