Tripartite classification conjecture for connected derangement graphs

Let GG be a transitive permutation group of degree nn, let ρ(G)\rho(G) be its intersection density, and let ΓG\Gamma_G be its derangement graph. Assume that ΓG\Gamma_G is connected.

Tripartite classification conjecture. If

ρ(G)=n3,\rho(G)=\frac{n}{3},

then ΓG\Gamma_G is complete tripartite.

The conjecture concerns the extremal case of the general upper bound ρ(G)n/3\rho(G)\leq n/3. The source notes that complete tripartite derangement graphs are known in several examples, but does not provide a resolution of this classification claim.

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.