The Setting
For a finite graph with a forbidden clique, the extremal question is how large an independent set must be in terms of the order and average degree.
Let be a finite simple graph, and write and for the maximum size of an independent set in . The average degree of is the real number given by (1) when is nonempty, and is zero when is empty. (1) For an integer , a -free graph is a graph containing no clique on vertices. All logarithms are natural.
The Claim
Theorem 1. For every integer there is a real constant such that every finite simple -free graph with satisfies the logarithmic independence bound (2): (2)✦
What Is Checked
The claim is stated over finite simple -free graphs with , using their independence numbers and the average degree (1), assumed to be at least two.