Extremal results for random discrete structures
From MaRDI portal
Publication:350549
DOI10.4007/ANNALS.2016.184.2.1zbMATH Open1351.05207arXiv1603.00894OpenAlexW3103981711WikidataQ97694035 ScholiaQ97694035MaRDI QIDQ350549FDOQ350549
Authors: M. Schacht 
Publication date: 7 December 2016
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Abstract: We study thresholds for extremal properties of random discrete structures. We determine the threshold for Szemer'edi's theorem on arithmetic progressions in random subsets of the integers and its multidimensional extensions and we determine the threshold for Tur'an-type problems for random graphs and hypergraphs. In particular, we verify a conjecture of Kohayakawa, L uczak, and R"odl for Tur'an-type problems in random graphs. Similar results were obtained by Conlon and Gowers.
Full work available at URL: https://arxiv.org/abs/1603.00894
Recommendations
Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Combinatorial probability (60C05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)
Cites Work
- Graph theory
- Graph theory
- Title not available (Why is that?)
- Title not available (Why is that?)
- On extremal problems of graphs and generalized graphs
- Title not available (Why is that?)
- On the structure of linear graphs
- Random graphs.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Combinatorial theorems in sparse random sets
- On sets of integers containing k elements in arithmetic progression
- On a problem of K. Zarankiewicz
- An ergodic Szemerédi theorem for commuting transformations
- Arithmetic progressions of length three in subsets of a random set
- An extremal problem for random graphs and the number of graphs with large even-girth
- Turán's extremal problem in random graphs: Forbidding even cycles
- On \(K^ 4\)-free subgraphs of random graphs
- Rado Partition Theorem for Random Subsets of Integers
- Threshold Functions for Ramsey Properties
- Supersaturated graphs and hypergraphs
- Large triangle-free subgraphs in graphs without \(K_ 4\)
- Quantitative theorems for regular systems of equations
- Random Ramsey graphs for the four-cycle
- On Schur properties of random subsets of integers
- Studien zur Kombinatorik
- Turán's extremal problem in random graphs: Forbidding odd cycles
- Ramsey properties of random discrete structures
- Title not available (Why is that?)
- Ramsey Properties of Random k-Partite, k-Uniform Hypergraphs
- Turán's theorem in sparse random graphs
- K5‐free subgraphs of random graphs
- Extremal subgraphs of random graphs
- The Turn Theorem for Random Graphs
- On Some Sequences of Integers
- Title not available (Why is that?)
Cited In (87)
- A note on sparse supersaturation and extremal results for linear homogeneous systems
- Sampling hierarchies of discrete random structures
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Dirac-type theorems in random hypergraphs
- Polynomial configurations in subsets of random and pseudo-random sets
- Independent sets in hypergraphs
- Combinatorial theorems in sparse random sets
- A randomized version of Ramsey's theorem
- Counting independent sets in graphs
- Independent sets in algebraic hypergraphs
- A multi-dimensional Szemerédi theorem for the primes via a correspondence principle
- Hypergraph containers
- An efficient container lemma
- An analogue of the Erdős-Gallai theorem for random graphs
- Threshold progressions in covering and packing contexts
- Ramsey games near the critical threshold
- Random sum-free subsets of abelian groups
- Ramsey properties of random discrete structures
- On zero-sum free sequences contained in random subsets of finite cyclic groups
- The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups
- The number of \(K_{m,m}\)-free graphs
- Relative Turán problems for uniform hypergraphs
- On the stability of the Erdős-Ko-Rado theorem
- Integer colorings with no rainbow \(k\)-term arithmetic progression
- Bandwidth theorem for random graphs
- On two-point configurations in subsets of pseudo-random sets
- Independent sets in hypergraphs and Ramsey properties of graphs and the integers
- Deviation probabilities for arithmetic progressions and other regular discrete structures
- A new proof of the KŁR conjecture
- Erdős-Ko-Rado for random hypergraphs: asymptotics and stability
- On the missing log in upper tail estimates
- A probabilistic threshold for monochromatic arithmetic progressions
- Normal limiting distributions for systems of linear equations in random sets
- Online containers for hypergraphs, with applications to linear equations
- Random combinatorial structures: the convergent case
- The typical structure of sparse \(K_{r+1}\)-free graphs
- A relative Szemerédi theorem
- On the number of \(B_h\)-sets
- Covering random graphs with monochromatic trees
- Hypergraph removal lemmas via robust sharp threshold theorems
- Triangle-free subgraphs of hypergraphs
- Extremal results in sparse pseudorandom graphs
- Upper tails for arithmetic progressions in random subsets
- A short nonalgorithmic proof of the containers theorem for hypergraphs
- Extremal results for odd cycles in sparse pseudorandom graphs
- Supersaturation in posets and applications involving the container method
- Arcs in \(\mathbb{F}_q^2\)
- Stability results for random discrete structures
- On the number of monotone sequences
- On the KŁR conjecture in random graphs
- Counting configuration-free sets in groups
- Bivariate fluctuations for the number of arithmetic progressions in random sets
- Counting sum-free sets in abelian groups
- The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
- Covering graphs by monochromatic trees and Helly-type results for hypergraphs
- Simple containers for simple hypergraphs
- On Erdős-Ko-Rado for random hypergraphs. II
- On Erdős-Ko-Rado for random hypergraphs. I
- Largest subgraph from a hereditary property in a random graph
- Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
- Infinite Sidon sets contained in sparse random sets of integers
- Monochromatic Schur Triples in Randomly Perturbed Dense Sets of Integers
- Diagonal Ramsey via effective quasirandomness
- Many \(T\) copies in \(H\)-free graphs
- The Maker-Breaker Rado game on a random set of integers
- Random polynomial graphs for random Turán problems
- Probabilistic hypergraph containers
- Seymour's second neighborhood conjecture for orientations of (pseudo)random graphs
- Rectilinear approximation and volume estimates for hereditary bodies via [0, 1]‐decorated containers
- Title not available (Why is that?)
- Counting configuration-free sets in groups
- Turán‐type problems for long cycles in random and pseudo‐random graphs
- Deviation probabilities for arithmetic progressions and other regular discrete structures
- Weakly saturated random graphs
- Triangle resilience of the square of a Hamilton cycle in random graphs
- On the threshold for Szemerédi's theorem with random differences
- Upper bounds for the number of substructures in finite geometries from the container method
- Ramsey goodness of trees in random graphs
- The power of many colours
- Sum-free sets of integers with a forbidden sum
- Turán theorems for even cycles in random hypergraph
- Lower tails via relative entropy
- Interview with David Conlon
- On the maximum \(F_5\)-free subhypergraphs of a random hypergraph
- Probabilistic intuition holds for a class of small subgraph games
- On Szemerédi's theorem with differences from a random set
- The regularity method for graphs with few 4‐cycles
This page was built for publication: Extremal results for random discrete structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q350549)
