The Spreading and Covering Numbers

$\DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\Sym}{Sym}$

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 Robertsgeramita86 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.carlini01 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.

Updated: A revised version of our paper was accepted for publication in the Australasian Journal of Combinatorics.

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$.

A graph consisting of 10 vertices adjacent in such a way as to form a triangle subdivided further into nine triangles. The max independent set consists of the three corner vertices and the middle vertex.
The graph of $S_3(3)$. Its maximum independent set is in red.

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àcarlini01 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)$.

The permutation (132) is applied to the graph to map one set of vertices to another.
The permutation $(132)$ sends the set $\{x_1^2x_2, x_2^2x_3, x_3^3\}$ to $\{x_1x_3^2, x_1^2x_2, x_2^3\}$.

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.geramita86 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.

Lower bounds for the spreading number when $n = 3$.
$d$ $\alpha_3(d)$ $\frac{v_n(d)}{n}$ RLB GLB
34434
46566
57777
610101010
712121112
815151515
919191719
1022222120
Lower bounds for the spreading number when $n = 4$.
$d$ $\alpha_4(d)$ $\frac{v_n(d)}{n}$ RLB GLB
35555
41191011
514141214
624212124
730302627
845423940
955554948
1076726764

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$:

Lower bounds for the spreading number when $n = 4$.
$d$ $\alpha_5(d)$ $\frac{v_n(d)}{n}$ RLB GLB
37767
4141616
5262125
6424040
76658
89983
9143116
10201
Graphic comparison of the bounds for $n = 3,4,5$. Click to view a larger image.
A graph that displays the results of the spreading number bound algorithms for n = 3. A graph that displays the results of the spreading number bound algorithms for n = 4. A graph that displays the results of the spreading number bound algorithms for n = 5.

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\}$.
And upward clique identified by an upward-pointing triangle.
In three variables, upward cliques correspond to the up-pointing triangles on the graph. The set $\{x_1^2x_2, x_1x_2^2, x_1x_2x_3\}$ is an upward clique identified with $x_1x_2 \in S_3(2)$.

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.

The three triangles to which the corner vertices contribute are shaded, as is one of the remaining triangles.
The graph of $S_3(3)$. Cliques that contribute to a minimal upward clique cover are shaded. Notice that this cover is not unique.

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:geramita86

\[\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$.

Upper bounds for the covering number when $n = 3$.
$d$ $\rho_3(d + 1)$ Explicit GUB
2464
3687
49119
5121413
6151716
7182119
8232523
9272928
Upper bounds for the covering number when $n = 4$.
$d$ $\rho_4(d + 1)$ Explicit GUB
26126
3122014
4182922
5274233
65744
77562
89681
9121113
Upper bounds for the covering number when $n = 5$.
$d$ $\rho_5(d + 1)$ Explicit GUB
29239
3204225
4337046
510973
6162108
7231160
8319229
9429325
Graphic comparison of the bounds for $n = 3,4,5$. Click to view a larger image.
A graph that displays the results of the covering number bound algorithms for n = 3. A graph that displays the results of the covering number bound algorithms for n = 4. A graph that displays the results of the covering number bound algorithms for n = 5.

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$?

References

  1. E. Carlini, H.T. Hà, A. Van Tuyl, Computing the spreading and covering numbers, Comm. Alg 29 (2001) 5687-5699.
  2. F. Curtis, A combinatorial problem involving monomial ideals, J. Pure Appl. Algebra 104 (1995) 161-167.
  3. A. Geramita, D. Gregory, L. Roberts, Monomial Ideals and Points in Projective Space, J. Pure Appl. Algebra 40 (1986) 33-62.
  4. H. Hulett, T. Will, Generating monomials in dimensions three and four, J. Pure Appl. Algebra 138 (1999) 139-150.