Stability results for random discrete structures
From MaRDI portal
Abstract: Two years ago, Conlon and Gowers, and Schacht proved general theorems that allow one to transfer a large class of extremal combinatorial results from the deterministic to the probabilistic setting. Even though the two papers solve the same set of long-standing open problems in probabilistic combinatorics, the methods used in them vary significantly and therefore yield results that are not comparable in certain aspects. The theorem of Schacht can be applied in a more general setting and yields stronger probability estimates, whereas the one of Conlon and Gowers also implies random versions of some structural statements such as the famous stability theorem of Erdos and Simonovits. In this paper, we bridge the gap between these two transference theorems. Building on the approach of Schacht, we prove a general theorem that allows one to transfer deterministic stability results to the probabilistic setting that is somewhat more general and stronger than the one obtained by Conlon and Gowers. We then use this theorem to derive several new results, among them a random version of the Erdos-Simonovits stability theorem for arbitrary graphs. The main new idea, a refined approach to multiple exposure when considering subsets of binomial random sets, may be of independent interest.
Recommendations
Cites work
- scientific article; zbMATH DE number 3523693 (Why is no real title available?)
- 4-books of three pages
- A Szemerédi-type regularity lemma in abelian groups, with applications
- A variant of the hypergraph removal lemma
- An exact Turán result for the generalized triangle
- Combinatorial theorems in sparse random sets
- Counting sum-free sets in abelian groups
- Exact computation of the hypergraph Turán function for expanded complete 2-graphs
- Maximal sum-free sets of elements of finite groups
- On Triple Systems with Independent Neighbourhoods
- On \(K^ 4\)-free subgraphs of random graphs
- On a hypergraph Turán problem of Frankl
- On the structure of linear graphs
- Quadruple systems with independent neighborhoods
- Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
- Random sum-free subsets of abelian groups
- Stability theorems for cancellative hypergraphs
- Sum-free sets in abelian groups
- Supersaturated graphs and hypergraphs
- The Turán number of the Fano plane
- The counting lemma for regular k‐uniform hypergraphs
- Threshold Functions for Ramsey Properties
- Triple Systems Not Containing a Fano Configuration
- Turán's extremal problem in random graphs: Forbidding even cycles
Cited in
(20)- A stability theorem for maximal C2k+1 ${C}_{2k+1}$‐free graphs
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Combinatorial theorems in sparse random sets
- Mantel's theorem for random graphs
- Independent sets in hypergraphs
- Counting independent sets in graphs
- Hypergraph containers
- Random sum-free subsets of abelian groups
- On \(k\)-uniform random hypergraphs without generalized fans
- The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups
- Mantel's theorem for random hypergraphs
- A new proof of the KŁR conjecture
- Erdős-Ko-Rado for random hypergraphs: asymptotics and stability
- The typical structure of sparse \(K_{r+1}\)-free graphs
- Hypergraph removal lemmas via robust sharp threshold theorems
- Upper tails for arithmetic progressions in random subsets
- Ramsey goodness of trees in random graphs
- On the KŁR conjecture in random graphs
- Exact stability for Turán's theorem
- On the maximum \(F_5\)-free subhypergraphs of a random hypergraph
This page was built for publication: Stability results for random discrete structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5415592)
