3 ms·
I think I'm misunderstanding or you left out an important condition. For your example where H forms a loop, I imagine an element of F_H which is a larger loop.
by ball_of_lint 5y ago
I think I'm misunderstanding or you left out an important condition.
For your example where H forms a loop, I imagine an element of F_H which is a larger loop. Then it could be arbitrarily large, have no cliques above size 2, a linear number of cliques of size 2, and have only one independent set.
- Dagonfly 5y agoI'm not an expert, but I think you are confused about what 'independent set' means. It's basically 'no vertex pair v,w in the set has a edge (v,w)' So in your loop example, you can take every other vertex in the loop and those form an independent set (of size n/2 ish). And n/2 is in Ω(n).