Contando $K_4$ está en un gráfico de Paley

Question

Deje que $p \equiv 1 \pmod {4}$ ser el primero, y dejar que $G$ ser un gráfico tal que $|V(G)| = p$ y $\{u,v\} \in E(G) \Longleftrightarrow u-v \equiv x^2 \pmod {p}$ para algunos enteros $x$ .

¿Cuántas veces $G$ contienen $K_4$ como un subgrafo?

---

Alternativamente, se puede pedir el número de subconjuntos $S = \{u_1, \ldots ,u_4\} \subset \mathbb {Z}_p$ de tal manera que $u_i - u_j$ es un residuo cuadrático para $i,j \in \{1, \ldots ,4\}$ , $i \neq j$ .

Answer 1

¿Hay alguna razón por la que necesites hacer esto, o sólo tienes curiosidad? Este documento tiene una fórmula, pero resumir el argumento sería una forma de anhelar que lo pusiera aquí: http://www.math.ucsd.edu/~revans/Pulham.pdf

Computacional también es bueno (computado en Magma):

p = 5 Número de subgrafías de K4: 0

p = 13 Número de subgrafías de K4: 0

p = 17 Número de subgrafías de K4: 0 *

p = 29 Número de subgrafías de K4: 203

p = 37 Número de subgrafías de K4: 555

p = 41 Número de subgrafías de K4: 1025

p = 53 Número de subgrafías de K4: 3445

p = 61 Número de subgrafías de K4: 6100

p = 73 Número de subgrafías de K4: 13140

p = 89 Número de subgrafías de K4: 31328

p = 97 Número de subgrafías de K4: 46560

Vale la pena señalar que para $p=17$ el gráfico de Paley es el gráfico más grande $G$ para el cual ninguno de los dos $G$ ni $G^{C}$ contienen una copia de $K4$ .]