Counting subgraphs in locally dense graphs

A graph G is said to be p-locally dense if every induced subgraph of G with linearly many vertices has edge density at least p. A famous conjecture of Kohayakawa, Nagle, R\"odl, and Schacht predicts that locally dense graphs have, asymptotically, at least as many copies of any fixed graph H as are found in a random graph of edge density p. In this paper, we prove several results around the KNRS conjecture. First, we prove that certain natural gluing operations on H preserve this property, thus proving the conjecture for many graphs H for which it was previously unknown. Secondly, we study a stability version of this conjecture, and prove that for many graphs H, approximate equality is attained in the KNRS conjecture if and only if the host graph G is quasirandom. Finally, we introduce a weakening of the KNRS conjecture, which requires the host graph to be nearly degree-regular, and prove this conjecture for a larger family of graphs. Our techniques reveal a surprising connection between these questions, semidefinite optimization, and the study of copositive matrices.