Counting in random combinatorial structures
组织者
马杰
, 本杰明·苏达科夫
演讲者
Peter Allen
时间
2026年05月19日 17:05 至 18:15
地点
Online
线上
Zoom 787 662 9899
(BIMSA)
摘要
Conlon and Gowers in 2016 described a general approach to proving sparse random analogues of extremal results in combinatorics, such as bounding the minimum and maximum number of triangles in any subgraph of G(n,p) with a given number of edges. The general part of this approach is a functional-analytic statement which, given a sparse setting, constructs a 'dense model'. However there is a condition which must be shown to hold with high probability to apply the dense model theorem. In Conlon and Gowers' work, there is a technical difficulty with the probabilistic part which leads to a rather involved proof, which applies only in a restricted setting (for example, they can handle triangles but not triangles with a pendant edge), and with quite poor bounds on 'high probability'.
Around the same time Schacht, with a very different method, was able to prove a related result, which is applicable in a much more general setting and which has optimal bounds on 'high probability': but Schacht's result does not provide sharp lower bounds on the number of triangles, and does not provide any upper bounds. What it does do is identify the number of edges in a subgraph of G(n,p) which guarantee that triangles will appear; subsequently the 'hypergraph container method' provides another approach to proving this kind of result, but again does not provide sharp lower bounds or any upper bounds.
We revisit Conlon and Gowers' approach, and show how to avoid their technical problem, giving a simpler proof of their counting result which applies in the general setting and with optimal probability bounds. As a corollary, we prove the 'Counting KLR' theorem of Conlon, Gowers, Samotij and Schacht, but for general hypergraphs and with optimal probability bounds. This is joint work with Julia Boettcher, Joanna Lada and Domenico Mergoni.
Around the same time Schacht, with a very different method, was able to prove a related result, which is applicable in a much more general setting and which has optimal bounds on 'high probability': but Schacht's result does not provide sharp lower bounds on the number of triangles, and does not provide any upper bounds. What it does do is identify the number of edges in a subgraph of G(n,p) which guarantee that triangles will appear; subsequently the 'hypergraph container method' provides another approach to proving this kind of result, but again does not provide sharp lower bounds or any upper bounds.
We revisit Conlon and Gowers' approach, and show how to avoid their technical problem, giving a simpler proof of their counting result which applies in the general setting and with optimal probability bounds. As a corollary, we prove the 'Counting KLR' theorem of Conlon, Gowers, Samotij and Schacht, but for general hypergraphs and with optimal probability bounds. This is joint work with Julia Boettcher, Joanna Lada and Domenico Mergoni.