Large Independent Sets in Flag Spheres
June 15, 2026
Abstract
We construct a family of \(3\)-dimensional flag simplicial spheres whose graphs have independent sets with size asymptotically equal to the number of vertices. This disproves a recent conjecture of Chudnovsky and Nevo [1].
1 Introduction↩︎
A simplicial complex \(\mathcal{K}\) is flag provided every minimal non-face of \(\mathcal{K}\) has \(2\) vertices. The condition of flagness often imposes strong combinatorial restrictions on the structure of simplicial spheres. For instance, the boundary of the \(d\)-simplex has \(\binom{d+1}{i+1}\) faces of dimension \(i\), the smallest among all \((d-1)\)-spheres. In contrast, Meshulam [2] proved that a flag simplicial \(d\)-sphere must satisfy \(f_i \geq 2^{d-i}\binom{d}{i}\) for all \(i\), with equality achieved by the boundary of the \(d\)-dimensional cross-polytope.
In this paper, we study graphs of simplicial spheres. A connected graph is said to be \(k\)-connected if it has more than \(k\) vertices and remains connected whenever fewer than \(k\) vertices are removed. The connectivity of a graph is the largest \(k\) for which the graph is \(k\)-connected. A classical result of Balinski [3], later extended by Barnette [4], states that graphs of \((d-1)\)-spheres are \(d\)-connected. In comparison, Athanasiadis [5] proved that the connectivity of the graph of every flag \((d-1)\)-sphere must be at least \(2d-2\).
The independence number \(\alpha(G)\) of a graph \(G\) is the size of its largest independent set. Chudnovsky and Nevo [1] conjectured that if \(\mathcal{K}\) is a flag \((d-1)\)-sphere, then its graph \(G(\mathcal{K})\) satisfies \[\label{eq:32main46eq} \alpha(G(\mathcal{K})) \leq \left\lfloor\frac{f_0(\mathcal{K})-2(d-2)}{2}\right\rfloor.\tag{1}\] The inequality is tight for the \((d-1)\)-sphere obtained by suspending an \((n-2(d-2))\)-gon \(d-2\) times. The assertion is immediate when \(d=2\), while the authors of [1] establish it for \(d=3\); however their arguments are inherently planar.
The analogous statement does not hold for simplicial spheres which are not necessarily flag. Let \(d \geq 4\). The number of facets \(m\) of a neighborly simplicial \((d-1)\)-sphere with \(n\) vertices (such as the boundary of the cyclic polytope \(C(d, n)\)) is on the order of \(n^{\lfloor d/2\rfloor}\); in particular, if \(d \geq 4\), then \(m/n\) approaches zero as \(n \to \infty\). Performing stellar subdivisions at each of the facets gives a complex with \(n + m \sim m\) vertices, while the \(m\) added vertices form an independent set. This shows that there exist simplicial spheres with independent sets of size asymptotically equal to the number of vertices.
In this paper, we disprove the conjecture of Chudnovsky and Nevo for all \(d \geq 4\) by establishing the following result.
Theorem 1. There exists a constant \(C>0\) and a family \(\mathcal{K}_n\) of \(3\)-dimensional flag spheres satisfying \(f_0(\mathcal{K}_n) \to \infty\) as \(n \to \infty\), and \[\alpha(G(\mathcal{K}_n)) \geq f_0(\mathcal{K}_n) - \frac{Cf_0(\mathcal{K}_n)}{(\log f_0(\mathcal{K}_n))^2}\] for all sufficiently large \(n\).
In particular, taking \(n \to \infty\), we obtain \[\frac{\alpha(G(\mathcal{K}_n))}{f_0(\mathcal{K}_n)} \longrightarrow 1.\]
Let \(d=4\). If true, 1 would imply that \(\alpha(G(\mathcal{K})) \leq \left\lfloor\frac{n-4}{2}\right\rfloor\) for all flag \(3\)-spheres \(\mathcal{K}\), in which case the above limit must be bounded above by \(1/2\). So Theorem 1 provides a counterexample to 1 when \(d=4\). When \(d > 4\), we can suspend the \(\mathcal{K}_n\) \((d-4)\)-times to obtain counterexamples of dimension \(d-1\). The resulting complexes still have large independence number, while we only add a constant number of vertices during the suspension.
Organization of the paper. In Section 2, we introduce necessary background on simplicial and cubical complexes, which are the main objects we use in this paper. In Section 3 we give an easier construction which only gives complexes with independence number approaching \(3f_0/4\) but displays the key ideas. Finally, we prove Theorem 1 in Section 4.
2 Background↩︎
2.1 Simplicial Complexes↩︎
A simplicial complex \(\mathcal{K}\) on a vertex set \(V = V(\mathcal{K})\) is a collection of subsets of \(V\) such that \(\{v\} \in \mathcal{K}\) for all \(v \in V\), and \(F \subseteq G \in \mathcal{K}\) implies \(F \in \mathcal{K}\). Elements of \(\mathcal{K}\) are called faces, and maximal faces (with respect to inclusion) are called facets. The dimension of a face \(F\) is \(|F|-1\), and the dimension of \(\mathcal{K}\) is the largest dimension of any face of \(\mathcal{K}\). If every facet of \(\mathcal{K}\) has the same dimension, then \(\mathcal{K}\) is said to be pure. Moreover, \(0\)-dimensional faces are called vertices, \(1\)-dimensional faces are called edges, and when \(\mathcal{K}\) is pure, faces of codimension \(1\) are called ridges. For all \(k \geq 0\), we denote by \(f_k(\mathcal{K})\) the number of \(k\)-dimensional faces of \(\mathcal{K}\).
We often omit the usual set notation for faces when no ambiguity can arise. For example, if \(\{x\}\) is a vertex of \(\mathcal{K}\), we denote it by \(x\), and if \(\{x,y,z\}\) is a face of \(\mathcal{K}\), we denote it by \(xyz\).
Let \(k\geq 0\). The \(k\)-skeleton of \(\mathcal{K}\) is the simplicial complex consisting of all faces of \(\mathcal{K}\) of dimension at most \(k\). We refer to the \(1\)-skeleton of \(\mathcal{K}\) as the graph of \(\mathcal{K}\) and denote it by \(G(\mathcal{K})\).
Every simplicial complex has a geometric realization as a topological space, which is unique up to homeomorphism. A simplicial \((d-1)\)-sphere (or simply a \((d-1)\)-sphere when it is clear from context) is a simplicial complex that is homeomorphic to \(\mathbb{S}^{d-1}\), the \((d-1)\)-dimensional sphere. In general, we will not distinguish a simplicial complex from its geometric realization.
If \(U\) is a subset of the vertex set of \(\mathcal{K}\), then the induced subcomplex \(\mathcal{K}[U]\) is the simplicial complex with vertex set \(U\) whose faces are precisely the faces of \(\mathcal{K}\) contained in \(U\). The cone over \(U\) (also referred to as the cone over \(\mathcal{K}[U]\)) is the simplicial complex obtained by adjoining a new vertex \(v\) (called the cone point) to the vertex set of \(\mathcal{K}\), and whose faces consist of the faces of \(\mathcal{K}\) together with all faces of the form \(F\cup v\), where \(F\) is a face of \(\mathcal{K}[U]\). See Figure 1 for an example.
An important special case of coning is suspension. The suspension of a simplicial complex \(\mathcal{K}\) with vertex set \(V\) is obtained by coning over \(V\) twice. The suspension of a simplicial \((d-1)\)-sphere is homeomorphic to \(\mathbb{S}^d\) (see [6]).
2.1.1 Flag Complexes↩︎
A simplicial complex is flag if all of its minimal non-faces have size \(2\) (see Figure 2 for an example). A set of pairwise adjacent vertices in a graph is a clique. An equivalent characterization of the flag property is that every clique in \(G(\mathcal{K})\) is a face of \(\mathcal{K}\).
Lemma 1. Let \(\mathcal{K}\) be a flag complex with vertex set \(V\). The cone over any subset \(U\subseteq V\) is also flag.
Proof. Let \(x\) be the cone point and let \(A\subseteq V\cup x\) be a clique in the graph of the cone. If \(x\notin A\), then \(A\) is a clique in \(G(\mathcal{K})\), and since \(\mathcal{K}\) is flag, \(A\) is a face of \(\mathcal{K}\). In particular, \(A\) is a face of the cone. Suppose instead that \(x\in A\). Then \(A\setminus x\) is a clique in \(G(\mathcal{K})\), and hence a face of \(\mathcal{K}\) by the flagness of \(\mathcal{K}\). Moreover, \(A\setminus x\subseteq U\), because \(x\) is adjacent only to vertices of \(U\). Therefore \(A\setminus x\) is a face of \(\mathcal{K}[U]\), and it follows from the definition of the cone that \(A\) is a face of the cone. ◻
The lemma implies that suspensions preserve the flag property.
2.2 Cubes & Cubical Complexes↩︎
The \(n\)-cube is the polytope \([0,1]^n\). We refer the reader to [7] for background on polytopes and the combinatorics of cubes. We will only need the following basic fact: every \(k\)-dimensional face of the \(n\)-cube is obtained by fixing \(n-k\) coordinates to be either \(0\) or \(1\) and allowing the remaining \(k\) coordinates to vary freely. Consequently, every \(k\)-face is itself an \(k\)-cube and has \(2^k\) vertices.
The graph \(Q_n\) of \([0,1]^n\) has vertex set \(\{0,1\}^n\), with two vertices \(u\) and \(v\) adjacent if they differ in exactly one coordinate. In general, the distance \(d(u, v)\) between vertices \(u, v\) is the number of coordinates they differ in. As noted above, the vertex set of any \(k\)-dimensional face of \([0,1]^n\) induces a subgraph of \(Q_n\) isomorphic to \(Q_k\). The converse, which we now prove, will be useful in Section 4.
Lemma 2. If \(H\) is a subgraph of \(Q_n\) isomorphic to \(Q_k\), then \(V(H)\) is the set of vertices of some \(k\)-dimensional face of \([0,1]^n\).
Proof. We argue by induction on \(k\). The cases \(k=0\) and \(k=1\) are immediate, so assume \(k\geq 2\). The vertex set of \(H\) can be partitioned into two sets \(A\) and \(B\), each of size \(2^{k-1}\), such that the induced subgraphs on \(A\) and \(B\) are both isomorphic to \(Q_{k-1}\). By the induction hypothesis, \(A\) and \(B\) are the vertex sets of \((k-1)\)-dimensional faces of \([0,1]^n\).
Let \(I\) be the set of coordinates that are fixed on \(A\). We claim that among the coordinates in \(I\), at most one is not fixed in \(B\) to the same value as on \(A\). Suppose otherwise. Then there exist two coordinates \(i,j \in I\) such that \(B\) is either free in those coordinates or fixed to the opposite value. Hence we may choose \(b \in B\) that differs from the fixed values on \(A\) in both coordinates \(i\) and \(j\).
Since \(A\) is the vertex set of a \((k-1)\)-dimensional face, the \(k-1\) coordinates in \([n] \setminus I\) vary freely in \(A\). Choosing \(a \in A\) so that it disagrees with \(b\) in each of these varying coordinates, we obtain \[d(a,b) \geq (k-1)+2 = k+1,\] contradicting the fact that every two vertices of \(H\) are at distance at most \(k\) in \(Q_n\). Indeed, since \(H\) is isomorphic to \(Q_k\), any pair of vertices in \(H\) is connected by a path of length at most \(k\), and each edge of \(Q_n\) changes exactly one coordinate.
It follows that the vertices of \(H\) freely vary in at most \(k\) coordinates, and hence \(V(H)\) is contained in the vertex set of a \(k\)-dimensional face of \([0,1]^n\). Since both \(V(H)\) and any \(k\)-dimensional face have \(2^k\) vertices, \(V(H)\) must coincide with the vertex set of such a face. ◻
A cubical complex \(\mathcal{B}\) on a vertex set \(V\) is a collection of subsets of \(V\), partially ordered by inclusion, satisfying the following properties:
\(\varnothing\in\mathcal{B}\) and \({v}\in\mathcal{B}\) for every \(v\in V\).
For every nonempty face \(F\in\mathcal{B}\), the interval \[[\varnothing,F]=\{G\in\mathcal{B}:\varnothing\subseteq G\subseteq F\}\] is isomorphic to the face poset of a cube of some dimension.
If \(F,G\in\mathcal{B}\), then \(F\cap G\in\mathcal{B}\).
The elements of \(\mathcal{B}\) are called faces. If \(F\in\mathcal{B}\) is nonempty, the dimension of \(F\) is the dimension of the cube whose face poset is isomorphic to \([\varnothing,F]\). The dimension of \(\mathcal{B}\) is the largest dimension of any face of \(\mathcal{B}\). As in the simplicial setting, maximal faces are called facets, \(0\)-dimensional faces are called vertices, \(1\)-dimensional faces are called edges, and in a pure cubical complex, faces of codimension \(1\) are called ridges. We denote by \(f_k(\mathcal{B})\) the number of \(k\)-dimensional faces of \(\mathcal{B}\).
Many constructions for simplicial complexes have cubical analogues. In particular, the graph of \(\mathcal{B}\), denoted \(G(\mathcal{B})\), is the graph whose vertices are the vertices of \(\mathcal{B}\) and whose edges are the \(1\)-dimensional faces of \(\mathcal{B}\).
Every cubical complex admits a geometric realization as a topological space, unique up to homeomorphism. A cubical \((d-1)\)-sphere is a cubical complex whose geometric realization is homeomorphic to \(\mathbb{S}^{d-1}\).
2.2.1 Neighborly Cubical Spheres↩︎
A cubical \((d-1)\)-sphere is said to be neighborly if its \((\lfloor d/2\rfloor-1)\)-skeleton is that of a cube. Any neighborly cubical \((d-1)\)-sphere must have \(2^n\) vertices for some \(n\geq d\). For every \(d\geq 1\) and \(n\geq d\), Babson, Billera, and Chan [8] constructed neighborly cubical \((d-1)\)-spheres with \(2^n\) vertices in 1997. Subsequently, Joswig and Ziegler [9] gave constructions of such spheres that are realizable as boundaries of convex polytopes.
The face numbers of cubical spheres satisfy a version of the Dehn–Sommerville equations [10]. Combined with the structure of neighborly spheres, these relations imply that if \(\mathcal{P}\) is a neighborly cubical \((d-1)\)-sphere, then \[\label{eq:32facet46bound} M_1 f_0(\mathcal{P})(\log f_0 (\mathcal{P}))^{\lfloor d/2\rfloor} \leq f_{d-1}(\mathcal{P}) \leq M_2 f_0(\mathcal{P})(\log f_0(\mathcal{P}))^{\lfloor d/2\rfloor}\tag{2}\] for some constants \(M_1, M_2 > 0\) depending only on \(d\).
3 A Simple Warm-Up↩︎
In this section we construct a family of flag \(3\)-spheres whose independence number is asymptotically at least \(\frac{3}{4} f_0\).
First we describe a flag triangulation of the \(3\)-dimensional cube \([0,1]^3\). Start with the graph of the cube and for each \(2\)-face \(R\) of the cube, cone the graph over the four vertices of \(R\) (or, equaivalently, over the boundary of \(R\)); see Section 2.1 for the definition of coning. This gives a triangulation of the boundary of the cube (see Figure 3). Next, cone over this triangulated \(2\)-sphere from a new interior vertex. The resulting simplicial complex \(\mathcal{C}\) triangulates the cube.
To see that \(\mathcal{C}\) is flag, observe that the graph of \([0,1]^3\) is triangle-free and hence a \(1\)-dimensional flag complex. Since each step of the construction is a coning over a subset of vertices — an operation that by Lemma 1, preserves fagness — it follows that \(\mathcal{C}\) is flag.
![Figure 3: A triangulated square face and the corresponding triangulation of the boundary of [0,1]^3.](/article/2606.16109/_pdflatex/hyfvqkus.png "fig:")
Let \(\mathcal{P}_n\) be a \(3\)-dimensional neighborly cubical sphere with \(f_0(\mathcal{P}_n)=2^n\). Every facet of \(\mathcal{P}_n\) is combinatorially a \(3\)-cube. We construct a simplicial complex \(\mathcal{S}_n\) by replacing each facet \(F\) of \(\mathcal{P}_n\) with a copy of \(\mathcal{C}\), and identifying boundary faces in the natural way. If \(F\) is a facet of \(\mathcal{P}_n\), let \(\mathcal{C}(F)\) denote the subcomplex of \(\mathcal{S}_n\) induced by the vertices introduced in the subdivision of \(F\), namely the original vertices of \(F\), the vertices corresponding to \(2\)-faces of \(F\) (ridges of \(\mathcal{P}_n\)), and the vertex corresponding to \(F\) itself. For every facet \(F\), the subcomplex \(\mathcal{C}(F)\) is combinatorially equivalent to \(\mathcal{C}\).
This is well-defined because the subdivisions on adjacent facets agree on their intersection. Indeed, if two facets \(F_1\) and \(F_2\) intersect in a ridge \(R\), then the induced subdivision on \(R\) in both \(\mathcal{C}(F_1)\) and \(\mathcal{C}(F_2)\) is the cone over the boundary of \(R\). Hence the triangulations agree along \(R\) and glue to a simplicial complex.
Proposition 1. The simplicial complex \(\mathcal{S}_n\) is a flag \(3\)-sphere.
Proof. Let \(A\) be a clique in the graph of \(\mathcal{S}_n\). We show that \(A\) is the set of vertices of some face of \(\mathcal{S}_n\).
Let \(V_O\), \(V_{\mathrm{ridge}}\), and \(V_{\mathrm{facet}}\) denote the sets of original vertices, ridge vertices, and facet vertices, respectively. Since the graph of \(\mathcal{P}_n\) is triangle-free, any clique of size at least three in \(\mathcal{S}_n\) contains a vertex in \(V_{\mathrm{ridge}}\cup V_{\mathrm{facet}}\).
First suppose \(A\) contains a facet vertex \(v \in V_{\mathrm{facet}}\) corresponding to a facet \(F\). By construction, \(v\) is adjacent only to vertices in \(\mathcal{C}(F)\), hence \(A \subseteq V(\mathcal{C}(F))\).
Now suppose \(A\) contains no facet vertex but contains a vertex \(w \in V_{\mathrm{ridge}}\) corresponding to a ridge \(R\). The only neighbors of \(w\) are the four vertices of the face \(R\) along with vertices in \(V_{\mathrm{facet}}\) corresponding to each facet containing \(R\). Since \(A \cap V_{\mathrm{facet}}= \varnothing\), \(A \subseteq V(\mathcal{C}(F))\) for some facet \(F\) containing \(R\).
In either case, \(A \subseteq V(\mathcal{C}(F))\) for some facet \(F\). Since each \(\mathcal{C}(F)\) is flag, it follows that \(A\) is a face of \(\mathcal{C}(F)\), hence also of \(\mathcal{S}_n\). Therefore \(\mathcal{S}_n\) is flag.
Furthermore, \(\mathcal{S}_n\) triangulates the \(3\)-sphere \(\mathcal{P}_n\), which shows that it is a flag \(3\)-sphere. ◻
Theorem 1. The complexes \(\mathcal{S}_n\) satisfy \[\lim\limits_{n \to \infty}\frac{\alpha(G(\mathcal{S}_n))}{f_0(S_n)} \geq \frac{3}{4}.\]
Proof. The vertices of \(\mathcal{S}_n\) consist of the original vertices of \(\mathcal{P}_n\), together with one vertex for every ridge and one vertex for every facet. Hence \(f_0(\mathcal{S}_n)=f_0(\mathcal{P}_n)+f_2(\mathcal{P}_n)+f_3(\mathcal{P}_n)\). Each facet of \(\mathcal{P}_n\) contains \(6\) ridges of \(\mathcal{P}_n\), and since \(\mathcal{P}_n\) is a simplicial \(3\)-sphere, each ridge belongs to exactly two facets. Therefore \(f_2(\mathcal{P}_n)=3f_3(\mathcal{P}_n)\), and hence \[f_0(\mathcal{S}_n)=f_0(\mathcal{P}_n)+4f_3(\mathcal{P}_n).\]
Let \(V_{\mathrm{ridge}}\) denote the set of ridge vertices in \(\mathcal{S}_n\). Since no two ridge vertices are adjacent, \(V_{\mathrm{ridge}}\) is an independent set in \(G(\mathcal{S}_n)\). Thus \[\alpha(G(\mathcal{S}_n)) \geq |V_{\mathrm{ridge}}| = 3f_3(\mathcal{P}_n).\] It follows that \[\frac{\alpha(G(\mathcal{S}_n))}{f_0(\mathcal{S}_n)} \geq \frac{3f_3(\mathcal{P}_n)}{f_0(\mathcal{P}_n)+4f_3(\mathcal{P}_n)}.\]
Since \(f_0(\mathcal{P}_n)=2^n\) and \(f_3(\mathcal{P}_n)=\Theta(n^2 2^n)\) by 2 , we have \(\frac{f_0(\mathcal{P}_n)}{f_3(\mathcal{P}_n)} \to 0\) as \(n \to \infty\). We conclude that \[\lim_{n\to\infty}\frac{\alpha(G(\mathcal{S}_n))}{f_0(\mathcal{S}_n)} \geq \frac{3}{4}.\] ◻
4 Proof of Theorem 1↩︎
In this section, we prove Theorem 1. While Theorem 1 already disproves the conjecture of Chudnovsky and Nevo, the construction below shows that the constant \(1/2\) in the conjectured bound cannot be replaced by \(1-\varepsilon\) for any \(\varepsilon>0\).
As before, our strategy is to construct a flag triangulation of the \(3\)-cube \([0,1]^3\) and then replace every facet of a neighborly cubical \(3\)-sphere with this triangulated cube to obtain a simplicial \(3\)-sphere.
We triangulate the boundary of the cube as follows: each square face is divided by adding the diagonal joining the vertex with the fewest number of ones to the vertex with the most ones among its four vertices. We then cone over this triangulated boundary to obtain a triangulation of the cube, denoted by \(\mathcal{D}\). It is straightforward to verify (for example from Figure 4) that the triangulation of the boundary of the cube is flag. Since \(\mathcal{D}\) is a cone over the boundary, Lemma 1 implies that \(\mathcal{D}\) must be flag.
![Figure 4: The diagonals added to [0,1]^3 and the resulting triangulation of its boundary.](/article/2606.16109/_pdflatex/kfzwrpmg.png "fig:")
Now let \(\mathcal{P}_n\) be a neighborly cubical \(3\)-sphere with \(2^n\) vertices. We describe how to replace each facet of \(\mathcal{P}_n\) with a copy of \(\mathcal{D}\). Fix a labelling of the vertices of \(\mathcal{P}_n\) by \(\{0,1\}^n\). The graph of \(\mathcal{P}_n\) is the graph \(Q_n\) of the n-cube \([0,1]^n\). For this reason, we can fix a labeling of the vertices of \(\mathcal{P}_n\) by \(\{0,1\}^n\). Furthermore, each facet of \(\mathcal{P}_n\) determines a subgraph of \(Q_n\) isomorphic to \(Q_3\). Hence, by Lemma 2, the vertices of such a facet are obtained by fixing \(n-3\) coordinates and allowing the remaining three to vary. Forgetting the fixed coordinates identifies the vertices of the facet with \(\{0,1\}^3\), thereby allowing us to transfer the triangulation \(\mathcal{D}\) to each facet.
This produces a well-defined triangulation \(\mathcal{K}_n\) of \(\mathcal{P}_n\). Indeed, it suffices to check compatibility on intersections of adjacent facets. Suppose two facets \(F_1\) and \(F_2\) intersect in a ridge \(R\). By Lemma 2, \(R\) corresponds to fixing \(n-2\) coordinates and freely varying the other two. Under either identification with \(\{0,1\}^3\), the induced triangulation on \(R\) is determined by the same rule: the diagonal connects the vertex with the fewest number of ones to the vertex with the most ones. Hence the triangulations induced from \(F_1\) and \(F_2\) agree on \(R\).
If \(F\) is a facet of \(\mathcal{P}_n\), let \(\mathcal{D}(F)\) denote the subcomplex of \(\mathcal{S}_n\) induced by the vertices introduced in the subdivision of \(F\), namely the original vertices of \(F\), and the vertex corresponding to \(F\) itself. For every facet \(F\), the subcomplex \(\mathcal{D}(F)\) is combinatorially equivalent to \(\mathcal{D}\).
Proposition 1. The simplicial complex \(\mathcal{K}_n\) is a flag \(3\)-sphere.
Proof. We will show that every clique in the graph of \(\mathcal{K}_n\) is contained in the graph of \(\mathcal{D}(F)\) for some facet \(F\) of \(\mathcal{P}_n\). Since the triangulation induced by each facet is flag, it will then follow, exactly as in the proof of Proposition 1, that \(\mathcal{K}_n\) is flag.
Let \(V_O\) and \(V_{\mathrm{facet}}\) denote the sets of original vertices and facet vertices, respectively. Let \(A\) be a clique. If \(|A|\leq 2\), there is nothing to prove, so assume that \(|A|\geq 3\). If \(A\) intersects \(V_{\mathrm{facet}}\), then there is a unique vertex \(v \in A \cap V_{\mathrm{facet}}\) because \(V_{\mathrm{facet}}\) is an independent set. Since neighbors of a facet vertex are exactly the vertices of the corresponding facet, it follows that \(A\) is contained in \(V(\mathcal{D}(F))\) for some facet \(F\).
Suppose therefore that \(A\) does not intersect \(V_{\mathrm{facet}}\). Then \(A\) is contained in \(V_O\). We will show that every clique in the graph of \(\mathcal{K}_n[V_O]\) is contained in a ridge of \(\mathcal{P}_n\).
Every edge of \(\mathcal{K}_n[V_O]\) is either an edge of \(\mathcal{P}_n\) or a diagonal added in a ridge. We call these edges type \(1\) and type \(2\), respectively. If an edge is of type \(1\), then the number of ones in its endpoints differs by \(1\), while if an edge is of type \(2\), it differs by \(2\).
Consider a triangle in the graph of \(\mathcal{K}_n[V_O]\). Traversing its edges and recording the change in the number of ones modulo \(2\), we see that the number of type \(1\) edges must be even. Hence a triangle contains either \(0\) or \(2\) type \(1\) edges.
On the other hand, a triangle cannot consist entirely of type \(2\) edges. Indeed, traversing a type \(2\) edge changes the number of ones by \(\pm 2\), and so the net change around such a triangle would be congruent to \(2\) modulo \(4\), contradicting the fact that the net change around a cycle must be \(0\). Thus every triangle contains exactly two type \(1\) edges and one type \(2\) edge; we call such triangles \(112\)-triangles.
Suppose \(A={x_1,\ldots,x_k}\). Since every three vertices of \(A\) form a triangle, the triangle \(x_1x_2x_3\) is a \(112\)-triangle. Relabeling if necessary, we may assume that \(x_1x_2\) is the unique type \(2\) edge. Since \(x_1x_2x_i\) is also a \(112\)-triangle for every \(i\geq 3\), it follows that both \(x_1x_i\) and \(x_2x_i\) are type \(1\) edges.
Because \(x_1\) and \(x_2\) differ in exactly two coordinates, there are exactly two vertices that differ from both \(x_1\) and \(x_2\) in exactly one coordinate. These are the remaining two vertices of the ridge having diagonal \(x_1x_2\). Consequently \(k\leq 4\), and every vertex of \(A\) lies in this ridge. Therefore \(A\) is contained in a ridge of \(\mathcal{P}_n\), and hence in \(\mathcal{D}(F)\) for any facet \(F\) containing that square.
We have shown that every clique of \(\mathcal{K}_n\) is contained in \(\mathcal{D}(F)\) for some facet \(F\). Since \(\mathcal{D}(F)\) is flag, every clique in its graph is a face of \(\mathcal{D}(F)\), and hence of \(\mathcal{K}_n\). Thus, \(\mathcal{K}_n\) is flag.
The complex \(\mathcal{K}_n\) triangulates the \(3\)-sphere \(\mathcal{P}_n\), which shows that it is a flag \(3\)-sphere. ◻
Now we can prove our main theorem.
Proof of Theorem 1. The complex \(\mathcal{K}_n\) has vertex set equal to the vertex set of \(\mathcal{P}_n\) together with a vertex for each facet of \(\mathcal{P}_n\), and hence \[f_0(\mathcal{K}_n)=f_0(\mathcal{P}_n)+f_3(\mathcal{P}_n).\] Since the set of facet vertices is independent, \(\alpha(G(\mathcal{K}_n))\geq f_3(\mathcal{P}_n)\). Therefore \[\label{eq:32ugly} \frac{\alpha(G(\mathcal{K}_n))}{f_0(\mathcal{K}_n)} \geq \frac{f_3(\mathcal{P}_n)}{f_0(\mathcal{P}_n)+f_3(\mathcal{P}_n)} = 1-\frac{f_0(\mathcal{P}_n)}{f_0(\mathcal{P}_n)+f_3(\mathcal{P}_n)} \geq 1-\frac{f_0(\mathcal{P}_n)}{f_3(\mathcal{P}_n)}.\tag{3}\]
Recall that \(f_0(\mathcal{P}_n)=2^n\), and so, by 2 , there exist constants \(M_1,M_2>0\) such that \[M_1n^22^n\leq f_3(\mathcal{P}_n)\leq M_2n^22^n.\] The upper bound implies \(f_0(\mathcal{K}_n)\leq 2^n(1+M_2n^2)\leq e^n\) for sufficiently large \(n\), and hence \(\log f_0(\mathcal{K}_n)\leq n\). Combining this with the lower bound on \(f_3(\mathcal{P}_n)\) gives \[\frac{f_0(\mathcal{P}_n)}{f_3(\mathcal{P}_n)} \leq \frac{1}{M_1n^2} \leq \frac{1}{M_1(\log f_0(\mathcal{K}_n))^2}.\] Substituting into 3 and multiplying through by \(f_0(\mathcal{K}_n)\) gives \[\alpha(G(\mathcal{K}_n)) \geq f_0(\mathcal{K}_n)-\frac{Cf_0(\mathcal{K}_n)}{(\log f_0(\mathcal{K}_n))^2},\] where \(C=1/M_1\). ◻
Remark 1 (Higher Dimensions). In fact, Theorem 1 extends to flag spheres of all dimensions at least \(3\). If \(d \geq 4\), then we can suspend \(\mathcal{K}_n\) \((d-4)\)-times to obtain a flag \((d-1)\)-sphere \(\mathcal{K}_{d,n}\). Each suspension adds two new vertices, so \[f_0(\mathcal{K}_{d,n})=f_0(\mathcal{K}_n)+2d-8.\] Moreover, any independent set in the graph of \(\mathcal{K}_n\) is also an independent set in the graph of \(\mathcal{K}_{d,n}\), and hence \[\alpha(G(\mathcal{K}_{d,n}))\geq \alpha(G(\mathcal{K}_n)).\] Therefore, \[\lim_{n\to\infty}\frac{\alpha(G(\mathcal{K}_{d,n}))}{f_0(\mathcal{K}_{d,n})} \geq \lim_{n\to\infty}\frac{\alpha(G(\mathcal{K}_n))}{f_0(\mathcal{K}_n)+2d-8} =1.\] In particular, 1 is false for all \(d\geq 4\).
Acknowledgements 1. The author thanks Isabella Novik for her invaluable guidance throughout this project and for her many helpful comments and suggestions on the manuscript.