Conjectures for maximum intersection density by permutation-group degree

At least 5 years old · documented by

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.

References

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.