Large Independent Sets in Flag Spheres

Abstract

For every $d\ge 4$, we construct a family of $(d-1)$-dimensional flag simplicial spheres ${\mathcal{K}}_n$ whose graphs contain independent sets of size asymptotically equal to the number of vertices. More precisely, we prove that for sufficiently large $n$, $$\hat{I}\pm (G({\mathcal{K}}_n))\ge f_0({\mathcal{K}}_n)-\frac{C{f}_0({\mathcal{K}}_n)}{{\left(\log f_0({\mathcal{K}}_n)\right)}^{\lfloor d/2\rfloor -1}},$$ where $C=C(d)>0$. This disproves a recent conjecture of Chudnovsky and Nevo.

Revised the statement and proof of Theorem 1.2, fixed typos and updated figures. 11 pages, 4 figures