The Spreading and Covering Numbers
Introduction
The spreading and covering numbers were the subject of my NSERC USRA from May to August 2010. These numbers were first discussed by Geramita, Gregory, and Roberts* in relation to the Ideal Generation Conjecture, which is mostly beyond me at the moment. For my research project, I focused on using combinatorial techniques to find values or at least bounds for these numbers.
In this I was following the research of my supervisor, Adam Van Tuyl. With E. Carlini and H. T. Hà, he developed a CoCoA algorithm that computes the spreading and covering numbers by constructing a simplicial complex and computing its dimension.* I ported this algorithm to Macaulay2 to run it on SHARCNET and also looked at other methods for computing these numbers.
I revisited this problem for a second research term in the summer of 2011. Among other things, made some more headway into computing upper bounds for the covering number. We have written up the results as a paper, available on the arXiv.
Preliminaries
We will start with some graph and ring theory. Let $S_n = k[x_1,\ldots,x_n]$, $k$ a field. Let $S_n(d)$ denote the $v_n(d) = \binom{d + n - 1}{n - 1}$ monomials of degree $d$ in $S$. We can consider $S_n(d)$ as a graph in which two monomials $f,g \in S_n(d)$ are adjacent if and only if $\deg\left(\lcm(f, g)\right) = d + 1$. For example, $x_1^3x_2$ and $x_1^3x_3$ are adjacent in $S_3(3)$, but $x_1^3x_2$ and $x_2^3x_3$ are not.
For notation purposes, let $T = k[z_1,\ldots,z_{v_n(d)}]$. We identify each monomial in $S_n(d)$ with an indeterminate of $T$ and relabel the vertices of $S_n(d)$ accordingly. Then we can represent a set of distinct vertices by writing the product of its elements as a monomial in $T$. Particularly, we can define the edge ideal of $S_n(d)$ by $I_{S_n(d)} = (z_iz_j ~|~ \{z_i, z_j\} \in E_{S_n(d)})$.
The Spreading Number
We now have enough to define the spreading number for $S_n(d)$:
The spreading number, denoted by $\alpha_n(d)$, is the cardinality of the maximum independent set on $S_n(d)$. Equivalently, it is the largest subset of monomials in $S_n(d)$ such that, when each element is multiplied by the indeterminates of $S$, there is no repetition among the resulting monomials.
An Example in 3 Variables
Consider $S_3(3) = k[x_1, x_2, x_3]$. Finding the maximum independent set of this graph is easy to do by inspection, and its cardinality is 4, so $\alpha_3(3) = 4$.
However, in general, finding the maximum independent of a graph is NP-hard. As the number of variables and degree of monomials increases, so too does the memory and time required to compute the spreading number. It would be best if we could use the structure of the graphs of $S_n(d)$ to find a better approach for computing these numbers, or at least for computing bounds.
Using Simplicial Complexes
A simplicial complex, $\Delta$, on a vertex set $V$ is a collection of subsets $F \subseteq V$ such that:
- If $v \in V$, then $\{v\} \in \Delta$.
- If $F \in \Delta$ and $G \subseteq F$, then $G \in \Delta$.
We call elements of $\Delta$ faces, and maximal elements are facets. For any face $F \in \Delta$, the dimension of $F$ is $|F| - 1$. The dimension of the entire simplicial complex is the maximum of the dimensions of its facets.
Using the vertices of $S_n(d)$ as the vertex set of our simplicial complex, it is possible to construct simplicial complexes that are associated with the graph of $S_n(d)$. In particular, the independence complex of a graph is the simplicial complex whose faces are independent sets on the graph. Since the spreading number is the cardinality of the maximum independent set, to find $\alpha_n(d)$, it is sufficient to find the dimension of the independence complex of $S_n(d)$.
Carlini, Van Tuyl, and Hà* created an algorithm that takes $n$ and $d$ as input, constructs the independence complex of $S_n(d)$, and computes the dimension of the associated Stanley-Reisner ring, which is equivalent to the spreading number. It is worth noting that because the Stanley-Reisner ideal, $I_\Delta$, is generated by all non-faces of $\Delta$, the Stanley-Reisner ideal for $S_n(d)$ is:
\[I_\Delta = \left(\{m_i{m_j} ~|~ \{m_i,m_j\} \in E_{S_n(d)}\}\right),\]i.e., the edge ideal of the graph.
On a Pentium II processor with 128 MB of RAM, this algorithm, implemented in CoCoA 3.7, ran into trouble for $n, d \geq 5$. At this point the memory and time required to complete the computation of the ring dimension exceeded what was available. Porting this algorithm to Macaulay2 and running it on SHARCNET revealed that time is the key component: the algorithm's memory footprint did not grow significantly, but even running for an entire week it failed to compute $\alpha_5(5)$. This appears to be a limitation in how CoCoA and Macaulay2 compute the dimension of a ring, namely by first finding the Hilbert-Poincaré series. Since this gives us more information than we need for our purposes, it is worth investigating alternative methods of finding the spreading and covering numbers.
Using Graph Symmetry
The graph of $S_n(d)$ is highly symmetrical. In particular, we can show that applying a rotation or reflection to an independent set on the graph preserves its independence. Furthermore, we can encode these transformations as elements of the symmetric group of degree $n$, $\Sym(n)$.
Observe that applying a permutation to a set preserves the exponents and changes only the indices of each indeterminate.
It is possible to exploit this symmetry to compute the spreading number. We begin with a greedy algorithm that takes any independent set on $S_n(d)$ and outputs a maximal independent set, $M$. Then $M$ is a lower bound for $\alpha_n(d)$, and we are interested in knowing if any independent sets larger than $M$ exist. So we iterate over the subsets of $S_n(d)$ of cardinality $|M| + 1$, checking if they contain $M$ or any of its permutations, because those must also be maximal independent sets. If the set is independent and does not contain $M$ or its permutations, then it is a larger independent set. We use our greedy algorithm to obtain another maximal independent set and repeat the process until we find a maximum independent set.
The problem, of course, is that it takes a lot of time to iterate over all these subsets, and the size of these subsets can grow large very fast. To compute $\alpha_5(5)$, we would need to check at least $2.33\times 10^{27}$ sets, and there is no guarantee we would be able to stop there. This method, at least on SHARCNET, is impractical. However, it did allow us to compute lower bounds for up to $\alpha_5(9)$.
Comparison of Various Lower Bounds
The following tables contain specific data for the spreading numbers for $n = 3, 4, 5$ and $3 \leq d \leq 10$. The first bound, $\frac{v_n(d)}{n}$, where $v_n(d)$ is the cardinality of $S_n(d)$, is given by Geramita et al.* In addition to the greedy lower bound algorithm, GLB, we developed a recursive lower bound, RLB, that of course has limited application given the small number of known values.
| $d$ | $\alpha_3(d)$ | $\frac{v_n(d)}{n}$ | RLB | GLB |
|---|---|---|---|---|
| 3 | 4 | 4 | 3 | 4 |
| 4 | 6 | 5 | 6 | 6 |
| 5 | 7 | 7 | 7 | 7 |
| 6 | 10 | 10 | 10 | 10 |
| 7 | 12 | 12 | 11 | 12 |
| 8 | 15 | 15 | 15 | 15 |
| 9 | 19 | 19 | 17 | 19 |
| 10 | 22 | 22 | 21 | 20 |
| $d$ | $\alpha_4(d)$ | $\frac{v_n(d)}{n}$ | RLB | GLB |
|---|---|---|---|---|
| 3 | 5 | 5 | 5 | 5 |
| 4 | 11 | 9 | 10 | 11 |
| 5 | 14 | 14 | 12 | 14 |
| 6 | 24 | 21 | 21 | 24 |
| 7 | 30 | 30 | 26 | 27 |
| 8 | 45 | 42 | 39 | 40 |
| 9 | 55 | 55 | 49 | 48 |
| 10 | 76 | 72 | 67 | 64 |
At $d = 7$, the greedy lower bound algorithm begins to provide a worse bound than the formula from Geramita et al. This continues for $n = 5$:
| $d$ | $\alpha_5(d)$ | $\frac{v_n(d)}{n}$ | RLB | GLB |
|---|---|---|---|---|
| 3 | 7 | 7 | 6 | 7 |
| 4 | 14 | 16 | 16 | |
| 5 | 26 | 21 | 25 | |
| 6 | 42 | 40 | 40 | |
| 7 | 66 | 58 | ||
| 8 | 99 | 83 | ||
| 9 | 143 | 116 | ||
| 10 | 201 |
The performance of this algorithm is interesting compared to the positive results given by its analog for the covering numbers, which we shall now describe.
The Covering Number
We will need a little more graph theory:
- A subset of $S_n(d)$ in which any two vertices are adjacent is called a clique.
- A clique is maximal if it is not properly contained in any larger clique. If a maximal clique consists of $n$ distinct vertices, then it is a maximum clique.
- For any monomial $m$ of degree $d - 1$, an upward clique is the clique consisting of the vertices $mx_i$ for all $x_i \in \{x_1,\ldots,x_n\}$.
A clique covering is a set of cliques, $C$, such that every vertex in the graph is contained in at least one clique in $C$.
The covering number, denoted by $\rho_n(d + 1)$, is the cardinality of the smallest subset of monomials in $S_n(d)$ that generate the monomials of degree $d + 1$. Equivalently, it is the minimum upward clique covering of $S_n(d)$.
An Example in 3 Variables
Once again, consider $S_3(3)$. As with the spreading number, the covering number is easily found by inspection: $\rho_3(3) = 4$. However, since finding a minimal clique cover is complementary to finding a maximum independent set, this problem is also very difficult as $n$ and $d$ increase.
An Algorithm for Finding Upper Bounds
We can use a similar approach in finding upper bounds as we used for finding lower bounds of the spreading number. We define a greedy algorithm to produce a minimal upward clique cover. We can compare this greedy upper bound, GUB, to an explicit upper bound given by Geramita et al:*
\[\rho_n(d + 1) \leq \frac{v_n(d + 1)}{n} + (n - 1)\frac{v_{n - 1}(d + 1)}{n}.\]Unlike the lower bound algorithm for the spreading number, this algorithm produces better upper bounds than the explicit formula.
Comparison of Upper Bounds
The following tables contain specific data for the covering numbers for $n = 3, 4, 5$ and $3 \leq d \leq 10$.
| $d$ | $\rho_3(d + 1)$ | Explicit | GUB |
|---|---|---|---|
| 2 | 4 | 6 | 4 |
| 3 | 6 | 8 | 7 |
| 4 | 9 | 11 | 9 |
| 5 | 12 | 14 | 13 |
| 6 | 15 | 17 | 16 |
| 7 | 18 | 21 | 19 |
| 8 | 23 | 25 | 23 |
| 9 | 27 | 29 | 28 |
| $d$ | $\rho_4(d + 1)$ | Explicit | GUB |
|---|---|---|---|
| 2 | 6 | 12 | 6 |
| 3 | 12 | 20 | 14 |
| 4 | 18 | 29 | 22 |
| 5 | 27 | 42 | 33 |
| 6 | 57 | 44 | |
| 7 | 75 | 62 | |
| 8 | 96 | 81 | |
| 9 | 121 | 113 |
| $d$ | $\rho_5(d + 1)$ | Explicit | GUB |
|---|---|---|---|
| 2 | 9 | 23 | 9 |
| 3 | 20 | 42 | 25 |
| 4 | 33 | 70 | 46 |
| 5 | 109 | 73 | |
| 6 | 162 | 108 | |
| 7 | 231 | 160 | |
| 8 | 319 | 229 | |
| 9 | 429 | 325 |
An Open Problem: OEIS Sequence A053307
Geramita, Gregory, and Roberts provide explicit formulas for $\alpha_4(d)$, one each for $d$ even and $d$ odd. It is possible to show that these formulas are equivalent to the two formulas for the interleaved integer sequence A053307, the number of nonnegative integer $2\times 2$ matrices with sum of elements equal to $d$, under row and column permutations.
What is the relationship between this sequence and $\alpha_4(d)$? That is, what is the relationship between the maximum independent set of $S_4(d)$ and the number of nonnegative integer $2\times 2$ matrices with sum of elements equal to $d$?