Improved counting relative to pseudorandom graphs

Graphs, Hypergraphs, and Computing

24 April 15:30 - 16:30

Jozef Skokan - The London School of Economics and Political Science (LSE)

Recently, Conlon, Fox and Zhao proved a counting lemma, counting small graphs in epsilon-regular subgraphs of sparse pseudorandom graphs. This counting lemma has many important applications such as sparse pseudorandom analogues of Turan's Theorem, Ramsey's Theorem and the graph removal lemma.

One key ingredient for the proof of their counting lemma is a regularity inheritance lemma, which states that for most vertices in an epsilon-regular subgraph of a pseudorandom graph, the neighbourhoods of this vertex form an epsilon'-regular graph. We improve this regularity inheritance lemma, so that it now applies to graphs with weaker pseudorandomness conditions. This implies an improved counting lemma relative to these pseudorandom graphs.

Based on joint work with Peter Allen, Julia Boettcher, Maya Stein.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to