Journal of Combinatorics

Volume 4 (2013)

Number 2

General deletion lemmas via the Harris inequality

Pages: 251 – 271

DOI: https://dx.doi.org/10.4310/JOC.2013.v4.n2.a5

Authors

Reto Spöhel (Technik und Informatik, Berner Fachochschule, Burgdorf, Switzerland)

Angelika Steger (Institute of Theoretical Computer Science, ETH Zürich, Switzerland)

Lutz Warnke (Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, United Kingdom)

Abstract

We present a new approach to the deletion method that is based on the Harris inequality. We obtain deletion lemmas that are similar in spirit to those of Rödl and Ruciński but hold for arbitrary decreasing properties. That is, we show that under appropriate conditions, with very high (‘Janson-like’) probability it suffices to delete a small fraction of the edges of a random graph $G_{n,p}$ to ensure that a given decreasing property holds. We also obtain stronger results for decreasing properties that only depend on edges involved in copies of some given graph $H.$ As an application of our methods, we present a new deletion lemma that concerns local subgraph counts, i.e., the number of copies of $H$ each edge or vertex of $G_{n,p}$ is contained in.

Keywords

random graphs, upper tails, subgraph counts, deletion method, Harris inequality

2010 Mathematics Subject Classification

Primary 05C80. Secondary 60C05.

Published 13 August 2013