Let V be a linear subspace of M_n(C) which contains the identity matrix and is stable under Hermitian transpose. A "quantum k-clique" for V is a rank k orthogonal projection P in M_n(C) for which dim(PVP) = k^2, and a "quantum k-anticlique" is a rank k orthogonal projection for which dim(PVP) = 1. We give upper and lower bounds both for the largest dimension of V which would ensure the existence of a quantum k-anticlique, and for the smallest dimension of V which would ensure the existence of a quantum k-clique.