This is inspired by a [recent question about complete multipartite integral graphs](https://mathoverflow.net/questions/225251/can-a-block-matrix-with-at-least-3-zero-blocks-of-different-size-on-the-diagonal/225289#225289). I am wondering if more can be said about tripartite integral graphs with block sizes $a<b<c$. It is easy to see that their three nonzero eigenvalues are the same as those of $$\begin{pmatrix} 0&b&c\\ a&0&c\\ a&b&0 \end{pmatrix}$$ because the corresponding eigenvectors must have the same entry inside each block. From Cardano's formula we get as a necessary condition for integer eigenvalues of this $3\times3$ matrix that $$\Delta=(ab+ac+bc)^3-27(abc)^2$$must be a square.  

(Or, in terms of their reciprocals $u,v,w$, which can be wlog required to be integers, $$\Delta'=\frac{(u+v+w)^3}{uvw}-27$$ must be a square.)  

Note that this condition is not sufficient; e.g. for $c<550$ it is fulfilled by $86$ coprime triples, but only for $71$ of them the eigenvalues are integers.


Here are the triples for $c<550$.



```
          a,b      c             λ1    λ2   λ3
        5     8    12           -10    -6   16
    *   5    12    77           -33    -7   40
       13     4    48           -26    -6   32
       13     7    45           -26    -9   35
       13    24    28           -26   -16   42
       17     3    65           -34    -5   39
       17    12    56           -34   -14   48
       17    33    35           -34   -21   55
       25     9    91           -50   -13   63
       25    12    88           -50   -16   66
       29    36    80           -58   -32   90
       29    39    77           -58   -33   91
       37    15   133           -74   -21   95
       37    16   132           -74   -22   96
       37    63    85           -74   -45  119
       41    11   153           -82   -17   99
       41    24   140           -82   -30  112
       41    60   104           -82   -48  130
    *  45   136   396          -240   -66  306
    *  49   220   441          -315   -77  392
       53     5   207          -106    -9  115
       53    44   168          -106   -48  154
       53    95   117          -106   -65  171
       61    13   231          -122   -21  143
       61    40   204          -122   -48  170
       61    84   160          -122   -70  192
       65     8   252          -130   -14  144
       65    51   209          -130   -57  187
       65    99   161          -130   -77  207
       73    84   208          -146   -78  224
       73   105   187          -146   -85  231
       85    21   319          -170   -33  203
       85   112   228          -170   -96  266
       89    20   336          -178   -32  210
       89    57   299          -178   -69  247
       89   176   180          -178  -110  288
       97   115   273          -194  -105  299
       97   136   252          -194  -112  306
      101    63   341          -202   -77  279
      101   143   261          -202  -117  319
      101    24   380          -202   -38  240
      109    96   340          -218  -102  320
      109   189   247          -218  -133  351
      109     7   429          -218   -13  231
      113   144   308          -226  -126  352
      113    84   368          -226   -96  322
      113    17   435          -226   -29  255
      125   221   279          -250  -153  403
   *  125   357   500          -425  -175  600
      137   203   345          -274  -161  435
      137   152   396          -274  -144  418
      145   112   468          -290  -126  416
      145    99   481          -290  -117  407
      149   260   336          -298  -182  480
      149    69   527          -298   -93  391
      149    56   540          -298   -80  378
      157   276   352          -314  -192  506
      157   135   493          -314  -145  459
      169   220   456          -338  -190  528
      169   217   459          -338  -189  527
      173   285   407          -346  -209  555
      181   220   504          -362  -198  560
      185   308   432          -370  -224  594
      193   364   408          -386  -238  624
      197   255   533          -394  -221  615
  * * 200    44   525          -330   -70  400
      205   391   429          -410  -253  663
   *  225   200   252          -240  -210  450
      233   464   468          -466  -288  754
      241   451   513          -482  -297  779

```

Note that most often, $\lambda\_1=-2a$ or $\lambda\_1=-2b$ (BTW the table is sorted by this $a$ or $b$ in the first column, sometimes swapping $a$ and $b$). If we denote the entries of the first column by $a$, all these values have only divisors of the form $4k+1$, moreover each time $b+c=4a$. Further, $\lambda\_2$ (and also $\lambda\_3$, because $\lambda\_1$ is even and the trace is $0$) has the same parity as $b$. I suppose all this can be explained easily by somebody who is knowledgeable about the properties of the related elliptical curve.  

**But the really intriguing thing are the exceptions where $-\lambda\_1$ is *not* the double of $a$ or $b$. They are marked by $\*$.**



> 
> * What about these exceptional triples? Are there infinitely many of them?
> * For the regular triples, does each prime $p=4k+1$ occur at least three times as one of $a$ or $b$?  
> 
>  (So far, $13$ and $17$ even occur four times)
> * Are there infinite families of co-prime triples which can be explicitely given (e.g. by a recursion)?
> 
> 
> 


I have also done a similar exhaustive search for 4-partite graphs with block sizes $a<b<c<d$. For $d<80$, there are none, but there are some, e.g. $K\_{8,15,32,40\ \ }$ or $K\_{3,35,48,77\ \ }$, which have two integer nonzero eigenvalues.



> 
> * Do such 4-partite integral graphs exist?
> 
> 
> 



Why are some solutions of these diophantine equations off the usual patterns?
I take this from my comments above and add something.


The question is about rational points on the surface $S$ given by
$$ \Delta(a,b,c) := (ab+bc+ca)^3 - 27(abc)^2 = z^2 $$
in the weighted projective space ${\mathbb P}\_{1,1,1,3}$. Along the line
$b+c = 4a$ the left hand side factors as a square times $b^2 + 18bc + c^2$,
and the equation effectively reduces to $b^2 + 18bc + c^2 = z^2$, which is a
solvable conic and has lots of rational points that can be parameterized.
Also, for these points, any odd prime divisor of $a$ satisfies
$p \mid (4b)^2 + z^2$, which implies (for coprime $a,b,c$) that
$p \equiv 1 \bmod 4$.


There are other curves on $S$. For example, considering lines through
the point $(1:1:1)$ (which is a simple double point of (the rational
curve) $\Delta = 0$), we obtain curves of the form $z^2 = q(x,y)$,
where $q$ is a quartic. If we take the line $4a = b + 3c$, this
results in a curve birational to
$$ y^2 = 64 x^4 + 480 x^3 + 912 x^2 + 640 x + 117, $$
which is a curve of genus 1 with some rational points. Doing the math,
we find that this curve is isomorphic to the elliptic curve
$y^2 + y = x^3 - 1$ (243a1 in the Cremona database) of Mordell-Weil rank 1.
This implies that there are infinitely many rational points on this
curve. The smallest points with strictly positive coordinates
coming from this curve have (after re-ordering)
$$(a,b,c) = (2,3,6), \quad (6,57,74), \quad (2068,7657,9520).$$


More generally, considering the pencil of lines through $(1:1:1)$
gives us a fibration of $S$ into genus 1 curves that admits a
horiziontal curve with a degree 2 map to the base; this curve
is the conic from above. So after a base-change of degree 2, we actually
have a fibration into elliptic curves, and one would expect at least half
of them to have positive rank, resulting in infinitely many genus 1
curves on $S$ with infinitely many rational points on each.
For example, your first starred solution $(5, 12, 77)$ is on a curve
isomorphic to $y^2 = x^3 - 41659288807500$, which has even rank 2.


