I. Smells like 1970. Problem. Given beta={beta_i in NN : i=0,...,n}, possibly non-zero Betti numbers, the task is to characterize the preimage of beta under the "Betti operator" BET : KK -> NN, where KK denotes the collection of all abstract simplicial complexes, and NN denotes the nonnegative integers. We only consider simplicial homology with integer coefficients. In particular, we seek to (i) characterize the cardinality of the preimage, perhaps as a function of the number of vertices used; (ii) give an algorithm to enumerate the elements of the preimage; and (iii) give an efficient algorithm to find the smallest element of the preimage, in a sense to be made precise. Solution to (iii). First, we show that no two i-cycles in a simplicial complex share more than one i-simplex. Lemma SHAR. Let c={sigma_0,sigma_1,...,sigma_i} and c'={sigma'_0,sigma'_1,...,sigma'_i} be i-cycles in a simplicial complex K. Then c != c' <=> #(intersection of c and c') <= 1, where #(.) denotes the number of elements. Proof. Let tau be the unique (i+1)-simplex whose boundary is c, and tau' be the unique (i+1)-simplex whose boundary is c'. Each element of c (resp c') omits one of the vertices of tau (resp tau'), and if sigma_i in c (resp c') omits v_k and sigma_j in c (resp c') omits v_l, then i != j <=> k != l. Thus the union of the vertices in any two elements of c (resp c') is equal to the set of vertices in tau (resp tau'). As a result, if c and c' share two or more simplices, then the set of vertices in tau equals that in tau', so tau=tau', so c and c' are both boundaries of tau, so c=c'. On the other hand, if c != c', then tau != tau', so c and c' do not share two or more simplices. ### Remark. An i-cycle can share an i-simplex with each of up to i+1 other i-cycles. For example: +---+---+ \ / \ / +---+ \ / + Here the center 1-cycle shares each of its 1-simplices with one of the other 1-cycles. ### Next, we let T_{i,beta_i} denote the minimal number of i-simplices needed to form beta_i i-cycles. Lemma TMIN. T_{i,beta_i} = min {n : beta_i <= binom(n,i+2)}. Proof. Two be written. ### Lemma NUEQB. #{beta_i : T_{i,beta_i} = n} = 0, if n < i+2, 2, if n = i+2, binom(n,i+2)-binom(n-1,i+2), if n > i+2. Proof. Two be written. ### Remark. Either of the previous two lemmas can be obtained from the other. ### Lemma NULEQB. #{beta_i : T_{i,beta_i} <= n} = 0, if n < i+2, 2, if n = i+1, 1 + binom(n,i+2), if n > i+2. Proof. Just sum: #{beta_i : T_{i,beta_i} <= n} = 0, if n < i+2, 2, if n = i+1, 2 + sum_{n'=i+3}^n [binom(n',i+2)-binom(n'-1,i+2)], if n > i+2, and sum_{n'=i+3}^n [binom(n',i+2)-binom(n'-1,i+2)] = -1 + binom(n,i+2). ### Remark. Evidently there is no closed form for T_{i,beta_i}; however, T_{i,beta_i} can be found, for any given i and beta_i, by linear search through n in 0,1,2,..., based on Lemma TMIN; the number of n that will need to be considered is sublinear in i and beta_i, due to Lemma NULEQB. the set of vertices in tau is equal to the set of vertices in tau', and in that case, tau=tau', so , and hence tau=tau', so c and c Thus any two elements of c contain, together, all the vertices be an i-cycle. Let sigma be (i+1)-simplex whos Each i-simplex in an i-cycle omits precisely one of the vertices of the (i+1)-simplex of which the i-cycle is Let T_{i,beta_i} denote the minimal number of i-simplices needed to form an i-cycle. Lemma. T_{i,beta_i} = min {n in NN : beta_i <= binom(n,i+2)}. Pf. Each distinct i-cycle in a simplicial complex can share at most It can be seen that beta_i i-cycles are formed by the following choice of i-simplices: { < % this prints the number of bi for which % T_{i,bi}=n, for all i and n in the appropriate range. % Note that tne number of bi for which T_{i,bi}=i+2, is 2 for all i. Problem. Given n, the number of 0-simplices, and beta={beta_i : i=0,...,n-1}, possibly non-zero Betti numbers, the task is to find the set of abstract simplicial complexes that have n 0-simplices and Betti numbers beta. In other words, the task is to find the preimage of beta under the "Betti operator" BET : KK -> ZZ^n, where KK denotes the collection of all abstract simplicial complexes with n 0-simplices, and ZZ denotes the integers. We only consider simplicial homology with integer coefficients. [Several related problems: - Compute the size of the preimage. - Specify a loss function and minimize the loss function over the preimage. - Remove the restriction to n 0-simplices. - Consider other kinds of homology.] Solution. We begin with more notation. Let K={K_i : i=0,...,n-1} denote a simplicial complex with i-simplices K_i, and let del_n del_{n-1} del_1 del_0 0 -> C_n -> C_{n-1} -> ... -> C_1 -> C_0 -> 0 be the chain complex corresponding to K. Recall that each C_i is a free abelian group and del_i is a map from C_i -> C_{i-1}. Let b={b_i : i=0,...,n-1} denote the Betti numbers of K. Recall that b_i = dim H_i, the ith homology group associated with K = dim Z_i - dim B_i, where Z_i = the i-cycles of K and B_i = the i-boundaries of K = ker del_i, = im del_{i+1}. By the rank-nullity theorem, dim ker del_i = dim C_i - rank del_i, and dim im del_{i+1} = rank del_{i+1}, so b_i = dim C_i - rank del_i - rank del_{i+1}. Thus all the simplicial complexes in the preimage of BET need to satisfy the following system: beta_n = dim C_n - rank del_n - rank del_{n+1}, beta_{n-1} = dim C_{n-1} - rank del_{n-1} - rank del_n, ... beta_0 = dim C_0 - rank del_0 - rank del_1. Since dim C_0 = n and rank del_{n+1} = 0, the system is equivalently beta_n = dim C_n - rank del_n beta_{n-1} = dim C_{n-1} - rank del_{n-1} - rank del_n, ... beta_0 = n - rank del_0 - rank del_1. Now, we are interested in finding the preimage {K}, and of course K does not directly appear above. But dim C_i = |K_i|, so beta_n = |K_n| - rank del_n beta_{n-1} = |K_{n-1}| - rank del_{n-1} - rank del_n, ... beta_0 = n - rank del_0 - rank del_1. Next, recall that if the simplex s=[v_0,...,v_i] is in K_i, then all the faces of s must be in K_{i-1}; these faces are [v_1,...,v_i], [v_0,v_2,...,v_i], ..., [v_0,...,v_{i-1}]. However, simplices may be in K_{i-1} that are not faces of any element of K. Now, we can represent del_i, i=0,...,n, using a Hasse matrix [DMPS]. This is given by M := [del_1 0 0 0 0; del_2^T del_3 0 0 0; 0 del_4^T del_5 0 0; 0 0 ... ... 0; 0 0 0 del_{n-1}^T del_n], if n is odd, and M := [del_1 0 0 0 0; del_2^T del_3 0 0 0; 0 del_4^T del_5 0 0; 0 0 ... ... 0; 0 0 0 del_{n-2}^T del_{n-1}; 0 0 0 0 del_n^T], if n is even. (Note this definition is the transpose of that given by [DMPS]. Also, in what follows we assume wlog that n is odd.) [!The Hasse matrix shows us clearly how to enumerate the feasible set {K}: - A basis for the row space of del_1, i.e. for C_0, is given by the problem. - We choose a basis for the column space of del_1 and del_2^T, i.e. for C_1. - We choose a basis for the row space of del_2^T and del_3, i.e. for C_2. - ... - We choose a basis for the row space of del_{n-2}^T and del_{n-1}, i.e. for C_{n-2}. - We choose a basis for the column space of del_{n-1} and del_n.!] The whole matrix M needs to have rank as follows: rank M = rank del_1 + rank del_3 + rank del_5 + ... + rank del_n = rank del_1 + rank del_2 + rank_del_4 + ... + rank_del_{n-1}. Proposition: Let M be any matrix with rank given above. Some choice of basis for M Of course, the rows and columns of M The rows of del_1 are determined First, we pick n (abstract) vertices, as the problem requires, and represent the rows space of del_1 using these vertices as a basis; thus del_1 has n rows. - Then we need to pick the ; these vertices form a basis for the column space of del_0, We can use this to count the del_0. beta_n = |K_n| - rank del_n beta_{n-1} = |K_{n-1}| - rank del_{n-1} - rank del_n, ... beta_0 = n - rank del_0 - rank del_1. This means that Finally, we know that the Recall also that the Betti numbers Then the preimage of beta under BET is the set {K} of simplicial complexes that satisfy beta_n = dim C_2 - rank bt C={C_i : i=0,...,n} be the free abelian group described further below chain group corresponding to K, del={del_i : i=0,...,n-1} denote the Let C={C_i : i=0,...,n-1} denote the free abelian group associated abstract simplicial complex. The preimage under BET is the set of solutions to the following system of equations. beta_n = dim C_2 - rank An algorithm for finding the preimage of the Betti map B : {simplicial complexes} -> {vectors of Betti numbers}.