Bounds on Ramsey games via alterations

DOI10.1002/JGT.22973zbMATH Open1522.05486arXiv1909.02691OpenAlexW4375865650MaRDI QIDQ6081572FDOQ6081572

He Guo, Lutz Warnke

Publication date: 5 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: We present a refinement of the classical alteration method for constructing $H$-free graphs: for suitable edge-probabilities $p$, we show that removing all edges in $H$-copies of the binomial random graph $G_{n,p}$ does not significantly change the independence number. This differs from earlier alteration approaches of ErdH{o}s and Krivelevich, who obtained similar guarantees by removing one edge from each $H$-copy (instead of all of them). We demonstrate the usefulness of our refined alternation method via two applications to online graph Ramsey games, where it enables easier analysis.

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

zbMATH Keywords

Ramsey theorydeletion methodonline Ramsey gamesalteration method

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Generalized Ramsey theory (05C55) Ramsey theory (05D10) 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?)
• Approximate Set Covering in Uniform Hypergraphs
• How to make a graph bipartite
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Ramsey's theorem - a new lower bound
• Asymptotic lower bounds for Ramsey functions
• On the minimal number of edges in color-critical graphs
• Coloring H-free hypergraphs
• The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘)
• Representations of integers as the sum of k terms
• The early evolution of the \(H\)-free process
• On the chromatic number of simple triangle-free triple systems
• Coloring number and on-line Ramsey theory for graphs and hypergraphs
• On-line Ramsey Numbers
• Graph Theory and Probability. II
• Bounding Ramsey numbers through large deviation inequalities
• The infamous upper tail
• General deletion lemmas via the Harris inequality
• Two variants of the size Ramsey number
• Online Ramsey Numbers and the Subgraph Query Problem
• Ramsey Numbers and the Size of Graphs
• On the power of random greedy algorithms
• Upper tails for arithmetic progressions in random subsets
• Dense induced bipartite subgraphs in triangle-free graphs
• Packing nearly optimal Ramsey \(R(3,t)\) graphs
• Ramsey, Paper, Scissors
• On the missing log in upper tail estimates
• Dynamic concentration of the triangle‐free process
• Upper tail bounds for stars
• A counterexample to the DeMarco‐Kahn upper tail conjecture

Cited In (2)

• A Ramsey bound on stable sets in Jordan pillage games
• Probabilistic One-Player Ramsey Games via Deterministic Two-Player Games

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Zero-sum dynamic games and a stochastic variation of Ramsey's theorem 👍 👎
• A Ramsey bound on stable sets in Jordan pillage games 👍 👎
• Upper Bounds for Online Ramsey Games in Random Graphs 👍 👎
• Ideal games and Ramsey sets 👍 👎
• On Ramsey-type positional games 👍 👎
• Ramsey games near the critical threshold 👍 👎
• Strong Ramsey games in unbounded time 👍 👎
• Size Ramsey number of bounded degree graphs for games 👍 👎

This page was built for publication: Bounds on Ramsey games via alterations

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