• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Working paper

On a question of Sidorenko

Cherkashin D., Sokolov V., Petrov F.
In a very recent paper Sidorenko stated the following problem: Let Gk be a graph whose vertices are functions f : Zk → Zk. A pair of vertices {f, g} forms an edge in Gk if f − g is a bijection. Lemma 2 restates the fact that Gk has no triangles when k is even. For odd k, the problem of counting triangles in Gk has been solved asymptotically in [1]. Let p(k) be the smallest prime factor of k. The p(k) functions f0, f1, . . . , fp(k)−1, where fi(j) := i· j mod k, form a complete subgraph in Gk. It is very tempting to conjecture that p(k) is indeed the size of the largest clique in Gk. We know that this is true for even k and for prime k. Computer search confirms that this is also true for k = 9. It turns out that there is a counterexample for k = 15.