OctoInformBeta

OpenAI preprint, September 2026 · Section 1. Introduction

Theorem 1.1: A positive constant for each excluded clique size r≥4r\ge4, with average degree at least two

A logarithmic bound for clique-free graphs.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

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 G=(V,E)G=(V,E) be a finite simple graph, and write n=|V|n=|V| and α(G)\alpha(G) for the maximum size of an independent set in GG. The average degree d(G)d(G) of GG is the real number given by (1) when VV is nonempty, and is zero when VV is empty. d(G)=2|E||V|.d(G)=\frac{2|E|}{|V|}.(1) For an integer r≥1r\ge1, a KrK_r-free graph GG is a graph containing no clique on rr vertices. All logarithms are natural.

The Claim

Theorem 1. For every integer r≥4r\ge4 there is a real constant cr>0c_r>0 such that every finite simple KrK_r-free graph GG with d(G)≥2d(G)\ge2 satisfies the logarithmic independence bound (2): α(G)≥crnlog⁡d(G)d(G).\alpha(G)\ge c_r n\,\frac{\log d(G)}{d(G)}.(2)✦

What Is Checked

The claim is stated over finite simple KrK_r-free graphs with r≥4r\ge4, using their independence numbers and the average degree (1), assumed to be at least two.