Arboricity, Dimension, Category

Arboricity, Dimension, Category

Crispin Nash-Williams, 1932-2001, British Mathematician. Picture is colorized from a gray picture

In mathematics there are three important types of optimization problems in geometry: packing problems, partition problems and covering problems. This happens especially in graph theory. An example of a graph partition problem is the arboricity arb(G) : what is the minimal number of forests into which one can partition a graph? For connected graphs this is equivalent to the question: how many trees are needed to cover a graph? A related question is the Lusternik-Schnirelmann category cat(G) of a graph which is the minimal number of contractible graphs that are needed to cover a graph. A graph of inductively defined to be contractible if there exists a vertex in that graph which has a contractible unit sphere and for which the graph without that vertex is still contractible. The induction assumption is that the 1-point graph is contractible. Since trees are contractible (the unit sphere of a leaf, a vertex with vertex degree 1 is a 1-point graph and so contractible and removing that leave produces a smaller tree allowing induction), we have cat(G) \leq arb(G).

Lusternik and Schnirelmann already proved that the category of a topological space is bounded above by the augmented dimension cat(G) \leq dim(G) + 1. We believe this is also true for graphs even so at the moment when talking about this now, I do not have a proof yet. I think the proof from the continuum can be adapted. But there should be a less topological, more graph theoretical way to see this. I at the moment even believe [Update Sunday, this is smashed now, see below] that any graph of dimension dim(G) satisfies arb(G) \leq dim(G)+1. It might be possible to derive this from the Nash-Williams formula (By the Way, Nash-Williams are not two people but one person: Crispin Nash-Williams (shown in the picture to the right).

Here is a MickeyMouse partial result. A graph is a 2-manifold if every unit sphere S(x) is a circular graph of 4 or more vertices.

Three-Tree-Theorem start: the arboricity of every connected 2-manifold is larger than 2

We have to show that we can not cover a 2-manifold with 2 trees. A consequence is that for every 2-manifold different from a sphere, the Lusternik-Schnirelmann capacity is 3. For 2-spheres, we have cat(G)=2 and arb(G)=3. To get the lower bound, note that the Euler characteristic of a 2-manifold is by Euler-Poincare \chi(G) = |V|-|E|+|F|=1-b_1+1=2-b_1, where b_1 is the genus. This means that \chi(G) \leq 2. We also have the Dehn-Sommerville relation 2|E|=3|F| so that \chi(G) = |V|-|E|/3 for any 2-manifold. If we could cover G with 2 trees, then |E| \leq 2|V|-2. Together this means \chi(G) \geq |V|/3+2/3 meaning |V| \leq 3 \chi(G) -2. This is not possible already for \chi(G)=2 as we do not allow tetrahedra G=K_4 as 2-manifolds. Note that a tetrahedron K_4 is a 3-simplex. It does not count as a 2-manifold. For K_4 we of course have arboricity 2.

[Sunday August 13, 2023: I made more experiments. There are projective planes for which the Nash-Williams bound is sharp 3. And (big surprise), there is a Klein bottle (with Betti vector=(1,1,0), f-vector =(50,150,100) for which the Nash William formula gives an arboricity of 4 because the Nash-Williarms ratio is 150/49 which is larger than 3! The question is now of course whether there are orientable 2-manifolds with arboricity 4. I’m pretty sure that for 2-spheres, the arboricity is 3 (we want a three tree theorem badly!). There are 2-spheres with Nash-Williams bound arbitrarily close to 3 because Barycentric refinements increases the bound and gets in the limit 3. Even simpler: we can take prism graphs (join of a cyclic graph and a 0-sphere) and get Nash William bound 3n/(n+1) which also gets arbitrarily close to 3. I then made experiments with higher dimensional manifolds. For the smallest 3 sphere, a graph with 8 vertices and 24 edges (one of the higher dimensional Platonic solids), the Nash Williams bound is 24/7=3.43 which is well below the originally expected bound4. But its Barycentric refinement, a graph with f-vector (80, 464, 768, 384) already has Nash Williams ratio 464/80=5.87 which means that there are 3-spheres with arboricity 6. The next Barycentric refinement has f-vector (1696, 10912, 18432, 9216) with Nash-Williams ratio 6.433 and so arboricity 7. From the eigenvectors of the Barycentric refinement operator one can see that the limit is 6.5. Of course, the Lusternik-Schnirelmann category of this sphere is 2 as for all spheres. The question now of course is how large the arboricity can get for d-dimensional spheres. A natural conjecture is that the upper bound is determined by the Perron-Frobenius eigenvector of the Barycentric refinement operator. In the two dimensional case, this gives 3. In the 3-dimensional case 6.5 and in the 4 dimensional case 22.7576. The arboricity explodes in terms of the dimension exponentially. The feel that it could grow linearly with the dimension was very naive. The Lusternik Schnirelmann bound however will hold, I’m still pretty sure because it holds classically. ]