The Stacks project

55.5 Classification of proper subgraphs

In this section we assume given a numerical type $n, m_ i, a_{ij}, w_ i, g_ i$ of genus $g$. We will find a complete list of possible “subgraphs” consisting entirely of $(-2)$-indices (Definition 55.3.16) and at the same time we classify all possible minimal numerical types of genus $1$. In other words, in this section we prove Proposition 55.5.17 and Lemma 55.6.2

Our strategy will be as follows. Let $n, m_ i, a_{ij}, w_ i, g_ i$ be a numerical type of genus $g$. Let $I \subset \{ 1, \ldots , n\} $ be a subset consisting of $(-2)$-indices such that there does not exist a nonempty proper subset $J \subset I$ with $a_{jj'} = 0$ for $j \in J$, $j' \in I \setminus J$. We work by induction on the cardinality $|I|$ of $I$. If $I = \{ i\} $ consists of $1$ index, then the only constraints on $m_ i$, $a_{ii}$, and $w_ i$ are $w_ i | a_{ii}$ from Definition 55.3.1 and $a_{ii} < 0$ from Lemma 55.3.6 and this will serve as our base case. In the induction step we first apply the induction hypothesis to subsets $I' \subset I$ of size $|I'| < |I|$. This will put some constraints on the possible $m_ i, a_{ij}, w_ i$, $i, j \in I$. In particular, since $|I'| < |I| \leq n$ it will follow from $\sum a_{ij}m_ j = 0$ and Lemma 55.2.3 that the sub matrices $(a_{ij})_{i, j \in I'}$ are negative definite and their determinant will have sign $(-1)^ m$. For each possibility left over we compute the determinant of $(a_{ij})_{i, j \in I}$. If the determinant has sign $-(-1)^{|I|}$ then this case can be discarded because Sylvester's theorem tells us the matrix $(a_{ij})_{i, j \in I}$ is not negative semi-definite. If the determinant has sign $(-1)^{|I|}$, then $|I| < n$ and we (tentatively) conclude this case can occur as a possible proper subgraph and we list it in one of the lemmas in this section. If the determinant is $0$, then we must have $|I| = n$ (by Lemma 55.2.3 again) and $g = 0$. In these cases we actually find all possible $m_ i, a_{ij}, w_ i$, $i, j \in I$ and list them in Lemma 55.6.2. After completing the argument we obtain all possible minimal numerical types of genus $1$ with $n > 1$ because each of these necessarily consists entirely of $(-2)$-indices (and hence will show up in the induction process) by the formula for the genus and the remarks in the previous section. At the very end of the day the reader can go through the list of possibilities given in Lemma 55.6.2 to see that all configurations of proper subgraphs listed in this section as possible do in fact occur already for numerical types of genus $1$.

Suppose that $i$ and $j$ are $(-2)$-indices with $a_{ij} > 0$. Since the matrix $A = (a_{ij})$ is semi-negative definite by Lemma 55.2.3 we see that the matrix

is negative definite unless $n = 2$. The case $n = 2$ can happen: then the determinant $4w_1w_2 - a_{12}^2$ is zero. Using that $\text{lcm}(w_1, w_2)$ divides $a_{12}$ the reader easily finds that the only possibilities are

Observe that the case $(4w, w, 4w)$ is obtained from the case $(w, 4w, 4w)$ by switching the indices $i, j$. In these cases $g = 1$. This leads to cases (2) and (3) of Lemma 55.6.2. Assuming $n > 2$ we see that the determinant $4w_ iw_ j - a_{ij}^2$ of the displayed matrix is $> 0$ and we conclude that $a_{ij}^2/w_ iw_ j < 4$. On the other hand, we know that $\text{lcm}(w_ i, w_ j) | a_{ij}$ and hence $a_{ij}^2/w_ iw_ j$ is an integer. Thus $a_{ij}^2/w_ iw_ j \in \{ 1, 2, 3\} $ and $w_ i | w_ j$ or vice versa. This leads to the following possibilities

Observe that the case $(2w, w, 2w)$ is obtained from the case $(w, 2w, 2w)$ by switching the indices $i, j$ and similarly for the cases $(3w, w, 3w)$ and $(w, 3w, 3w)$. The first three solutions lead to cases (1), (2), and (3) of Lemma 55.5.1. In this lemma we wrote out the consequences for the integers $m_ i$ and $m_ j$ using that $\sum _ l a_{kl}m_ l = 0$ for each $k$ in particular implies $a_{ii}m_ i + a_{ij}m_ j \leq 0$ for $k = i$ and $a_{ij}m_ i + a_{jj}m_ j \leq 0$ for $k = j$.

Suppose that $i$, $j$, and $k$ are three $(-2)$-indices with $a_{ij} > 0$ and $a_{jk} > 0$. In other words, the index $i$ “meets” $j$ and $j$ “meets” $k$. We will use without further mention that each pair $(i, j)$, $(i, k)$, and $(j, k)$ is as listed in Lemma 55.5.1. Since the matrix $A = (a_{ij})$ is semi-negative definite by Lemma 55.2.3 we see that the matrix

is negative definite unless $n = 3$. The case $n = 3$ can happen: then the determinant¹ of the matrix is zero and we obtain the equation

of integers. The last term on the right in this equation is determined by the others because

Since we have seen above that $\frac{a_{ij}^2}{w_ iw_ j}, \frac{a_{jk}^2}{w_ jw_ k}$ are in $\{ 1, 2, 3\} $ and $\frac{a_{ik}^2}{w_ iw_ k}$ in $\{ 0, 1, 2, 3\} $, we conclude that the only possibilities are

Observe that the case $(3, 1, 0)$ is obtained from the case $(1, 3, 0)$ by reversing the order the indices $i, j, k$. In each of these cases $g = 1$; the reader can find these as cases (4), (5), (6), (7), (8), (9) of Lemma 55.6.2 with one case corresponding to $(1, 1, 1)$, two cases corresponding to $(1, 3, 0)$, and three cases corresponding to $(2, 2, 0)$. Assuming $n > 3$ we obtain the inequality

of integers. Using the restrictions on the numbers given above we see that the only possibilities are

in particular $a_{ik} = 0$ (recall we are assuming $a_{ij} > 0$ and $a_{jk} > 0$). Observe that the case $(2, 1, 0)$ is obtained from the case $(1, 2, 0)$ by reversing the ordering of the indices $i, j, k$. The first two solutions lead to cases (1), (2), and (3) of Lemma 55.5.2 where we also wrote out the consequences for the integers $m_ i$, $m_ j$, and $m_ k$.

Suppose that $i$, $j$, $k$, and $l$ are four $(-2)$-indices with $a_{ij} > 0$, $a_{jk} > 0$, and $a_{kl} > 0$. In other words, the index $i$ “meets” $j$, $j$ “meets” $k$, and $k$ “meets” $l$. Then we see from Lemma 55.5.2 that $a_{ik} = a_{jl} = 0$. Since the matrix $A = (a_{ij})$ is semi-negative definite we see that the matrix

is negative definite unless $n = 4$. The case $n = 4$ can happen: then the determinant² of the matrix is zero and we obtain the equation

of nonnegative integers. The last term on the right in this equation is determined by the others because

Since we have seen above that $\frac{a_{ij}^2}{w_ iw_ j}, \frac{a_{jk}^2}{w_ jw_ k}, \frac{a_{kl}^2}{w_ kw_ l}$ are in $\{ 1, 2\} $ and $\frac{a_{il}^2}{w_ iw_ l}$ in $\{ 0, 1, 2\} $, we conclude that the only possible solutions are

and case $g = 1$; the reader can find these as cases (10), (11), (12), and (13) of Lemma 55.6.2. Assuming $n > 4$ we obtain the inequality

of nonnegative integers. Using the restrictions on the numbers given above we see that the only possibilities are

in particular $a_{il} = 0$ (recall that we assumed the other three to be nonzero). Observe that the case $(2, 1, 1, 0)$ is obtained from the case $(1, 1, 2, 0)$ by reversing the ordering of the indices $i, j, k, l$. The first three solutions lead to cases (1), (2), (3), and (4) of Lemma 55.5.3 where we also wrote out the consequences for the integers $m_ i$, $m_ j$, $m_ k$, and $m_ l$.

Suppose that $i$, $j$, $k$, and $l$ are four $(-2)$-indices with $a_{ij} > 0$, $a_{ij} > 0$, and $a_{il} > 0$. In other words, the index $i$ “meets” the indices $j$, $k$, $l$. Then we see from Lemma 55.5.2 that $a_{jk} = a_{jl} = a_{kl} = 0$. Since the matrix $A = (a_{ij})$ is semi-negative definite we see that the matrix

is negative definite unless $n = 4$. The case $n = 4$ can happen: then the determinant³ of the matrix is zero and we obtain the equation

of nonnegative integers. Since we have seen above that $\frac{a_{ij}^2}{w_ iw_ j}, \frac{a_{ik}^2}{w_ iw_ k}, \frac{a_{il}^2}{w_ iw_ l}$ are in $\{ 1, 2\} $, we conclude that the only possibilities are up to reordering: $4 = 1 + 1 + 2$. In each of these cases $g = 1$; the reader can find these as cases (14) and (15) of Lemma 55.6.2. Assuming $n > 4$ we obtain the inequality

of nonnegative integers. This implies that $\frac{a_{ij}^2}{w_ iw_ j} = \frac{a_{ik}^2}{w_ iw_ k} = \frac{a_{il}^2}{w_ jw_ l} = 1$ and that $w_ i = w_ j = w_ k = w_ l$. This leads to case (1) of Lemma 55.5.4 where we also wrote out the consequences for the integers $m_ i$, $m_ j$, $m_ k$, and $m_ l$.

Suppose that $h$, $i$, $j$, $k$, and $l$ are five $(-2)$-indices with $a_{hi} > 0$, $a_{ij} > 0$, $a_{jk} > 0$, and $a_{kl} > 0$. In other words, the index $h$ “meets” $i$, $i$ “meets” $j$, $j$ “meets” $k$, and $k$ “meets” $l$. Then we can apply Lemmas 55.5.2 and 55.5.3 to see that $a_{hj} = a_{hk} = a_{ik} = a_{il} = a_{jl} = 0$ and that the fractions $\frac{a_{hi}^2}{w_ hw_ i}, \frac{a_{ij}^2}{w_ iw_ j}, \frac{a_{jk}^2}{w_ jw_ k}, \frac{a_{kl}^2}{w_ kw_ l}$ are in $\{ 1, 2\} $ and the fraction $\frac{a_{hl}^2}{w_ hw_ l} \in \{ 0, 1, 2\} $. Since the matrix $A = (a_{ij})$ is semi-negative definite we see that the matrix

is negative definite unless $n = 5$. The case $n = 5$ can happen: then the determinant⁴ of the matrix is zero and we obtain the equation

of nonnegative integers. The last term on the right in this equation is determined by the others because

We conclude the only possible solutions are

Observe that the case $(1, 2, 1, 1, 0)$ is obtained from the case $(1, 1, 2, 1, 0)$ by reversing the order of the indices $h, i, j, k, l$. In these cases $g = 1$; the reader can find these as cases (16), (17), (18), (19), (20), and (21) of Lemma 55.6.2 with one case corresponding to $(1, 1, 1, 1, 1)$, two cases corresponding to $(1, 1, 2, 1, 0)$, and three cases corresponding to $(2, 1, 1, 2, 0)$. Assuming $n > 5$ we obtain the inequality

of nonnegative integers. Using the restrictions on the numbers given above we see that the only possibilities are

in particular $a_{hl} = 0$ (recall that we assumed the other four to be nonzero). Observe that the case $(1, 1, 1, 2, 0)$ is obtained from the case $(2, 1, 1, 1, 0)$ by reversing the order of the indices $h, i, j, k, l$. The first two solutions lead to cases (1), (2), and (3) of Lemma 55.5.5 where we also wrote out the consequences for the integers $m_ h$, $m_ i$, $m_ j$, $m_ k$, and $m_ l$.

Suppose that $h$, $i$, $j$, $k$, and $l$ are five $(-2)$-indices with $a_{hi} > 0$, $a_{hj} > 0$, $a_{hk} > 0$, and $a_{hl} > 0$. In other words, the index $h$ “meets” the indices $i$, $j$, $k$, $l$. Then we see from Lemma 55.5.2 that $a_{ij} = a_{ik} = a_{il} = a_{jk} = a_{jl} = a_{kl} = 0$ and by Lemma 55.5.4 that $w_ h = w_ i = w_ j = w_ k = w_ l = w$ for some integer $w > 0$ and $a_{hi} = a_{hj} = a_{hk} = a_{hl} = -2w$. The corresponding matrix

is singular. Hence this can only happen if $n = 5$ and $g = 1$. The reader can find this as case (22) Lemma 55.6.2.

Suppose that $h$, $i$, $j$, $k$, and $l$ are five $(-2)$-indices with $a_{hi} > 0$, $a_{ij} > 0$, $a_{jk} > 0$, and $a_{jl} > 0$. In other words, the index $h$ “meets” $i$ and the index $j$ “meets” the indices $i$, $k$, $l$. Then we see from Lemma 55.5.4 that $a_{ik} = a_{il} = a_{kl} = 0$, $w_ i = w_ j = w_ k = w_ l = w$, and $a_{ij} = a_{jk} = a_{jl} = w$ for some integer $w$. Applying Lemma 55.5.3 to the four tuples $h, i, j, k$ and $h, i, j, l$ we see that $a_{hj} = a_{hk} = a_{hl} = 0$, that $w_ h = \frac{1}{2}w$, $w$, or $2w$, and that correspondingly $a_{hi} = w$, $w$, or $2w$. Since $A$ is semi-negative definite we see that the matrix

is negative definite unless $n = 5$. The reader computes that the determinant of the matrix is $0$ when $w_ h = \frac{1}{2}w$ or $2w$. This leads to cases (23) and (24) of Lemma 55.6.2. For $w_ h = w$ we obtain case (1) of Lemma 55.5.7.

Suppose that $t > 5$ and $i_1, \ldots , i_ t$ are $t$ distinct $(-2)$-indices such that $a_{i_ ji_{j + 1}}$ is nonzero for $j = 1, \ldots , t - 1$. We will prove by induction on $t$ that if $n = t$ this leads to possibilities (25), (26), (27), (28) of Lemma 55.6.2 and if $n > t$ to cases (1), (2), and (3) of Lemma 55.5.8. First, if $a_{i_1i_ t}$ is nonzero, then it is clear from the result of Lemma 55.5.5 that $w_{i_1} = \ldots = w_{i_ t} = w$ and that $a_{i_ ji_{j + 1}} = w$ for $j = 1, \ldots , t - 1$ and $a_{i_1i_ t} = w$. Then the vector $(1, \ldots , 1)$ is in the kernel of the corresponding $t \times t$ matrix. Thus we must have $n = t$ and we see that the genus is $1$ and that we are in case (25) of Lemma 55.6.2. Thus we may assume $a_{i_1i_ t} = 0$. By induction hypothesis (or Lemma 55.5.5 if $t = 6$) we see that $a_{i_ ji_ k} = 0$ if $k > j + 1$. Moreover, we have $w_{i_1} = \ldots = w_{i_{t - 1}} = w$ for some integer $w$ and $w_{i_1}, w_{i_ t} \in \{ \frac{1}{2}w, w, 2w\} $. Moreover, the value of $w_{i_1}$, resp. $w_{i_ t}$ being $\frac{1}{2}w$, $w$, or $2w$ implies that the value of $a_{i_1i_2}$, resp. $a_{i_{t - 1}i_ t}$ is $w$, $w$, or $2w$. This gives $9$ possibilities. In each case it is easy to decide what happens:

1. if $(w_{i_1}, w_{i_ t}) = (\frac{1}{2}w, \frac{1}{2}w)$, then we are in case (27) of Lemma 55.6.2,

2. if $(w_{i_1}, w_{i_ t}) = (\frac{1}{2}w, w)$ or $(w, \frac{1}{2}w)$ then we are in case (3) of Lemma 55.5.8,

3. if $(w_{i_1}, w_{i_ t}) = (\frac{1}{2}w, 2w)$ or $(2w, \frac{1}{2}w)$ then we are in case (26) of Lemma 55.6.2,

4. if $(w_{i_1}, w_{i_ t}) = (w, w)$ then we are in case (1) of Lemma 55.5.8,

5. if $(w_{i_1}, w_{i_ t}) = (w, 2w)$ or $(2w, w)$ then we are in case (2) of Lemma 55.5.8, and

6. if $(w_{i_1}, w_{i_ t}) = (2w, 2w)$ then we are in case (28) of Lemma 55.6.2.

Suppose that $t > 4$ and $i_1, \ldots , i_{t + 1}$ are $t + 1$ distinct $(-2)$-indices such that $a_{i_ ji_{j + 1}} > 0$ for $j = 1, \ldots , t - 1$ and such that $a_{j_{t - 1}j_{t + 1}} > 0$. See picture in Lemma 55.5.9. We will prove by induction on $t$ that if $n = t + 1$ this leads to possibilities (29) and (30) of Lemma 55.6.2 and if $n > t + 1$ to case (1) of Lemma 55.5.9. By induction hypothesis (or Lemma 55.5.7 in case $t = 5$) we see that $a_{i_ ji_ k}$ is zero outside of the required nonvanishing ones for $j, k \geq 2$. Moreover, we see that $w_2 = \ldots = w_{t + 1} = w$ for some integer $w$ and that the nonvanishing $a_{i_ ji_ k}$ for $j, k \geq 2$ are equal to $w$. Applying Lemma 55.5.8 (or Lemma 55.5.5 if $t = 5$) to the sequence $i_1, \ldots , i_ t$ and to the sequence $i_1, \ldots , i_{t - 1}, i_{t + 1}$ we conclude that $a_{i_1 i_ j} = 0$ for $j \geq 3$ and that $w_1$ is equal to $\frac{1}{2}w$, $w$, or $2w$ and that correspondingly $a_{i_1i_2}$ is $w, w, 2w$. This gives $3$ possibilities. In each case it is easy to decide what happens:

1. If $w_1 = \frac{1}{2}w$, then we are in case (30) of Lemma 55.6.2.

2. If $w_1 = w$, then we are in case (1) of Lemma 55.5.9.

3. If $w_1 = 2w$, then we are in case (29) of Lemma 55.6.2.

Suppose we are given $6$ distinct $(-2)$-indices $g, h, i, j, k, l$ such that $a_{gh}, a_{hi}, a_{ij}, a_{jk}, a_{il}$ are nonzero. See picture in Lemma 55.5.10. Then we can apply Lemma 55.5.7 to see that we must be in the situation of Lemma 55.5.10. Since the determinant is $3w^6 > 0$ we conclude that in this case it never happens that $n = 6$!

Suppose that $t \geq 4$ and $i_0, \ldots , i_{t + 1}$ are $t + 2$ distinct $(-2)$-indices such that $a_{i_ ji_{j + 1}} > 0$ for $j = 1, \ldots , t - 1$ and $a_{i_0i_2} > 0$ and $a_{i_{t - 1}i_{t + 1}} > 0$. See picture in Lemma 55.5.11. Then we can apply Lemmas 55.5.7 and 55.5.9 to see that all other $a_{i_ ji_ k}$ for $j < k$ are zero and that $w_{i_0} = \ldots = w_{i_{t + 1}} = w$ for some integer $w$ and that the required nonzero off diagonal entries of $A$ are equal to $w$. A computation shows that the determinant of the corresponding matrix is zero. Hence $n = t + 2$ and we are in case (31) of Lemma 55.6.2.

Suppose we are given $7$ distinct $(-2)$-indices $f, g, h, i, j, k, l$ such that the numbers $a_{fg}, a_{gh}, a_{ij}, a_{jh}, a_{kl}, a_{lh}$ are nonzero. See picture in Lemma 55.5.12. Then we can apply Lemma 55.5.7 to see that the corresponding matrix is

Since the determinant is $0$ we conclude that we must have $n = 7$ and $g = 1$ and we get case (32) of Lemma 55.6.2.

Suppose we are given $7$ distinct $(-2)$-indices $f, g, h, i, j, k, l$ such that the numbers $a_{fg}, a_{gh}, a_{hi}, a_{ij}, a_{jk}, a_{il}$ are nonzero. See picture in Lemma 55.5.13. Then we can apply Lemmas 55.5.7 and 55.5.9 to see that we must be in the situation of Lemma 55.5.13. Since the determinant is $-8w^7 > 0$ we conclude that in this case it never happens that $n = 7$!

Suppose we are given $8$ distinct $(-2)$-indices whose pattern of nonzero entries $a_{ij}$ of the matrix $A$ looks like

or like

Arguing exactly as in the proof of Lemma 55.5.13 we see that the first pattern leads to case (1) in Lemma 55.5.14 and does not lead to a new case in Lemma 55.6.2. Arguing exactly as in the proof of Lemma 55.5.12 we see that the second pattern does not occur if $n > 8$, but leads to case (33) in Lemma 55.6.2 when $n = 8$.

Suppose we are given $9$ distinct $(-2)$-indices whose pattern of nonzero entries $a_{ij}$ of the matrix $A$ looks like

Arguing exactly as in the proof of Lemma 55.5.12 we see that this pattern does not occur if $n > 9$, but leads to case (34) in Lemma 55.6.2 when $n = 9$.

Collecting all the information together we find the following.