Upper bounds on probability thresholds for asymmetric Ramsey properties

DOI10.1002/RSA.20446zbMATH Open1280.05084arXiv1602.04059OpenAlexW3098920135MaRDI QIDQ2874080FDOQ2874080

Reto Spöhel, M. Schacht, Yoshiharu Kohayakawa

Publication date: 28 January 2014

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: Given two graphs $G$ and $H$, we investigate for which functions $p=p(n)$ the random graph $G_{n,p}$ (the binomial random graph on $n$ vertices with edge probability $p$) satisfies with probability $1-o(1)$ that every red-blue-coloring of its edges contains a red copy of $G$ or a blue copy of $H$. We prove a general upper bound on the threshold for this property under the assumption that the denser of the two graphs satisfies a certain balancedness condition. Our result partially confirms a conjecture by the first author and Kreuter, and together with earlier lower bound results establishes the exact order of magnitude of the threshold for the case in which $G$ and $H$ are complete graphs of arbitrary size. In our proof we present an alternative to the so-called deletion method, which was introduced by R"odl and Ruci'{n}ski in their study of symmetric Ramsey properties of random graphs (i.e. the case $G=H$), and has been used in many proofs of similar results since then.

Full work available at URL: https://arxiv.org/abs/1602.04059

zbMATH Keywords

Ramsey theoryrandom graphsthreshold functionsnon-diagonal Ramsey properties

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Generalized Ramsey theory (05C55)

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?)
• Title not available (Why is that?)
• Correlation inequalities on some partially ordered sets
• On \(K^ 4\)-free subgraphs of random graphs
• Szemerédi’s Regularity Lemma for Sparse Graphs
• Threshold Functions for Ramsey Properties
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• Ramsey properties of random hypergraphs
• The deletion method for upper tail estimates
• Ramsey properties of random discrete structures
• Ramsey Properties of Random k-Partite, k-Uniform Hypergraphs
• Poisson approximation for large deviations
• Ramsey properties of random graphs
• Regular pairs in sparse random graphs I
• Asymmetric Ramsey properties of random graphs involving cliques

Cited In (11)

• Title not available (Why is that?)
• Independent sets in hypergraphs
• Towards the Kohayakawa–Kreuter conjecture on asymmetric Ramsey properties
• Towards the 0-statement of the Kohayakawa-Kreuter conjecture
• On the stability of the Erdős-Ko-Rado theorem
• A new proof of the KŁR conjecture
• SYMMETRIC AND ASYMMETRIC RAMSEY PROPERTIES IN RANDOM HYPERGRAPHS
• Asymmetric Ramsey properties of random graphs involving cliques and cycles
• Bounding Ramsey numbers through large deviation inequalities
• Title not available (Why is that?)
• An asymmetric random Rado theorem: 1-statement

This page was built for publication: Upper bounds on probability thresholds for asymmetric Ramsey properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2874080)