Upper Tails of Subgraph Counts in Sparse Regular Graphs

Publication date 1 October 2020

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80)

Abstract: What is the probability that a sparse

n

-vertex random

d

-regular graph

G_{n}^{d}

,

n^{1 - c} < d = o (n)

contains many more copies of a fixed graph

K

than expected? We determine the behavior of this upper tail to within a logarithmic gap in the exponent. For most graphs

K

(for instance, for any

K

of average degree greater than

4

) we determine the upper tail up to a

1 + o (1)

factor in the exponent. However, we also provide an example of a graph, given by adding an edge to

K_{2, 4}

, where the upper tail probability behaves differently from previously studied behavior in both the sparse random regular and sparse ErdH{o}s-R'{e}nyi models in this sparsity regime.

This page was built for publication: Upper Tails of Subgraph Counts in Sparse Regular Graphs

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