{'fraction_non_alphanumeric': 0.05138952164009112, 'fraction_numerical': 0.023507972665148064, 'mean_word_length': 3.763671875, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Independence Complexes of Stable Kneser Graphs

For integers n\geq 1, k\geq 0, the stable Kneser graph SG_{n,k} (also called the Schrijver graph) has as vertex set the stable n-subsets of [2n+k] and as edges disjoint pairs of n-subsets, where a stable n-subset is one that does not contain any 2-subset of the form {i,i+1} or {1,2n+k}. The stable Kneser graphs have been an interesting object of study since the late 1970's when A. Schrijver determined that they are a vertex critical class of graphs with chromatic number k+2. This article contains a study of the independence complexes of SG_{n,k} for small values of n and k. Our contributions are two-fold: first, we find that the homotopy type of the independence complex of SG_{2,k} is a wedge of spheres of dimension two. Second, we determine the homotopy types of the independence complexes of certain graphs related to SG_{n,2}.


Introduction
Let [n] := {1, 2, 3, . . . , n} and consider the following family of graphs. Definition 1.1. For each pair of integers n ≥ 1, k ≥ 0, the Kneser graph KG n,k has as vertices the n-subsets of [2n + k] with edges defined by disjoint pairs of n-subsets. For the same parameters, the stable Kneser graph SG n,k , also called the Schrijver graph, is the subgraph of KG n,k induced by the stable n-subsets of [2n + k], i.e. those n-subsets that do not contain any 2-subset of the form {i, i + 1} or {1, 2n + k}.
The Kneser and stable Kneser graphs have interesting properties related to independent sets of vertices, where a collection of vertices in a graph G is an independent set if the vertices are pairwise non-adjacent in G. Perhaps the most widely-known structure in graph theory related to independent sets is that of a proper graph coloring, i.e. a partition of the vertices of G into disjoint independent sets. The minimal number of independent sets required for such a partition is called the chromatic number of G and is denoted χ(G). In 1978, L. Lovász proved in [13] that χ(KG n,k ) = k + 2 by using an ingenious application of the Borsuk-Ulam theorem, thus verifying a conjecture due to M. Kneser from 1955. Shortly afterwards, A. Schrijver determined in [15] that χ(SG n,k ) = χ(KG n,k ), again using the Borsuk-Ulam theorem. Schrijver also proved that the stable Kneser graphs are vertex critical, i.e. the chromatic number of any subgraph of a stable Kneser graph SG n,k obtained by removing vertices is strictly less than χ(SG n,k ). These theorems were one source of inspiration for subsequent work involving the interaction of combinatorics and algebraic topology, see [10,11,14] for recent textbook accounts of further developments.
Recall that an (abstract) simplicial complex ∆ = (V, F ) is a finite set V , called the vertices of ∆, together with a collection of subsets F ⊆ 2 V such that F ∈ F, G ⊆ F ⇒ G ∈ F, called the faces of ∆. For technical purposes, we include the emptyset as a face. Lovász's original proof that χ(KG n,k ) = k + 2 followed from a general theorem bounding χ(G) from below by a function of the connectivity of the neighborhood complex of G, the complex whose vertices are the vertices of G and whose faces are vertices sharing a common neighbor. In [2], Björner and De Longueville proved that the neighborhood complex of SG n,k is homotopy equivalent to a k-sphere, implying that SG n,k is well-behaved topologically with regard to this construction and Lovász's theorem. While the neighborhood complex plays a fundamental role in providing topological lower bounds on chromatic numbers, this is not the only topological construction that investigates independence structures. If one is interested in the interplay among all the independent sets in G, without regard to chromatic numbers, one is led to the following construction. Independence complexes have been the subject of recent investigation, see for example [3,5,6,7,9,17]. Five of these papers involve a connection between independence complexes of graphs and hard squares models in statistical mechanics. Additionally, the homotopy type of the independence complexes of cycles played a critical role in the recent resolution by E. Babson and D. Kozlov in [1] of Lovász's conjecture regarding odd cycles and graph homomorphism complexes.
Our purpose in this paper is to investigate the homotopy type of the independence complexes of the stable Kneser graphs SG 2,k and the independence complexes of a family of graphs related to SG n,2 . There are several reasons to be curious about the independence complex of SG n,k . Since the stable Kneser graphs are vertex-critical, they are a minimal obstruction to colorability in the Kneser graphs, and the chromatic number inherently measures some restricted behavior of independent sets which is reflected in the neighborhood complex. It is of interest to see what, if any, properties of independent sets in SG n,k are exposed through Ind(SG n,k ). Also, an independent set in SG n,k is a pairwise intersecting family of stable n-subsets of [2n + k]. Such families have been previously studied from an extremal perspective, see for example [16] and the references therein.
The homotopy types of the independence complexes of some stable Kneser graphs are already known. For n = 1, the stable Kneser graphs are complete graphs and thus their independence complexes are wedges of 0-dimensional spheres. For k = 0, the stable Kneser graphs are complete graphs on two vertices, hence their independence complexes are zero dimensional spheres. For k = 1, it is easy to see that SG n,1 = C 2n+1 , the cycle of odd length, and the homotopy types of independence complexes of cycles are known. [12]) For n ≥ 1, let C n denote the cycle of length n. The following homotopy equivalence holds: Our first contribution is to describe Ind(SG 2,k ) up to homotopy. Also, Our second contribution is to investigate Ind(SG n,2 ). Unfortunately, as will be discussed in Section 4, these complexes are more complicated than those where n = 2, and their homotopy type is still unknown. However, we will be able to determine the homotopy type of a class of graphs we call E 2n+2 , close relatives of SG n,2 that will be fully defined in Section 4. A rough description of SG n,2 is as a cylinder graph with some additional edges on the cycles forming the ends of the cylinder; E 2n+2 is then obtained by "squeezing" SG n,2 so that only the end cycles and additional edges remain. Theorem 1.5. Let n ≥ 3. If 4 | 2n + 2, i.e. n is odd, then If 4 ∤ 2n + 2, i.e. n is even, then It is interesting to compare the case in Theorem 1.5 where n is even with Theorem 1.3, as we will later see that when n is even the graph E 2n+2 is closely related to an odd cycle of length n + 1.
Our primary tool for proving these theorems is discrete Morse theory. The remainder of the paper is structured as follows. In Section 2, we discuss the basics of discrete Morse theory, including the construction of acyclic partial matchings via matching trees introduced in [3]. In Section 3, we prove Theorem 1.4. In Section 4, we provide an explicit description of the graphs SG n,2 leading to the definition of E 2n+2 and remark on a connection between Ind(SG n,2 ) and [9]. Finally, in Section 5 we provide a proof of Theorem 1.5.

Tools From Discrete Morse Theory
In this section we introduce the tools we need from discrete Morse theory. Discrete Morse theory was introduced by R. Forman in [8] and has since become a standard tool in topological combinatorics. The main idea of (simplicial) discrete Morse theory is to pair cells in a simplicial complex in a manner that allows them to be cancelled via elementary collapses, reducing the complex under consideration to a homotopy equivalent complex, cellular but possibly non-simplicial, with fewer cells. Detailed discussions of the following definitions and theorems, along with their proofs, can be found in [10,11].
Definition 2.1. A partial matching in a poset P is a partial matching in the underlying graph of the Hasse diagram of P , i.e. it is a subset M ⊆ P × P such that • (a, b) ∈ M implies b covers a, i.e. a < b and no c satisfies a < c < b, and • each a ∈ P belongs to at most one element in M . When (a, b) ∈ M we write a = d(b) and b = u(a). A partial matching on P is called acyclic if there does not exist a cycle with n ≥ 2, and all b i ∈ P being distinct.
Given an acyclic partial matching M on P , we say that the unmatched elements of P are critical. The following theorem asserts that an acyclic partial matching on the face poset of a polyhedral cell complex is exactly the pairing needed to produce our desired homotopy equivalence. It is often useful to be able to make acyclic partial matchings on different sections of a poset and combine them to form a larger acyclic partial matching. This process is formalized via the following theorem, referred to as the Cluster Lemma in [10,Lemma 4.2] and the Patchwork Theorem in [11,Theorem 11.10].
Theorem 2.4. If φ : P → Q is an order-preserving map and, for each q ∈ Q, each subposet φ −1 (q) carries an acyclic partial matching M q , then the union of the M q is an acyclic partial matching on P .
Refer to v as a matching vertex of M (G) with respect to p. The node Σ(∅, ∅) is called the root of the matching tree, while any non-root node of degree 2 in M (G) is called a matching site of M (G) and any non-root node of degree 3 is called a splitting site of M (G).
The key observation in [3] is that a matching tree on G yields an acyclic partial matching on the face poset of Ind(G), as the following theorem indicates. The case k = 2 is a simple exercise that can be completed by drawing Ind(SG 2,2 ) on a sheet of paper (the complex is pure two-dimensional and has only eight maximal faces). The case k = 3 is handled at the end of this section. Thus, we need to first consider the situation where k ≥ 4. Let Q k denote the face poset of Ind(SG 2,k ) and let I k+2 be a (k + 2)-element chain, with elements labeled 3 < 4 < 5 < 6 < · · · < k + 4. Our goal is to create an acyclic partial matching on Q k by using Theorem 2.4 to break Q k into preimages and produce acyclic partial matchings on these. Note that we consider below only sets {i, j} that are stable, regardless of the parameters provided. In this section, addition and subtraction are modulo k + 4.
Observe that the maximal elements of Q k are of two types: W: A wheel through i is an independent set of the form T: A triangle is an independent set of the form Thus, Ind(SG 2,k ) is built from k + 4 simplices of dimension k corresponding to wheels, with additional 2-cells corresponding to triangles. Let φ : Q k → I k+2 be defined as follows. Note that all variables referenced (e.g. i, j, h = 1 It is straightforward to check that this is an order-preserving map. For 3 ≤ l < k + 4, we produce an acyclic matching M l on φ −1 (l) via the matching (σ, σ ∪ {1, l}) for each σ not containing {1, l}. It is straightforward to check that for each l, every element of φ −1 (l) is an element of some matched pair in M l . M l is acyclic because if one attempts to construct a directed cycle in φ −1 (l) as in Definition 2.1, starting from an element σ not containing {1, l}, we must begin our cycle with Remaining is only the poset φ −1 (k + 4). To establish an acyclic partial matching here, we apply Theorem 2.4 a second time. Let C := {b < r 6 < r 7 < · · · < r k+3 < m 1 < m 2 < t 2 < s 4 < s 5 < · · · < s k+2 < m 3 < m 4 < t k+4 } be a chain, and define ψ : φ −1 (k + 4) → C as follows.
It is straightforward to check that this is an order preserving map. To form acyclic partial matchings on these preimages, for all elements in the chain except t 2 and t k+4 , match the pair of elements in the preimage. Match the pair (σ, σ ∪ {2, 4}) on ψ −1 (t 2 ); this matching is acyclic and matches every element. Match the pair (σ, σ ∪ {2, k + 4}) on ψ −1 (t k+4 ); this matching is again acyclic, but does not match every element. One can check that the critical cells on ψ −1 (t k+4 ) are given by the set It is straightforward to calculate that the size of as desired. We are now in a position to invoke Theorems 2.2 and 2.4, completing our proof for the case k ≥ 4. For the case k = 3, we define φ as above, but we must modify the definition of ψ. In particular, for this case we eliminate ψ −1 (m 1 ) and ψ −1 (m 2 ) and in- . Note that the triangle T 2,5,7 is already present in ψ −1 (s 5 ). There are only four stable triangles avoiding 1, namely T 2,4,6 , T 2,4,7 , T 2,5,7 , and T 3,5,7 . These four cells are paired individually in the preimages of r 6 , s 4 , s 5 , and m 3 , respectively, implying that there are no unlisted triangles contained in ψ −1 (t 7 ). Thus, for the case k = 3, the only critical cell is {{2, 4}, {2, 5}}, and our proof is complete.

The graphs SG n,2 and E 2n+2
The graphs SG n,2 admit an alternate description which we will discuss here. This description is given in detail in [4], but the details are easy to fill in from the following. For an integer n ≥ 2, we define: Observe that a vertex of SG n,2 is given by a stable n-subset of [2n + 2] and that these subsets may be partitioned into three classes.  Figures 1 and 2 contain representations of SG 4,2 and SG 5,2 which we will use as references throughout this discussion. Recall that given two graphs G and H, the Note that each copy of SG n,2 contains a complete bipartite graph K n+1,n+1 induced by the bipartite end vertices of SG n,2 , hence the nomenclature. In Figures 1 and 2, these vertices are the outer ring of the graph, where for visual clarity we have not displayed all the edges, replacing them instead with dashed lines at each vertex indicating the presence of an edge. Let C j denote the cycle of length j and let P j denote the path with j vertices. For every n, the middle vertices of SG n,2 induce as a subgraph a copy of C 2n+2 P o(n)−2 which we call the middle cylinder. In our and 2 are C 10 P 1 and C 12 P 1 , respectively. It is easy to see that each bipartite end vertex of SG n,2 is connected to a unique vertex on an end cycle of the middle cylinder. Finally, the alternating end vertices of SG n,2 induce a copy of C n+1 in the case when 2 | n and a copy of DC 2n+2 in the case when 2 ∤ n, where DC 2n+2 is defined to be a (2n + 2)-cycle augmented by edges connecting antipodal vertices. In the first case, each alternating end vertex of SG n,2 is connected to a pair of middle vertices, while in the latter case each alternating end vertex of SG n,2 is connected to a unique middle vertex. A moment of thought reveals that when n is even, there are n + 1 alternating end vertices, while for n odd there are 2n + 2 alternating end vertices, and there are 2n + 2 bipartite end vertices and (2n + 2) · (o(n) − 2) middle vertices.
Remark 4.2. In the case where n is odd, the graph SG n,2 can be described as an even cylinder C 2n+2 P o(n) with additional edges forming a complete bipartite graph on one end and a cycle with diagonals on the other end, with a similar description for n even. Though the graphs SG n,2 admit this nice description, the complexes Ind(SG n,2 ) have been resistant to investigation. The difficult nature of this problem is similar to the difficult nature of the study of Ind(C 2n+2 P l ) for arbitrary l ≥ 6, n ≥ 3. As discussed in Section 6 of [9], even a determination of the Euler characteristic of Ind(C 2n+2 P l ) is unknown in general. For small values of n and l, there are some results regarding the homotopy type and Euler characteristic of these complexes, e.g. [17], but in general this is an interesting open problem.
One approach for studying Ind(SG n,2 ) would be to consider arbitrary even circumference cylinders C 2n+2 P l and augment their end cycles in a manner consistent with that described above. One might hope to then induct on l in some fashion, though our attempts following this approach have been unsuccessful. However, were one to pursue this strategy, the base case would be a cylinder of length two, i.e. a cylinder with no middle vertices. We therefore introduce the following class of graphs, which are formed by considering only the end vertices of SG n,2 and connecting them directly via edges. Let K n+1,n+1 denote the complete bipartite graph on vertex set {1, 2, . . . , 2n + 2} with bipartition into the set of odds and evens. Let DC 2n+2 denote the cycle on the vertex set {c 1 , c 2 , . . . , c 2n+2 } with edges {{c i , c i+1 } : i ∈ [2n + 2]} ∪ {{c i , c i+n+1 } : i ∈ [n + 1]}. Let C n+1 denote the cycle on the vertex set {c 1 , c 3 , c 5 , . . . , c 2n+1 } with edges {{c i , c i+2 } : i ∈ {1, 3, 5, . . . , 2n+1}}. For all of these graphs, addition of indices for vertices is modulo 2n + 2. Definition 4.3. For n ≥ 2, let E 2n+2 denote the following graph: if 2 ∤ n, take a copy of K n+1,n+1 and a copy of DC 2n+2 and add an edge connecting each vertex i of K n+1,n+1 to the vertex c i of DC 2n+2 . If 2 | n, take a copy of K n+1,n+1 and a copy of C n+1 and add edges connecting each vertex c i of C n+1 to the vertices i and i + n + 1 of K n+1,n+1 .
As Theorem 1.5 indicates, the topology of Ind(E 2n+2 ) is reasonably well-behaved. It would be of interest to understand more about the topology of the independence complexes of the graphs obtained by adding middle cycles back into E 2n+2 ; in particular, it would be interesting to know if there is any relation between the independence complexes of the graphs obtained by adding j middle cycles and j + k middle cycles to E 2n+2 for small values of k.

Proof of Theorem 1.5
To prove Theorem 1.5, we will construct matching trees for the graphs E 2n+2 , dividing our proof into the cases where 4 | 2n + 2 and 4 ∤ 2n + 2. We will refer to vertices of the matching tree as nodes, reserving the word vertices for the vertices of E 2n+2 . During the construction of our trees, references to matching, splitting, and free vertices of E 2n+2 are references to the types of vertices possible in the matching tree construction algorithm given in Section 2. Throughout, it might be helpful for the reader to use diagrams like Figures 4, 5, and 6 to illustrate our matching trees, which we typically describe with Σ(A, B) notation; in these diagrams, each node of the matching tree is shown as a graph representing Σ (A, B), where the black dots are elements of A, the white dots are elements of B, and the gray dots are in neither A nor B. Before we begin, we provide a definition and three lemmas.
Definition 5.1. Let EL 0 := K 2 and let EL 1 := K 1,3 , where K 1,3 is a complete bipartite graph with bipartition sets of size 1 and 3. For r ≥ 2, let EL r be the graph with 2r + 2 vertices depicted in Figure 3.  Proof. Figure 4 demonstrates a matching tree taking EL r to EL r−4 via matching vertices. Iterate this process until the only gray vertices remaining form a copy of EL r for r = 0, 1, 2, or 3. At each iteration, exactly two black vertices are added.
It is now an easy exercise to check that there are matching trees on EL 0 and EL 1 yielding a single non-empty leaf with a single black vertex, while there are matching trees on EL 2 and EL 3 with no critical cells. Remark 5.5. Lemmas 5.3 and 5.4 were not originally proved using matching trees, but it is simple to convert the proofs referenced in [11] to the language of matching trees.  where j is 2n + 1 or 2n + 2 depending on the parity of i. For the latter node, we have that vertex c i+3 is a matching vertex with respect to i + 3, thus we can create a new edge to a node labeled Finally, vertex i + 4 + n is a free vertex for this node (because n is odd), and thus we can create a new edge to a node labeled ∅.
Using vertex c n−1 as a splitting vertex, we see that vertex c 2n+1 is a free vertex for Using vertex c n+2 as a splitting vertex, we see that vertex c n+1 is a free vertex for hence we only need to consider node The remaining vertices induce as a subgraph of E 2n+2 a copy of EL n−5 . Thus, we are in a position to invoke Lemma 5.2, and we see that the portion of the resulting matching tree M (E 2n+2 ) rooted from our remaining node yields a critical cell of size 2k + 2 if n = 4k + 1 and no critical cells if n = 4k + 3.
We next use vertex c n as a matching vertex with respect to vertex c n−1 , leaving us to consider only the node We now use vertex c n+2 as a splitting vertex, yielding the new nodes The remaining vertices for the first of these nodes induce as a subgraph of E 2n+2 a copy of EL n−5 while for the second of these nodes the remaining vertices induce as a subgraph of E 2n+2 a copy of EL n−6 . Thus, we are in a position to invoke Lemma 5.2, and we conclude that the portions of the resulting matching tree M (E 2n+2 ) rooted from these final two nodes yield a critical cell of size 2k + 2 if n = 4k + 1 and a critical cell of size 2k + 3 if n = 4k + 3.  Figure 6. Using vertex c n+1 as a splitting vertex for Σ(∅, {1, 2, 3, . . . , 2n − 2}) leaves us with two subcases. We must address the cases n = 6k and n = 6k + 2 separately from n = 6k + 4 for the first part of the splitting. induce as a subgraph of E 2n+2 a disjoint union of two paths of length n 2 . Hence, applying Lemma 5.3, for n = 6k we have that the portion of the resulting matching tree M (E 2n+2 ) rooted at this node yields a single critical cell of size 2k + 1. For n = 6k + 2, it yields no critical cells.
It is a straightforward observation that 2n + 2 is a free vertex for this node. Thus, this portion of the matching tree yields no critical cells. Finally, vertex 2n − 1 is a free vertex for this node, yielding a new edge to a new node labeled ∅.

5.11
. Summary of Case: 4 ∤ 2n+ 2. Thus, for n = 6k we can produce a matching tree with one critical cell of size 2k + 1. For n = 6k + 2, our matching tree has two critical cells of size 2k + 2, and for n = 6k + 4 our matching tree has one critical cell of size 2k + 3. As each of these cases yield cells of the same dimension, our resulting cell complex is a wedge of spheres, as desired.