Conjectures for maximum intersection density by permutation-group degree

Let I(n)I(n) denote the maximum intersection density among transitive permutation groups of degree nn. For a transitive group GG of degree nn, let ΓG\Gamma_G be its derangement graph.

Conjectures for I(n)I(n).

  1. If nn is even but not a power of 22, then there is a transitive group GG of degree nn such that ΓG\Gamma_G is a complete multipartite graph with n/2n/2 parts.
  2. If nn is a prime power, then I(n)=1I(n)=1.
  3. If n=pqn=pq where pp and qq are odd primes, then I(n)=1I(n)=1.
  4. If n=2qn=2q where qq is prime, then I(n)=2I(n)=2.

These conjectures are based on computational evidence for transitive groups of degree at most 4848. The source presents them as conjectural values and constructions for the maximum intersection density.

Sources & referencesView supporting material

Primary source

Andriaherimanana Sarobidy Razafimahatratra, Karen Meagher and Pablo Spiga, “On triangles in derangement graphs”, arXiv:2009.01086 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.