2024/06/18 by Domagoj Bradač, Benny Sudakov, Bradač, Domagoj +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2406.12418
openalex publication_date 2024/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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ödl, 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.