For given block sizes $a<b<c<d$, consider the complete 4-partite graph $K_{a,b,c,d }$.

- Can such a graph be integral, i.e. have only integer eigenvalues?

It is easy to see that the four nonzero eigenvalues of $K_{a,b,c,d }$ are the same as those of $$\begin{pmatrix} 0&b&c&d\\ a&0&c&d\\ a&b&0&d\\ a&b&c&0 \end{pmatrix}$$ because the corresponding eigenvectors must have the same entry inside each block.

So we can consider instead the characteristic polynomial of this matrix, $$\lambda^4-(ab+ac+ad+bc+bd+cd) \lambda^2- 2( a b c+abd+acd+bcd) \lambda-3 a b c d.$$

Though not related, it reminds me of the question about the existence of perfect Euler bricks.

The corresponding question for tripartite graphs with pairwise different block sizes has been settled here.

I have done an exhaustive computer search for all quadruples with $d\leqslant 200$ and found none with four integer eigenvalues. Many of them have exactly one integer eigenvalue, and a few have *two*, e.g. $K_{8,15,32,40}$. The complete list of the latter solutions (that is, the coprime ones) follows, including each time the two integer eigenvalues $λ1 <λ2$.

```
d c b a λ1 λ2
40 32 15 8 -36 -20
42 28 15 7 -35 63
56 41 32 24 -36 112
64 44 24 9 -54 -96
72 18 9 2 -12 54
77 48 35 3 -63 -40
79 75 35 11 -77 -45
91 89 40 15 -90 -52
93 75 40 7 -84 -50
102 70 63 50 -54 210
104 56 48 39 -84 -52
105 96 70 55 -80 -60
112 56 40 7 -84 140
112 57 30 21 -84 -24
112 100 99 84 -108 -88
117 83 40 25 -100 -54
117 90 40 18 -54 180
117 91 48 13 -104 182
119 54 24 14 -84 -34
128 80 63 12 -70 192
130 39 18 13 -78 -26
130 91 67 32 -112 -39
133 47 40 15 -90 -19
135 110 72 54 -60 270
144 54 14 9 -24 126
145 70 33 15 -105 -45
160 40 8 7 -84 -16
160 104 65 40 -80 260
165 22 21 7 -77 -9
165 102 44 12 -132 -60
168 40 15 12 -90 -24
168 40 32 25 -100 -36
168 57 25 15 -105 -36
175 80 69 63 -135 -75
175 85 63 60 -135 -75
175 87 63 55 -135 -75
175 90 63 45 -135 -75
175 93 63 30 -135 -75
175 95 63 15 -135 -75
175 96 63 5 -135 -75
175 111 55 39 -143 -75
175 141 130 63 -135 -75
175 150 125 63 -135 -75
175 155 123 63 -135 -75
175 165 120 63 -135 -75
176 40 15 4 -90 -22
180 175 117 63 -135 -75
187 163 75 35 -175 -99
192 88 33 12 -48 198
195 57 48 35 -126 -39
195 117 104 69 -78 351
195 144 116 104 -174 -130
195 175 115 63 -135 -75
200 52 48 35 -126 -50
200 98 35 2 -50 196
```

- Note that in those quadruples, a few primes do occur. But among the eigenvalues... the first prime ($-19$) only appears at $d=133$ and is so far the only one!
- So far, all prime factors of the eigenvalues divide at least one of $a,b,c,d$.
Moreover, if the two eigenvalues have a common prime factor, it divides most often (but sadly not always) three of $a,b,c,d$.

And now: What is happening for $d=175$? All solutions except $(175, 111,55, 39)$ not only have the same two integer eigenvalues $-135$ and $-75$, but also have $63$ among the block sizes. This includes as well the solutions $(180, 175, 117, 63 )$ and $(195, 175, 115, 63)$ and possibly more with larger $d$'s.

**How to explain such a "cluster"?**

Similarly, the pair of block sizes $(40,7)$ co-occurs several times with the eigenvalue $-84$.

This all is obviously intriguing and raises the following question, which is interesting on its own, whether or not integral graphs exist:

- In terms of elliptic functions, is it possible to characterize the solutions $(a,b,c,d)$ with two integer nonzero eigenvalues?