Counting extensions revisited
arXiv:1911.03012 · doi:10.1002/rsa.21050
Abstract
We consider rooted subgraphs in random graphs, i.e., extension counts such as (i) the number of triangles containing a given vertex or (ii) the number of paths of length three connecting two given vertices. In 1989, Spencer gave sufficient conditions for the event that, with high probability, these extension counts are asymptotically equal for all choices of the root vertices. For the important strictly balanced case, Spencer also raised the fundamental question as to whether these conditions are necessary. We answer this question by a careful second moment argument, and discuss some intriguing problems that remain open.
arXiv comment22 pages, 2 figures. Minor edits, to appear in Random Structures and Algorithms (RSA)
References in corpus (11)
- The early evolution of the H-free process
- On the method of typical bounded differences
- Upper tails for arithmetic progressions in random subsets
- The lower tail: Poisson approximation revisited
- Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
- Large girth approximate Steiner triple systems
- The Janson inequalities for general up-sets
- A counterexample to the DeMarco-Kahn Upper Tail Conjecture
- On the missing log in upper tail estimates
- Sharp thresholds for Ramsey properties of strictly balanced nearly bipartite graphs
- On the Cycle Space of a Random Graph