Algorithmically Adjusting Subgraph Counts of Randomly Sampled Graphs

Algorithmically Adjusting Subgraph Counts of Randomly Sampled Graphs

Algorithmically Adjusting Subgraph Counts of Randomly Sampled Graphs

יום רביעי, יוני 17, 2026
  • דובר: Hillel Raz
  • מארגן: Howard Nuer and Alan Lew
  • מיקום: 8th floor Lounge
  • קובץ מצורף: לחץ להורדה
Abstract:
A result of Janson and Spencer (1992) establishes, via a greedy probabilistic construction, the existence of graphs whose 3-vertex subgraph counts match exactly the expected counts in the Erd˝os–R´enyi random graph G(n,p). In this talk, I will present a general algorithmic framework extending this construction to any graphon bounded away from 0 and 1. Graphons arise as limit objects of dense graphs and encode their subgraph densities. By extending the original method—here referred to as the Janson–Spencer algorithm—we construct finite graphs whose 3-vertex subgraph counts agree exactly with the averages prescribed by the random graph model induced by a given graphon. I will then discuss further applications of this approach to extremal problems: when a graphon is close to optimizing certain subgraph counts, the algorithm produces quantitative degeneracy and structural rigidity results. These results provide finite, explicit analogues of variational principles on graphons, connecting algorithmic constructions with analytic extremal methods.
הדפס ל-PDF