Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs

Abstract

General upper tail estimates are given for counting edges in a random induced subhypergraph of a fixed hypergraph H, with an easy proof by estimating the moments. As an application we consider the numbers of arithmetic progressions and Schur triples in random subsets of integers. In the second part of the paper we return to the subgraph counts in random graphs and provide upper tail estimates in the rooted case.

15 pages

Cited by in corpus (11)

• Combinatorial theorems in sparse random sets
• Upper tails for arithmetic progressions in random subsets
• The lower tail: Poisson approximation revisited
• Upper tails for arithmetic progressions in a random set
• On the missing log in upper tail estimates
• Upper tail bounds for Stars
• Threshold functions and Poisson convergence for systems of equations in random sets
• Counting extensions revisited
• A Note on Sparse Supersaturation and Extremal Results for Linear Homogeneous Systems
• Trees in Random Sparse Graphs with a Given Degree Sequence
• Deviation probabilities for arithmetic progressions and irregular discrete structures