Triangle-free graph with sub-power independence number

ID: triangle-free-graph-with-sub-power-independence-number

For every sufficiently large , there is a triangle-free graph on vertices with . One construction samples : with positive probability it has fewer than triangles and no independent set of size . Delete one vertex from each triangle and then take an induced -vertex subgraph.

New to topics? Read the docs here!