Extremal results for random discrete structures

By Mathias Schacht. 2016

163 citations recorded by the source corpus.

We study thresholds for extremal properties of random discrete structures. We determine the threshold for Szemeredi's theorem on arithmetic progressions in random subsets of the integers and its multidimensional extensions and we determine the threshold for Turan-type problems for random graphs and hypergraphs. In particular, we verify a conjecture of Kohayakawa, Łuczak, and Rodl for Turan-type problems in random graphs. Similar results were obtained by Conlon and Gowers.

Subfields: Algebra and Number Theory, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/8185f597033462bd12e8af811bad1149af341bcb

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algebra and Number Theory

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Diagonal Ramsey via effective quasirandomness (2020, background): “[10, 1, 3, 19, 6, 7]) in connection with extremal graph theory and additive combinatorics.”
THE METHOD OF HYPERGRAPH CONTAINERS (2018, methodology): “In this survey we will describe an alternative approach to the problem of understanding the family of independent sets in a hypergraph, whose development was inspired by the work in [25, 43, 83] and also strongly influenced by that of Kleitman and Winston [56] and Sapozhenko [77, 78, 79].”
The existence of designs via iterative absorption (2016, background): “Recent highlights include the transference results for random hypergraphs by Conlon and Gowers [10] as well as Schacht [39].”