Combinatorial theorems relative to sparse sets

2026/08/02 by David Conlon
Mathematics · #math.CO

paper · pdf

16 pages, survey written for the Proceedings of the 2025 ICBS

arxiv created 2026/08/02 · arxiv updated 2026/08/04

Abstract

A key theme in modern extremal combinatorics is the study of classical combinatorial theorems relative to sparse subsets of their natural settings. Here we describe some of the recent progress in this area and state a number of problems that remain open and pressing.

Citations

• Resolution of the Kohayakawa-Kreuter conjecture
• On the Kohayakawa-Kreuter conjecture
• Proof of the Kohayakawa--Kreuter conjecture for the majority of cases
• Canonical colourings in random graphs
• Partition universality for graphs of bounded degeneracy and degree
• Size-Ramsey numbers of graphs with maximum degree three
• The size-Ramsey number of cubic graphs
• Which graphs can be counted in C₄-free graphs?
• A clique-free pseudorandom subgraph of the pseudo polarity graph
• An upper bound on the size of Sidon sets
• Size-Ramsey numbers of powers of hypergraph trees and long subdivisions
• The regularity method for graphs with few 4-cycles
• A note on pseudorandom Ramsey graphs
• Many Turan exponents via subdivisions
• A construction for clique-free pseudorandom graphs
• Towards the Kohayakawa--Kreuter conjecture on asymmetric Ramsey properties
• The method of hypergraph containers
• Large-scale structures in random graphs
• Blow-up lemmas for sparse graphs
• Regularity inheritance in pseudorandom graphs
• Polynomial patterns in the primes
• Rational exponents in extremal graph theory
• Random algebraic construction of extremal graphs
• Combinatorial theorems relative to a random set
• The history of degenerate (bipartite) extremal graph problems
• Independent sets in hypergraphs
• Stability results for random discrete structures
• Dirac's theorem for random graphs
• Combinatorial theorems in sparse random sets
• Hypergraph regularity and the multidimensional Szemerédi theorem
• The primes contain arbitrarily long arithmetic progressions
• A sharp threshold for random graphs with a monochromatic triangle in every edge coloring
• On sets of integers containing k elements in arithmetic progression
• On Certain Sets of Integers