On a conjecture of Erdős for multiplicities of cliques

Denote by kt(G) the number of cliques of order t in a graph G having n vertices. Let kt(n)=min{kt(G)+kt(G¯)} where G¯ denotes the complement of G. Let ct(n)=kt(n)/(nt) and ct be the limit of ct(n) for n going to infinity. A 1962 conjecture of Erdős stating that ct=21−(t2) was disproved by Thomason in 1989 for all t⩾4. Tighter counterexamples have been constructed by Jagger, Šťovíček and Thomason in 1996, by Thomason for t⩽6 in 1997, and by Franek for t=6 in 2002. We investigate a computational framework to search for tighter upper bounds for small t and provide the following improved upper bounds for t=6,7 and 8: c6⩽0.7445×21−(62), c7⩽0.6869×21−(72), and c8⩽0.7002×21−(82). The constructions are based on a large but highly regular variant of Cayley graphs for which the number of cliques and cocliques can be expressed in closed form. Note that if we consider the quantity et=2(t2)−1ct, the new upper bound of 0.687 for e7 is the first bound for any et smaller than the lower bound of 0.695 for e4 due to Giraud in 1979.