Let be an integer and let be a finite simple graph with at most vertices and edges. The random graph on includes each edge independently with probability . For finite simple graphs and , let count the subgraphs of isomorphic to , allowing additional edges between their vertices. The containment threshold is . The graph expectation threshold is . The problem is to bound the containment threshold in terms of the graph expectation threshold uniformly as varies with .
Kahn and Kalai conjectured that uniformly over . Dubroff, Kahn, and Park proved the general bound . Tran improved this to .
The preprint proves . It also proves .
The Lean library GraphThreshold formalizes these threshold bounds. Lean has checked every result of the Lean library, so the Lean library is the reference for the statements on these pages. Each result is stated as in the Lean library and linked to its statement there. Where a statement differs from the preprint’s, the preprint’s statement is given beside the Lean library’s. The preprint is a guide only to the order and names of the results.
GraphThreshold is a Lean library: 11 items, in four groups. Each has a page written by OctoInform, listed below.
No item matches.