Partitions and Graphs

Partitions and Graphs

Happy new year 2024. Here is the code displayed on the right upper corner of the board written this morning when wondering how frequent the situation is that the year is divisible by the year modulo 1000 minus 1. This happens for 2024 as it is divisible by 23. The mathematica code Select[Range[9999],(IntegerQ[(#/Mod[#-1,1000])]) &] illustrates more than just an example: It shows how the concept of lists (arrays) and working on lists and arrays without building loops is a powerful paradigm and that with “Select” similarly as “grep” in unix one can quickly build powerful programs instantly without the need of any IDE or AI.

While on vacation on Block Island, I figured out a riddle which bothered me in the last week of December: if G is a d-manifold and f a map from G to an other graph H and f(G)=N, in which cases is { f = N } = { x, f(x) contains a facet of N } a submanifold. It works for all complete k+1 partite graphs K_{(n_0, \dots, n_k)}. There is a bit of inconsistency in the notation. We write K_n for the complete graph with n vertices. It should be denoted K_{\{ 1, \dots, 1 \}} because this means it is the n fold join of K_1 graphs. The graph K_{k,m} = K_{\{k,m\}} is the join of \overline{K_k} and \overline{K_m}. The graph K_{(1,1,\dots, 1)} is the join of k graphs K_1. There are p(n) graphs of this type with n elements. The function p(n) is the integer partition function. I had investigated partition problems in high school. One of the results was the Euler pentagonal number theorem which I used to recursively compute the partition numbers. Partition numbers also appear in the famous movie “The man who knew infinity”. There is a scene about partitions there.

Here is the deliverable. Lets look at n=7 and the partition (2,2,3), one of the 15 partitions of 7. As host graph G, we take the 4 manifold C_{13} \oplus I, where I is the icosahedron graph. As a join of a 1-sphere and a 2-sphere, this is a 4-sphere with 25 vertices. If N=K_{2,2,3} we look at \{ f =N \}.

A = PolyhedronData[“Icosahedron”, “Skeleton”]; B=CycleGraph[13]; G =GraphJoin[A,B]

Now we chose a random function f from G to {1,2,3,4,5,6}. We took f=(1,3,6,3,3,1,6,2,3,6,2,1,6,5,1,5,7,7,1,5,2,4,6,5). Now, lets look at the 4-manifold G and the 2-manifold \{ f = N\}. The next picture gives the Cuisinaire picture of all partitions of n=7. The last picture shows the 15 graphs associated to the 15 partitions. What is amazing about this construction is how little data we need to get relatively complex manifolds. The host manifold has only 25 vertices. The submanifold of the Barycentric refinement is much larger. The other mesmerizing thing is of course that we always get manifolds like this. No singularities to deal with!