Talk information

Date: Sunday, April 19, 2026
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Hillel Raz (Technion)
Title: Algorithmically Adjusting Subgraph Counts of Randomly Sampled Graphs

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ős–Rényi 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.