{'fraction_non_alphanumeric': 0.050397501419647925, 'fraction_numerical': 0.01249290176036343, 'mean_word_length': 3.8750865051903114, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Special cycles in independence complexes and superfrustration in some lattices

We prove that the independence complexes of some grids have exponential Betti numbers. This corresponds to the number of ground states in the hard-core model in statistical physics with fermions in the vertices of the grid.


Introduction
The purpose of this paper is to investigate some topological questions arising from the study of supersymmetric lattice models in statistical physics. Suppose one has a finite graph L, which in applications is usually a periodic lattice with some boundary conditions. Square, triangular or hexagonal grids are the most notable examples. The vertices of the graph can be occupied by particles, such as fermions, which satisfy the hard-core restriction: two adjacent vertices cannot be occupied simultaneously. A configuration of particles which satisfies this assumption is an independent set in the graph L.
Associated with L there is a simplicial complex called the independence complex of L and denoted I(L). Its vertices are the vertices of L and its faces are the independent sets in L. It is a standard object studied in combinatorial algebraic topology. There is a close connection between the simplicial and topological invariants of I(L) and certain characteristics of the corresponding lattice model which are of interest to physicists. It is beyond the scope of this paper to discuss this relationship in detail; we refer to [10] and we limit ourselves to presenting just the most basic dictionary: the partition function of L the f -polynomial of I(L), the Witten index of L minus the reduced Euler characteristic − χ(I(L)), the number of zero energy ground states the dimension of H * (I(L); Q). There has been some very successful work calculating the Witten index, homology groups or indeed the complete homotopy type of the independence complex for various lattices, eg. [2,6,8,9,11,12,13,14,22]. In this paper we focus on the large-scale picture. Computer simulations of van Eerten [3] indicate that for some types of lattices, as their size increases, the number of ground states grows exponentially with the number of vertices, that is for some constant a depending on the type of the lattice, where v(L) denotes the number of vertices in a graph L. This situation is called superfrustration and has interesting physical implications, see [9]. Engström [5] developed a general method of computing upper bounds for the constant a. For the lattices of [3] it gives bounds very close to the values predicted in [3]. This paper has two main parts. In the first one we present a method which can be used to construct exponentially many linearly independent homology classes in I(L) for graphs L of certain type. That proves superfrustration of certain lattices and we give examples based on modifications of the triangular lattice. In the second part we prove a generalization of the main result of [5], which can sometimes give better upper bounds.
Both methods work particularly nicely with one type of lattice studied in [3,5]: the hexagonal dimer, also known as the Kagome lattice (see Fig.1). Under suitable divisibility conditions on the height and width we will prove that a graph H of that type satisfies: We will prove the lower bound in Section 3 and the upper bound in Section 5. The previous upper bound of [5] was 2 1/3 ≈ 1.26 and the experimental approximation by [3] is 1.25 ± 0.1.
Our technique for lower bounds produces slightly more than just homology classes: we obtain a large wedge of spheres that splits off. For instance, for a suitable lattice H of Kagome type, this reads as a homotopy equivalence for some space X. This type of result is proved in Section 4. This follows from the results of [17]; for another short proof see [1].
For any simplicial complex K and a subset U ⊆ V (K) of the vertices K[U ] denotes the induced subcomplex of K with vertex set U . The same notation is used for graphs. If H is an induced subgraph of G then I(H) is an induced subcomplex of I(G). By |K| we denote the number of faces in K, including the empty one. The join K * L of two complexes K and L is the simplicial complex with faces of the form σ τ for σ ∈ K and τ ∈ L. For any two graphs G and H, if G H is their disjoint union, we have I(G H) = I(G) * I(H).
The symbol S k denotes the topological sphere of dimension k. The suspension Σ K is the join K * S 0 . If e is the graph consisting of a single edge then I(e) = S 0 . The reduced homology and cohomology groups of K, denoted H * (K), H * (K), are the homology groups of the augmented chain, resp. cochain complex of K. Throughout the paper we always use rational coefficients and omit them from notation. We have H i (Σ K) = H i−1 (K). There is a standard bilinear pairing, denoted ·, · : given by evaluating cochains on chains. The i-th reduced Betti number is β i (K) = dim H i (K) and the total Betti number of K is Note the empty simplicial complex ∅ which has no vertices and a unique face ∅. It satisfies Σ ∅ = S 0 , so it is good to think of it as S −1 . It has a single reduced homology group H −1 (∅) = Q and in particular β(∅) = 1. Of course for every non-empty space K we have H i (K) = 0 for i < 0.
We do not distinguish between a simplicial complex and its geometric realization. The symbol means homotopy equivalence. The reference for other notions of combinatorial algebraic topology is [19].

Cycles defined by matchings
A matching of size k is the disjoint union of k edges. An induced matching in a graph G is a matching which is an induced subgraph of G. Explicitly, it is a set of k edges of G such that any two vertices from distinct edges are non-adjacent in G.
Every transversal of an induced matching is an independent set in G. It is dominating if and only if it is a maximal independent set.
If M is a disjoint union of k edges then I(M ) = S 0 * · · · * S 0 = S k−1 is the boundary of the crosspolytope. If M is an induced matching in G then we obtain an embedding S k−1 = I(M ) → I(G). We will denote by α M ∈ H k−1 (I(G)) the image of the fundamental class of S k−1 under this embedding (there is a choice of orientations involved, but it does not matter). Explicitly, if If σ is an independent set of cardinality k in G then we denote by σ ∨ ∈ C k−1 (I(G)) the cochain which associates ±1 to the two orientations of σ and 0 to all other simplices (again, this depends, up to sign, on the choice of orientation for σ). If σ is a maximal independent set (hence a maximal face in I(G)) then this cochain is in fact a cocycle, hence it determines an element of H k−1 (I(G)) which we continue to denote σ ∨ .
is an induced matching with a dominating transversal then α M and σ ∨ are nonzero classes in H * (I(G)) and H * (I(G)), respectively. Moreover Proof. The last statement holds because σ ∨ evaluates to ±1 on exactly one of the simplices in the chain representation of α M . It immediately implies that both elements are nonzero.
Remark 2.4. In general, if α 1 , . . . , α k ∈ H i (X) and γ 1 , . . . , γ l ∈ H i (X) then the i-th Betti number β i (X) is at least as big as the rank of the l × k matrix with entries γ s , α t for 1 ≤ s ≤ l, 1 ≤ t ≤ k.

Hexagonal dimer and related grids
The hexagonal dimer or the Kagome lattice is the lattice obtained from the triangular lattice by erasing every other line in each direction in the way shown in Fig.1  Proof. Let k = v(H)/36 be the number of large hexagons in the tiling of H. We are going to construct 2 k linearly independent elements in H 8k−1 (I(H)). That proves the claim since then β(I(H)) ≥ 2 k = 2 v(H)/36 . Consider the tiles A and B of Fig.1, where they are shown with an induced matching (thick edges) and its dominating transversal (thick vertices). Note that for any placement of A and B in place of the large hexagons in the grid we obtain a valid induced matching with a dominating transversal in H. Indeed, there are no edges directly between the tiles, so the matching is induced and each vertex located between the tiles is adjacent to one of the transversal vertices on the outer cycle of a tile. We therefore have 2 k homology (and cohomology) classes in I(H).
To prove linear independence we need some notation. Suppose that the big hexagons in the grid are labeled 1, . . . , k in some order. For any sequence s = (s 1 , . . . , s k ) of letters A, B let M (s) and σ(s) denote the matching and transversal obtained in the above construction by placing the tile of type s i in the i-th spot for i = 1, . . . , k. Then for any two sequences s and t we have Consider a 2 k × 2 k matrix with rows and columns indexed by sequences in {A, B} k in lexicographical order, where the entry in column t and row s is σ(t) ∨ , α M (s) . By the last observation that matrix has ±1 on the diagonal and 0 above the diagonal (where t > LEX s), so it is of full rank. Therefore all α M (s) are linearly independent. Similar results can be obtained for some other lattices derived from the triangular lattice. Proof. The proof is similar: ∆ 3 has k = v(∆ 3 )/8 tiles and ∆ 4 has k = v(∆ 4 )/45 of them. In each case we construct 2 k induced matchings with dominating transversals using the tiles A, B of appropriate type (Fig.2) and prove linear independence of the resulting homology classes as before.

Homotopical splittings
We will now show for completeness that induced matchings with dominating transversals in G correspond to sphere wedge summands in the homotopy type of I(G). This is stronger than just saying that they define a nonzero homology class. The results of this section are not needed in the previous calculations, where analyzing the cohomology-homology pairing is sufficient (and easier). where C(j) is the homotopy cofibre of j.
Proof. Since σ is a maximal face of I(G) we can remove it and form the simplicial complex I(G)\σ whose geometric realization is obtained by removing the interior of σ. Then we have a cofibre sequence ∂σ → I(G) \ σ → I(G) → Σ (∂σ) → · · · i.e. I(G) is the homotopy cofibre of the inclusion ∂σ → (I(G) \ σ). But this inclusion is nullhomotopic since it factors through the space I(M ) \ σ, homeomorphic to the disk D k−1 . As a consequence Together with S k−1 = I(M ) this ends the proof.
To analyze our situation further we need to understand homotopy cofibres of maps between independence complexes.
Then there is a homotopy equivalence for some space X.
Proof. Let i 1 : M 1 → G be the inclusion of the first matching. Then, by Lemmas 4.1 and 4.2 we have a splitting I(G) I(M 1 ) ∨ I(C(i 1 )). If k = 1 then we are done. Otherwise note that the pairs (M j , σ j ) for 2 ≤ j ≤ k define a sequence of induced matchings with dominating transversals in the graph C(i 1 ). Indeed, to build C(i 1 ) we did not add any edges within G itself, so the matchings are still induced. Moreover, by (*) every set σ j contains a vertex which is not in V (M 1 ), hence it is adjacent to the new vertex of C(i 1 ), which means σ j is a dominating set in C(i 1 ). The condition (*) still holds, so by induction and that completes the proof.

Upper bounds
In this section we improve, for the hexagonal dimer grids H, the upper bound of [5]. We develop a more general result, which is modeled entirely on the technique of [5] with just two small improvements. Firstly, it avoids discrete Morse theory and relies just on the Betti numbers and homotopy. Secondly, it allows arbitrary graphs in a place where [5] requires a forest (see Cor.5.4).
We first need some extra notation. Suppose K is a simplicial complex with a fixed splitting of the vertex set into two disjoint subsets U and W (V (K) = U W ). For every simplex σ ∈ K[U ] we denote by lk W σ the subcomplex of K[W ] consisting of those simplices τ ∈ K[W ] for which τ σ ∈ K. By st W σ we denote the subcomplex of K consisting of those τ ∈ K for which τ ∩ U ⊆ σ and τ ∩ W ∈ lk W σ. Clearly st W σ = (lk W σ) * σ.
Since each of those quotients has total Betti number at most B, the E 1 page of the homology spectral sequence associated with this filtration has dimension at most B·D. The spectral sequence converges to H * (K), hence the result. Proof. If G \ U is a forest then so is G \ (U ∪ N [σ]) for every σ. Since by [4] the independence complex of a forest is either contractible or homotopy equivalent to a sphere (possibly S −1 ), we can apply Lemma 5.3 with B = 1. Proof. This follows from the formula for the reduced homology of the join (eg.[20, Lemma 2.1]), which for rational coefficients reduces to Proposition 5.6. If H is any hexagonal dimer lattice which can be tiled as in Fig.1 then  N [σ]) is a disjoint union of k graphs, each of which is an induced subgraph of the 30-vertex tile. More precisely, it is an induced subgraph obtained by removing the neighbourhood of some subset of the vertices of U which surround that tile. There are 2 12 = 4096 graphs that can arise in this way, with only 217 isomorphism classes [21], and the homology of their independence complexes can be easily calculated by a computer [16]. It turns out that for each of those graphs the total Betti number is at most 14 (the graph which attains maximum is shown in Fig.5). Using β(I(∆ 3 )) ≤ (2 3/8 ) v(∆3) , β(I(∆ 4 )) ≤ (10 1/45 · 2 1/5 ) v(∆4) .

Concluding remarks
It would be most interesting to prove similar lower bounds for the classical triangular and hexagonal lattice, for which superfrustration is also predicted [3]. In those cases, however, the present methods do not seem to work, and it is not clear if exponentially many homology classes should be given by embedded spheres or if more complicated constructions are necessary. Recent results in this direction include [11], where "long and thin" triangular lattices of size c × n for small constants 2 ≤ c ≤ 7 are investigated. Also, the constructions of Jonsson [15] can be adapted to show that for the hexagonal grids of suitable sizes c × n with fixed c the number of ground states is exponential in n.
More generally, it would also be interesting to know what aspect of regularity is responsible for superfrustration in arbitrary lattices.