Extremal results for random discrete structures
From MaRDI portal
Publication:350549
DOI10.4007/ANNALS.2016.184.2.1zbMATH Open1351.05207arXiv1603.00894OpenAlexW3103981711WikidataQ97694035 ScholiaQ97694035MaRDI QIDQ350549FDOQ350549
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
thresholdsrandom graphs[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Szemer%EF%BF%BD%EF%BF%BDdi%27s+theorem&go=Go Szemer��di's theorem][https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Tur%EF%BF%BD%EF%BF%BDn%27s+theorem&go=Go Tur��n's theorem]
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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 (82)
- Relative Turán Problems for Uniform Hypergraphs
- 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
- Erdős–Ko–Rado for Random Hypergraphs: Asymptotics and Stability
- 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
- Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems
- An analogue of the Erdős-Gallai theorem for random graphs
- On the Number ofBh-Sets
- Ramsey games near the critical threshold
- Random sum-free subsets of abelian groups
- On zero-sum free sequences contained in random subsets of finite cyclic groups
- Seymour's second neighborhood conjecture for orientations of (pseudo)random graphs
- The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups
- The number of \(K_{m,m}\)-free graphs
- 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
- Infinite Sidon Sets Contained in Sparse Random Sets of Integers
- Deviation probabilities for arithmetic progressions and other regular discrete structures
- A new proof of the KŁR conjecture
- On the missing log in upper tail estimates
- A probabilistic threshold for monochromatic arithmetic progressions
- On Erdős–Ko–Rado for Random Hypergraphs II
- On Erdős–Ko–Rado for random hypergraphs I
- 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 Maker--Breaker Rado Game on a Random Set of Integers
- Simple Containers for Simple Hypergraphs
- The typical structure of sparse \(K_{r+1}\)-free graphs
- A relative Szemerédi theorem
- Triangle resilience of the square of a Hamilton cycle in random graphs
- Covering random graphs with monochromatic trees
- 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\)
- 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
- 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
- Monochromatic Schur Triples in Randomly Perturbed Dense Sets of Integers
- Diagonal Ramsey via effective quasirandomness
- Independent Sets in Hypergraphs and Ramsey Properties of Graphs and the Integers
- Many \(T\) copies in \(H\)-free graphs
- Random polynomial graphs for random Turán problems
- Sum-Free Sets of Integers with a Forbidden Sum
- Probabilistic hypergraph containers
- 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
- 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
- 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
- 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)
