Mathematics – Combinatorics
Scientific paper
2011-11-29
Mathematics
Combinatorics
19 pages; slightly simplified proof of the main theorem; fixed a few typos
Scientific paper
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.
No associations
LandOfFree
Stability results for random discrete structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Stability results for random discrete structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stability results for random discrete structures will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-16769